Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
In this article, a stochastic optimal control problem involving an unmanned aerial vehicle flying patrols around a perimeter is considered. To determine the optimal control policy, one has to solve a Markov decision problem, whose large size renders exact dynamic programming methods intractable. Therefore, a state aggregation based approximate linear programming methodis used instead, to construct provably good suboptimal patrol policies. The state spaceis partitioned and the optimal cost-to-go or value functionis restricted to be a constant over each partition. The resulting restricted system of linear inequalities embeds a family of Markov chains of lower dimension, one of which can be used to construct a lower bound on the optimal value function. In general, the construction of a lower bound requires the solution to a combinatorial problem. But the perimeter patrol problem exhibits a special structure that enables tractable linear programming formulation for the lower bound. This is demonstrated and numerical results that corroborate the efficacy of the proposed methodology are also provided. Copyright 2013 by the American Institute of Aeronautics and Astronautics, Inc.
