An Improved DHA Star and ADA-DWA Fusion Algorithm for Robot Path Planning

Yizhe Jia, Yong Cai, Jun Zhou, Hui Hu, Xuesheng Ouyang, Jinlong Mo, Hao DaiRobotics 2025 · DOI

TL;DR

This paper introduces a novel fusion algorithm, DHA-ADA-DWA, that combines a globally optimized path planner (DHA) with a dynamically adaptive local planner (ADA-DWA) to achieve robust and efficient navigation for mobile robots in complex, dynamic environments. The approach significantly improves path optimality, reduces computation time, and enhances obstacle avoidance capabilities compared to existing methods.

What Problem Does This Paper Address?

Autonomous navigation for mobile robots hinges on effective path planning. Traditional approaches often fall into two categories: global planners that generate an optimal path in a static environment but struggle with dynamic changes, and local planners that react to immediate obstacles but can get stuck in local minima or produce inefficient paths. This creates a trade-off between path optimality and real-time adaptability, especially in unstructured and dynamic environments with unforeseen obstacles. Existing methods often suffer from issues like redundant nodes, non-smooth trajectories, low search efficiency, and poor obstacle avoidance, limiting their practical application.

Methods

The paper proposes a hierarchical fusion framework that synergizes two core algorithms:

  • Dynamic Hybrid A (DHA): This is an enhanced version of the A* algorithm for global path planning. Key improvements include:
  • Dynamic Hybrid Heuristic Function: Combines Chebyshev and Manhattan distances with adaptive weights that adjust based on the robot's proximity to the goal, balancing global exploration and local convergence.
  • Key-Node Selection Strategy (KNSS): Prunes redundant nodes and ensures kinematic feasibility by checking for collisions and validating safety margins between consecutive nodes.
  • Direction-Aware Neighborhood Search: Prioritizes nodes that are more aligned with the goal direction, reducing computational redundancy and improving search efficiency.
  • Adaptive Dynamic Window Approach (ADA-DWA): This is an improved local path planner for real-time obstacle avoidance. Its key innovation is an:
  • Adaptive Evaluation Function: Dynamically adjusts the weights of sub-functions (obstacle avoidance, goal alignment, velocity, distance to goal) based on environmental feedback. This allows the robot to prioritize safety in cluttered environments while maximizing speed and efficiency when possible.

The fusion framework uses the key nodes generated by DHA* as intermediate waypoints for ADA-DWA, guiding the local planner towards the global goal while ensuring dynamic obstacle avoidance.

Datasets

The paper does not explicitly mention training datasets. Evaluation was performed using:

  • Numerical Simulations: Diverse 2D grid maps were used to simulate environments with varying complexity, including scenarios with randomly moving obstacles.
  • Real-world Experiments: A Limo omnidirectional mobile robot platform was used in a laboratory setting with both static and dynamic obstacles.

Key Insights and Ideas

  • Synergy of Global and Local Planning: The core insight is that a hierarchical fusion of a robust global planner (DHA*) and an adaptive local planner (ADA-DWA) can overcome the limitations of each individual approach.
  • Adaptive Heuristics for A*: Dynamically adjusting heuristic weights in A* is crucial for balancing exploration and exploitation, leading to more efficient and optimal pathfinding.
  • Dynamic Weighting for DWA: Making DWA's evaluation function adaptive to the environment allows it to better handle dynamic obstacles and avoid local optima, improving safety and efficiency.
  • Key Nodes as Guidance: Using strategically selected key nodes from the global path as intermediate targets for the local planner provides a robust guidance mechanism for complex navigation.

Key Results

  • DHA* Performance: Compared to traditional A and other improved algorithms, DHA reduced the number of traversed nodes by an average of 51.952%, shortened path length by 30.517%, and decreased search time by 71.694%.
  • Fusion Algorithm Performance (Simulations): The DHA*-ADA-DWA fusion algorithm achieved the shortest planned path (24.08 m) and minimal computation time (20.32 s) in dynamic environments, outperforming traditional DWA and improved DWA variants. It reduced path length by 15.68% and planning time by 32.16%.
  • Fusion Algorithm Performance (Real-world): Compared to existing methods [38, 39], the proposed fusion algorithm reduced path length by 29.176% and running time by 37.656%, while successfully avoiding dynamic obstacles and maintaining collision-free paths.
  • Collision Avoidance: The fusion algorithm successfully navigated around unknown dynamic obstacles in real-time, demonstrating superior adaptability and robustness.

Limitations and Future Work

  • Limitations:
    • The paper focuses on 2D path planning. Extending to 3D environments could be a future direction.
  • While dynamic obstacles were handled, the complexity of highly chaotic or unpredictable environments might still pose challenges.
  • The paper does not detail the computational cost of the adaptive weight adjustments in ADA-DWA, which could be a factor in real-time performance on resource-constrained platforms.
  • Future Work:
    • The authors suggest that this hierarchical architecture provides a strong foundation for autonomous robot systems in practical applications, implying potential for further refinement and deployment in more complex scenarios.
  • Further exploration of the adaptive weighting mechanisms and their impact on different types of dynamic environments could be beneficial.

Summary updated

BibTeX
@article{jia2025improved,
  author = {Yizhe Jia and Yong Cai and Jun Zhou and Hui Hu and Xuesheng Ouyang and Jinlong Mo and Hao Dai},
  title = {{An Improved DHA Star and ADA-DWA Fusion Algorithm for Robot Path Planning}},
  journal = {Robotics},
  year = {2025},
  doi = {10.3390/robotics14070090},
}
Figure