# Fast Path Generation Algorithm for Mobile Robot Navigation Using Hybrid Map
## 2 Related Works
### Path Planning  
The A* algorithm is one of the most widely used path planning algorithms in mobile robotics [32; 33; 34]. It efficiently finds the shortest path by combining the cost from the starting point to a node and an estimated cost from that node to the destination. A major advantage of A* is its ability to guarantee an optimal path if the heuristic is admissible and consistent. Additionally, it is flexible and can be adapted to different environments and constraints by modifying the heuristic function. However, A* can be computationally expensive, especially in large maps with high resolution, as it explores a significant number of nodes. This leads to increased memory usage and slower performance in real-time applications. Moreover, it does not handle dynamic obstacles well, requiring a complete re-computation of the path when the environment changes. Despite its limitations, A* is ideal for static environments where precision and optimality are critical.  
The Rapidly Exploring Random Tree (RRT) algorithm is a sampling-based path planning method that is particularly effective in high-dimensional and complex environments [35]. It generates a path by randomly sampling points in space and incrementally building a tree that connects the robot's starting position to the goal. One of its strengths is its ability to handle non-linear constraints and dynamic environments, making it suitable for real-time applications. Additionally, RRT requires less memory and computational resources compared to grid-based methods like A*. However, the paths generated by RRT are often suboptimal and may require additional post-processing to smoothen them. Furthermore, the randomness of the algorithm can lead to inconsistent results, with the quality of the path depending on the sampling process. Despite these drawbacks, RRT is highly versatile and well suited for navigating in complex or unknown environments.  
The Distance Transform algorithm is a grid-based path planning method that calculates the shortest path by propagating distance values from the destination to the robot's starting position [36]. One of its primary advantages is its simplicity and ease of implementation, making it a popular choice for straightforward environments. Additionally, it generates precise paths by taking the exact geometry of obstacles into account, which is useful for environments with static and well-defined boundaries. The algorithm also guarantees optimal paths in terms of distance when no dynamic changes occur in the environment. However, the Distance Transform algorithm has notable drawbacks. It requires a high-resolution occupancy grid map, which can significantly increase memory consumption and computational load. This makes it less efficient for large or complex environments, particularly when used in real-time applications. Another limitation is its inability to handle dynamic obstacles, as it relies on a pre-generated map. If the environment changes during navigation, the entire path needs to be recalculated, leading to delays. Despite these challenges, the algorithm is well suited for static environments where precision is more important than adaptability.