Robots Navigate Faster Using Simplified Maps

Motion planning—the process of finding a collision-free path for a robot from start to finish—is fundamental to robotics applications from manufacturing to exploration. However, as robots become more complex with more degrees of freedom, the computational time required for planning grows exponentially, making real-time applications challenging. Researchers from the University of Stuttgart have developed a new approach that dramatically reduces this planning time by using simplified representations of the robot's environment.

The key finding is that the Quotient-space Rapidly-exploring Random Tree (QRRT) algorithm can reduce motion planning runtime by at least one order of magnitude compared to traditional methods. In experiments with various robotic systems, the researchers observed runtime reductions from over 300 seconds to just 17 seconds in some cases—a 94% improvement. However, the effectiveness depends on the specific sequence of simplifications used and the complexity of the environment.

The methodology builds on the concept of sequential simplifications, where the robot's configuration space is progressively simplified through a series of lower-dimensional representations called quotient spaces. The QRRT algorithm grows trees in these simplified spaces both sequentially and simultaneously, allowing it to quickly prune infeasible paths while maintaining probabilistic completeness—meaning it will eventually find a solution if one exists. The algorithm takes as input a start configuration, goal configuration, and a sequence of these quotient spaces, then efficiently explores multiple simplified versions of the problem simultaneously.

Results from four different robotic systems demonstrate the algorithm's effectiveness. For an 8-degree-of-freedom manipulator, the traditional RRT algorithm performed worst, while at least one QRRT configuration achieved runtime of less than one second—an improvement of at least one magnitude. The researchers also investigated why performance varies between different simplification sequences, discovering that environments with narrow passages benefit most from the approach. In narrow passage scenarios with opening sizes between 0.115 and 0.125 units, the best-performing QRRT configuration reduced planning time from 120 seconds to 30 seconds compared to the worst-performing configuration.

This research matters because faster motion planning enables more responsive robotics in time-sensitive applications. Manufacturing robots could adapt more quickly to changing environments, exploration robots could navigate complex terrain more efficiently, and tele-operated systems could provide more immediate feedback. The ability to reduce planning time by an order of magnitude could make previously impractical robotics applications feasible.

The approach does have limitations. The researchers note that they cannot definitively say which specific simplification sequence minimizes runtime for all scenarios, as performance depends on factors like robot geometry and environment characteristics. The choice of good simplification sequences remains an important consideration, and the method incurs additional computational overhead when building multiple trees simultaneously, which may not be worthwhile in simple environments without narrow passages.