TY - JOUR
T1 - A randomized greedy algorithm for piecewise linear motion planning
AU - Ortiz, Carlos
AU - Lara, Adriana
AU - González, Jesús
AU - Borat, Ayse
N1 - Publisher Copyright:
© 2021 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2021/10/1
Y1 - 2021/10/1
N2 - We describe and implement a randomized algorithm that inputs a polyhedron, thought of as the space of states of some automated guided vehicle R, and outputs an explicit system of piecewise linear motion planners for R. The algorithm is designed in such a way that the cardinality of the output is probabilistically close (with parameters chosen by the user) to the minimal possible cardinality.This yields the first automated solution for robust-to-noise robot motion planning in terms of simplicial complexity (SC) techniques, a discretization of Farber’s topological complexity TC. Besides its relevance toward technological applications, our work reveals that, unlike other discrete approaches to TC, the SC model can recast Farber’s invariant without having to introduce costly subdivisions. We develop and implement our algorithm by actually discretizing Macías-Virgós and Mosquera-Lois’ notion of homotopic distance, thus encompassing computer estimations of other sectional category invariants as well, such as the Lusternik-Schnirelmann category of polyhedra.
AB - We describe and implement a randomized algorithm that inputs a polyhedron, thought of as the space of states of some automated guided vehicle R, and outputs an explicit system of piecewise linear motion planners for R. The algorithm is designed in such a way that the cardinality of the output is probabilistically close (with parameters chosen by the user) to the minimal possible cardinality.This yields the first automated solution for robust-to-noise robot motion planning in terms of simplicial complexity (SC) techniques, a discretization of Farber’s topological complexity TC. Besides its relevance toward technological applications, our work reveals that, unlike other discrete approaches to TC, the SC model can recast Farber’s invariant without having to introduce costly subdivisions. We develop and implement our algorithm by actually discretizing Macías-Virgós and Mosquera-Lois’ notion of homotopic distance, thus encompassing computer estimations of other sectional category invariants as well, such as the Lusternik-Schnirelmann category of polyhedra.
KW - Abstract simplicial complex
KW - Barycentric subdivision
KW - Contiguity of simplicial maps
KW - Homotopic distance
KW - Motion planning
KW - Randomized algorithm
UR - http://www.scopus.com/inward/record.url?scp=85115919509&partnerID=8YFLogxK
U2 - 10.3390/math9192358
DO - 10.3390/math9192358
M3 - Artículo
AN - SCOPUS:85115919509
SN - 2227-7390
VL - 9
JO - Mathematics
JF - Mathematics
IS - 19
M1 - 2358
ER -