Informed Guided Rapidly-exploring Random Trees*-Connect for Path Planning of Walking Robots

Dominik Belter

TL;DR

This paper introduces the Informed Guided Rapidly-exploring Random Trees*-Connect (IGRSC) algorithm, a novel approach to full-body path planning for walking robots. IGRSC significantly improves planning efficiency and path quality by combining a guided search for an initial path with an informed optimization strategy, outperforming existing methods in complex environments.

What Problem Does This Paper Address?

Planning paths for walking robots is a complex challenge due to the high dimensionality of their state space (body and leg configurations), which can involve dozens of degrees of freedom. Beyond just avoiding collisions with the environment, planners must also ensure static stability, prevent self-collisions, and respect the robots' leg workspace constraints. Checking these constraints for every potential robot configuration is computationally expensive, making traditional path planning methods struggle. Existing sampling-based planners, while capable of handling high-dimensional spaces, often produce suboptimal paths or require excessive computation time. This paper aims to bridge this gap by developing a more efficient and effective path planning method for walking robots that can handle these complex constraints.

Methods

The IGRSC algorithm is a two-stage approach:

  • Stage 1: GuidedRRT for Initial Path Finding: This stage leverages a GuidedRRT planner, which uses a lower-resolution A* search on a simplified representation of the environment to guide a local RRT-Connect planner. This helps find an initial, feasible, though not necessarily optimal, full-body path more quickly than standard RRT-Connect. The planner also incorporates an improved posture optimization strategy and uses B-spline interpolation for smoother, more stable trajectories, particularly important for quadrupedal robots.
  • Stage 2: Informed RRT*-Connect for Optimization: The feasible path found in Stage 1 is then used to inform an Informed RRT-Connect algorithm. Instead of starting from scratch, this algorithm uses the initial path to define an ellipsoidal sampling region, focusing the search on areas likely to contain shorter, more optimal paths. This "informed" sampling significantly speeds up the optimization process compared to standard RRT-Connect. The algorithm also employs a greedy approach to connect two trees (one from the start, one from the goal) and a rewiring procedure to shorten paths within the trees.

Datasets

The paper does not explicitly mention or introduce new datasets. Instead, it uses simulated environments and robot models (six-legged Messor II and quadrupedal ANYmal) to evaluate the proposed algorithm. The "maps" used for testing include flat terrain, rough terrain, a box obstacle, and a "bug trap" environment, each designed to challenge different aspects of path planning.

Key Insights and Ideas

  • The power of informed sampling: Using a pre-computed feasible path to guide the sampling process in RRT*-Connect dramatically improves efficiency, allowing for faster optimization and potentially shorter paths.
  • Two-stage planning is effective: Combining a fast initial path finder (GuidedRRT) with an optimizer (Informed RRT*-Connect) offers a robust strategy for complex path planning problems.
  • Smoothness matters for stability: For quadrupedal robots, ensuring smooth trajectories via B-splines is crucial for maintaining quasi-static stability, especially on uneven terrain.
  • Generalization is key: The proposed methods are designed to be generalizable across different legged robot platforms (six-legged and four-legged), demonstrating the robustness of the approach.
  • "Bug trap" environments highlight planner weaknesses: Complex environments with narrow passages or specific obstacle configurations reveal the limitations of simpler planners and the advantages of more sophisticated strategies.

Key Results

  • Improved Path Length: In all tested scenarios, the proposed IGRSC algorithm consistently found the shortest average path length.
  • Faster Planning in Complex Environments: While optimization times were set to a constant for informed planners, IGRSC demonstrated superior performance in challenging environments (e.g., "bug trap") where other planners struggled or failed.
  • High Success Rate: IGRSC achieved a 100% success rate across various scenarios and robot types within the given time constraints.
  • Comparison to Baseline: RRT-Connect was efficient for local planning but failed in complex scenarios. RRT-Connect and Informed RRT-Connect showed improvements but were still outperformed by IGRSC, especially in demanding environments.

Limitations and Future Work

  • Greedy Nature: The use of greedy variants of sampling-based planners can sometimes lead to unsuccessful attempts to connect trees, especially in cluttered environments.
  • Computational Cost of Constraint Checking: While the paper uses efficient methods, constraint checking (stability, collisions, workspace) remains a significant computational bottleneck.
  • Future Work: The authors suggest training neural networks to predict locomotion costs to further guide the sampling strategy and improve planning time. They also plan to use the generated near-optimal paths to train MPNet-based neural planners.

Summary updated

BibTeX
@inproceedings{belter2022informed,
  author = {Dominik Belter},
  title = {{Informed Guided Rapidly-exploring Random Trees*-Connect for Path Planning of Walking Robots}},
  booktitle = {ICARCV},
  year = {2022},
  doi = {10.1109/icarcv57592.2022.10004330},
}
Figure