Self-Adaptive A* Algorithm with Enhanced Dynamic Window Approach for Optimal Trajectory Planning in Narrow Environments Jiaquan Yan1,† , Zineng Zhou2,3,† , Haiyong Luo2,3,* , Fang Zhao1,* , You Xiong1 , Juan Wang4 and XuePeng Ma4 1 Beijing University of Posts and Telecommunications, No 10, Xitucheng Road, Haidian District, Beijing, China 2 Institute of Computing Technology Chinese Academy of Sciences, No.6 Kexueyuan South Road, Haidian District, Beijing, China 3 University of Chinese Academy of Sciences, Beijing, China 4 Shouguang Cheng Zhi Feng Xing Technology Co., Ltd. Abstract Path planning in narrow environments presents substantial challenges for autonomous driving and robotic navigation. This paper introduces an innovative adaptive search method tailored for the hybrid A* algorithm, designed to fully leverage the capabilities of differential drive models. This method enhances the algorithm’s ability to generate trajectories that are more in tune with the dynamics of differential drive chassis, particularly in narrow passages. Here, the algorithm adaptively transitions between hybrid A* and traditional A* strategies, utilizing variable search step lengths to effectively balance precision and computational efficiency. Furthermore, we introduce a novel reward function for the hybrid A* algorithm, which incorporates considerations for safety and the costs associated with in-place rotations. This reward function takes into account the number of nearby obstacles, a safety cost, a rotation cost, and a zero-speed cost, all aimed at minimizing unnecessary rotations and optimizing the overall path planning process. To implement our approach in real-world scenarios, we present an Enhanced Dynamic Window Approach (EDWA) that employs multi-scale path sampling to more effectively navigate complex environments with sharp turns. Simulation results demonstrate the effectiveness and superiority of our proposed algorithms in managing narrow path navigation. The improved hybrid A* and DWA algorithms notably enhance safety, efficiency, and trajectory smoothness, showing significant advancements over traditional methods. Keywords Hybrid A*, Enhanced Dynamic Window Approach, Autonomous Navigation, Path Planning, Multi-Scale Sampling 1. Introduction In the field of autonomous navigation, efficient trajectory planning in narrow environments remains one of the most challenging tasks, demanding high levels of precision and adaptability from path planning algorithms [1]. Traditional path planning methods, such as the basic A* algorithm and its derivatives, have been extensively utilized due to their effectiveness in grid-based mapping and clear path determination [2]. However, these conventional techniques often fall short in complex, narrow environments due to their rigid pathfinding rules and inability to dynamically adapt to varying constraints and obstacles. The standard A* algorithm, a cornerstone in path planning, is primarily designed for environments where the movement between nodes is constrained to fixed steps and predefined directions. This rigidity can result in suboptimal path generation in constrained spaces where the ability to maneuver freely Proceedings of the Work-in-Progress Papers at the 14th International Conference on Indoor Positioning and Indoor Navigation (IPIN-WiP 2024) * Corresponding author. † These authors contributed equally. $ yanjiaquan@bupt.edu.cn (J. Yan); zhouzineng22s@ict.ac.cn (Z. Zhou); yhluo@ict.ac.cn (H. Luo); zfsse@bupt.edu.cn (F. Zhao); xy@bupt.edu.cn (Y. Xiong); sllhjt@139.com (J. Wang); 139225785@qq.com (X. Ma)  0009-0001-6327-8080 (J. Yan); 0009-0008-9740-4103 (Z. Zhou); 0000-0001-6827-4225 (H. Luo); 0000-0002-4784-5778 (F. Zhao); 0009-0009-7184-7982 (Y. Xiong) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings and adjust to obstacles dynamically is crucial. Moreover, the A* algorithm’s heuristic nature does not inherently account for the kinematic constraints of different robotic platforms, which are essential in tight spaces. Enhancements such as the Hybrid A* algorithm have attempted to address these issues by incorporating the ability to plan paths that consider the vehicle’s orientation and kinematics [3]. However, Hybrid A* fails in narrow paths that require in-place rotations, and efficiency issues arise primarily with multi-scale sampling. Given the deficiencies of these traditional algorithms in narrow and dynamic environments, there is a pressing need for more adaptive and dynamically responsive path planning methods. The challenges in such environments include not only avoiding static and dynamic obstacles but also optimizing the path for safety, efficiency, and compliance with the vehicle’s dynamic capabilities. This necessitates an algorithm that can adjust its planning strategy based on real-time environmental data and vehicle state, transitioning smoothly between different planning modes to accommodate varying spatial constraints. To address these challenges, our paper introduces an innovative adaptive search method within the Hybrid A* framework specially designed for differential drive models, which have the capability for in-place rotations. This method allows for dynamic adjustment of search step lengths, enabling a balance between computational efficiency and the precision needed in constricted spaces. Additionally, we propose a novel reward function that integrates multiple cost factors, such as proximity to obstacles, safety margins, and the costs associated with rotational and zero-speed movements. This function is designed to minimize unnecessary movements and optimize the path for both safety and efficiency. To ensure effective alignment between the model’s dynamically generated trajectory and the pre- planned trajectory during operation, we have implemented an Enhanced Dynamic Window Approach, which generates control commands based on the trajectory to navigate complex environments more effectively [4]. This approach allows for better anticipation and handling of sharp turns and narrow passages, significantly improving the robot’s ability to navigate safely and smoothly. By integrating these advanced techniques, our approach significantly outperforms traditional path planning methods in terms of safety, efficiency, and adaptability in narrow environments. The combi- nation of adaptive Hybrid A* and EDWA represents a substantial step forward in the field of robotic navigation, offering a robust solution to one of the most pressing challenges in autonomous vehicle and robotics technology today. Through rigorous simulation and practical application, our methods demon- strate their superiority, paving the way for more sophisticated and reliable autonomous navigation systems. 2. Related Work Path planning in narrow passages presents unique challenges due to the need for precise maneuverability and obstacle avoidance in constrained environments. Various approaches have been proposed to address these challenges, focusing on optimizing safety, efficiency, and adaptability of navigation algorithms. However, several limitations remain in these methods. 2.1. Model Predictive Control and Hybrid Algorithms Several studies have explored the integration of Model Predictive Control (MPC) with traditional path planning algorithms to enhance navigation in cluttered environments. For instance, Chen and Li [5] developed an MPC-based trajectory planning method to navigate obstacle-cluttered environments, demonstrating significant improvements in safety. However, it often requires extensive computational resources and may struggle with real-time adaptability in highly dynamic environments. Similarly, Borrello et al. [6] introduced a real-time trajectory planner with dynamic obstacle avoidance, but its reliance on accurate environmental modeling limits its effectiveness. Xing et al. [7] combined state-based decision-making with an inertial dynamic window approach, yet it remains computationally intensive. In contrast, our adaptive search method within the Hybrid A* framework dynamically adjusts search step lengths based on environmental constraints, balancing precision and computational efficiency. Our novel reward function integrates multiple cost factors, optimizing the path for both safety and efficiency, thus addressing the computational and real-time adaptability limitations of traditional MPC and hybrid algorithms. 2.2. Dynamic Window Approach Enhancements The Dynamic Window Approach (DWA) has been widely utilized for local trajectory optimization. Cao and Nor [4] improved DWA by integrating multi-scale path sampling, navigating complex environments more effectively. However, their method may suffer from suboptimal path smoothness due to discrete path sampling. Works like Banday et al. [8] and Abtahi et al. [9] optimized DWA for specific applications, highlighting its adaptability but also its limitations in general applicability. Our approach enhances DWA with multi-scale path sampling, significantly improving navigation in sharp turns and narrow passages. This ensures better path smoothness and adaptability, addressing the limitations of previous DWA-based methods. 2.3. Sampling-based Methods and Reinforcement Learning The combination of sampling-based methods and reinforcement learning has shown promise for narrow passage problems. Huang et al. [10] presented Agile-RRT*, enhancing initial solution quality and convergence rate in complex environments but requiring extensive parameter tuning. Weerakoon et al. [11] developed a context-aware planner using offline reinforcement learning, showing superior performance in cluttered outdoor environments but heavily relying on pre-trained models. Other works, such as Levit et al. [12], integrated reinforcement learning for path planning, emphasizing the potential but also the reliance on extensive training data. Our approach combines Hybrid A* and EDWA, improving initial solution quality and convergence rate while reducing computational costs. Our reward function enhances adaptability and efficiency without relying heavily on pre-trained models, addressing the limitations of traditional sampling-based methods. 3. Method In this section, we introduce our methodology for the development and implementation of the Adaptive Hybrid A* Algorithm combined with the Enhanced Dynamic Window Approach for optimal trajectory planning in narrow environments. This approach utilizes the differential drive model’s capabilities to ensure efficient and safe navigation through complex spaces. As illustrated in Figure 1, our approach integrates both the Adaptive Hybrid A* and EDWA into a cohesive framework, enabling dynamic and efficient path planning. 3.1. Adaptive Hybrid A* Algorithm The Adaptive Hybrid A* Algorithm enhances trajectory planning by dynamically alternating between traditional A* and Hybrid A* methods. This flexibility allows for adjusting search step lengths to optimize precision and computational efficiency in constrained environments, a feature crucial for differential drive models that may require in-place rotations. The node expansion strategy is designed to extend search nodes with a mix of curve and straight movements, adhering to the kinematic constraints and employing in-place rotations. This multi-scale trajectory generation is crucial for effective navigation in tight spaces. Node evaluation is conducted using an enhanced cost function, which considers additional factors beyond the traditional A* evaluation. The cost function is defined as: 𝑓 (𝑛) = 𝑔(𝑛) + ℎ(𝑛) + 𝑠(𝑛) + 𝑟(𝑛) + 𝑧(𝑛) where: Self Adaption A Star Node Node Pruning Extension Evaluation Strategy Enhanced Dynamic Window Approach Adaptive Trajectory Sampling Trajectory Sampling Scale Evaluation Estimate Figure 1: Framework of the Self-Adapting A* Algorithm • 𝑔(𝑛) represents the distance traveled, • ℎ(𝑛) is the predicted distance to the goal using A*, • 𝑠(𝑛) denotes the number of nearby obstacles, • 𝑟(𝑛) accounts for the in-place rotation cost, • 𝑧(𝑛) represents the zero-speed cost. Figure 2: Step-by-step trajectory planning using the Adaptive Hybrid A* Algorithm Figure 2 demonstrates the trajectory planning process at each step, showcasing how our algorithm adapts to the immediate environment. 3.2. Enhanced Dynamic Window Approach The EDWA refines local trajectory planning through multi-scale path sampling and adaptive evaluation. Initially, trajectory sampling is performed for different angular velocities, generating multiple sampled trajectories. Considering the in-place rotation capability, sampling is conducted in multiple directions to ensure comprehensive coverageas shown in Figure 3. (b) Perform in-place rotations in multiple di- (a) Use the DWA algorithm to generate a di- rections to ensure comprehensive trajec- rectional control command. tory coverage. Figure 3: Illustrations of the EDWA in action. The first image demonstrates the generation of a directional control command, while the second image showcases the algorithm’s capability to perform in-place rotations in multiple directions, ensuring comprehensive trajectory coverage. The EDWA includes an adaptive sampling strategy specifically designed for narrow environments. Reference points are selected based on the global trajectory, and the lengths of sampled trajectories are adjusted accordingly. This adaptive sampling ensures that the vehicle can navigate tight spaces while maintaining a smooth and efficient path. The sampling trajectory length 𝐿 is defined as: 𝐿 = 𝑓 (𝑑ref , 𝜃ref ) where 𝑑ref is the distance to the reference point and 𝜃ref is the angle to the reference point. Adaptive sampling scale estimation is based on the global trajectory shape, allowing DWA to generate local trajectories that conform to the global path. The trajectory evaluation function in EDWA is designed to consider the global trajectory shape, ensuring that the vehicle’s movements are smooth and closely follow the planned path. This integration of global and local planning improves the vehicle’s ability to navigate complex environments effectively. By combining the Adaptive Hybrid A* Algorithm with the EDWA, our method significantly improves trajectory planning in narrow environments, enhancing safety, efficiency, and path smoothness. 4. Experiment To validate the effectiveness of our proposed adaptive Hybrid A* algorithm with the Enhanced Dynamic Window Approach (DWA), we conducted a series of experiments. These experiments were designed to measure both the computational efficiency and the path planning performance of our algorithm compared to traditional approaches. 4.1. Pruning Efficiency We first evaluated the efficiency of our pruning strategy by measuring the planning time before and after pruning. Efficient pruning is crucial for reducing computational overhead and ensuring the algorithm can operate in real-time scenarios. The results are shown in Table 1. Before Pruning (s) After Pruning (s) Planning Time 13.231000 6.854000 Table 1 Comparison of Planning Time Before and After Pruning The results indicate that our pruning strategy significantly reduces the planning time, almost halving it. This improvement in computational efficiency ensures that the algorithm can quickly adapt to changes in the environment, which is essential for real-time autonomous navigation. 4.2. Path Planning Performance To comprehensively assess the path planning capabilities of our algorithm, we conducted experiments under different scenarios and compared the results with various existing algorithms. The algorithms tested include: • 𝐴* algorithm with an inscribed circle radius expansion map • 𝐴* algorithm with a circumscribed circle radius expansion map • Hybrid 𝐴* algorithm • Our proposed adaptive Hybrid A* algorithm We evaluated these algorithms in two specific scenarios: • Route 1: A path that is actually impassable, containing obstacles that make it non-traversable. • Route 2: A path that is actually passable, designed to test the algorithm’s ability to find a viable route through a complex but navigable environment. The results of these experiments are summarized in Table 2. Algorithm Route 1 (Impassable) Route 2 (Passable) 𝐴* (Inscribed Circle Expansion) Path Found Path Found 𝐴* (Circumscribed Circle Expansion) No Path Found No Path Found Hybrid 𝐴* No Path Found No Path Found Ours No Path Found Path Found Table 2 Summary of Path Planning Results for Different Scenarios and Algorithms. The table shows whether each algorithm was able to find a path in the two test routes: an impassable route (Route 1) and a passable route (Route 2). 4.2.1. Route 1: Impassable Path In Route 1, the path contains obstacles that make it non-traversable. The 𝐴* algorithm with the inscribed circle radius expansion was able to find a path, which indicates that it may not be accurately assessing the impassability of the route. The 𝐴* algorithm with the circumscribed circle radius expansion and the Hybrid 𝐴* algorithm both correctly identified that no path could be planned. Our proposed algorithm also correctly identified that no path could be planned, demonstrating its capability to accurately assess impassable routes and avoid proposing infeasible paths. (a) Path planned by 𝐴* (Inscribed Circle Ex- (b) Path planning by 𝐴* (Inscribed Circle Ex- pansion) for Route 1, which is actually im- pansion) for Route 2, which is actually passable. passable. (c) No path found by 𝐴* (Circumscribed Cir- (d) Failed planned by 𝐴* (Circumscribed Cir- cle Expansion) for Route 1, correctly iden- cle Expansion) for Route 2, which is actu- tifying it. ally passable. (e) No path found by our algorithm for Route (f) Successful path planning by our algorithm 1, accurately assessing it as impassable. for Route2 demonstrating its effectiveness. Figure 4: Path planning results for different algorithms based on various experimental routes, showcasing their effectiveness and limitations. 4.2.2. Route 2: Passable Path In Route 2, the path is designed to be navigable but complex, with narrow passages and sharp turns. The 𝐴* algorithm with the inscribed circle radius expansion and the Hybrid 𝐴* algorithm both failed to find a path, which shows their limitations in dealing with narrow and complex environments. Our proposed algorithm successfully planned a path, indicating its superior ability to navigate through complex but passable environments. 4.2.3. Result analysis As show in figure 4, Experimental results clearly demonstrate the strengths and weaknesses of the differ- ent path planning algorithms. Our proposed algorithm consistently shows its ability to accurately assess impassable routes and effectively navigate passable ones, which is crucial for real-world applications requiring reliable and efficient autonomous navigation in narrow and complex environments. 4.3. Discussion The experimental results validate the enhancements achieved by our adaptive Hybrid A* algorithm with the Enhanced Dynamic Window Approach. The substantial reduction in planning time showcases the efficiency of our pruning strategy. Moreover, the improved path planning accuracy highlights the algorithm’s ability to effectively navigate complex and narrow environments, which is critical for autonomous navigation in real-world scenarios. The significant reduction in planning time, as shown in Table 1, is a direct result of our pruning strategy, which efficiently eliminates less promising paths early in the search process. This improvement ensures that the algorithm remains computationally feasible even in highly dynamic and constrained environments. In terms of path planning performance, our algorithm’s success in the passable route scenario (Route 2) while accurately identifying the impassable route scenario (Route 1) underscores its robustness and reliability. Traditional algorithms either found infeasible paths or failed to find paths in complex environments, whereas our algorithm demonstrated the ability to make precise and feasible path planning decisions. This capability is particularly advantageous for autonomous vehicles and robots operating in tight and cluttered spaces, where accuracy and adaptability are paramount. Overall, these experiments confirm that our proposed approach not only enhances computational efficiency but also significantly improves the accuracy and feasibility of path planning in narrow and complex environments. This makes it a valuable tool for advancing autonomous navigation technologies. 5. Conclusion In this paper, we presented a novel adaptive Hybrid A* algorithm combined with an Enhanced Dynamic Window Approach for optimal trajectory planning in narrow and complex environments. By dynam- ically adjusting search step lengths and integrating a comprehensive reward function, our method enhances the algorithm’s ability to generate trajectories that are more in tune with the dynamics of dif- ferential drive chassis, particularly in narrow passages. This significantly improves both computational efficiency and path planning accuracy. The proposed pruning strategy effectively reduces planning time by nearly half, ensuring that our algorithm can operate in real-time scenarios. This improvement is crucial for applications that require quick and reliable decision-making, such as autonomous driving and robotic navigation. Our experimental results demonstrate the superiority of our method in both impassable and passable route scenarios. Unlike conventional algorithms, our adaptive Hybrid A* algorithm consistently and accurately identifies impassable routes while successfully navigating complex, passable paths. The Enhanced Dynamic Window Approach (EDWA) further complements our approach by refining local trajectory planning through multi-scale path sampling and adaptive evaluation. This ensures smooth and efficient navigation, even in environments with sharp turns and narrow passages. The integration of global and local planning allows our algorithm to maintain trajectory alignment and optimize path smoothness, enhancing the overall safety and efficiency of the navigation process. Our approach offers a robust solution to one of the most pressing challenges in autonomous vehicle and robotics technology today. By combining adaptive search strategies with advanced dynamic window techniques, we pave the way for more sophisticated and reliable autonomous navigation systems. Future work will focus on extending our framework to accommodate a wider range of environmental conditions and further enhancing the adaptability of our algorithm to real-world scenarios. In summary, the adaptive Hybrid A* algorithm with Enhanced Dynamic Window Approach represents a significant advancement in the field of path planning. It not only enhances computational efficiency but also significantly improves the accuracy and feasibility of trajectory planning in narrow and complex environments. This makes it a valuable tool for advancing autonomous navigation technologies, with the potential to impact various applications requiring precise and reliable navigation in constrained spaces. 6. acknowledge This work was supported in part by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant XDA28040500, the National Natural Science Foundation of China under Grant 62261042, the Key Research Projects of the Joint Research Fund for Beijing Natural Science Foundation and the Fengtai Rail Transit Frontier Research Joint Fund under Grant L221003, and the Beijing Natural Science Foundation under Grant 4232035 and 4222034(Corresponding author: Haiyong Luo and Fang Zhao) References [1] J. Lian, W. Ren, D. Yang, L. Li, F. Yu, Trajectory planning for autonomous valet parking in narrow environments with enhanced hybrid a* search and nonlinear optimization, IEEE Transactions on Intelligent Vehicles 8 (2023) 3723–3734. [2] M. Reda, A. Onsy, A. Y. Haikal, A. Ghanbari, Path planning algorithms in the autonomous driving system: A comprehensive review, Robotics and Autonomous Systems 174 (2024) 104630. [3] M. D. Tezerjani, D. Carrillo, D. Qu, S. Dhakal, A. Mirzaeinia, Q. Yang, Real-time motion planning for autonomous vehicles in dynamic environments, arXiv preprint arXiv:2406.02916 (2024). [4] Y. Cao, N. M. Nor, An improved dynamic window approach algorithm for dynamic obstacle avoidance in mobile robot formation, Decision Analytics Journal 11 (2024) 100471. [5] Y. Chen, Z. Li, Formation adaptation in obstacle-cluttered environments via mpc-based trajectory planning, Science China Information Sciences 67 (2024) 174201. [6] G. Borrello, L. Lorusso, M. Basso, A. Acernese, Trajectory planning based on model predictive control with dynamic obstacle avoidance in unstructured environments, in: 2024 European Control Conference (ECC), IEEE, 2024, pp. 448–455. [7] S. Xing, P. Fan, X. Ma, Y. Wang, Research on robot path planning by integrating state-based decision-making a* algorithm and inertial dynamic window approach, Intelligent Service Robotics (2024) 1–14. [8] B. Banday, V. Kasula, N. Surwade, S. R. Nagrare, D. Ghose, Uav path planning for cave exploration using tangent based intersection method, in: AIAA SCITECH 2024 Forum, 2024, p. 1993. [9] S.-A. Abtahi, M. A. Atashgah, B. Tarvirdizadeh, M. Shahbazi, Aerial robotics in urban environments: Optimized path planning and sitl assessments, in: 2023 11th RSI International Conference on Robotics and Mechatronics (ICRoM), IEEE, 2023, pp. 271–278. [10] C. Huang, B. Tang, Z. Guo, Q. Su, J. Gai, Agile-rrt*: A faster and more robust path planner with enhanced initial solution and convergence rate in complex environments, IEEE Access (2024). [11] K. Weerakoon, A. J. Sathyamoorthy, M. Elnoor, D. Manocha, Vapor: Holonomic legged robot navi- gation in outdoor vegetation using offline reinforcement learning, arXiv preprint arXiv:2309.07832 (2023). [12] S. Levit, J. Ortiz-Haro, M. Toussaint, Solving sequential manipulation puzzles by finding easier subproblems, arXiv preprint arXiv:2405.02053 (2024).