Search-and-fetch with 2 robots on a disk: Wireless and face-to-face communication models

We introduce and study treasure-evacuation with 2 robots, a new problem on distributed searching and fetching related to well studied problems in searching, rendezvous and exploration. The problem is motivated by real-life search-and-rescue operations in areas of a disaster, where unmanned vehicles (robots) search for a victim (treasure) and subsequently bring (fetch) her to safety (the exit). One of the critical components in such operations is the communication protocol between the robots. We provide search algorithms and contrast two standard models, the face-to-face and the wireless model. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can take advantage of some minimal information of the topology (i.e., the disk) in order to allow for information exchange without meeting. The result is a highly efficient distributed treasure-evacuation protocol which is minimally affected by the lack of distant communication.