Sequential parametrized motion planning and its complexity, II Article Swipe

PDF

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

This is a continuation of our recent paper in which we developed the theory of sequential parametrized motion planning. A sequential parametrized motion planning algorithm produced a motion of the system which is required to visit a prescribed sequence of states, in a certain order, at specified moments of time. In the previous publication we analysed the sequential parametrized topological complexity of the Fadell - Neuwirth fibration which in relevant to the problem of moving multiple robots avoiding collisions with other robots and with obstacles in the Euclidean space. Besides, in the preceeding paper we found the sequential parametrised topological complexity of the Fadell - Neuwirth bundle for the case of the Euclidean space $\Bbb R^d$ of odd dimension as well as the case $d=2$. In the present paper we give the complete answer for an arbitrary $d\ge 2$ even. Moreover, we present an explicit motion planning algorithm for controlling multiple robots in $\Bbb R^d$ having the minimal possible topological complexity; this algorithm is applicable to any number $n$ of robots and any number $m\ge 2$ of obstacles.

Related Topics

Artificial Intelligence

Geometry

Homotopy

Biology

Concepts

Motion planning Motion (physics) Topological complexity Robot Dimension (graph theory) Mathematics Euclidean geometry Sequence (biology) Euclidean space Topology (electrical circuits) Fibration Space (punctuation) Algorithm Computer science Combinatorics Pure mathematics Artificial intelligence Geometry Homotopy Operating system Biology Genetics

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Sequential parametrized motion planning and its complexity, II

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-12-02

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

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

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

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

Direct OA link when available
Concepts: Motion planning, Motion (physics), Topological complexity, Robot, Dimension (graph theory), Mathematics, Euclidean geometry, Sequence (biology), Euclidean space, Topology (electrical circuits), Fibration, Space (punctuation), Algorithm, Computer science, Combinatorics, Pure mathematics, Artificial intelligence, Geometry, Homotopy, Operating system, Biology, 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/W4310745425
doi	https://doi.org/10.48550/arxiv.2212.01091
ids.doi	https://doi.org/10.48550/arxiv.2212.01091
ids.openalex	https://openalex.org/W4310745425
fwci
type	preprint
title	Sequential parametrized motion planning and its complexity, II
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/T12536
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9848999977111816
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Topological and Geometric Data Analysis
topics[1].id	https://openalex.org/T12002
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9767000079154968
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Computability, Logic, AI Algorithms
topics[2].id	https://openalex.org/T10996
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9751999974250793
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1704
topics[2].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[2].display_name	Computational Geometry and Mesh Generation
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/C81074085
concepts[0].level	3
concepts[0].score	0.631783127784729
concepts[0].wikidata	https://www.wikidata.org/wiki/Q366872
concepts[0].display_name	Motion planning
concepts[1].id	https://openalex.org/C104114177
concepts[1].level	2
concepts[1].score	0.6118212342262268
concepts[1].wikidata	https://www.wikidata.org/wiki/Q79782
concepts[1].display_name	Motion (physics)
concepts[2].id	https://openalex.org/C2778478883
concepts[2].level	2
concepts[2].score	0.5853078961372375
concepts[2].wikidata	https://www.wikidata.org/wiki/Q7825025
concepts[2].display_name	Topological complexity
concepts[3].id	https://openalex.org/C90509273
concepts[3].level	2
concepts[3].score	0.5695384740829468
concepts[3].wikidata	https://www.wikidata.org/wiki/Q11012
concepts[3].display_name	Robot
concepts[4].id	https://openalex.org/C33676613
concepts[4].level	2
concepts[4].score	0.5600832104682922
concepts[4].wikidata	https://www.wikidata.org/wiki/Q13415176
concepts[4].display_name	Dimension (graph theory)
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.529551088809967
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C129782007
concepts[6].level	2
concepts[6].score	0.5271420478820801
concepts[6].wikidata	https://www.wikidata.org/wiki/Q162886
concepts[6].display_name	Euclidean geometry
concepts[7].id	https://openalex.org/C2778112365
concepts[7].level	2
concepts[7].score	0.5154793858528137
concepts[7].wikidata	https://www.wikidata.org/wiki/Q3511065
concepts[7].display_name	Sequence (biology)
concepts[8].id	https://openalex.org/C186450821
concepts[8].level	2
concepts[8].score	0.5142728686332703
concepts[8].wikidata	https://www.wikidata.org/wiki/Q17295
concepts[8].display_name	Euclidean space
concepts[9].id	https://openalex.org/C184720557
concepts[9].level	2
concepts[9].score	0.4964311718940735
concepts[9].wikidata	https://www.wikidata.org/wiki/Q7825049
concepts[9].display_name	Topology (electrical circuits)
concepts[10].id	https://openalex.org/C54486226
concepts[10].level	3
concepts[10].score	0.4458414912223816
concepts[10].wikidata	https://www.wikidata.org/wiki/Q493941
concepts[10].display_name	Fibration
concepts[11].id	https://openalex.org/C2778572836
concepts[11].level	2
concepts[11].score	0.4325862526893616
concepts[11].wikidata	https://www.wikidata.org/wiki/Q380933
concepts[11].display_name	Space (punctuation)
concepts[12].id	https://openalex.org/C11413529
concepts[12].level	1
concepts[12].score	0.4208299219608307
concepts[12].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[12].display_name	Algorithm
concepts[13].id	https://openalex.org/C41008148
concepts[13].level	0
concepts[13].score	0.3864986300468445
concepts[13].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[13].display_name	Computer science
concepts[14].id	https://openalex.org/C114614502
concepts[14].level	1
concepts[14].score	0.26555541157722473
concepts[14].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[14].display_name	Combinatorics
concepts[15].id	https://openalex.org/C202444582
concepts[15].level	1
concepts[15].score	0.23982682824134827
concepts[15].wikidata	https://www.wikidata.org/wiki/Q837863
concepts[15].display_name	Pure mathematics
concepts[16].id	https://openalex.org/C154945302
concepts[16].level	1
concepts[16].score	0.23786798119544983
concepts[16].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[16].display_name	Artificial intelligence
concepts[17].id	https://openalex.org/C2524010
concepts[17].level	1
concepts[17].score	0.12473505735397339
concepts[17].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[17].display_name	Geometry
concepts[18].id	https://openalex.org/C5961521
concepts[18].level	2
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q746083
concepts[18].display_name	Homotopy
concepts[19].id	https://openalex.org/C111919701
concepts[19].level	1
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q9135
concepts[19].display_name	Operating system
concepts[20].id	https://openalex.org/C86803240
concepts[20].level	0
concepts[20].score	0.0
concepts[20].wikidata	https://www.wikidata.org/wiki/Q420
concepts[20].display_name	Biology
concepts[21].id	https://openalex.org/C54355233
concepts[21].level	1
concepts[21].score	0.0
concepts[21].wikidata	https://www.wikidata.org/wiki/Q7162
concepts[21].display_name	Genetics
keywords[0].id	https://openalex.org/keywords/motion-planning
keywords[0].score	0.631783127784729
keywords[0].display_name	Motion planning
keywords[1].id	https://openalex.org/keywords/motion
keywords[1].score	0.6118212342262268
keywords[1].display_name	Motion (physics)
keywords[2].id	https://openalex.org/keywords/topological-complexity
keywords[2].score	0.5853078961372375
keywords[2].display_name	Topological complexity
keywords[3].id	https://openalex.org/keywords/robot
keywords[3].score	0.5695384740829468
keywords[3].display_name	Robot
keywords[4].id	https://openalex.org/keywords/dimension
keywords[4].score	0.5600832104682922
keywords[4].display_name	Dimension (graph theory)
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.529551088809967
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/euclidean-geometry
keywords[6].score	0.5271420478820801
keywords[6].display_name	Euclidean geometry
keywords[7].id	https://openalex.org/keywords/sequence
keywords[7].score	0.5154793858528137
keywords[7].display_name	Sequence (biology)
keywords[8].id	https://openalex.org/keywords/euclidean-space
keywords[8].score	0.5142728686332703
keywords[8].display_name	Euclidean space
keywords[9].id	https://openalex.org/keywords/topology
keywords[9].score	0.4964311718940735
keywords[9].display_name	Topology (electrical circuits)
keywords[10].id	https://openalex.org/keywords/fibration
keywords[10].score	0.4458414912223816
keywords[10].display_name	Fibration
keywords[11].id	https://openalex.org/keywords/space
keywords[11].score	0.4325862526893616
keywords[11].display_name	Space (punctuation)
keywords[12].id	https://openalex.org/keywords/algorithm
keywords[12].score	0.4208299219608307
keywords[12].display_name	Algorithm
keywords[13].id	https://openalex.org/keywords/computer-science
keywords[13].score	0.3864986300468445
keywords[13].display_name	Computer science
keywords[14].id	https://openalex.org/keywords/combinatorics
keywords[14].score	0.26555541157722473
keywords[14].display_name	Combinatorics
keywords[15].id	https://openalex.org/keywords/pure-mathematics
keywords[15].score	0.23982682824134827
keywords[15].display_name	Pure mathematics
keywords[16].id	https://openalex.org/keywords/artificial-intelligence
keywords[16].score	0.23786798119544983
keywords[16].display_name	Artificial intelligence
keywords[17].id	https://openalex.org/keywords/geometry
keywords[17].score	0.12473505735397339
keywords[17].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2212.01091
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/2212.01091
locations[0].version	submittedVersion
locations[0].raw_type
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/2212.01091
locations[1].id	doi:10.48550/arxiv.2212.01091
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.2212.01091
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/2212.01091
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, II
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12536
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9848999977111816
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Topological and Geometric Data Analysis
related_works	https://openalex.org/W2610298398, https://openalex.org/W4281992692, https://openalex.org/W2145396827, https://openalex.org/W2279239548, https://openalex.org/W4294294347, https://openalex.org/W63976795, https://openalex.org/W2404658402, https://openalex.org/W164473625, https://openalex.org/W2105228010, https://openalex.org/W122023996
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2212.01091
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/2212.01091
best_oa_location.version	submittedVersion
best_oa_location.raw_type
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/2212.01091
primary_location.id	pmh:oai:arXiv.org:2212.01091
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/2212.01091
primary_location.version	submittedVersion
primary_location.raw_type
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/2212.01091
publication_date	2022-12-02
publication_year	2022
referenced_works_count	0
abstract_inverted_index.-	64, 104
abstract_inverted_index.A	19
abstract_inverted_index.a	2, 26, 36, 42
abstract_inverted_index.2$	138, 175
abstract_inverted_index.In	50, 125
abstract_inverted_index.an	135, 143
abstract_inverted_index.as	119, 121
abstract_inverted_index.at	45
abstract_inverted_index.in	8, 41, 68, 85, 90, 152
abstract_inverted_index.is	1, 32, 163
abstract_inverted_index.of	4, 14, 28, 39, 48, 61, 73, 101, 110, 116, 169, 176
abstract_inverted_index.to	34, 70, 165
abstract_inverted_index.we	10, 54, 94, 129, 141
abstract_inverted_index.$n$	168
abstract_inverted_index.and	82, 171
abstract_inverted_index.any	166, 172
abstract_inverted_index.for	107, 134, 148
abstract_inverted_index.odd	117
abstract_inverted_index.our	5
abstract_inverted_index.the	12, 29, 51, 56, 62, 71, 86, 91, 96, 102, 108, 111, 122, 126, 131, 156
abstract_inverted_index.R^d$	115, 154
abstract_inverted_index.This	0
abstract_inverted_index.case	109, 123
abstract_inverted_index.give	130
abstract_inverted_index.this	161
abstract_inverted_index.well	120
abstract_inverted_index.with	79, 83
abstract_inverted_index.$\Bbb	114, 153
abstract_inverted_index.$d\ge	137
abstract_inverted_index.$m\ge	174
abstract_inverted_index.even.	139
abstract_inverted_index.found	95
abstract_inverted_index.other	80
abstract_inverted_index.paper	7, 93, 128
abstract_inverted_index.space	113
abstract_inverted_index.time.	49
abstract_inverted_index.visit	35
abstract_inverted_index.which	9, 31, 67
abstract_inverted_index.$d=2$.	124
abstract_inverted_index.Fadell	63, 103
abstract_inverted_index.answer	133
abstract_inverted_index.bundle	106
abstract_inverted_index.having	155
abstract_inverted_index.motion	17, 22, 27, 145
abstract_inverted_index.moving	74
abstract_inverted_index.number	167, 173
abstract_inverted_index.order,	44
abstract_inverted_index.recent	6
abstract_inverted_index.robots	76, 81, 151, 170
abstract_inverted_index.space.	88
abstract_inverted_index.system	30
abstract_inverted_index.theory	13
abstract_inverted_index.certain	43
abstract_inverted_index.minimal	157
abstract_inverted_index.moments	47
abstract_inverted_index.present	127, 142
abstract_inverted_index.problem	72
abstract_inverted_index.states,	40
abstract_inverted_index.Besides,	89
abstract_inverted_index.Neuwirth	65, 105
abstract_inverted_index.analysed	55
abstract_inverted_index.avoiding	77
abstract_inverted_index.complete	132
abstract_inverted_index.explicit	144
abstract_inverted_index.multiple	75, 150
abstract_inverted_index.planning	23, 146
abstract_inverted_index.possible	158
abstract_inverted_index.previous	52
abstract_inverted_index.produced	25
abstract_inverted_index.relevant	69
abstract_inverted_index.required	33
abstract_inverted_index.sequence	38
abstract_inverted_index.Euclidean	87, 112
abstract_inverted_index.Moreover,	140
abstract_inverted_index.algorithm	24, 147, 162
abstract_inverted_index.arbitrary	136
abstract_inverted_index.developed	11
abstract_inverted_index.dimension	118
abstract_inverted_index.fibration	66
abstract_inverted_index.obstacles	84
abstract_inverted_index.planning.	18
abstract_inverted_index.specified	46
abstract_inverted_index.applicable	164
abstract_inverted_index.collisions	78
abstract_inverted_index.complexity	60, 100
abstract_inverted_index.obstacles.	177
abstract_inverted_index.preceeding	92
abstract_inverted_index.prescribed	37
abstract_inverted_index.sequential	15, 20, 57, 97
abstract_inverted_index.complexity;	160
abstract_inverted_index.controlling	149
abstract_inverted_index.publication	53
abstract_inverted_index.topological	59, 99, 159
abstract_inverted_index.continuation	3
abstract_inverted_index.parametrised	98
abstract_inverted_index.parametrized	16, 21, 58
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.7400000095367432
sustainable_development_goals[0].display_name	Sustainable cities and communities
citation_normalized_percentile