Correlated Orienteering Problem and it Application to Persistent Monitoring Tasks
This addresses the challenge of efficient monitoring in robotics or environmental sensing, but it is incremental as it extends the Orienteering Problem with correlations.
The authors tackled the problem of planning informative tours for persistent monitoring of spatiotemporal fields with spatial correlations by proposing the Correlated Orienteering Problem (COP), specifically QCOP with a quadratic utility function, and developed an anytime algorithm using mixed integer quadratic programming that can plan near-optimal tours for up to 150 nodes, validated through simulations and applied to tasks like temperature estimation in Massachusetts.
We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to model the planning of informative tours for the persistent monitoring of a spatiotemporal field with time-invariant spatial correlations, in which the tours are constrained to have limited length. Our focus in this paper is QCOP a quadratic COP formulation that only looks at correlations between neighboring nodes in a node network. The main feature of QCOP is a quadratic utility function capturing the said spatial correlation. QCOP may be solved using mixed integer quadratic programming (MIQP), with the resulting anytime algorithm capable of planning multiple disjoint tours that maximize the quadratic utility. In particular, our algorithm can quickly plan a near-optimal tour over a network with up to $150$ nodes. Besides performing extensive simulation studies to verify the algorithm's correctness and characterize its performance, we also successfully applied it to two realistic persistent monitoring tasks: (i) estimation over a synthetic spatiotemporal field, and (ii) estimating the temperature distribution in the state of Massachusetts.