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 diferential drive models. This method enhances the algorithm's ability to generate trajectories that are more in tune with the dynamics of diferential drive chassis, particularly in narrow passages. Here, the algorithm adaptively transitions between hybrid A* and traditional A* strategies, utilizing variable search step lengths to efectively balance precision and computational eficiency. 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 efectively navigate complex environments with sharp turns. Simulation results demonstrate the efectiveness and superiority of our proposed algorithms in managing narrow path navigation. The improved hybrid A* and DWA algorithms notably enhance safety, eficiency, and trajectory smoothness, showing significant advancements over traditional methods.
In the field of autonomous navigation, eficient trajectory planning in narrow environments remains
one of the most challenging tasks, demanding high levels of precision and adaptability from path
planning algorithms [
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
and adjust to obstacles dynamically is crucial. Moreover, the A* algorithm’s heuristic nature does not
inherently account for the kinematic constraints of diferent 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 [
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, eficiency, 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 diferent 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 diferential 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 eficiency 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 eficiency.
To ensure efective alignment between the model’s dynamically generated trajectory and the
preplanned trajectory during operation, we have implemented an Enhanced Dynamic Window Approach,
which generates control commands based on the trajectory to navigate complex environments more
efectively [
By integrating these advanced techniques, our approach significantly outperforms traditional path planning methods in terms of safety, eficiency, and adaptability in narrow environments. The combination of adaptive Hybrid A* and EDWA represents a substantial step forward in the field of robotic navigation, ofering 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 demonstrate their superiority, paving the way for more sophisticated and reliable autonomous navigation systems.
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, eficiency, and adaptability of navigation algorithms. However, several limitations remain in these methods.
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 [
In contrast, our adaptive search method within the Hybrid A* framework dynamically adjusts search step lengths based on environmental constraints, balancing precision and computational eficiency. Our novel reward function integrates multiple cost factors, optimizing the path for both safety and eficiency, thus addressing the computational and real-time adaptability limitations of traditional MPC and hybrid algorithms.
The Dynamic Window Approach (DWA) has been widely utilized for local trajectory optimization. Cao
and Nor [
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.
The combination of sampling-based methods and reinforcement learning has shown promise for narrow
passage problems. Huang et al. [
Our approach combines Hybrid A* and EDWA, improving initial solution quality and convergence rate while reducing computational costs. Our reward function enhances adaptability and eficiency without relying heavily on pre-trained models, addressing the limitations of traditional sampling-based methods.
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 diferential drive model’s capabilities to ensure eficient 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 eficient path planning.
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 eficiency in constrained environments, a feature crucial for diferential 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 efective 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:
Node Extension Node Evaluation Pruning Strategy
Trajectory Sampling
Adaptive Sampling
Scale Estimate
Trajectory Evaluation • () 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.
The EDWA refines local trajectory planning through multi-scale path sampling and adaptive evaluation. Initially, trajectory sampling is performed for diferent 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.
(a) Use the DWA algorithm to generate a directional control command.
(b) Perform in-place rotations in multiple directions to ensure 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 eficient 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 efectively.
By combining the Adaptive Hybrid A* Algorithm with the EDWA, our method significantly improves trajectory planning in narrow environments, enhancing safety, eficiency, and path smoothness.
To validate the efectiveness 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 eficiency and the path planning performance of our algorithm compared to traditional approaches.
We first evaluated the eficiency of our pruning strategy by measuring the planning time before and after pruning. Eficient pruning is crucial for reducing computational overhead and ensuring the algorithm can operate in real-time scenarios. The results are shown in Table 1.
Planning Time
Before Pruning (s) 13.231000
After Pruning (s) 6.854000
The results indicate that our pruning strategy significantly reduces the planning time, almost halving it. This improvement in computational eficiency ensures that the algorithm can quickly adapt to changes in the environment, which is essential for real-time autonomous navigation.
To comprehensively assess the path planning capabilities of our algorithm, we conducted experiments under diferent 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 * (Inscribed Circle Expansion) * (Circumscribed Circle Expansion) Hybrid * Ours
Route 1 (Impassable) Path Found No Path Found No Path Found No Path Found
Route 2 (Passable) Path Found No Path Found No Path Found Path Found 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 Expansion) 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 Circle Expansion) for Route 1, correctly iden- cle Expansion) for Route 2, which is actutifying 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 efectiveness. 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 diferent path planning algorithms. Our proposed algorithm consistently shows its ability to accurately assess impassable routes and efectively navigate passable ones, which is crucial for real-world applications requiring reliable and eficient autonomous navigation in narrow and complex environments.
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 eficiency of our pruning strategy. Moreover, the improved path planning accuracy highlights the algorithm’s ability to efectively 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 eficiently 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 eficiency 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.
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 dynamically 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 differential drive chassis, particularly in narrow passages. This significantly improves both computational eficiency and path planning accuracy.
The proposed pruning strategy efectively 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 eficient 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 eficiency of the navigation process.
Our approach ofers 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 eficiency 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.
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)