Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers

The graph search problem is the problem of searching for a mobile evader in a dark cave by a group of mobile searchers, where the cave is modeled by an undirected connected graph G. An offline and centralized version of the graph search problem is formalized as a pebble game on G, and has been extensively investigated under the name of the edge search problem. By es(G) we denote the number of pebbles (i.e., searchers) necessary and sufficient to edge search G. An online and distributed version of the graph search problem is the graph search by mobile agents. We investigate the graph search problem under a weaker online and distributed setting called the dark cave model, which models the dark cave more directly than a graph; G is completely anonymous, and we do not introduce any artificial facilities in G such as a port numbering, a homebase, and a whiteboard. Instead, we assume that the searchers can exchange information wherever they meet. Under the dark cave model, we propose a search algorithm OLSEARCH for es(G) searchers, and show that it is optimal in terms of the number of searchers.