Evasive path planning under surveillance uncertainty
From MaRDI portal
Publication:778086
convex optimizationNash equilibriumpath planningHamilton-Jacobi PDEssemi-infinite gamessurveillance evasion
Convex programming (90C25) Multi-objective and goal programming (90C29) Pursuit and evasion games (49N75) 2-person games (91A05) Hamilton-Jacobi equations (35F21) Optimality conditions for problems involving partial differential equations (49K20) Optimality conditions for minimax problems (49K35) Applications of optimal control and differential games (49N90)
Abstract: 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 {em worst-case} cumulative observability, and in the second, the evader is concerned with minimizing the {em 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.
Recommendations
- An efficient algorithm for a visibility-based surveillance-evasion game
- Surveillance for security as a pursuit-evasion game
- Optimal evasion with a path-angle constraint and against two pursuers
- Evasion from detection by a system of heterogeneous observers in threat environment
- Mobile object evasion from detection by a group of observers
Cites work
- scientific article; zbMATH DE number 3621462 (Why is no real title available?)
- scientific article; zbMATH DE number 1226083 (Why is no real title available?)
- scientific article; zbMATH DE number 1349965 (Why is no real title available?)
- A course in game theory.
- A fast marching level set method for monotonically advancing fronts.
- A fast sweeping method for Eikonal equations
- A note on two problems in connexion with graphs
- A parallel two-scale method for eikonal equations
- An O(n) algorithm for quadratic knapsack problems
- An efficient method for multiobjective optimal control and optimal control subject to integral constraints
- An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
- Approximation of the Pareto optimal set for multiobjective optimal control problems using viability kernels
- Causal domain restriction for eikonal equations
- Conic surveillance evasion
- Corner cases, singularities, and dynamic factoring
- Efficient algorithms for globally optimal trajectories
- Efficient fast marching with Finsler metrics
- Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
- Fast two-scale methods for eikonal equations
- First-order methods in optimization
- Mathematics and Computation in Imaging Science and Information Processing
- Mean field games and applications
- Optimal Control with State-Space Constraint I
- Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
- Optimal control with budget constraints and resets
- Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
- Pareto front characterization for multiobjective optimal control problems using Hamilton-Jacobi approach
- Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations
- Survey of multi-objective optimization methods for engineering
- The surveillance-evasion game of degree
- Viscosity Solutions of Hamilton-Jacobi Equations
Cited in
(7)- A discrete optimisation approach for target path planning whilst evading sensors
- Detection-averse optimal and receding-horizon control for Markov decision processes
- Automatic differentiation of non-holonomic fast marching for computing most threatening trajectories under sensors surveillance
- Control-theoretic models of environmental crime
- Decision-theoretic planning for autonomous robotic surveillance
- Surveillance for security as a pursuit-evasion game
- Modeling illegal logging in Brazil
This page was built for publication: Evasive path planning under surveillance uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778086)
