Multi-Query Shortest-Path Problem in Graphs of Convex Sets Article Swipe
Savva Morozov
,
Tobia Marcucci
,
Alexandre Amice
,
Bernhard Paus Graesdal
,
Rohan Bosworth
,
Pablo A. Parrilo
,
Russ Tedrake
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.19543
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.19543
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.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2409.19543
- https://arxiv.org/pdf/2409.19543
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4403812684
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4403812684Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2409.19543Digital Object Identifier
- Title
-
Multi-Query Shortest-Path Problem in Graphs of Convex SetsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-09-29Full publication date if available
- Authors
-
Savva Morozov, Tobia Marcucci, Alexandre Amice, Bernhard Paus Graesdal, Rohan Bosworth, Pablo A. Parrilo, Russ TedrakeList of authors in order
- Landing page
-
https://arxiv.org/abs/2409.19543Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2409.19543Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2409.19543Direct OA link when available
- Concepts
-
Combinatorics, Shortest path problem, Mathematics, Regular polygon, Computer science, Graph, GeometryTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4403812684 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2409.19543 |
| ids.doi | https://doi.org/10.48550/arxiv.2409.19543 |
| ids.openalex | https://openalex.org/W4403812684 |
| fwci | |
| type | preprint |
| title | Multi-Query Shortest-Path Problem in Graphs of Convex Sets |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12288 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9825000166893005 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Optimization and Search Problems |
| topics[1].id | https://openalex.org/T10567 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9549000263214111 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2209 |
| topics[1].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[1].display_name | Vehicle Routing Optimization Methods |
| topics[2].id | https://openalex.org/T12176 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9329000115394592 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2209 |
| topics[2].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[2].display_name | Optimization and Packing Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C114614502 |
| concepts[0].level | 1 |
| concepts[0].score | 0.5994817018508911 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[0].display_name | Combinatorics |
| concepts[1].id | https://openalex.org/C22590252 |
| concepts[1].level | 3 |
| concepts[1].score | 0.5961445569992065 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1058754 |
| concepts[1].display_name | Shortest path problem |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5560754537582397 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C112680207 |
| concepts[3].level | 2 |
| concepts[3].score | 0.46164458990097046 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[3].display_name | Regular polygon |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.3291029930114746 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C132525143 |
| concepts[5].level | 2 |
| concepts[5].score | 0.12523135542869568 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[5].display_name | Graph |
| concepts[6].id | https://openalex.org/C2524010 |
| concepts[6].level | 1 |
| concepts[6].score | 0.0 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[6].display_name | Geometry |
| keywords[0].id | https://openalex.org/keywords/combinatorics |
| keywords[0].score | 0.5994817018508911 |
| keywords[0].display_name | Combinatorics |
| keywords[1].id | https://openalex.org/keywords/shortest-path-problem |
| keywords[1].score | 0.5961445569992065 |
| keywords[1].display_name | Shortest path problem |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.5560754537582397 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/regular-polygon |
| keywords[3].score | 0.46164458990097046 |
| keywords[3].display_name | Regular polygon |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.3291029930114746 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/graph |
| keywords[5].score | 0.12523135542869568 |
| keywords[5].display_name | Graph |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2409.19543 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2409.19543 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2409.19543 |
| locations[1].id | doi:10.48550/arxiv.2409.19543 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2409.19543 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5093957497 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Savva Morozov |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Morozov, Savva |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5018909196 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-8249-0434 |
| authorships[1].author.display_name | Tobia Marcucci |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Marcucci, Tobia |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5007798248 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-3955-9560 |
| authorships[2].author.display_name | Alexandre Amice |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Amice, Alexandre |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5093957495 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Bernhard Paus Graesdal |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Graesdal, Bernhard Paus |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5114424970 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Rohan Bosworth |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Bosworth, Rohan |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5031935416 |
| authorships[5].author.orcid | https://orcid.org/0000-0003-1132-8477 |
| authorships[5].author.display_name | Pablo A. Parrilo |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Parrilo, Pablo A. |
| authorships[5].is_corresponding | False |
| authorships[6].author.id | https://openalex.org/A5074291890 |
| authorships[6].author.orcid | |
| authorships[6].author.display_name | Russ Tedrake |
| authorships[6].author_position | last |
| authorships[6].raw_author_name | Tedrake, Russ |
| authorships[6].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2409.19543 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Multi-Query Shortest-Path Problem in Graphs of Convex Sets |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12288 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9825000166893005 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Optimization and Search Problems |
| related_works | https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2409.19543 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2409.19543 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2409.19543 |
| primary_location.id | pmh:oai:arXiv.org:2409.19543 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2409.19543 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2409.19543 |
| publication_date | 2024-09-29 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 12, 74, 112, 139 |
| abstract_inverted_index.In | 53 |
| abstract_inverted_index.We | 72 |
| abstract_inverted_index.an | 40 |
| abstract_inverted_index.as | 30, 39 |
| abstract_inverted_index.be | 35 |
| abstract_inverted_index.by | 59, 133 |
| abstract_inverted_index.in | 3, 9, 27, 42, 69, 80 |
| abstract_inverted_index.is | 11, 85, 126 |
| abstract_inverted_index.of | 5, 62, 77, 94, 102, 155 |
| abstract_inverted_index.on | 116 |
| abstract_inverted_index.to | 86, 110, 128, 152 |
| abstract_inverted_index.up | 151 |
| abstract_inverted_index.we | 56, 106 |
| abstract_inverted_index.For | 138 |
| abstract_inverted_index.Our | 99 |
| abstract_inverted_index.SPP | 41, 79 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 20, 37, 47, 96 |
| abstract_inverted_index.are | 57 |
| abstract_inverted_index.arm | 141 |
| abstract_inverted_index.can | 34 |
| abstract_inverted_index.our | 145 |
| abstract_inverted_index.the | 78, 83, 117 |
| abstract_inverted_index.two | 103, 153 |
| abstract_inverted_index.use | 107 |
| abstract_inverted_index.(SPP | 8 |
| abstract_inverted_index.GCS) | 10 |
| abstract_inverted_index.GCS, | 43, 81 |
| abstract_inverted_index.Many | 24 |
| abstract_inverted_index.Sets | 7 |
| abstract_inverted_index.arms | 64 |
| abstract_inverted_index.cast | 36 |
| abstract_inverted_index.goal | 84 |
| abstract_inverted_index.must | 66 |
| abstract_inverted_index.sets | 93 |
| abstract_inverted_index.such | 29 |
| abstract_inverted_index.than | 50, 158 |
| abstract_inverted_index.that | 17, 65 |
| abstract_inverted_index.this | 54, 123 |
| abstract_inverted_index.used | 127 |
| abstract_inverted_index.with | 142 |
| abstract_inverted_index.Graph | 4 |
| abstract_inverted_index.Then, | 121 |
| abstract_inverted_index.bound | 115, 125 |
| abstract_inverted_index.given | 92 |
| abstract_inverted_index.lower | 114, 124 |
| abstract_inverted_index.paths | 90, 132 |
| abstract_inverted_index.robot | 63, 140 |
| abstract_inverted_index.seven | 143 |
| abstract_inverted_index.where | 82 |
| abstract_inverted_index.Convex | 6 |
| abstract_inverted_index.blends | 18 |
| abstract_inverted_index.coarse | 113 |
| abstract_inverted_index.convex | 136 |
| abstract_inverted_index.faster | 48, 157 |
| abstract_inverted_index.higher | 148 |
| abstract_inverted_index.method | 146 |
| abstract_inverted_index.motion | 32, 60, 160 |
| abstract_inverted_index.orders | 154 |
| abstract_inverted_index.paper, | 55 |
| abstract_inverted_index.solved | 38 |
| abstract_inverted_index.static | 70 |
| abstract_inverted_index.target | 97 |
| abstract_inverted_index.Problem | 2 |
| abstract_inverted_index.between | 91 |
| abstract_inverted_index.compute | 111 |
| abstract_inverted_index.designs | 147 |
| abstract_inverted_index.initial | 95 |
| abstract_inverted_index.joints, | 144 |
| abstract_inverted_index.making. | 23 |
| abstract_inverted_index.online, | 122 |
| abstract_inverted_index.operate | 67 |
| abstract_inverted_index.optimal | 89 |
| abstract_inverted_index.quality | 149 |
| abstract_inverted_index.solving | 134 |
| abstract_inverted_index.stages. | 104 |
| abstract_inverted_index.swiftly | 68 |
| abstract_inverted_index.Offline, | 105 |
| abstract_inverted_index.consider | 73 |
| abstract_inverted_index.consists | 101 |
| abstract_inverted_index.decision | 22 |
| abstract_inverted_index.discrete | 19 |
| abstract_inverted_index.existing | 159 |
| abstract_inverted_index.feasible | 131 |
| abstract_inverted_index.generate | 130 |
| abstract_inverted_index.planning | 61 |
| abstract_inverted_index.problems | 26 |
| abstract_inverted_index.recently | 13 |
| abstract_inverted_index.relevant | 25 |
| abstract_inverted_index.runtimes | 49 |
| abstract_inverted_index.solution | 100 |
| abstract_inverted_index.yielding | 44 |
| abstract_inverted_index.developed | 14 |
| abstract_inverted_index.extension | 76 |
| abstract_inverted_index.framework | 16 |
| abstract_inverted_index.function. | 120 |
| abstract_inverted_index.magnitude | 156 |
| abstract_inverted_index.motivated | 58 |
| abstract_inverted_index.planners. | 161 |
| abstract_inverted_index.planning, | 33 |
| abstract_inverted_index.problem's | 118 |
| abstract_inverted_index.programs. | 137 |
| abstract_inverted_index.robotics, | 28 |
| abstract_inverted_index.solutions | 46 |
| abstract_inverted_index.continuous | 21 |
| abstract_inverted_index.cost-to-go | 119 |
| abstract_inverted_index.lower-cost | 45 |
| abstract_inverted_index.precompute | 88 |
| abstract_inverted_index.algorithms. | 52 |
| abstract_inverted_index.conditions. | 98 |
| abstract_inverted_index.efficiently | 87 |
| abstract_inverted_index.multi-query | 75 |
| abstract_inverted_index.programming | 109 |
| abstract_inverted_index.optimization | 15 |
| abstract_inverted_index.semidefinite | 108 |
| abstract_inverted_index.trajectories | 150 |
| abstract_inverted_index.Shortest-Path | 1 |
| abstract_inverted_index.environments. | 71 |
| abstract_inverted_index.incrementally | 129 |
| abstract_inverted_index.short-horizon | 135 |
| abstract_inverted_index.collision-free | 31 |
| abstract_inverted_index.state-of-the-art | 51 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 7 |
| citation_normalized_percentile |