GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets Article Swipe
Shao Yuan Chew Chia
,
Rebecca H. Jiang
,
Bernhard Paus Graesdal
,
Leslie Pack Kaelbling
,
Russ Tedrake
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2407.08848
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2407.08848
We consider large-scale, implicit-search-based solutions to Shortest Path Problems on Graphs of Convex Sets (GCS). We propose GCS*, a forward heuristic search algorithm that generalizes A* search to the GCS setting, where a continuous-valued decision is made at each graph vertex, and constraints across graph edges couple these decisions, influencing costs and feasibility. Such mixed discrete-continuous planning is needed in many domains, including motion planning around obstacles and planning through contact. This setting provides a unique challenge for best-first search algorithms: the cost and feasibility of a path depend on continuous-valued points chosen along the entire path. We show that by pruning paths that are cost-dominated over their entire terminal vertex, GCS* can search efficiently while still guaranteeing cost-optimality and completeness. To find satisficing solutions quickly, we also present a complete but suboptimal variation, pruning instead reachability-dominated paths. We implement these checks using polyhedral-containment or sampling-based methods. The former implementation is complete and cost-optimal, while the latter is probabilistically complete and asymptotically cost-optimal and performs effectively even with minimal samples in practice. We demonstrate GCS* on planar pushing tasks where the combinatorial explosion of contact modes renders prior methods intractable and show it performs favorably compared to the state-of-the-art. Project website: https://shaoyuan.cc/research/gcs-star/
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2407.08848
- https://arxiv.org/pdf/2407.08848
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4400667645
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4400667645Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2407.08848Digital Object Identifier
- Title
-
GCS*: Forward Heuristic Search on Implicit Graphs of Convex SetsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-07-11Full publication date if available
- Authors
-
Shao Yuan Chew Chia, Rebecca H. Jiang, Bernhard Paus Graesdal, Leslie Pack Kaelbling, Russ TedrakeList of authors in order
- Landing page
-
https://arxiv.org/abs/2407.08848Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2407.08848Direct 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/2407.08848Direct OA link when available
- Concepts
-
Regular polygon, Heuristic, Computer science, Combinatorics, Mathematics, Mathematical optimization, 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/W4400667645 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2407.08848 |
| ids.doi | https://doi.org/10.48550/arxiv.2407.08848 |
| ids.openalex | https://openalex.org/W4400667645 |
| fwci | |
| type | preprint |
| title | GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10586 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9983000159263611 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Robotic Path Planning Algorithms |
| topics[1].id | https://openalex.org/T11596 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9884999990463257 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Constraint Satisfaction and Optimization |
| topics[2].id | https://openalex.org/T10567 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9872000217437744 |
| 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 | Vehicle Routing Optimization Methods |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C112680207 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7178211808204651 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[0].display_name | Regular polygon |
| concepts[1].id | https://openalex.org/C173801870 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6423012018203735 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q201413 |
| concepts[1].display_name | Heuristic |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.47151458263397217 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.37137818336486816 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.3577936291694641 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| concepts[5].id | https://openalex.org/C126255220 |
| concepts[5].level | 1 |
| concepts[5].score | 0.328712522983551 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[5].display_name | Mathematical optimization |
| concepts[6].id | https://openalex.org/C2524010 |
| concepts[6].level | 1 |
| concepts[6].score | 0.044180989265441895 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[6].display_name | Geometry |
| keywords[0].id | https://openalex.org/keywords/regular-polygon |
| keywords[0].score | 0.7178211808204651 |
| keywords[0].display_name | Regular polygon |
| keywords[1].id | https://openalex.org/keywords/heuristic |
| keywords[1].score | 0.6423012018203735 |
| keywords[1].display_name | Heuristic |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.47151458263397217 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.37137818336486816 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.3577936291694641 |
| keywords[4].display_name | Mathematics |
| keywords[5].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[5].score | 0.328712522983551 |
| keywords[5].display_name | Mathematical optimization |
| keywords[6].id | https://openalex.org/keywords/geometry |
| keywords[6].score | 0.044180989265441895 |
| keywords[6].display_name | Geometry |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2407.08848 |
| 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/2407.08848 |
| 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/2407.08848 |
| locations[1].id | doi:10.48550/arxiv.2407.08848 |
| 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 | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| 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.2407.08848 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5093957496 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Shao Yuan Chew Chia |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Chia, Shao Yuan Chew |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5114191877 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Rebecca H. Jiang |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Jiang, Rebecca H. |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5093957495 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Bernhard Paus Graesdal |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Graesdal, Bernhard Paus |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5012862284 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Leslie Pack Kaelbling |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Kaelbling, Leslie Pack |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5074291890 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Russ Tedrake |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Tedrake, Russ |
| authorships[4].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/2407.08848 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10586 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9983000159263611 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Robotic Path Planning Algorithms |
| related_works | 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, https://openalex.org/W2600246793, https://openalex.org/W4238204885 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2407.08848 |
| 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/2407.08848 |
| 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/2407.08848 |
| primary_location.id | pmh:oai:arXiv.org:2407.08848 |
| 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/2407.08848 |
| 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/2407.08848 |
| publication_date | 2024-07-11 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 18, 32, 74, 86, 129 |
| abstract_inverted_index.A* | 25 |
| abstract_inverted_index.To | 121 |
| abstract_inverted_index.We | 0, 15, 97, 138, 172 |
| abstract_inverted_index.at | 37 |
| abstract_inverted_index.by | 100 |
| abstract_inverted_index.in | 59, 170 |
| abstract_inverted_index.is | 35, 57, 150, 157 |
| abstract_inverted_index.it | 192 |
| abstract_inverted_index.of | 11, 85, 183 |
| abstract_inverted_index.on | 9, 89, 175 |
| abstract_inverted_index.or | 144 |
| abstract_inverted_index.to | 5, 27, 196 |
| abstract_inverted_index.we | 126 |
| abstract_inverted_index.GCS | 29 |
| abstract_inverted_index.The | 147 |
| abstract_inverted_index.and | 41, 51, 67, 83, 119, 152, 160, 163, 190 |
| abstract_inverted_index.are | 104 |
| abstract_inverted_index.but | 131 |
| abstract_inverted_index.can | 112 |
| abstract_inverted_index.for | 77 |
| abstract_inverted_index.the | 28, 81, 94, 155, 180, 197 |
| abstract_inverted_index.GCS* | 111, 174 |
| abstract_inverted_index.Path | 7 |
| abstract_inverted_index.Sets | 13 |
| abstract_inverted_index.Such | 53 |
| abstract_inverted_index.This | 71 |
| abstract_inverted_index.also | 127 |
| abstract_inverted_index.cost | 82 |
| abstract_inverted_index.each | 38 |
| abstract_inverted_index.even | 166 |
| abstract_inverted_index.find | 122 |
| abstract_inverted_index.made | 36 |
| abstract_inverted_index.many | 60 |
| abstract_inverted_index.over | 106 |
| abstract_inverted_index.path | 87 |
| abstract_inverted_index.show | 98, 191 |
| abstract_inverted_index.that | 23, 99, 103 |
| abstract_inverted_index.with | 167 |
| abstract_inverted_index.GCS*, | 17 |
| abstract_inverted_index.along | 93 |
| abstract_inverted_index.costs | 50 |
| abstract_inverted_index.edges | 45 |
| abstract_inverted_index.graph | 39, 44 |
| abstract_inverted_index.mixed | 54 |
| abstract_inverted_index.modes | 185 |
| abstract_inverted_index.path. | 96 |
| abstract_inverted_index.paths | 102 |
| abstract_inverted_index.prior | 187 |
| abstract_inverted_index.still | 116 |
| abstract_inverted_index.tasks | 178 |
| abstract_inverted_index.their | 107 |
| abstract_inverted_index.these | 47, 140 |
| abstract_inverted_index.using | 142 |
| abstract_inverted_index.where | 31, 179 |
| abstract_inverted_index.while | 115, 154 |
| abstract_inverted_index.(GCS). | 14 |
| abstract_inverted_index.Convex | 12 |
| abstract_inverted_index.Graphs | 10 |
| abstract_inverted_index.across | 43 |
| abstract_inverted_index.around | 65 |
| abstract_inverted_index.checks | 141 |
| abstract_inverted_index.chosen | 92 |
| abstract_inverted_index.couple | 46 |
| abstract_inverted_index.depend | 88 |
| abstract_inverted_index.entire | 95, 108 |
| abstract_inverted_index.former | 148 |
| abstract_inverted_index.latter | 156 |
| abstract_inverted_index.motion | 63 |
| abstract_inverted_index.needed | 58 |
| abstract_inverted_index.paths. | 137 |
| abstract_inverted_index.planar | 176 |
| abstract_inverted_index.points | 91 |
| abstract_inverted_index.search | 21, 26, 79, 113 |
| abstract_inverted_index.unique | 75 |
| abstract_inverted_index.Project | 199 |
| abstract_inverted_index.contact | 184 |
| abstract_inverted_index.forward | 19 |
| abstract_inverted_index.instead | 135 |
| abstract_inverted_index.methods | 188 |
| abstract_inverted_index.minimal | 168 |
| abstract_inverted_index.present | 128 |
| abstract_inverted_index.propose | 16 |
| abstract_inverted_index.pruning | 101, 134 |
| abstract_inverted_index.pushing | 177 |
| abstract_inverted_index.renders | 186 |
| abstract_inverted_index.samples | 169 |
| abstract_inverted_index.setting | 72 |
| abstract_inverted_index.through | 69 |
| abstract_inverted_index.vertex, | 40, 110 |
| abstract_inverted_index.Problems | 8 |
| abstract_inverted_index.Shortest | 6 |
| abstract_inverted_index.compared | 195 |
| abstract_inverted_index.complete | 130, 151, 159 |
| abstract_inverted_index.consider | 1 |
| abstract_inverted_index.contact. | 70 |
| abstract_inverted_index.decision | 34 |
| abstract_inverted_index.domains, | 61 |
| abstract_inverted_index.methods. | 146 |
| abstract_inverted_index.performs | 164, 193 |
| abstract_inverted_index.planning | 56, 64, 68 |
| abstract_inverted_index.provides | 73 |
| abstract_inverted_index.quickly, | 125 |
| abstract_inverted_index.setting, | 30 |
| abstract_inverted_index.terminal | 109 |
| abstract_inverted_index.website: | 200 |
| abstract_inverted_index.algorithm | 22 |
| abstract_inverted_index.challenge | 76 |
| abstract_inverted_index.explosion | 182 |
| abstract_inverted_index.favorably | 194 |
| abstract_inverted_index.heuristic | 20 |
| abstract_inverted_index.implement | 139 |
| abstract_inverted_index.including | 62 |
| abstract_inverted_index.obstacles | 66 |
| abstract_inverted_index.practice. | 171 |
| abstract_inverted_index.solutions | 4, 124 |
| abstract_inverted_index.best-first | 78 |
| abstract_inverted_index.decisions, | 48 |
| abstract_inverted_index.suboptimal | 132 |
| abstract_inverted_index.variation, | 133 |
| abstract_inverted_index.algorithms: | 80 |
| abstract_inverted_index.constraints | 42 |
| abstract_inverted_index.demonstrate | 173 |
| abstract_inverted_index.effectively | 165 |
| abstract_inverted_index.efficiently | 114 |
| abstract_inverted_index.feasibility | 84 |
| abstract_inverted_index.generalizes | 24 |
| abstract_inverted_index.influencing | 49 |
| abstract_inverted_index.intractable | 189 |
| abstract_inverted_index.satisficing | 123 |
| abstract_inverted_index.cost-optimal | 162 |
| abstract_inverted_index.feasibility. | 52 |
| abstract_inverted_index.guaranteeing | 117 |
| abstract_inverted_index.large-scale, | 2 |
| abstract_inverted_index.combinatorial | 181 |
| abstract_inverted_index.completeness. | 120 |
| abstract_inverted_index.cost-optimal, | 153 |
| abstract_inverted_index.asymptotically | 161 |
| abstract_inverted_index.cost-dominated | 105 |
| abstract_inverted_index.implementation | 149 |
| abstract_inverted_index.sampling-based | 145 |
| abstract_inverted_index.cost-optimality | 118 |
| abstract_inverted_index.continuous-valued | 33, 90 |
| abstract_inverted_index.probabilistically | 158 |
| abstract_inverted_index.state-of-the-art. | 198 |
| abstract_inverted_index.discrete-continuous | 55 |
| abstract_inverted_index.implicit-search-based | 3 |
| abstract_inverted_index.polyhedral-containment | 143 |
| abstract_inverted_index.reachability-dominated | 136 |
| abstract_inverted_index.https://shaoyuan.cc/research/gcs-star/ | 201 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |