Randomized pursuit-evasion with limited visibility

ABSTRACT

We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the l ocation of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with limited visibility with high probability. We distinguish between reactive rabbits who who move only when the hunter is visible and general rabbits can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.

REFERENCES

• 1: Micah Adler , Harald Räcke , Naveen Sivadasan , Christian Sohler , Berthold Vöcking, Randomized Pursuit-Evasion in Graphs, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.901-912, July 08-13, 2002
• 2: M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Math, 8:1--12, 1984.
• 3: T. Basar and P. R. Kumar. On worst case design strategies. Computers and Mathematics with Applications: Special Issue on Pursuit-Evasion Differential Games, 13(1--3):239--245, 1987.
• 4: T. Basar and G. J. Olsder. Dynamic Noncooperative Game Theory. SIAM, 1998.
• 5: P. Bernhard, A.-L. Colomb, and G. P. Papavassilopou-los. Rabbit and hunter game: two discrete stochastic formulations. Comput. Math. Appl., 13(1--3):205--225, 1987.
• 6: Graham R. Brightwell , Peter Winkler, Gibbs measures and dismantlable graphs, Journal of Combinatorial Theory Series B, v.78 n.1, p.141-166, Jan. 2000 [doi>10.1006/jctb.1999.1935]
• 7: J. A. Ellis , I. H. Sudborough , J. S. Turner, The vertex separation and search number of a graph, Information and Computation, v.113 n.1, p.50-79, Aug. 15, 1994 [doi>10.1006/inco.1994.1064]
• 8: S. Fitzpatrick and R. Nowakowski. Copnumber of graphs with strong isometric dimension two. ARS COMBINATORIA, 59:65--73, 2001.
• 9: L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. A visibility-based pursuit-evasion problem. International Journal of Computational Geometry and Applications, 9(4/5):471-, 1999.
• 10: J. P. Hespanha, G. J. Pappas, and M. Prandini. Greedy control for hybrid pursuit-evasion games. In Proceedings of the European Control Conference, pages 2621--2626, Porto, Portugal, September 2001.
• 11: Ioannis Chatzigiannakis , Sotiris E. Nikoletseas , Paul G. Spirakis, An Efficient Communication Strategy for Ad-hoc Mobile Networks, Proceedings of the 15th International Conference on Distributed Computing, p.285-299, October 03-05, 2001
• 12: Andrea S. LaPaugh, Recontamination does not help to search a graph, Journal of the ACM (JACM), v.40 n.2, p.224-245, April 1993 [doi>10.1145/151261.151263]
• 13: N. Megiddo , S. L. Hakimi , M. R. Garey , D. S. Johnson , C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM (JACM), v.35 n.1, p.18-44, Jan. 1988 [doi>10.1145/42267.42268]
• 14: S. Neufeld , R. Nowakowski, A game of cops and robbers played on products of graphs, Discrete Mathematics, v.186 n.1-3, p.253-268, May 15, 1998 [doi>10.1016/S0012-365X(97)00165-9]
• 15: R. Nowakawski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Math, 43:235--239, 1983.
• 16: Sang-Min Park , Jae-Ha Lee , Kyung-Yong Chwa, Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.456-468, July 08-12, 2001
• 17: T. D. Parsons. Pursuit evasion in a graph. In Y. Alavi and D. R. Lick, editors, Theory and Application of Graphs, pages 426--441. Springer Verlag, 1976.
• 18: R. Vidal, O. Shakernia, J. Kim, D. Shim, and S. Sastry. Probabilistic pursuit-evasion games: Theory, implementation and experimental evaluation. IEEE Transactions on Robotics and Automation, 18:662--669, 2002.