Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem Conference Paper uri icon


  • 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.

author list (cited authors)

  • Kalyanam, K., Park, M., Darbha, S., Casbeer, D., Chandler, P., & Pachter, M.

citation count

  • 3

publication date

  • January 1, 2014 11:11 AM
  • March 2014