Exploring an Unknown Graph by a Team of Robots Using Serendipity Rendezvous Algorithms

Dependence on a team of robots to carry out the exploration missions has many benefits such as speeding up the missions; provided that the coordination among robots is maintained. Many circumstances limit the communication which is crucial for the coordination among robots (e.g. impenetrable barriers, high temperature etc.). A periodic rendezvous strategy is considered in this dissertation a work-around in order to overlap communication ranges of the robots. Attending these periodic rendezvous sessions requires that the robots interrupt their current exploration progress periodically and traverse back to the rendezvous points (i.e. Interruptibility). During their trips to these points, they do not gain new knowledge since they cross already explored parts of the area. Therefore, using rendezvous strategies improves the team behaviour but has a negative impact on the time efficiency. Serendipity Rendezvous – the contribution of this dissertation - invests the dedicated time of Interruptibility trip in the inter-coordination among the robots by finding a serendipity path. This path is where the robot, which runs Serendipity Rendezvous, meets its colleagues accidentally on its way to the rendezvous point. The evaluation results show that Serendipity Rendezvous is able to mitigate the negative impact of Interruptibility while maintaining its positive impacts. Moreover, it provides a balance utilization of robots for the exploration activities. These results are achieved without affecting the already scheduled rendezvous. Hence, Serendipity Rendezvous optimizes periodic rendezvous sessions as long as the margin of the gaining knowledge by meeting other robots on the serendipity path is considered rewarded for the robots which run Serendipity Rendezvous.