Abstract
We consider the following variant of a classical pursuit-evasion problem: how many pursuers are needed to capture a single (adversarial) evader on the surface of a 3-dimensional polyhedral body? The players remain on the closed polyhedral surface, have the same maximum speed, and are always aware of each others’ current positions. This generalizes the classical lion-and-the-man game, originally proposed by Rado [12], in which the players are restricted to a two-dimensional circular arena. The extension to a polyhedral surface is both theoretically interesting and practically motivated by applications in robotics where the physical environment is often approximated as a polyhedral surface. We analyze the game under the discrete-time model, where the players take alternate turns, however, by choosing an appropriately small time step t > 0, one can approximate the continuous time setting to an arbitrary level of accuracy. Our main result is that 4 pursuers always suffice (upper bound), and that 3 are sometimes necessary (lower bound), for catching an adversarial evader on any polyhedral surface with genus zero. Generalizing this bound to surfaces of genus g, we prove the sufficiency of (4g + 4) pursuers. Finally, we show that 4 pursuers also suffice under the “weighted region” constraints where the movement costs through different regions of the (genus zero) surface have (different) multiplicative weights.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Applied Mathematics 8(1), 1–12 (1984)
Alexander, S., Bishop, R., Ghrist, R.: Capture pursuit games on unbounded domains. Enseign. Math. (2) 55(1-2), 103–125 (2009)
Alpern, S., Fokkink, R., Lindelauf, R., Olsder, G.-J.: The “princess and monster” game on an interval. SIAM J. on Control and Optimization 47(3), 1178–1190 (2008)
Bhadauria, D., Klein, K., Isler, V., Suri, S.: Capturing an evader in polygonal environments with obstacles: The full visibility case. International Journal of Robotics Research 31(10), 1176–1189 (2012)
Bopardikar, S.D., Bullo, F., Hespanha, J.: A cooperative homicidal chauffeur game. In: 46th IEEE Conference on Decision and Control, pp. 4857–4862 (2007)
Chen, J., Han, Y.: Shortest paths on a polyhedron. In: Proc. of 6th Symposium on Computational Geometry, pp. 360–369. ACM, New York (1990)
Isler, V., Kannan, S., Khanna, S.: Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics 21(5), 875–884 (2005)
Isler, V., Kannan, S., Khanna, S.: Randomized pursuit-evasion with local visibility. SIAM Journal on Discrete Mathematics 1, 26–41 (2006)
Klein, K., Suri, S.: Catch me if you can: Pursuit and capture in polygonal environments with obstacles. In: Proc. of 26th Conference on Artificial Intelligence, pp. 2010–2016 (2012)
Kolling, A., Kleiner, A., Lewis, M., Sycara, K.: Pursuit-evasion in 2.5d based on team-visibility. In: Proc. IROS, pp. 4610–4616 (2010)
Kovshov, A.: The simple pursuit by a few objects on the multidimensional sphere. In: Game Theory & Applications II, pp. 27–36 (1996)
Littlewood, J.E.: Littlewood’s Miscellany. Cambridge University Press (1986)
Melikyan, A.: Geometry of pursuit-evasion games on two-dimensional manifolds. Annals of the International Society of Dynamic Games 9, 173–194 (2007)
Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM Journal on Computing 16(4), 647–668 (1987)
Schroder, B.S.W.: The copnumber of a graph is bounded by \(\lfloor\) 3/2 genus(g)\(\rfloor\) +3. In: “Categorical Perspectives” — Proc. of the Conference in Honor of George Strecker’s 60th Birthday, pp. 243–263 (2001)
Sgall, J.: Solution of david gale’s lion and man problem. Theor. Comput. Sci. 259(1-2), 663–670 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klein, K., Suri, S. (2013). Pursuit Evasion on Polyhedral Surfaces. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)