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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Lower Bounding Linear Program for the Perimeter Patrol Optimization Problem


    Contributors:

    Published in:

    Publication date :

    2014-02-05


    Size :

    8 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A Lower Bounding Linear Programming approach to the Perimeter Patrol Stochastic Control Problem

    Kalyanam, Krishnamoorthy / Darbha, Swaroop / Park, Myoungkuk et al. | AIAA | 2012


    2012-2454 A Lower Bounding Linear Programming approach to the Perimeter Patrol Stochastic Control Problem

    Kalyanam, K. / Darbha, S. / Park, M. et al. | British Library Conference Proceedings | 2012



    Approximate Dynamic Programming Applied to UAV Perimeter Patrol

    Krishnamoorthy, K. / Park, M. / Darbha, S. et al. | Springer Verlag | 2013