Obstacle Crossing Path Planning for a Wheel-Legged Robot Using an Improved A* Algorithm

J. D. Lu, Ming Pi, Gengsheng L. ZengSensors 2025 · DOI

TL;DR

This paper presents an improved A* path planning algorithm for wheel-legged robots that enables them to efficiently cross obstacles by "jumping" over them, rather than just navigating around. By integrating a jump-point search, dynamic heuristic weighting, and a continuous jumping constraint, the algorithm significantly reduces path length and search time in complex environments, making robots more adaptable and efficient.

What Problem Does This Paper Address?

Wheel-legged robots, with their hybrid locomotion capabilities, are excellent for navigating complex terrains and overcoming obstacles. However, existing path planning algorithms, like the standard A*, primarily focus on obstacle avoidance by finding detours. This can be inefficient and time-consuming in environments with numerous obstacles that could be more easily traversed by a robot's unique ability to "jump" or step over them. The challenge is to develop a path planner that can intelligently decide when jumping is a more efficient strategy than simply going around, while also ensuring the robot's stability and the smoothness of the generated path.

Methods

The core of this work is an enhanced A* algorithm with several key innovations:

  • Jump-Point Search (JPS) Extension: The traditional 8-neighborhood search is expanded to a 16-neighborhood, allowing for "jump" actions in horizontal, vertical, and diagonal directions. This enables the robot to traverse single-grid obstacles.
  • Obstacle Crossing Mechanism: Specific rules are defined for valid jumps, ensuring the intermediate cell is a "crossable obstacle" (gray in their grid representation) and the landing cell is "free space" (white). Diagonal jumps have additional checks for adjacent corner cells.
  • Dynamically Weighted Heuristic: To balance search efficiency and path optimality, a dynamic weight is applied to the heuristic function. This weight adaptively adjusts the influence of the heuristic, prioritizing faster convergence early in the search and greater accuracy near the goal.
  • Continuous Jumping Constraint: To prevent excessive and potentially unstable continuous jumping, a mechanism is introduced that limits consecutive jumps, ensuring motion stability.
  • Redundant Point Removal and Bézier Curve Smoothing: After path planning, redundant points are pruned, and Bézier curves are used to smooth the resulting path, improving its continuity and reducing jerky movements.

Datasets

The paper does not mention specific datasets for training. Instead, it relies on simulated environments.

  • Simulated Grid Maps: The experiments were conducted on 40x40 grid maps with randomly generated insurmountable (black) and surmountable (gray) obstacles. Different map sizes (20x20, 40x40, 60x60) were also used to test scalability.

Key Insights and Ideas

  • Jumping as a Strategic Choice: The most significant insight is framing obstacle crossing not just as a capability, but as a strategic decision within path planning. The algorithm intelligently identifies when a jump is more beneficial than a detour.
  • Balancing Optimality and Efficiency: The dynamic heuristic weighting is crucial. It demonstrates that for real-time applications, a near-optimal path achieved quickly is often more valuable than a perfectly optimal path that takes too long.
  • The Importance of Stability Constraints: The continuous jumping constraint highlights a critical real-world consideration: even if a path is shorter, it must be physically achievable and stable for the robot.
  • Multi-Modal Path Planning: This work pushes towards multi-modal path planning, where robots can leverage different movement strategies (walking, jumping) based on the environment.

Key Results

The improved algorithm demonstrated significant performance gains compared to the traditional A* algorithm on a 40x40 grid:

  • Path Nodes: Reduced by 73.7% (from 54 to 16).
  • Search Nodes: Reduced by 85% (from 542 to 78).
  • Planning Time: Achieved in just 0.0032 seconds.
  • Path Length: Shortened by approximately 8.5% (from 63.355 to 61.012).
  • Scalability: The performance advantage of the optimized algorithm became more pronounced as the map size increased, indicating strong robustness.

Limitations and Future Work

  • 2D Grid Simplification: The current study uses a simplified 2D grid map and treats the robot as a point particle. This abstracts away critical real-world complexities like robot dimensions, kinematics, dynamics, and precise foot placement during jumps.
  • Static Environments: The algorithm is currently designed for static environments.
  • Future Work:
    • Physical Robot Validation: Further validation on a physical robot platform or in a high-fidelity simulator (e.g., Gazebo) is essential to assess engineering applicability and motion stability.
  • Dynamic Environments: Extending the framework to handle moving obstacles by integrating reactive collision avoidance algorithms (like DWA).
  • 3D Perception: Developing a system that uses stereo cameras for real-time 3D environmental perception.
  • Realistic Obstacle Modeling: Moving from binary obstacle representations to using actual physical dimensions (height, slope) in 3D point cloud representations.
  • Dynamic Model Integration: Refining the jump cost function by integrating the robot's dynamic model for more physically feasible and stable maneuvers.

Summary updated

Abstract

In response to the challenges of obstacle avoidance and terrain negotiation encountered by wheel-legged robots in static environments with complex obstacles, this study introduces an enhanced A* path planning algorithm that incorporates a jump-point search strategy, a dynamically weighted heuristic strategy, and a continuous jumping constraint mechanism to facilitate efficient obstacle traversal. The algorithm extends the traditional 8-neighborhood rule to support jumping in the horizontal, vertical, and diagonal directions. A dynamic, weighted heuristic is introduced to adaptively adjust heuristic weights, guide the search direction, improve efficiency, and reduce detours. Redundant point removal and Bézier curve smoothing were employed to enhance path smoothness, whereas the continuous jumping constraint limited the jump frequency and improved motion stability. The results validate that-relative to the standard A* algorithm, which achieves a 73.7% reduction in path nodes (from 54 to 16)-85% fewer search nodes (from 542 to 78) and a planning time of 0.0032 s were achieved while also enhancing performance in crossing complex structures. This enhances the capability of wheel-legged robots to perform real-time path planning in structurally complex yet static environments, thereby improving their autonomous navigation efficiency.
BibTeX
@inproceedings{lu2025obstacle,
  author = {J. D. Lu and Ming Pi and Gengsheng L. Zeng},
  title = {{Obstacle Crossing Path Planning for a Wheel-Legged Robot Using an Improved A* Algorithm}},
  booktitle = {Sensors},
  year = {2025},
  doi = {10.3390/s25185795},
}
Figure