Dynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games
Preprint
Abstract
We study two player pursuit-evasion games with concurrent moves, infinite horizon, and discounted rewards. The players have partial observability, however, the evader is given an advantage of knowing the current position of the units of the pursuer. We show that (1) value functions of this game depend only on the position of the pursuing units and the belief the pursuer has about the position of the evader, and (2) that they are piecewise linear convex functions in the belief. Finally, we exploit this representation of value functions and design a value iteration algorithm that approximates the value of the game.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Partial-Observation Stochastic Games: How to Win When Belief Fails2012
- Search and pursuit-evasion in mobile roboticsAutonomous Robots, 2011
- On Stefan Banach and some of his resultsBanach Journal of Mathematical Analysis, 2007
- Some Classes of Imperfect Information Finite State-Space Stochastic Games with Finite-Dimensional SolutionsApplied Mathematics & Optimization, 2004
- Zero-Sum Stochastic Games with Partial InformationJournal of Optimization Theory and Applications, 2004
- Efficient Computation of Equilibria for Extensive Two-Person GamesGames and Economic Behavior, 1996
- State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and AlgorithmsManagement Science, 1982
- The Optimal Control of Partially Observable Markov Processes over a Finite HorizonOperations Research, 1973