Abstract
Navigating in search and rescue environments is challenging, since a variety of terrains has to be considered. Hybrid driving-stepping locomotion, as provided by our robot Momaro, is a promising approach. Similar to other locomotion methods, it incorporates many degrees of freedom—offering high flexibility but making planning computationally expensive for larger environments. We propose a navigation planning method, which unifies different levels of representation in a single planner. In the vicinity of the robot, it provides plans with a fine resolution and a high robot state dimensionality. With increasing distance from the robot, plans become coarser and the robot state dimensionality decreases. We compensate this loss of information by enriching coarser representations with additional semantics. Experiments show that the proposed planner provides plans for large, challenging scenarios in feasible time.
Introduction
Search and rescue environments present a unique challenge for robotic navigation due to their highly unstructured nature, ranging from flat corridors to steep staircases and debris-filled rooms. Hybrid robots, such as the wheeled-legged robot Momaro, are designed to address this by combining the speed and efficiency of wheeled driving with the obstacle-clearing capabilities of legged stepping.
However, the flexibility of hybrid locomotion comes with a significant computational burden. Planning individual foot placements and base shifts across complex terrain requires searching through a massive, high-dimensional state space. While standard multiresolution planning—where a coarse global plan is refined by a detailed local planner—can reduce complexity, it often fails in rough terrain. Coarse maps typically blur critical geometric features, such as individual steps, leading a global planner to incorrectly label traversable areas as impassable. This paper introduces a unified planning approach that maintains execution feasibility across long distances by integrating multiple levels of abstraction.
Methodology: Multi-Level Unified Planning
The core of the proposed system is a single Anytime Repairing A (ARA) planner that unifies three distinct levels of representation based on the distance from the robot. This spatial distribution ensures high fidelity where it is most needed for execution, while maintaining computational efficiency for global pathfinding.
As detailed in the planning hierarchy, the levels are defined as follows:
- Level 1 (Vicinity): Operates at a high resolution (2.5 cm) with high degrees of freedom (DoF). The planner considers individual foot actions, base shifts, and 64 discrete orientations.
- Level 2 (Medium Distance): Uses a coarser resolution (5.0 cm) and lower DoF. The robot is abstracted to move pairs of feet rather than individual legs.
- Level 3 (Global): The coarsest resolution (10 cm) and lowest DoF, treating the robot as a single entity moving across the map.
Semantic Enrichment and Heuristics
To prevent the loss of vital terrain information at coarser levels, the authors introduce semantic enrichment. In Level 3, map cells are classified into terrain types: flat, rough, step, or wall. This allows the coarse planner to recognize that a height change is a traversable "step" rather than an impassable "wall," enabling accurate cost estimation without the need for detailed footstep calculations.
Furthermore, the system utilizes the Level 3 representation to perform a 3D Dijkstra search from the goal. This generates a terrain-aware heuristic that guides the main A* search through traversable paths, drastically pruning the search space compared to standard Euclidean distance heuristics.
Key Insights and Results
The unified planning approach addresses the "unexecutable path" trap common in tiered planners. Because all levels are evaluated within a single search with matched cost functions, the global path is inherently compatible with the local refinement.
Experimental results demonstrate significant performance gains:
- Massive Speedup: Planning with combined levels of abstraction is at least one order of magnitude faster than pure high-resolution planning.
- Heuristic Impact: The semantically-enriched Level 3 Dijkstra heuristic accelerates planning by more than two orders of magnitude compared to standard methods. Precomputing this heuristic is highly efficient, taking approximately 0.5 seconds.
- Path Quality: Despite the heavy abstraction at a distance, the generated paths remain high-quality. When coarse segments are refined into executable Level 1 steps, the actual costs differ from the initial estimates by only 3.3% to 15%.
Conclusion
By unifying multiple levels of abstraction and enriching coarse representations with semantic data, this method enables efficient long-range planning for high-DoF hybrid robots. While the current heuristic is not strictly admissible and relies on manually tuned height thresholds, the system successfully generates executable paths in complex search and rescue scenarios. Future work will explore improving terrain classification through visual segmentation and camera data to complement geometric LIDAR sensors.
Summary updated