Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints
In this paper we present a method for automatic planning of optimal paths for a group of robots that satisfy a common high-level mission specification. The motion of each robot is modeled as a weighted transition system, and the mission is given as a linear temporal logic (LTL) formula over a set of...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
SAGE Publications
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134287 |
| _version_ | 1811075477161377792 |
|---|---|
| author | Ulusoy, Alphan Smith, Stephen L Ding, Xu Chu Belta, Calin 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 Ulusoy, Alphan Smith, Stephen L Ding, Xu Chu Belta, Calin Rus, Daniela |
| author_sort | Ulusoy, Alphan |
| collection | MIT |
| description | In this paper we present a method for automatic planning of optimal paths for a group of robots that satisfy a common high-level mission specification. The motion of each robot is modeled as a weighted transition system, and the mission is given as a linear temporal logic (LTL) formula over a set of propositions satisfied at the regions of the environment. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize a cost function that captures the maximum time between successive satisfactions of the optimizing proposition while guaranteeing that the formula is satisfied. When the robots can follow a given trajectory exactly, our method computes a set of optimal satisfying paths that minimize the cost function and satisfy the LTL formula. However, if the traveling times of the robots are uncertain, then the robots may not be able to follow a given trajectory exactly, possibly violating the LTL formula during deployment. We handle such cases by leveraging the communication capabilities of the robots to guarantee correctness during deployment and provide bounds on the deviation from the optimal values. We implement and experimentally evaluate our method for various persistent surveillance tasks in a road network environment. © The Author(s) 2013. |
| first_indexed | 2024-09-23T10:06:44Z |
| format | Article |
| id | mit-1721.1/134287 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:06:44Z |
| publishDate | 2021 |
| publisher | SAGE Publications |
| record_format | dspace |
| spelling | mit-1721.1/1342872023-12-08T21:29:33Z Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints Ulusoy, Alphan Smith, Stephen L Ding, Xu Chu Belta, Calin Rus, Daniela Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory In this paper we present a method for automatic planning of optimal paths for a group of robots that satisfy a common high-level mission specification. The motion of each robot is modeled as a weighted transition system, and the mission is given as a linear temporal logic (LTL) formula over a set of propositions satisfied at the regions of the environment. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize a cost function that captures the maximum time between successive satisfactions of the optimizing proposition while guaranteeing that the formula is satisfied. When the robots can follow a given trajectory exactly, our method computes a set of optimal satisfying paths that minimize the cost function and satisfy the LTL formula. However, if the traveling times of the robots are uncertain, then the robots may not be able to follow a given trajectory exactly, possibly violating the LTL formula during deployment. We handle such cases by leveraging the communication capabilities of the robots to guarantee correctness during deployment and provide bounds on the deviation from the optimal values. We implement and experimentally evaluate our method for various persistent surveillance tasks in a road network environment. © The Author(s) 2013. 2021-10-27T20:04:20Z 2021-10-27T20:04:20Z 2013 2019-07-17T12:07:48Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134287 Ulusoy, A., et al. "Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints." International Journal of Robotics Research 32 8 (2013): 889-911. en 10.1177/0278364913487931 International Journal of Robotics Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf SAGE Publications other univ website |
| spellingShingle | Ulusoy, Alphan Smith, Stephen L Ding, Xu Chu Belta, Calin Rus, Daniela Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title | Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title_full | Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title_fullStr | Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title_full_unstemmed | Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title_short | Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints |
| title_sort | optimality and robustness in multi robot path planning with temporal logic constraints |
| url | https://hdl.handle.net/1721.1/134287 |
| work_keys_str_mv | AT ulusoyalphan optimalityandrobustnessinmultirobotpathplanningwithtemporallogicconstraints AT smithstephenl optimalityandrobustnessinmultirobotpathplanningwithtemporallogicconstraints AT dingxuchu optimalityandrobustnessinmultirobotpathplanningwithtemporallogicconstraints AT beltacalin optimalityandrobustnessinmultirobotpathplanningwithtemporallogicconstraints AT rusdaniela optimalityandrobustnessinmultirobotpathplanningwithtemporallogicconstraints |