Planning motions for robots with complex physics — high-dimensional state spaces, nonlinear dynamics — is slow. This paper speeds it up by building a lightweight roadmap over a simplified version of the robot, then using that roadmap to steer where the full motion planner looks next. Instead of searching blindly, the planner follows hints from the roadmap. That simple trick leads to big speedups on high-dimensional robots.
Problem
Consider a robot with complex dynamics — a physics-based vehicle, a snake-like manipulator, or a blimp. Its state space is high-dimensional and its dynamics are nonlinear. Sampling-based planners like RRT can find solutions but spend most of their budget exploring irrelevant regions.
Approach
The key idea: build a probabilistic roadmap in a simplified configuration space derived from a relaxed robot model, then use that roadmap to bias tree expansion in the full state space.
The roadmap acts as a lightweight abstraction — it captures global connectivity without enforcing full dynamics. During tree search, nodes in the roadmap indicate which directions of the state space are promising, steering the sampler away from dead ends.
This produces significant computational speedups compared to workspace decomposition approaches, because the guidance is derived from the actual robot’s geometry rather than generic spatial partitions.
Applications
The approach was validated on three systems of increasing complexity:
- Physics-based vehicle motion
- High-dimensional snake-like robot
- High-dimensional blimp-like robot
Each demonstrates that roadmap abstraction guidance scales to systems where unguided search fails to find solutions in practical time budgets.
Future Work
Improving sampling and connection strategies in roadmap construction — particularly for navigating narrow passages in configuration space — remains an open challenge.
Videos
Simulation with physics-based vehicle
Simulation with high-dimensional snake-like robot
Simulation with high-dimensional blimp-like robot