Correlated Orienteering Problem and its Application to Persistent Monitoring Tasks

@article{yu_correlated_2016,
  title = {Correlated {Orienteering} {Problem} and its {Application} to {Persistent} {Monitoring} {Tasks}},
  volume = {32},
  issn = {1552-3098, 1941-0468},
  url = {http://ieeexplore.ieee.org/document/7555356/},
  abstract = {We propose the Correlated Orienteering Problem (COP) as a novel non-linear extension to the classic Orienteering Problem (OP). With the introduction of COP it becomes possible to model the planning of informative tours for the persistent monitoring of a spatiotemporal ﬁeld with time-invariant spatial correlations using autonomous mobile robots, in which the robots are range- or time-constrained. Our focus in this paper is QCOP, a quadratic COP instantiation that 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. We solve QCOP 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. Beside performing extensive simulation studies to verify the algorithm’s correctness and characterize its performance, we also successfully applied QCOP to two realistic persistent monitoring tasks: (i) estimation over a synthetic spatiotemporal ﬁeld, and (ii) estimating the temperature distribution in the state of Massachusetts.},
  language = {en},
  number = {5},
  urldate = {2020-09-15},
  journal = {IEEE Transactions on Robotics},
  author = {Yu, Jingjin and Schwager, Mac and Rus, Daniela},
  month = oct,
  year = {2016},
  keywords = {cooperative\_planning},
  pages = {1106--1118},
  month_numeric = {10}
}