Group Search and Evacuation

摘要

Group search and evacuation are fundamental tasks performed by a set of co-operating, autonomous mobile agents. The two tasks are similar in that they both aim to search a given domain so as to locate a target which has been placed at an unknown location in the domain. However they also differ in that the former terminates when the first searcher in the group reaches the target while the latter when the last searcher in the group reaches the target. Variations where termination is determined by some designated agent have also been considered. Depending on the domain being explored we distinguish linear search when the target is placed on the infinite line and circular search when the target is placed on the perimeter of a disk. The agents move with their own maximum speed, and the goal is to design algorithms that minimize the worst case termination time. Two communication models between the robots are being considered: in the non-wireless (or face-to-face) communication model, robots exchange information only when simultaneously located at the same point, and wireless communication in which robots can communicate with one another anywhere at any time. In this paper we survey some of the most interesting recent algorithmic results on search and evacuation concerning mobile agents with and without faults.