Topological complexity of collision free motion planning algorithms in the presence of multiple moving obstacles

2006/09/17 by Michael Färber, Farber, Michael, Mark Grant +3 · 3 citations
Computer Science · #55R80 #93C83 #Algebraic Topology (math.AT) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Optimization and Control (math.OC) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.math/0609476

openalex publication_date 2006/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study motion planning algorithms for collision free control of multiple objects in the presence of moving obstacles. We compute the topological complexity of algorithms solving this problem. We apply topological tools and use information about cohomology algebras of configuration spaces. The results of the paper may potentially be used in systems of automatic traffic control.

Cited by

• Autonomous motion in changing environment, fibrations and reaction mechanisms
• Parametrized Topological Complexity for a Multi-Robot System with Variable Tasks
• On the complexity of parametrized motion planning algorithms

Related

• Parametrized topological complexity of collision-free motion planning in the plane
• Topological complexity of motion planning
• Collision Free Motion Planning on Graphs
• Configuration Spaces and Robot Motion Planning Algorithms
• Collision free motion planning on a wedge of circles