Abstract
It has been observed that the motion planning problem of robotics reduces mathematically to the problem of finding a section of the path-space fibration, leading to the notion of topological complexity, as introduced by M. Farber. In this approach one imposes no limitations on motion of the system assuming that any continuous motion is admissible. In many applications, however, a physical apparatus may have constrained controls, leading to constraints on its potential dynamics. In the present paper we adapt the notion of topological complexity to the case of directed topological spaces, which encompass such controlled systems, and also systems which appear in concurrency theory. We study properties of this new notion and make calculations for some interesting classes of examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Note that we do not need to ask for s(b, b) to be the constant path on b. The section on the diagonal of \(\varGamma _X\) is in fact necessarily made of paths homotopic to b. We thank an anonymous referee and Jeremy Dubut for pointing out this fact to us.
References
Aubin, J.-P., Cellina, A.: Differential Inclusions, Set-Valued Maps And Viability Theory. Number 264 in Grundl. der Math. Wiss. Springer, Berlin (1984)
Baues, H.-J., Wirsching, G.: Cohomology of small categories. J. Pure Appl. Algebra 38(2–3), 187–211 (1985)
Bergner, J.: A model category structure on the category of simplicial categories. Trans. Am. Math. Soc. 359, 2043–2058 (2004)
Borat, A., Grant, M.: Directed Topological Complexity of Spheres (2019). (To appear in the same volume)
Dubut, J., Goubault, E., Goubault-Larrecq, J.: Natural homology. In: Proceedings, Part II Automata, Languages, and Programming—42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015, pp. 171–183 (2015)
Dubut, J., Goubault, É., Goubault-Larrecq, J.: Directed homology theories and Eilenberg–Steenrod axioms. Appl. Categ. Struct. 25, 775 (2016)
Fajstrup, L.: Dipaths and dihomotopies in a cubical complex. Adv. Appl. Math. 35(2), 188–206 (2005)
Fajstrup, L., Goubault, E., Haucourt, E., Mimram, S., Raussen, M.: Directed Algebraic Topology and Concurrency. Springer, Berlin (2016)
Farber, M.: Topological complexity of motion planning. Discrete Comput. Geom. 29(2), 211–221 (2003)
Farber, M.: Invitation to Topological Robotics. Zurich Lectures in Advanced Mathematics. European Mathematical Society, Zurich (2008)
Goubault, E.: On directed homotopy equivalences and a notion of directed topological complexity (2017). CoRR arXiv:1709.05702
Goubault, E., Mimram, S.: Directed homotopy in non-positively curved spaces. Log. Methods. Comput. Sci. (2019). (To appear, special issue for the 60th birthday of Pierre-Louis Curien)
Grandis, M.: Directed Algebraic Topology. Models of Non-reversible Worlds. Cambridge University Press, Cambridge (2009)
Raussen, M.: Trace spaces in a pre-cubical complex. Topol. Appl. 156(9), 1718–1728 (2009)
Funding
The study was funded by DGA-MRIS (Grant No. Safety of Complex Robotic Systems).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Goubault, E., Farber, M. & Sagnier, A. Directed topological complexity. J Appl. and Comput. Topology 4, 11–27 (2020). https://doi.org/10.1007/s41468-019-00034-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41468-019-00034-x
Keywords
- Directed topology
- Robot motion planning
- Topological complexity
- Controlled systems
- Concurrent systems
- Homotopy theory