Optimal multi-robot path planning with temporal logic constraints
In this paper we present a method for automatically planning optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system. The mission is given as a Linear Temporal Logic formula. In...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72507 https://orcid.org/0000-0001-5473-3566 |
| _version_ | 1826205289736568832 |
|---|---|
| author | Ulusoy, Alphan Smith, Stephen L. Ding, Xu Chu Belta, Calin Rus, Daniela L. |
| 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 L. |
| author_sort | Ulusoy, Alphan |
| collection | MIT |
| description | In this paper we present a method for automatically planning optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system. The mission is given as a Linear Temporal Logic formula. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize the maximum time between satisfying instances of the optimizing proposition. Our method is guaranteed to compute an optimal set of robot paths. We utilize a timed automaton representation in order to capture the relative position of the robots in the environment. We then obtain a bisimulation of this timed automaton as a finite transition system that captures the joint behavior of the robots and apply our earlier algorithm for the single robot case to optimize the group motion. We present a simulation of a persistent monitoring task in a road network environment. |
| first_indexed | 2024-09-23T13:10:21Z |
| format | Article |
| id | mit-1721.1/72507 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:10:21Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/725072022-10-01T13:30:24Z Optimal multi-robot path planning with temporal logic constraints Ulusoy, Alphan Smith, Stephen L. Ding, Xu Chu Belta, Calin Rus, Daniela L. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. School of Engineering Rus, Daniela L. Rus, Daniela L. In this paper we present a method for automatically planning optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system. The mission is given as a Linear Temporal Logic formula. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize the maximum time between satisfying instances of the optimizing proposition. Our method is guaranteed to compute an optimal set of robot paths. We utilize a timed automaton representation in order to capture the relative position of the robots in the environment. We then obtain a bisimulation of this timed automaton as a finite transition system that captures the joint behavior of the robots and apply our earlier algorithm for the single robot case to optimize the group motion. We present a simulation of a persistent monitoring task in a road network environment. United States. Office of Naval Research. Multidisciplinary University Research Initiative (N00014-09-1051) United States. Army Research Office (W911NF-09-1-0088) United States. Air Force Office of Scientific Research (YIP FA9550-09-1-020) National Science Foundation (U.S.). (CNS- 0834260) 2012-09-04T18:50:33Z 2012-09-04T18:50:33Z 2011-12 2011-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-61284-454-1 2153-0858 http://hdl.handle.net/1721.1/72507 Ulusoy, Alphan et al. “Optimal Multi-robot Path Planning with Temporal Logic Constraints.” IEEE/RSJ International Conference on Intelligent Robots and Systems 2011 (IROS). 3087–3092. https://orcid.org/0000-0001-5473-3566 en_US http://dx.doi.org/10.1109/IROS.2011.6094884 IEEE/RSJ International Conference on Intelligent Robots and Systems 2011 (IROS) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Ulusoy, Alphan Smith, Stephen L. Ding, Xu Chu Belta, Calin Rus, Daniela L. Optimal multi-robot path planning with temporal logic constraints |
| title | Optimal multi-robot path planning with temporal logic constraints |
| title_full | Optimal multi-robot path planning with temporal logic constraints |
| title_fullStr | Optimal multi-robot path planning with temporal logic constraints |
| title_full_unstemmed | Optimal multi-robot path planning with temporal logic constraints |
| title_short | Optimal multi-robot path planning with temporal logic constraints |
| title_sort | optimal multi robot path planning with temporal logic constraints |
| url | http://hdl.handle.net/1721.1/72507 https://orcid.org/0000-0001-5473-3566 |
| work_keys_str_mv | AT ulusoyalphan optimalmultirobotpathplanningwithtemporallogicconstraints AT smithstephenl optimalmultirobotpathplanningwithtemporallogicconstraints AT dingxuchu optimalmultirobotpathplanningwithtemporallogicconstraints AT beltacalin optimalmultirobotpathplanningwithtemporallogicconstraints AT rusdanielal optimalmultirobotpathplanningwithtemporallogicconstraints |