Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets Article Swipe

PDF

Savva Morozov , Tobia Marcucci , Bernhard Paus Graesdal , Alexandre Amice , Pablo A. Parrilo , Russ Tedrake ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2507.10878

We study the Shortest-Walk Problem (SWP) in a Graph of Convex Sets (GCS). A GCS is a graph where each vertex is paired with a convex program, and each edge couples adjacent programs via additional costs and constraints. A walk in a GCS is a sequence of vertices connected by edges, where vertices may be repeated. The length of a walk is given by the cumulative optimal value of the corresponding convex programs. To solve the SWP in GCS, we first synthesize a piecewise-quadratic lower bound on the problem's cost-to-go function using semidefinite programming. Then we use this lower bound to guide an incremental-search algorithm that yields an approximate shortest walk. We show that the SWP in GCS is a natural language for many mixed discrete-continuous planning problems in robotics, unifying problems that typically require specialized solutions while delivering high performance and computational efficiency. We demonstrate this through experiments in collision-free motion planning, skill chaining, and optimal control of hybrid systems.

Related Topics

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2507.10878
PDF: https://arxiv.org/pdf/2507.10878
OA Status: green
OpenAlex ID: https://openalex.org/W4414943754

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4414943754

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2507.10878

Digital Object Identifier
Title: Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-07-15

Full publication date if available
Authors: Savva Morozov, Tobia Marcucci, Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo, Russ Tedrake

List of authors in order
Landing page: https://arxiv.org/abs/2507.10878

Publisher landing page
PDF URL: https://arxiv.org/pdf/2507.10878

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2507.10878

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4414943754
doi	https://doi.org/10.48550/arxiv.2507.10878
ids.doi	https://doi.org/10.48550/arxiv.2507.10878
ids.openalex	https://openalex.org/W4414943754
fwci
type	preprint
title	Mixed Discrete and Continuous Planning using Shortest Walks in 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.9836000204086304
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/T10906
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.941100001335144
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	AI-based Problem Solving and Planning
topics[2].id	https://openalex.org/T10142
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9402999877929688
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Formal Methods in Verification
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2507.10878
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/2507.10878
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/2507.10878
locations[1].id	doi:10.48550/arxiv.2507.10878
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.2507.10878
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/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/A5007798248
authorships[3].author.orcid	https://orcid.org/0000-0002-3955-9560
authorships[3].author.display_name	Alexandre Amice
authorships[3].author_position	middle
authorships[3].raw_author_name	Amice, Alexandre
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5031935416
authorships[4].author.orcid	https://orcid.org/0000-0003-1132-8477
authorships[4].author.display_name	Pablo A. Parrilo
authorships[4].author_position	middle
authorships[4].raw_author_name	Parrilo, Pablo A.
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5074291890
authorships[5].author.orcid
authorships[5].author.display_name	Russ Tedrake
authorships[5].author_position	last
authorships[5].raw_author_name	Tedrake, Russ
authorships[5].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/2507.10878
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Mixed Discrete and Continuous Planning using Shortest Walks 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/T10586
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9836000204086304
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
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2507.10878
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/2507.10878
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/2507.10878
primary_location.id	pmh:oai:arXiv.org:2507.10878
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/2507.10878
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/2507.10878
publication_date	2025-07-15
publication_year	2025
referenced_works_count	0
abstract_inverted_index.A	13, 38
abstract_inverted_index.a	7, 16, 24, 41, 44, 59, 82, 119
abstract_inverted_index.To	73
abstract_inverted_index.We	0, 111, 144
abstract_inverted_index.an	102, 107
abstract_inverted_index.be	54
abstract_inverted_index.by	49, 63
abstract_inverted_index.in	6, 40, 77, 116, 128, 149
abstract_inverted_index.is	15, 21, 43, 61, 118
abstract_inverted_index.of	9, 46, 58, 68, 158
abstract_inverted_index.on	86
abstract_inverted_index.to	100
abstract_inverted_index.we	79, 95
abstract_inverted_index.GCS	14, 42, 117
abstract_inverted_index.SWP	76, 115
abstract_inverted_index.The	56
abstract_inverted_index.and	27, 36, 141, 155
abstract_inverted_index.for	122
abstract_inverted_index.may	53
abstract_inverted_index.the	2, 64, 69, 75, 87, 114
abstract_inverted_index.use	96
abstract_inverted_index.via	33
abstract_inverted_index.GCS,	78
abstract_inverted_index.Sets	11
abstract_inverted_index.Then	94
abstract_inverted_index.each	19, 28
abstract_inverted_index.edge	29
abstract_inverted_index.high	139
abstract_inverted_index.many	123
abstract_inverted_index.show	112
abstract_inverted_index.that	105, 113, 132
abstract_inverted_index.this	97, 146
abstract_inverted_index.walk	39, 60
abstract_inverted_index.with	23
abstract_inverted_index.(SWP)	5
abstract_inverted_index.Graph	8
abstract_inverted_index.bound	85, 99
abstract_inverted_index.costs	35
abstract_inverted_index.first	80
abstract_inverted_index.given	62
abstract_inverted_index.graph	17
abstract_inverted_index.guide	101
abstract_inverted_index.lower	84, 98
abstract_inverted_index.mixed	124
abstract_inverted_index.skill	153
abstract_inverted_index.solve	74
abstract_inverted_index.study	1
abstract_inverted_index.using	91
abstract_inverted_index.value	67
abstract_inverted_index.walk.	110
abstract_inverted_index.where	18, 51
abstract_inverted_index.while	137
abstract_inverted_index.(GCS).	12
abstract_inverted_index.Convex	10
abstract_inverted_index.convex	25, 71
abstract_inverted_index.edges,	50
abstract_inverted_index.hybrid	159
abstract_inverted_index.length	57
abstract_inverted_index.motion	151
abstract_inverted_index.paired	22
abstract_inverted_index.vertex	20
abstract_inverted_index.yields	106
abstract_inverted_index.Problem	4
abstract_inverted_index.control	157
abstract_inverted_index.couples	30
abstract_inverted_index.natural	120
abstract_inverted_index.optimal	66, 156
abstract_inverted_index.require	134
abstract_inverted_index.through	147
abstract_inverted_index.adjacent	31
abstract_inverted_index.function	90
abstract_inverted_index.language	121
abstract_inverted_index.planning	126
abstract_inverted_index.problems	127, 131
abstract_inverted_index.program,	26
abstract_inverted_index.programs	32
abstract_inverted_index.sequence	45
abstract_inverted_index.shortest	109
abstract_inverted_index.systems.	160
abstract_inverted_index.unifying	130
abstract_inverted_index.vertices	47, 52
abstract_inverted_index.algorithm	104
abstract_inverted_index.chaining,	154
abstract_inverted_index.connected	48
abstract_inverted_index.planning,	152
abstract_inverted_index.problem's	88
abstract_inverted_index.programs.	72
abstract_inverted_index.repeated.	55
abstract_inverted_index.robotics,	129
abstract_inverted_index.solutions	136
abstract_inverted_index.typically	133
abstract_inverted_index.additional	34
abstract_inverted_index.cost-to-go	89
abstract_inverted_index.cumulative	65
abstract_inverted_index.delivering	138
abstract_inverted_index.synthesize	81
abstract_inverted_index.approximate	108
abstract_inverted_index.demonstrate	145
abstract_inverted_index.efficiency.	143
abstract_inverted_index.experiments	148
abstract_inverted_index.performance	140
abstract_inverted_index.specialized	135
abstract_inverted_index.constraints.	37
abstract_inverted_index.programming.	93
abstract_inverted_index.semidefinite	92
abstract_inverted_index.Shortest-Walk	3
abstract_inverted_index.computational	142
abstract_inverted_index.corresponding	70
abstract_inverted_index.collision-free	150
abstract_inverted_index.incremental-search	103
abstract_inverted_index.discrete-continuous	125
abstract_inverted_index.piecewise-quadratic	83
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	6
citation_normalized_percentile