Multi-Query Shortest-Path Problem in Graphs of Convex Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929520283484160 |
|---|---|
| author | Morozov, Savva Marcucci, Tobia Amice, Alexandre Graesdal, Bernhard Paus Bosworth, Rohan Parrilo, Pablo A. Tedrake, Russ |
| author_facet | Morozov, Savva Marcucci, Tobia Amice, Alexandre Graesdal, Bernhard Paus Bosworth, Rohan Parrilo, Pablo A. Tedrake, Russ |
| contents | The Shortest-Path Problem in Graph of Convex Sets (SPP in GCS) is a recently developed optimization framework that blends discrete and continuous decision making. Many relevant problems in robotics, such as collision-free motion planning, can be cast and solved as an SPP in GCS, yielding lower-cost solutions and faster runtimes than state-of-the-art algorithms. In this paper, we are motivated by motion planning of robot arms that must operate swiftly in static environments. We consider a multi-query extension of the SPP in GCS, where the goal is to efficiently precompute optimal paths between given sets of initial and target conditions. Our solution consists of two stages. Offline, we use semidefinite programming to compute a coarse lower bound on the problem's cost-to-go function. Then, online, this lower bound is used to incrementally generate feasible paths by solving short-horizon convex programs. For a robot arm with seven joints, our method designs higher quality trajectories up to two orders of magnitude faster than existing motion planners. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_19543 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Query Shortest-Path Problem in Graphs of Convex Sets Morozov, Savva Marcucci, Tobia Amice, Alexandre Graesdal, Bernhard Paus Bosworth, Rohan Parrilo, Pablo A. Tedrake, Russ Robotics The Shortest-Path Problem in Graph of Convex Sets (SPP in GCS) is a recently developed optimization framework that blends discrete and continuous decision making. Many relevant problems in robotics, such as collision-free motion planning, can be cast and solved as an SPP in GCS, yielding lower-cost solutions and faster runtimes than state-of-the-art algorithms. In this paper, we are motivated by motion planning of robot arms that must operate swiftly in static environments. We consider a multi-query extension of the SPP in GCS, where the goal is to efficiently precompute optimal paths between given sets of initial and target conditions. Our solution consists of two stages. Offline, we use semidefinite programming to compute a coarse lower bound on the problem's cost-to-go function. Then, online, this lower bound is used to incrementally generate feasible paths by solving short-horizon convex programs. For a robot arm with seven joints, our method designs higher quality trajectories up to two orders of magnitude faster than existing motion planners. |
| title | Multi-Query Shortest-Path Problem in Graphs of Convex Sets |
| topic | Robotics |
| url | https://arxiv.org/abs/2409.19543 |