Evasive path planning under surveillance uncertainty.

*(English)*Zbl 1445.49019Summary: The classical setting of optimal control theory assumes full knowledge of the process dynamics and the costs associated with every control strategy. The problem becomes much harder if the controller only knows a finite set of possible running cost functions, but has no way of checking which of these running costs is actually in place. In this paper we address this challenge for a class of evasive path planning problems on a continuous domain, in which an evader needs to reach a target while minimizing his exposure to an enemy observer, who is in turn selecting from a finite set of known surveillance plans. Our key assumption is that both the evader and the observer need to commit to their (possibly probabilistic) strategies in advance and cannot immediately change their actions based on any newly discovered information about the opponent’s current position. We consider two types of evader behavior: in the first one, a completely risk-averse evader seeks a trajectory minimizing his worst-case cumulative observability, and in the second, the evader is concerned with minimizing the average-case cumulative observability. The latter version is naturally interpreted as a semi-infinite strategic game, and we provide an efficient method for approximating its Nash equilibrium. The proposed approach draws on methods from game theory, convex optimization, optimal control, and multiobjective dynamic programming. We illustrate our algorithm using numerical examples and discuss the computational complexity, including for the generalized version with multiple evaders.

##### MSC:

49N75 | Pursuit and evasion games |

49N90 | Applications of optimal control and differential games |

49K35 | Optimality conditions for minimax problems |

91A05 | 2-person games |

90C29 | Multi-objective and goal programming |

35F21 | Hamilton-Jacobi equations |

90C25 | Convex programming |

49K20 | Optimality conditions for problems involving partial differential equations |

##### Keywords:

path planning; semi-infinite games; Nash equilibrium; surveillance evasion; convex optimization; Hamilton-Jacobi PDEs##### Software:

NBI
PDF
BibTeX
XML
Cite

\textit{M. A. Gilles} and \textit{A. Vladimirsky}, Dyn. Games Appl. 10, No. 2, 391--416 (2020; Zbl 1445.49019)

Full Text:
DOI

##### References:

[1] | Alton, K.; Mitchell, IM, An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations, J Sci Comput, 51, 313-348 (2012) · Zbl 1256.65099 |

[2] | Bardi, M.; Capuzzo-Dolcetta, I., Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations (2008), Berlin: Springer, Berlin · Zbl 1134.49022 |

[3] | Beck, A., First-order methods in optimization (2017), Philadelphia: SIAM, Philadelphia · Zbl 1384.65033 |

[4] | Brucker, P., An \(O(n)\) algorithm for quadratic knapsack problems, Oper Res Lett, 3, 163-166 (1984) · Zbl 0544.90086 |

[5] | Carmona, R.; Delarue, F., Probabilistic theory of mean field games with applications I-II (2017), Berlin: Springer, Berlin |

[6] | Cartee E, Lai L, Song Q, Vladimirsky A (2019) Time-dependent surveillance-evasion games, preprint arXiv:1903.01332 |

[7] | Chacon, A.; Vladimirsky, A., Fast two-scale methods for Eikonal equations, SIAM J Sci Comput, 34, A547-A578 (2012) · Zbl 1244.49047 |

[8] | Chacon, A.; Vladimirsky, A., A parallel two-scale method for Eikonal equations, SIAM J Sci Comput, 37, A156-A180 (2015) · Zbl 1348.49025 |

[9] | Clawson, Z.; Chacon, A.; Vladimirsky, A., Causal domain restriction for Eikonal equations, SIAM J Sci Comput, 36, A2478-A2505 (2014) · Zbl 1306.49048 |

[10] | Clawson Z, Ding X, Englot B, Frewen TA, Sisson WM, Vladimirsky A (2015) A bi-criteria path planning algorithm for robotics applications, preprint arXiv:1511.01166 |

[11] | Crandall, MG; Lions, P-L, Viscosity solutions of Hamilton-Jacobi equations, Trans Am Math Soc, 277, 1-42 (1983) · Zbl 0599.35024 |

[12] | Das, I.; Dennis, JE, A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, Struct Optim, 14, 63-69 (1997) |

[13] | Desilles A, Zidani H (2018) Pareto front characterization for multi-objective optimal control problems using Hamilton-Jacobi approach, preprint · Zbl 1429.49003 |

[14] | Dijkstra, EW, A note on two problems in connexion with graphs, Numer Math, 1, 269-271 (1959) · Zbl 0092.16002 |

[15] | Dobbie J (1966) Solution of some surveillance-evasion problems by the methods of differential games. In: Proceedings of the 4th international conference on operational research. MIT, Wiley, New York |

[16] | Falcone, M.; Ferretti, R., Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations (2014), Philadelphia: SIAM, Philadelphia · Zbl 1335.65001 |

[17] | Guéant, O.; Lasry, J-M; Lions, P-L, Mean field games and applications, Paris-Princeton lectures on mathematical finance, 205-266 (2010), Berlin: Springer, Berlin |

[18] | Guigue, A., Approximation of the pareto optimal set for multiobjective optimal control problems using viability kernels, ESAIM COCV, 20, 95-115 (2014) · Zbl 1307.90159 |

[19] | Kumar, A.; Vladimirsky, A., An efficient method for multiobjective optimal control and optimal control subject to integral constraints, J Comput Math, 1, 517-551 (2010) · Zbl 1240.90345 |

[20] | Lewin J (1973) Decoy in pursuit-evasion games. PhD thesis, Department of Aeronautics and Astronautics, Stanford University |

[21] | Lewin, J.; Breakwell, JV, The surveillance-evasion game of degree, J Optim Theory Appl, 16, 339-353 (1975) · Zbl 0283.90082 |

[22] | Lewin, J.; Olsder, GJ, Conic surveillance evasion, J Optim Theory Appl, 27, 107-125 (1979) · Zbl 0378.90106 |

[23] | Marler, RT; Arora, JS, Survey of multi-objective optimization methods for engineering, Struct Multidiscip Optim, 26, 369-395 (2004) · Zbl 1243.90199 |

[24] | Mirebeau, J-M, Efficient fast marching with Finsler metrics, Numer Math, 126, 515-557 (2014) · Zbl 1297.65074 |

[25] | Mitchell IM, Sastry S (2003) Continuous path planning with multiple constraints. In: 2003 42nd IEEE conference on decision and control, vol 5, pp 5502-5507 |

[26] | Osborne, MJ; Rubinstein, A., A course in game theory (1994), Cambridge: MIT press, Cambridge |

[27] | Qi, D.; Vladimirsky, A., Corner cases, singularities, and dynamic factoring, J Sci Comput, 79, 1456-1476 (2019) · Zbl 1419.49034 |

[28] | Raghavan, T., Zero-sum two-person games, Handb Game Theory Econ Appl, 2, 735-768 (1994) · Zbl 0925.90101 |

[29] | Sethian JA (1996) A fast marching level set method for monotonically advancing fronts. In: Proceedings of the National Academy of Sciences, vol 93, pp 1591-1595 · Zbl 0852.65055 |

[30] | Sethian, JA, Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0973.76003 |

[31] | Sethian, JA; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms, SIAM J Numer Anal, 41, 325-363 (2003) · Zbl 1040.65088 |

[32] | Shu, C-W, High order numerical methods for time dependent Hamilton-Jacobi equations, Mathematics and computation in imaging science and information processing, 47-91 (2007), Singapore: World Scientific, Singapore |

[33] | Soner, H., Optimal control with state-space constraint, I SIAM J Control Optim, 24, 552-561 (1986) · Zbl 0597.49023 |

[34] | Takei, R.; Chen, W.; Clawson, Z.; Kirov, S.; Vladimirsky, A., Optimal control with budget constraints and resets, SIAM J Control Optim, 53, 712-744 (2015) · Zbl 1322.90091 |

[35] | Tijs, S., Semi-infinite linear programs and semi-infinite matrix games (1976), Nijmegen: Katholieke Universiteit Nijmegen, Mathematisch Instituut, Nijmegen · Zbl 0399.90054 |

[36] | Tsai, Y-HR; Cheng, L-T; Osher, S.; Zhao, H-K, Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM J Numer Anal, 41, 673-694 (2003) · Zbl 1049.35020 |

[37] | Tsitsiklis, JN, Efficient algorithms for globally optimal trajectories, IEEE Trans Autom Control, 40, 1528-1538 (1995) · Zbl 0831.93028 |

[38] | Wang W, Carreira-Perpinán MA (2013) Projection onto the probability simplex: an efficient algorithm with a simple proof, and an application, arXiv preprint arXiv:1309.1541 |

[39] | Zhao, H., A fast sweeping method for Eikonal equations, Math Comput, 74, 603-627 (2005) · Zbl 1070.65113 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.