Visualizing local minima in multi-robot motion planning using multilevel Morse theory

DOI10.1007/978-3-030-66723-8_30MaRDI QIDQ3382002zbMATH OpenOpenAlexFDO

Authors Andreas Orthey, Marc Toussaint

Publication date 20 September 2021

Published in Algorithmic Foundations of Robotics XIV (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.04385

zbMATH Keywords

fiber bundlesMorse theorymulti-robot motion planningvisualization of local minima

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Artificial intelligence for robotics (68T40) Topology of vector bundles and fiber bundles (57R22) Discrete Morse theory and related ideas in manifold topology (57Q70)

Abstract: Multi-robot motion planning problems often have many local minima. It is essential to visualize those local minima such that we can better understand, debug and interact with multi-robot systems. Towards this goal, we present the multi-robot motion explorer, an algorithm which extends previous results on multilevel Morse theory by introducing a component-based framework, where we reduce multi-robot configuration spaces by reducing each robots component space using fiber bundles. Our algorithm exploits this component structure to search for and visualize local minima. A user of the algorithm can specify a multilevel abstraction and an optimization algorithm. We use this information to incrementally build a local minima tree for a given problem. We demonstrate this algorithm on several multi-robot systems of up to 20 degrees of freedom.

Recommendations

• Building and navigating a network of local minima
• Multi-modal motion planning in non-expansive spaces
• Subdimensional expansion for multirobot path planning
• Motion planning for multiple robots

Cites work

• scientific article; zbMATH DE number 3479762 (Why is no real title available?)
• scientific article; zbMATH DE number 3086604 (Why is no real title available?)
• On multiple moving objects
• On the topology of algorithms. I
• Planning Algorithms
• Subdimensional expansion for multirobot path planning
• Theory of braids

Cited in

(2)

• Building and navigating a network of local minima
• Some geometric and topological data-driven methods in robot motion path planning

Describes a project that uses

Uses Software

• OMPL

This page was built for publication: Visualizing local minima in multi-robot motion planning using multilevel Morse theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3382002)