A Randomized Greedy Algorithm for Piecewise Linear Motion Planning

Carlos Ortiz, Adriana Lara, Jesús González and Ayse Borat
Additional contact information
Carlos Ortiz: Departamento de Matemáticas, Escuela Superior de Física y Matemáticas del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Adriana Lara: Departamento de Matemáticas, Escuela Superior de Física y Matemáticas del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Jesús González: Departamento de Matemáticas, Centro de Investigación y de Estudios Avanzados del Istituto Politécnico Nacional, Av. IPN 2508, Zacatenco, Mexico City 07000, Mexico
Ayse Borat: Department of Mathematics, Faculty of Engineering and Natural Sciences, Bursa Technical University, Bursa 16330, Turkey

Mathematics, 2021, vol. 9, issue 19, 1-17

Abstract: 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.

Keywords: abstract simplicial complex; barycentric subdivision; contiguity of simplicial maps; motion planning; randomized algorithm; homotopic distance (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/19/2358/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/19/2358/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:19:p:2358-:d:641399

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().