TL;DR
Path planning for hybrid driving-stepping robots is computationally expensive due to their high-dimensional state spaces. This paper introduces a unified planner that uses multiple levels of abstraction—high detail near the robot and coarser, semantically-enriched representations further away. This approach speeds up planning by over two orders of magnitude while maintaining high-quality, executable paths in complex search and rescue environments.
What Problem Does This Paper Address?
Search and rescue environments feature highly unstructured terrain, from flat corridors to steep staircases and rubble. Hybrid robots, like the authors' wheeled-legged robot Momaro, tackle this by combining the speed of wheeled driving with the obstacle-clearing ability of legged stepping.
However, this flexibility comes at a steep computational cost. Planning individual foot placements and base shifts requires searching through a massive, high-dimensional state space. While standard multiresolution planning (coarse global plans refined by detailed local planners) can speed things up, it often fails in rough terrain. A coarse map might blur a staircase into a steep ramp, leading the global planner to incorrectly label it as impassable or generate a path that the high-resolution local planner cannot actually execute. The authors need a way to plan over long distances quickly without losing the critical terrain details required for legged locomotion.
Methods
The authors propose a single Anytime Repairing A (ARA) planner that unifies three levels of representation based on distance from the robot:
- Level 1 (Vicinity): High resolution (2.5 cm) and high degrees of freedom (DoF). The planner considers individual foot actions, base shifts, and 64 discrete orientations.
- Level 2 (Medium Distance): Coarser resolution (5.0 cm) and lower DoF. The robot is abstracted to move pairs of feet rather than individual legs.
- Level 3 (Global): Coarsest resolution (10 cm) and lowest DoF. The robot is treated as a single entity moving across the map.
The Key Novelty: To prevent the coarser levels from losing vital terrain information, the authors enrich them with semantics. In Level 3, map cells are explicitly classified into terrain types: flat, rough, step, or wall. This allows the coarse planner to know that a height change is a traversable "step" rather than an impassable "wall," assigning accurate traversal costs without needing to calculate exact foot placements.
Additionally, the authors use the Level 3 representation to run a 3D Dijkstra search from the goal. This generates a highly informative, terrain-aware heuristic for the main A* search. As the robot moves along the path and gathers better sensor data, the coarse path segments are continuously refined into Level 1 executable steps.
Datasets
Not discussed in the form of standard public benchmarks. The authors evaluate their approach using custom 3D height maps generated from onboard Velodyne 3D laser scanner data in simulated and real-world search-and-rescue scenarios (e.g., navigating corridors with stairs, ramps, and scattered obstacles).
Key Insights and Ideas
- Semantics rescue low resolution: Simply downsampling a map destroys the geometric features necessary for legged planning. By replacing lost geometry with semantic labels (like "step" or "rough"), a low-dimensional planner can accurately estimate the cost of complex maneuvers.
- Unified planning prevents unexecutable paths: Because all three levels are evaluated in a single planner with carefully matched cost functions, the algorithm avoids the classic trap where a global planner suggests a route that the local planner finds physically impossible.
- Terrain-aware heuristics are game-changers: Using a standard Euclidean (straight-line) distance heuristic in complex terrain forces the planner to explore many dead ends. The semantically-enriched Level 3 Dijkstra heuristic guides the search directly through traversable terrain, drastically pruning the search space.
Key Results
- Massive Speedup: Planning with combined levels of abstraction is at least one order of magnitude faster than pure high-resolution (Level 1) planning.
- Heuristic Impact: Introducing the Level 3 Dijkstra heuristic accelerates planning by more than two orders of magnitude compared to a standard Euclidean heuristic. Precomputing this heuristic took only ~0.5 seconds.
- Maintained Path Quality: Despite the heavy abstraction, the cost of the generated paths remains highly comparable to optimal fine-grained paths. When coarse segments are eventually refined into detailed footstep plans, the actual costs differ from the initial coarse estimates by only 3.3% to 15% (depending on the heuristic weight used).
Limitations and Future Work
- Admissibility: The proposed Dijkstra heuristic is not strictly admissible (it can sometimes overestimate costs). This means the ARA* search is not mathematically guaranteed to find the absolute optimal path, though empirical results show it finds highly satisfying paths in feasible time.
- Manual Tuning: The terrain classification relies on manually tuned height-difference thresholds (e.g., defining exactly what height constitutes a "step" vs. a "wall").
- Future Directions: The authors note that terrain classification could be improved by incorporating camera images and visual terrain segmentation, rather than relying purely on geometric height differences from LIDAR.
Summary updated