Visualizing Local Minima in Multi-robot Motion Planning Using Multilevel Morse Theory

DOI10.1007/978-3-030-66723-8_30zbMATH Open1469.68131arXiv2002.04385OpenAlexW3162628365MaRDI QIDQ3382002FDOQ3382002

Marc Toussaint, Andreas Orthey

Publication date: 20 September 2021

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of braids
• Planning Algorithms
• On the topology of algorithms. I
• On multiple moving objects
• Subdimensional expansion for multirobot path planning
• Path homotopy invariants and their application to optimal trajectory planning

Cited In (2)

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

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)