Hybrid planning solves complex multi-robot motion problems faster
Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling
Robotics
Summary
Moving many robots at once in tight spaces is really hard because there isn’t much room to move without bumping into something. The authors created new methods that mix two existing strategies for exploring movement options, making it easier to find paths even when the space is very crowded. They tested these methods on problems from moving piano parts to simulating many connected molecules, showing their methods can solve very complicated puzzles much faster than older approaches. One method they call HARF is especially good at speeding up the planning when many robots need to move together.
What this means in practice
- •For robotics engineers: Plan complex movements for many robots simultaneously in constrained environments faster and more reliably than traditional methods.
- •For computational chemists: Simulate the relative movement of multiple connected molecular domains more efficiently, aiding in modeling large molecular systems.
Authors
Frederic Cazals, Nelson Feyeux
Abstract
The exploration of high-dimensional spaces remains a challenging problem, in particular in the presence of narrow passages and small clearances. We propose novel sampling-based path-planning methods for high-dimensional spaces combining Rapidly-exploring Random Trees (RRT) and Hit-and-Run (HAR) random walks by decoupling the point being extended from the direction of extension. We also show that RRT and HAR appear as special cases of a generic algorithm coupling the biases used for the point and direction extension, respectively. We further study a sparse-move strategy in which only a fraction p_r of the robots is moved at each step, helping both RRT and the proposed HAR algorithms handle cluttered instances. Tests are presented for two families of models: classical piano mover problems in 3D, and complex molecular systems involving tens of rigid domains moving relatively to one another -- the latter viewed as independent robots exploring the motion space SE(3)N . Within seconds on a standard laptop, our algorithms solve instances with up to 64 robots and 384 degrees of freedom. We conclude by suggesting one of our methods, HARF, as the method of choice for complex multi-robot planning problems, being up to two orders of magnitude faster than the classical RRT moving all robots at each step--when it succeeds at all, and still up to 2.4 fold faster on most instances when both use their best p_r.