RRT-based nonholonomic motion planning using any-angle path biasing

RRT and RRT* have become popular planning techniques, in particular for high-dimensional systems such as wheeled robots with complex nonholonomic constraints. Their planning times, however, can scale poorly for such robots, which has motivated researchers to study hierarchical techniques that grow the RRT trees in more focused ways. Along this line, we introduce Theta*-RRT that hierarchically combines (discrete) any-angle search with (continuous) RRT motion planning for nonholonomic wheeled robots. Theta*-RRT is a variant of RRT that generates a trajectory by expanding a tree of geodesics toward sampled states whose distribution summarizes geometric information of the any-angle path. We show experimentally, for both a differential drive system and a high-dimensional truck-and-trailer system, that Theta*-RRT finds shorter trajectories significantly faster than four baseline planners (RRT, A*-RRT, RRT*, A*-RRT*) without loss of smoothness, while A*-RRT* and RRT* (and thus also Informed RRT*) fail to generate a first trajectory sufficiently fast in environments with complex nonholonomic constraints. We also prove that Theta*-RRT retains the probabilistic completeness of RRT for all small-time controllable systems that use an analytical steer function.

Authors

• Luigi Palmieri
• Sven Koenig
• Kai O. Arras

Keywords

• Trajectory
• Aerospace electronics
• Planning
• Mobile robots
• Robot kinematics
• Path Planning
• Control System
• Planning Time
• Hierarchical Technique
• Smoothness Loss
• Wheeled Robot
• Nonholonomic Constraints
• Rapidly-exploring Random Tree
• Heuristic
• Cost Function
• Performance Metrics
• State Space
• Positive Bias
• Free Space
• Equations Of Motion
• Workspace
• Membership Function
• Discrete Set
• Tree Size
• Trajectory Length
• Orientation Bias
• Smooth Trajectory
• Geodesic Distance
• Random Environment