Efficient live exploration of a dynamic ring with mobile robots

Mandal, Subhrangsu; Molla, Anisur Rahaman; Moses Jr., William K.

Abstract

The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the termination condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced by Di Luna et al. [DC 2020]. More specifically, they studied the problem of live exploration in a dynamic ring and proposed multiple algorithms to solve this problem in the fully synchronous and semi-synchronous settings with various guarantees when 2 robots were involved. They also showed that, under certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of 3 robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous setting.

In particular, we present algorithms for exploration with explicit termination using 3 robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there does not exist any explicit termination algorithm for 2 robots even when each robot has a unique ID, edge crossing detection capability, and access to randomness. The theoretical analysis and comprehensive simulations of our algorithm show the effectiveness and efficiency of the algorithm in dynamic rings. We also present an algorithm to achieve exploration with partial termination using 3 robots with unique IDs in the semi-synchronous setting, when robots have access to edge crossing detection capability and randomness but do not know a bound on the size of the ring or have access to a landmark or are guaranteed that robots have common chirality. Our algorithms are fully decentralized, lightweight, and easily implementable.

Citation

Mandal, S., Molla, A. R., & Moses Jr., W. K. (2023). Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science, 980, Article 114201. https://doi.org/10.1016/j.tcs.2023.114201

• Journal Article Type: Article
• Acceptance Date: Sep 14, 2023
• Online Publication Date: Sep 27, 2023
• Publication Date: Nov 20, 2023
• Deposit Date: Nov 6, 2023
• Publicly Available Date: Sep 28, 2024
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 980
• Article Number: 114201
• DOI: https://doi.org/10.1016/j.tcs.2023.114201
• Public URL: https://durham-repository.worktribe.com/output/1898969