Sequential Parametrized Motion Planning and its Complexity Article Swipe

PDF

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2205.08453

In this paper we develop theory of sequential parametrized motion planning which generalises the approach of parametrized motion planning, which was introduced recently in [3]. A sequential parametrized motion planning algorithm produced a motion of the system which is required to visit a prescribed sequence of states, in certain order, at specified moments of time. The sequential parametrized algorithms are universal as the external conditions are not fixed in advance but rather constitute part of the input of the algorithm. The second part of this article consists of a detailed analysis of the sequential parametrized topological complexity of the Fadell - Neuwirth fibration. In the language of robotics, sections of the Fadell - Neuwitrh fibration are algorithms for moving multiple robots avoiding collisions with other robots and with obstacles in Euclidean space. In the last section of the paper we introduce the new notion of TC-generating function of a fibration, examine examples and raise some general questions about its analytic properties.

Related Topics

Artificial Intelligence

Concepts

Fibration Motion (physics) Motion planning Euclidean geometry Robotics Robot Sequence (biology) Function (biology) Computer science Algorithm Euclidean space Mathematics Artificial intelligence Topology (electrical circuits) Pure mathematics Geometry Combinatorics Evolutionary biology Biology Homotopy Genetics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2205.08453
PDF: https://arxiv.org/pdf/2205.08453
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4280508567

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Sequential Parametrized Motion Planning and its Complexity

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-05-17

Full publication date if available
Authors: Michael Färber, Amit Kumar Paul

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

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

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/2205.08453

Direct OA link when available
Concepts: Fibration, Motion (physics), Motion planning, Euclidean geometry, Robotics, Robot, Sequence (biology), Function (biology), Computer science, Algorithm, Euclidean space, Mathematics, Artificial intelligence, Topology (electrical circuits), Pure mathematics, Geometry, Combinatorics, Evolutionary biology, Biology, Homotopy, Genetics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4280508567
doi	https://doi.org/10.48550/arxiv.2205.08453
ids.doi	https://doi.org/10.48550/arxiv.2205.08453
ids.openalex	https://openalex.org/W4280508567
fwci
type	preprint
title	Sequential Parametrized Motion Planning and its Complexity
awards[0].id	https://openalex.org/G7605593694
awards[0].funder_id	https://openalex.org/F4320334627
awards[0].display_name
awards[0].funder_award_id	EP/V009877/1
awards[0].funder_display_name	Engineering and Physical Sciences Research Council
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.9433000087738037
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/T12170
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9376000165939331
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2614
topics[1].subfield.display_name	Theoretical Computer Science
topics[1].display_name	History and Theory of Mathematics
topics[2].id	https://openalex.org/T12002
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9211999773979187
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	Computability, Logic, AI Algorithms
funders[0].id	https://openalex.org/F4320334627
funders[0].ror	https://ror.org/0439y7842
funders[0].display_name	Engineering and Physical Sciences Research Council
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C54486226
concepts[0].level	3
concepts[0].score	0.6880512237548828
concepts[0].wikidata	https://www.wikidata.org/wiki/Q493941
concepts[0].display_name	Fibration
concepts[1].id	https://openalex.org/C104114177
concepts[1].level	2
concepts[1].score	0.6588090658187866
concepts[1].wikidata	https://www.wikidata.org/wiki/Q79782
concepts[1].display_name	Motion (physics)
concepts[2].id	https://openalex.org/C81074085
concepts[2].level	3
concepts[2].score	0.6280345320701599
concepts[2].wikidata	https://www.wikidata.org/wiki/Q366872
concepts[2].display_name	Motion planning
concepts[3].id	https://openalex.org/C129782007
concepts[3].level	2
concepts[3].score	0.5267609357833862
concepts[3].wikidata	https://www.wikidata.org/wiki/Q162886
concepts[3].display_name	Euclidean geometry
concepts[4].id	https://openalex.org/C34413123
concepts[4].level	3
concepts[4].score	0.5236004590988159
concepts[4].wikidata	https://www.wikidata.org/wiki/Q170978
concepts[4].display_name	Robotics
concepts[5].id	https://openalex.org/C90509273
concepts[5].level	2
concepts[5].score	0.5216639041900635
concepts[5].wikidata	https://www.wikidata.org/wiki/Q11012
concepts[5].display_name	Robot
concepts[6].id	https://openalex.org/C2778112365
concepts[6].level	2
concepts[6].score	0.5140658617019653
concepts[6].wikidata	https://www.wikidata.org/wiki/Q3511065
concepts[6].display_name	Sequence (biology)
concepts[7].id	https://openalex.org/C14036430
concepts[7].level	2
concepts[7].score	0.5043092966079712
concepts[7].wikidata	https://www.wikidata.org/wiki/Q3736076
concepts[7].display_name	Function (biology)
concepts[8].id	https://openalex.org/C41008148
concepts[8].level	0
concepts[8].score	0.4740554988384247
concepts[8].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[8].display_name	Computer science
concepts[9].id	https://openalex.org/C11413529
concepts[9].level	1
concepts[9].score	0.4595905542373657
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[9].display_name	Algorithm
concepts[10].id	https://openalex.org/C186450821
concepts[10].level	2
concepts[10].score	0.44687986373901367
concepts[10].wikidata	https://www.wikidata.org/wiki/Q17295
concepts[10].display_name	Euclidean space
concepts[11].id	https://openalex.org/C33923547
concepts[11].level	0
concepts[11].score	0.42909082770347595
concepts[11].wikidata	https://www.wikidata.org/wiki/Q395
concepts[11].display_name	Mathematics
concepts[12].id	https://openalex.org/C154945302
concepts[12].level	1
concepts[12].score	0.4104987382888794
concepts[12].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[12].display_name	Artificial intelligence
concepts[13].id	https://openalex.org/C184720557
concepts[13].level	2
concepts[13].score	0.33961671590805054
concepts[13].wikidata	https://www.wikidata.org/wiki/Q7825049
concepts[13].display_name	Topology (electrical circuits)
concepts[14].id	https://openalex.org/C202444582
concepts[14].level	1
concepts[14].score	0.1373637318611145
concepts[14].wikidata	https://www.wikidata.org/wiki/Q837863
concepts[14].display_name	Pure mathematics
concepts[15].id	https://openalex.org/C2524010
concepts[15].level	1
concepts[15].score	0.11552715301513672
concepts[15].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[15].display_name	Geometry
concepts[16].id	https://openalex.org/C114614502
concepts[16].level	1
concepts[16].score	0.09744548797607422
concepts[16].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[16].display_name	Combinatorics
concepts[17].id	https://openalex.org/C78458016
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q840400
concepts[17].display_name	Evolutionary biology
concepts[18].id	https://openalex.org/C86803240
concepts[18].level	0
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q420
concepts[18].display_name	Biology
concepts[19].id	https://openalex.org/C5961521
concepts[19].level	2
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q746083
concepts[19].display_name	Homotopy
concepts[20].id	https://openalex.org/C54355233
concepts[20].level	1
concepts[20].score	0.0
concepts[20].wikidata	https://www.wikidata.org/wiki/Q7162
concepts[20].display_name	Genetics
keywords[0].id	https://openalex.org/keywords/fibration
keywords[0].score	0.6880512237548828
keywords[0].display_name	Fibration
keywords[1].id	https://openalex.org/keywords/motion
keywords[1].score	0.6588090658187866
keywords[1].display_name	Motion (physics)
keywords[2].id	https://openalex.org/keywords/motion-planning
keywords[2].score	0.6280345320701599
keywords[2].display_name	Motion planning
keywords[3].id	https://openalex.org/keywords/euclidean-geometry
keywords[3].score	0.5267609357833862
keywords[3].display_name	Euclidean geometry
keywords[4].id	https://openalex.org/keywords/robotics
keywords[4].score	0.5236004590988159
keywords[4].display_name	Robotics
keywords[5].id	https://openalex.org/keywords/robot
keywords[5].score	0.5216639041900635
keywords[5].display_name	Robot
keywords[6].id	https://openalex.org/keywords/sequence
keywords[6].score	0.5140658617019653
keywords[6].display_name	Sequence (biology)
keywords[7].id	https://openalex.org/keywords/function
keywords[7].score	0.5043092966079712
keywords[7].display_name	Function (biology)
keywords[8].id	https://openalex.org/keywords/computer-science
keywords[8].score	0.4740554988384247
keywords[8].display_name	Computer science
keywords[9].id	https://openalex.org/keywords/algorithm
keywords[9].score	0.4595905542373657
keywords[9].display_name	Algorithm
keywords[10].id	https://openalex.org/keywords/euclidean-space
keywords[10].score	0.44687986373901367
keywords[10].display_name	Euclidean space
keywords[11].id	https://openalex.org/keywords/mathematics
keywords[11].score	0.42909082770347595
keywords[11].display_name	Mathematics
keywords[12].id	https://openalex.org/keywords/artificial-intelligence
keywords[12].score	0.4104987382888794
keywords[12].display_name	Artificial intelligence
keywords[13].id	https://openalex.org/keywords/topology
keywords[13].score	0.33961671590805054
keywords[13].display_name	Topology (electrical circuits)
keywords[14].id	https://openalex.org/keywords/pure-mathematics
keywords[14].score	0.1373637318611145
keywords[14].display_name	Pure mathematics
keywords[15].id	https://openalex.org/keywords/geometry
keywords[15].score	0.11552715301513672
keywords[15].display_name	Geometry
keywords[16].id	https://openalex.org/keywords/combinatorics
keywords[16].score	0.09744548797607422
keywords[16].display_name	Combinatorics
language	en
locations[0].id	pmh:oai:arXiv.org:2205.08453
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/2205.08453
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/2205.08453
locations[1].id	doi:10.48550/arxiv.2205.08453
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.2205.08453
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5036975533
authorships[0].author.orcid	https://orcid.org/0000-0003-1419-4347
authorships[0].author.display_name	Michael Färber
authorships[0].author_position	first
authorships[0].raw_author_name	Farber, Michael
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5076241964
authorships[1].author.orcid	https://orcid.org/0000-0001-7074-1232
authorships[1].author.display_name	Amit Kumar Paul
authorships[1].author_position	last
authorships[1].raw_author_name	Paul, Amit Kumar
authorships[1].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/2205.08453
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Sequential Parametrized Motion Planning and its Complexity
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.9433000087738037
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/W2145396827, https://openalex.org/W2279239548, https://openalex.org/W115379796, https://openalex.org/W4294294347, https://openalex.org/W63976795, https://openalex.org/W2404658402, https://openalex.org/W2610298398, https://openalex.org/W4281992692, https://openalex.org/W164473625, https://openalex.org/W2105228010
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2205.08453
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/2205.08453
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/2205.08453
primary_location.id	pmh:oai:arXiv.org:2205.08453
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/2205.08453
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/2205.08453
publication_date	2022-05-17
publication_year	2022
referenced_works_count	0
abstract_inverted_index.-	100, 112
abstract_inverted_index.A	25
abstract_inverted_index.a	32, 42, 88, 148
abstract_inverted_index.In	0, 103, 132
abstract_inverted_index.as	61
abstract_inverted_index.at	50
abstract_inverted_index.in	23, 47, 68, 129
abstract_inverted_index.is	38
abstract_inverted_index.of	6, 15, 34, 45, 53, 74, 77, 83, 87, 91, 97, 106, 109, 136, 144, 147
abstract_inverted_index.to	40
abstract_inverted_index.we	3, 139
abstract_inverted_index.The	55, 80
abstract_inverted_index.and	126, 152
abstract_inverted_index.are	59, 65, 115
abstract_inverted_index.but	70
abstract_inverted_index.for	117
abstract_inverted_index.its	158
abstract_inverted_index.new	142
abstract_inverted_index.not	66
abstract_inverted_index.the	13, 35, 62, 75, 78, 92, 98, 104, 110, 133, 137, 141
abstract_inverted_index.was	20
abstract_inverted_index.[3].	24
abstract_inverted_index.last	134
abstract_inverted_index.part	73, 82
abstract_inverted_index.some	154
abstract_inverted_index.this	1, 84
abstract_inverted_index.with	123, 127
abstract_inverted_index.about	157
abstract_inverted_index.fixed	67
abstract_inverted_index.input	76
abstract_inverted_index.other	124
abstract_inverted_index.paper	2, 138
abstract_inverted_index.raise	153
abstract_inverted_index.time.	54
abstract_inverted_index.visit	41
abstract_inverted_index.which	11, 19, 37
abstract_inverted_index.Fadell	99, 111
abstract_inverted_index.motion	9, 17, 28, 33
abstract_inverted_index.moving	118
abstract_inverted_index.notion	143
abstract_inverted_index.order,	49
abstract_inverted_index.rather	71
abstract_inverted_index.robots	120, 125
abstract_inverted_index.second	81
abstract_inverted_index.space.	131
abstract_inverted_index.system	36
abstract_inverted_index.theory	5
abstract_inverted_index.advance	69
abstract_inverted_index.article	85
abstract_inverted_index.certain	48
abstract_inverted_index.develop	4
abstract_inverted_index.examine	150
abstract_inverted_index.general	155
abstract_inverted_index.moments	52
abstract_inverted_index.section	135
abstract_inverted_index.states,	46
abstract_inverted_index.Neuwirth	101
abstract_inverted_index.Neuwitrh	113
abstract_inverted_index.analysis	90
abstract_inverted_index.analytic	159
abstract_inverted_index.approach	14
abstract_inverted_index.avoiding	121
abstract_inverted_index.consists	86
abstract_inverted_index.detailed	89
abstract_inverted_index.examples	151
abstract_inverted_index.external	63
abstract_inverted_index.function	146
abstract_inverted_index.language	105
abstract_inverted_index.multiple	119
abstract_inverted_index.planning	10, 29
abstract_inverted_index.produced	31
abstract_inverted_index.recently	22
abstract_inverted_index.required	39
abstract_inverted_index.sections	108
abstract_inverted_index.sequence	44
abstract_inverted_index.Euclidean	130
abstract_inverted_index.algorithm	30
abstract_inverted_index.fibration	114
abstract_inverted_index.introduce	140
abstract_inverted_index.obstacles	128
abstract_inverted_index.planning,	18
abstract_inverted_index.questions	156
abstract_inverted_index.robotics,	107
abstract_inverted_index.specified	51
abstract_inverted_index.universal	60
abstract_inverted_index.algorithm.	79
abstract_inverted_index.algorithms	58, 116
abstract_inverted_index.collisions	122
abstract_inverted_index.complexity	96
abstract_inverted_index.conditions	64
abstract_inverted_index.constitute	72
abstract_inverted_index.fibration,	149
abstract_inverted_index.fibration.	102
abstract_inverted_index.introduced	21
abstract_inverted_index.prescribed	43
abstract_inverted_index.sequential	7, 26, 56, 93
abstract_inverted_index.generalises	12
abstract_inverted_index.properties.	160
abstract_inverted_index.topological	95
abstract_inverted_index.parametrized	8, 16, 27, 57, 94
abstract_inverted_index.TC-generating	145
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
sustainable_development_goals[0].id	https://metadata.un.org/sdg/11
sustainable_development_goals[0].score	0.8199999928474426
sustainable_development_goals[0].display_name	Sustainable cities and communities
citation_normalized_percentile