Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks
© 2014 IEEE. We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to plan informative tours (cyclic paths) for persistent monitoring of an environment with spatial correlations, where the tours are constrained to a fix...
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
IEEE
2021
|
Online Access: | https://hdl.handle.net/1721.1/137110 |
_version_ | 1811076892271312896 |
---|---|
author | Yu, Jingjin Schwager, Mac Rus, Daniela |
author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Yu, Jingjin Schwager, Mac Rus, Daniela |
author_sort | Yu, Jingjin |
collection | MIT |
description | © 2014 IEEE. We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to plan informative tours (cyclic paths) for persistent monitoring of an environment with spatial correlations, where the tours are constrained to a fixed length or time budget. The main feature of COP is a quadratic utility function that captures spatial correlations among points of interest that are close to each other. COP may be solved using mixed integer quadratic programming (MIQP) that can plan multiple disjoint tours that maximize the quadratic utility function. We perform extensive characterization of our method to verify its correctness, as well as its applicability to the estimation of a realistic, time-varying, and spatially correlated scalar field. |
first_indexed | 2024-09-23T10:29:53Z |
format | Article |
id | mit-1721.1/137110 |
institution | Massachusetts Institute of Technology |
language | English |
last_indexed | 2024-09-23T10:29:53Z |
publishDate | 2021 |
publisher | IEEE |
record_format | dspace |
spelling | mit-1721.1/1371102023-04-18T19:31:33Z Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks Yu, Jingjin Schwager, Mac Rus, Daniela Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2014 IEEE. We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to plan informative tours (cyclic paths) for persistent monitoring of an environment with spatial correlations, where the tours are constrained to a fixed length or time budget. The main feature of COP is a quadratic utility function that captures spatial correlations among points of interest that are close to each other. COP may be solved using mixed integer quadratic programming (MIQP) that can plan multiple disjoint tours that maximize the quadratic utility function. We perform extensive characterization of our method to verify its correctness, as well as its applicability to the estimation of a realistic, time-varying, and spatially correlated scalar field. 2021-11-02T16:59:16Z 2021-11-02T16:59:16Z 2014-09 2019-07-17T12:41:03Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137110 Yu, Jingjin, Schwager, Mac and Rus, Daniela. 2014. "Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks." en 10.1109/iros.2014.6942582 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
spellingShingle | Yu, Jingjin Schwager, Mac Rus, Daniela Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title | Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title_full | Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title_fullStr | Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title_full_unstemmed | Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title_short | Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks |
title_sort | correlated orienteering problem and its application to informative path planning for persistent monitoring tasks |
url | https://hdl.handle.net/1721.1/137110 |
work_keys_str_mv | AT yujingjin correlatedorienteeringproblemanditsapplicationtoinformativepathplanningforpersistentmonitoringtasks AT schwagermac correlatedorienteeringproblemanditsapplicationtoinformativepathplanningforpersistentmonitoringtasks AT rusdaniela correlatedorienteeringproblemanditsapplicationtoinformativepathplanningforpersistentmonitoringtasks |