×

On determining optimal strategies in pursuit games in the plane. (English) Zbl 0911.90376

Summary: We investigate a class of differential games, which we call pursuit games. Pursuit games have application to robotics: the pursuer models a moving obstacle and the evader models a robot that tries to reach a goal region without colliding with the moving obstacle, at each moment the robot does not know the future trajectory of the obstacle. The motion of the pursuer and the evader is controlled by its set of permissible velocities, called indicatrices. We allow indicatrices that are more general than the simple motion (i.e., velocities are bounded by an \(L_2\)-norm circle). We provide sufficient condition for a pursuit game to “have value”; in this case, we give optimal strategies for the pursuer and the evader. We prove that the pursuit game in which the pursuer and the evader are convex objects moving with simple motion “has value”.

MSC:

91A24 Positional games (pursuit and evasion, etc.)
93C85 Automated systems (robots, etc.) in control theory
91A23 Differential games (aspects of game theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P.; Sharir, M.; Shor, P., Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences, J. Combin. Theory Ser. A, 52, 228-274 (1989) · Zbl 0697.05003
[2] N.M. Amato, Determining the separation of simple polygons, Internat. J. Comput. Geom. Appl., to appear.; N.M. Amato, Determining the separation of simple polygons, Internat. J. Comput. Geom. Appl., to appear. · Zbl 0829.68060
[3] Aronov, B., On the geodesic Voronoi diagram of point sites in a simple polygon, Algorithmica, 4, 109-140 (1989) · Zbl 0664.68043
[4] Aurenhammer, F., Voronoi diagrams — a survey of a fundamental data structure, ACM Comput. Surveys, 23, 3 (1991)
[5] Aurenhammer, F.; Edelsbrunner, H., An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, 17, 2, 251-257 (1984) · Zbl 0539.52008
[6] Bajaj, C.; Kim, M.-S., Generation of configuration space obstacles: the case of moving algebraic curves, Algorithmica, 4, 157-172 (1989) · Zbl 0672.68009
[7] Bajaj, C.; Kim, M.-S., Convex hulls of objects bounded by algebraic curves, Algorithmica, 6, 533-553 (1991) · Zbl 0726.68073
[8] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, ACM, 28, 1, 114-133 (1981) · Zbl 0473.68043
[9] Chew, L. P.; Drysdale, R. L., Voronoi diagrams based on convex distance functions, (Proc. ACM Symp. on Computational Geometry (1985)), 235-244
[10] Chin, F.; Wang, C. A., Optimal algorithms for the intersection and the minimum distance problems between planar polygons, IEEE Trans. Comput., 32, 12, 1203-1207 (1983) · Zbl 0531.51002
[11] Dobkin, D. B.; Kirkpatrick, D. G., A linear algorithm for determining the separation of convex polyhedra, J. Algorithms, 6, 381-392 (1985) · Zbl 0577.52004
[12] Dobkin, D. B.; Souvaine, D. L.; Van Wyk, C. J., Decomposition and intersection of simple splinegons, Algorithmica, 3, 473-485 (1988) · Zbl 0648.68062
[13] Dobkin, D. B.; Souvaine, D. L., Computational geometry in a curved world, Algorithmica, 5, 421-457 (1990) · Zbl 0696.68101
[14] Edelsbrunner, H., Computing the extreme distances between two convex polygons, J. Algorithms, 6, 213-224 (1985) · Zbl 0604.68079
[15] El Gindy, H.; Avis, D., A linear algorithm for computing the visibility polygon from a point, J. Algorithms, 2, 186-197 (1981) · Zbl 0459.68057
[16] Friedman, A., Differential Games (1971), Wiley-lnterscience: Wiley-lnterscience New York · Zbl 0229.90060
[17] Guibas, L. J.; Seidel, R., Computing convolutions by reciprocal search, Discrete Comput. Geom., 2, 175-193 (1987) · Zbl 0623.68043
[18] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177 (1986) · Zbl 0636.05003
[19] Hershberger, J., Finding the upper envelope of \(n\) line segments in \(O(n\) log \(n)\) time, Inform. Process. Lett., 33, 169-174 (1989) · Zbl 0689.68058
[20] Icking, C.; Klein, R.; Lê, N.-M.; Ma, L., Convex distance functions in 3-space are different, (Proc. 9th ACM Symp. on Computational Geometry (1993))
[21] Isaacs, R., Differential Games (1965), Wiley: Wiley New York · Zbl 0152.38407
[22] Leven, D.; Sharir, M., Intersection and proximity problems and Voronoi diagrams, (Schwartz, J. T.; Yap, C. K., Advances in Robotics, vol. 1 (1987), Erlbaum: Erlbaum Hillsdale, NJ), 187-228
[23] Lê, N.-M., On general properties of smooth strictly convex distance functions in \(R^D\), (Proc. 5th Canadian Conf. on Computational Geometry (1993)), 375-380
[24] Lozano-Pérez, T., Spatial planning: a configuration space approach, IEEE Trans. Comput., 32, 2, 108-120 (1983) · Zbl 0513.68081
[25] Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0759.68037
[26] Reif, J. H.; Tate, S. R., Continuous alternation: the complexity of pursuit in continuous domains, Algorithmica, 10, 156-181 (1993) · Zbl 0798.90146
[27] Sharir, M., Almost tight upper bounds for lower envelopes in higher dimensions, (Proc. 34th Symp. Found. Comp. Sci. (1993)), 498-507 · Zbl 0819.68068
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.