Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem
Document Type
Article
Publication Date
3-2014
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 method is used instead, to construct provably good suboptimal patrol policies. The state space is partitioned and the optimal cost-to-go or value function is 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. Abstract © AIAA
DOI
Source Publication
Journal of Guidance, Control, and Dynamics
Recommended Citation
Kalyanam, K., Park, M., Darbha, S., Casbeer, D., Chandler, P., & Pachter, M. (2014). Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem. Journal of Guidance, Control, and Dynamics, 37(2), 558–565. https://doi.org/10.2514/1.60487
Comments
Copyright © 2013 by the American Institute of Aeronautics and Astronautics, Inc.
The full article is available via subscription or purchase using the DOI link below.
Funding note: This work was partly supported by the U.S. Air Force Research Laboratory Summer Faculty Program and Air Force Office of Scientific Research award number FA9550-10-1-0392.