Motion Planning with Precedence Specifications via Augmented Graphs of Convex Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915903835209728 |
|---|---|
| author | You, Shilin Luna, Gael Shaikh, Juned Gostin, David Xiang, Yu Koeln, Justin Summers, Tyler |
| author_facet | You, Shilin Luna, Gael Shaikh, Juned Gostin, David Xiang, Yu Koeln, Justin Summers, Tyler |
| contents | We present an algorithm for planning trajectories that avoid obstacles and satisfy key-door precedence specifications expressed with a fragment of signal temporal logic. Our method includes a novel exact convex partitioning of the obstacle free space that encodes connectivity among convex free space sets, key sets, and door sets. We then construct an augmented graph of convex sets that exactly encodes the key-door precedence specifications. By solving a shortest path problem in this augmented graph of convex sets, our pipeline provides an exact solution up to a finite parameterization of the trajectory. To illustrate the effectiveness of our approach, we present a method to generate key-door mazes that provide challenging problem instances, and we perform numerical experiments to evaluate the proposed pipeline. Our pipeline is faster by several orders of magnitude than recent state-of-the art methods that use general purpose temporal logic tools. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22015 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Motion Planning with Precedence Specifications via Augmented Graphs of Convex Sets You, Shilin Luna, Gael Shaikh, Juned Gostin, David Xiang, Yu Koeln, Justin Summers, Tyler Systems and Control We present an algorithm for planning trajectories that avoid obstacles and satisfy key-door precedence specifications expressed with a fragment of signal temporal logic. Our method includes a novel exact convex partitioning of the obstacle free space that encodes connectivity among convex free space sets, key sets, and door sets. We then construct an augmented graph of convex sets that exactly encodes the key-door precedence specifications. By solving a shortest path problem in this augmented graph of convex sets, our pipeline provides an exact solution up to a finite parameterization of the trajectory. To illustrate the effectiveness of our approach, we present a method to generate key-door mazes that provide challenging problem instances, and we perform numerical experiments to evaluate the proposed pipeline. Our pipeline is faster by several orders of magnitude than recent state-of-the art methods that use general purpose temporal logic tools. |
| title | Motion Planning with Precedence Specifications via Augmented Graphs of Convex Sets |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2510.22015 |