Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2405.00687 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909187567517696 |
|---|---|
| author | Watanabe, Kandai Fainekos, Georgios Hoxha, Bardh Lahijanian, Morteza Okamoto, Hideki Sankaranarayanan, Sriram |
| author_facet | Watanabe, Kandai Fainekos, Georgios Hoxha, Bardh Lahijanian, Morteza Okamoto, Hideki Sankaranarayanan, Sriram |
| contents | This paper addresses the challenge of planning a sequence of tasks to be performed by multiple robots while minimizing the overall completion time subject to timing and precedence constraints. Our approach uses the Timed Partial Orders (TPO) model to specify these constraints. We translate this problem into a Traveling Salesman Problem (TSP) variant with timing and precedent constraints, and we solve it as a Mixed Integer Linear Programming (MILP) problem. Our contributions include a general planning framework for TPO specifications, a MILP formulation accommodating time windows and precedent constraints, its extension to multi-robot scenarios, and a method to quantify plan robustness. We demonstrate our framework on several case studies, including an aircraft turnaround task involving three Jackal robots, highlighting the approach's potential applicability to important real-world problems. Our benchmark results show that our MILP method outperforms state-of-the-art open-source TSP solvers OR-Tools. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00687 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Planning for Timed Partial Order Specifications Watanabe, Kandai Fainekos, Georgios Hoxha, Bardh Lahijanian, Morteza Okamoto, Hideki Sankaranarayanan, Sriram Robotics Logic in Computer Science This paper addresses the challenge of planning a sequence of tasks to be performed by multiple robots while minimizing the overall completion time subject to timing and precedence constraints. Our approach uses the Timed Partial Orders (TPO) model to specify these constraints. We translate this problem into a Traveling Salesman Problem (TSP) variant with timing and precedent constraints, and we solve it as a Mixed Integer Linear Programming (MILP) problem. Our contributions include a general planning framework for TPO specifications, a MILP formulation accommodating time windows and precedent constraints, its extension to multi-robot scenarios, and a method to quantify plan robustness. We demonstrate our framework on several case studies, including an aircraft turnaround task involving three Jackal robots, highlighting the approach's potential applicability to important real-world problems. Our benchmark results show that our MILP method outperforms state-of-the-art open-source TSP solvers OR-Tools. |
| title | Optimal Planning for Timed Partial Order Specifications |
| topic | Robotics Logic in Computer Science |
| url | https://arxiv.org/abs/2405.00687 |