Evasive path planning under surveillance uncertainty

DOI10.1007/S13235-019-00327-XzbMATH Open1445.49019arXiv1812.10620OpenAlexW2982082268WikidataQ127028106 ScholiaQ127028106MaRDI QIDQ778086FDOQ778086

Authors: Marc Aurèle Gilles, Alexander Vladimirsky 

Publication date: 30 June 2020

Published in: Dynamic Games and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1812.10620

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

zbMATH Keywords

convex optimizationNash equilibriumpath planningHamilton-Jacobi PDEssemi-infinite gamessurveillance evasion

Mathematics Subject Classification ID

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)

Cites Work

• A note on two problems in connexion with graphs
• First-Order Methods in Optimization
• Mean field games and applications
• Optimal Control with State-Space Constraint I
• Viscosity Solutions of Hamilton-Jacobi Equations
• Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
• Semi-Lagrangian Approximation Schemes for Linear and Hamilton—Jacobi Equations
• Efficient fast marching with Finsler metrics
• A course in game theory.
• Survey of multi-objective optimization methods for engineering
• Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
• A fast sweeping method for Eikonal equations
• Efficient algorithms for globally optimal trajectories
• A fast marching level set method for monotonically advancing fronts.
• Title not available (Why is that?)
• An efficient method for multiobjective optimal control and optimal control subject to integral constraints
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• An O(n) algorithm for quadratic knapsack problems
• An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
• Mathematics and Computation in Imaging Science and Information Processing
• Fast two-scale methods for eikonal equations
• A Parallel Two-Scale Method for Eikonal Equations
• Conic surveillance evasion
• Title not available (Why is that?)
• Title not available (Why is that?)
• The surveillance-evasion game of degree
• Corner cases, singularities, and dynamic factoring
• Causal Domain Restriction for Eikonal Equations
• Pareto Front Characterization for Multiobjective Optimal Control Problems Using Hamilton--Jacobi Approach
• Optimal Control with Budget Constraints and Resets
• Approximation of the pareto optimal set for multiobjective optimal control problems using viability kernels

Cited In (3)

• Modeling illegal logging in Brazil
• Decision-theoretic planning for autonomous robotic surveillance
• Control-Theoretic Models of Environmental Crime

Uses Software

• NBI

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)