Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

2013/05/13 by Kiril Solovey, Solovey, Kiril, Oren Salzman +3 · 3 citations
Computer Science · Engineering · #Robotic Path Planning Algorithms #Robotic Locomotion and Control #Human Pose and Action Recognition

paper · pdf · doi:10.48550/arxiv.1305.2889

Abstract

We present a sampling-based framework for multi-robot motion planning which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.

Cited by

• RVC-NMPC: Nonlinear Model Predictive Control with Reciprocal Velocity Constraints for Mutual Collision Avoidance in Agile UAV Flight
• Effective Game-Theoretic Motion Planning via Nested Search
• Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks

Related

• Near-Optimal Multi-Robot Motion Planning with Finite Sampling
• Scalable Asymptotically-Optimal Multi-Robot Motion Planning
• Effective Metrics for Multi-Robot Motion-Planning
• Growing Trees with an Agent: Accelerating RRTs with Learned, Multi-Step Episodic Exploration
• Zonal RL-RRT: Integrated RL-RRT Path Planning with Collision Probability and Zone Connectivity