×

Offline variants of the “lion and man” problem: some problems and techniques for measuring crowdedness and for safe path planning. (English) Zbl 1146.68066

Summary: Consider the following safe path planning problem: Given a set of trajectories (paths) of \(k\) point robots with maximum unit speed in a bounded region over a (long) time interval \([0,T]\), find another trajectory (if it exists) subject to the same maximum unit speed limit, that avoids (that is, stays at a safe distance of) each of the other \(k\) trajectories over the entire time interval. We call this variant the continuous model of the safe path planning problem. The discrete model of this problem is: Given a set of trajectories (paths) of \(k\) point robots in a graph over a (long) time interval \(0,1,2,\dots ,T\), find a trajectory (path) for another robot, that avoids each of the other \(k\) at any time instant in the given time interval.
We introduce the notions of the avoidance number of a region, and that of a graph, respectively, as the maximum number of trajectories which can be avoided in the region (respectively, graph). We give the first estimates on the avoidance number of the \(n\times n\) grid \(G_n\), and also devise an efficient algorithm for the corresponding safe path planning problem in arbitrary graphs. We then show that our estimates on the avoidance number of \(G_n\) can be extended for the avoidance number of a bounded (fat) region. In the final part of our paper, we consider other related offline questions, such as the maximum number of men problem and the spy problem.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Spencer, J., The Probabilistic Method (2000), Wiley: Wiley New York
[2] Alonso, L.; Goldstein, A.; Reingold, E., ‘Lion and man’: Upper and lower bounds, ORSA Journal on Computing, 4, 447-452 (1992) · Zbl 0764.90105
[3] F. Berger, A. Grüne, R. Klein, How many lions can one man avoid? Technical Report 006 (2007), Department of Computer Science I, University of Bonn. Also in Abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry, New York, 2007; F. Berger, A. Grüne, R. Klein, How many lions can one man avoid? Technical Report 006 (2007), Department of Computer Science I, University of Bonn. Also in Abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry, New York, 2007
[4] Bienstock, D., Graph searching, path-width, tree-width and related problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 5, 33-49 (1991) · Zbl 0777.05090
[5] Bollobás, B., The Art of Mathematics (2006), Cambridge University Press
[6] P. Braß, K.D. Kim, H.S. Na, C.S. Shin, Escaping off-line searchers and a discrete isoperimetric theorem, in: Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), in: Lecture Notes in Computer Science, vol. 4835, pp. 65-74; P. Braß, K.D. Kim, H.S. Na, C.S. Shin, Escaping off-line searchers and a discrete isoperimetric theorem, in: Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), in: Lecture Notes in Computer Science, vol. 4835, pp. 65-74 · Zbl 1193.68267
[7] Croft, H. T., Lion and man: A postscript, Journal of the London Mathematical Society, 39, 385-390 (1964) · Zbl 0125.03003
[8] A. Dumitrescu, H. Kok, I. Suzuki, P. Żyliński, Vision-based pursuit-evasion in a grid, manuscript, 2007 (submitted for publication); A. Dumitrescu, H. Kok, I. Suzuki, P. Żyliński, Vision-based pursuit-evasion in a grid, manuscript, 2007 (submitted for publication) · Zbl 1155.68550
[9] Dendris, N. D.; Kirousis, L. M.; Thilikos, D. M., Fugitive-search games on graphs and related parameters, Theoretical Computer Science, 172, 233-254 (1997) · Zbl 0903.68052
[10] Fomin, F. V.; Golovach, P. A.; Petrov, N. N., Search problems on 1-skeletons of regular polyhedrons, International Journal of Mathematics, Game Theory and Algebra, 7, 101-111 (1997) · Zbl 0904.90091
[11] Fomin, F. V.; Thilikos, D., An annotated bibliography on guaranteed graph searching · Zbl 1160.68007
[12] Littlewood, J. E., A Mathematician’s Miscellany, vol. VII (1953), Mathuen: Mathuen London · Zbl 0051.00101
[13] Mitzenmacher, M.; Upfal, E., Probability and Computing (2005), Cambridge University Press
[14] Nowakowski, R. J.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Mathematics, 43, 235-239 (1983) · Zbl 0508.05058
[15] Petrov, N. N., Some extremal searching problems on graphs, Differential Equations, 18, 591-595 (1982), (in Russian) · Zbl 0506.90099
[16] Reif, J.; Sharir, M., Motion planning in the presence of moving obstacles, Journal of ACM, 41, 764-790 (1994) · Zbl 0812.68115
[17] Sgall, J., Solution to David Gale’s lion and man problem, Theoretical Computer Science, 259, 663-670 (2001) · Zbl 1028.91011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.