Anytime RRTs

We present an anytime algorithm for planning paths through high-dimensional, non-uniform cost search spaces. Our approach works by generating a series of rapidly-exploring random trees (RRTs), where each tree reuses information from previous trees to improve its growth and the quality of its resulting path. We also present a number of modifications to the RRT algorithm that we use to bias the search in favor of less costly solutions. The resulting approach is able to produce an initial solution very quickly, then improve the quality of this solution while deliberation time allows. It is also able to guarantee that subsequent solutions will be better than all previous ones by a user-defined improvement bound. We demonstrate the effectiveness of the algorithm on both single robot and multirobot planning domains

Authors

• Dave Ferguson 0001
• Anthony Stentz

Keywords

• Costs
• Orbital robotics
• Path planning
• Intelligent robots
• Sampling methods
• Time factors
• Navigation
• Rapidly-exploring Random Tree
• Search Space
• Solution Quality
• Upper Bound
• Tree Nodes
• Considerable Cost
• Area Of Space
• Configuration Space
• Second Set Of Experiments
• Node Samples
• Planning Time
• Previous Solution
• Node Selection
• Cost Of Solution
• Successful Solution
• Regularization Approach
• Sites In Lines
• Cost Path
• Node Cost
• Extension Operator
• Heuristic Value
• Uniform Spacing
• Standard Algorithm
• Adaptive Algorithm