# Fast Path Generation Algorithm for Mobile Robot Navigation Using Hybrid Map
## 2 Related Works
### Mapping  
Simultaneous Localization and Mapping (SLAM) is a critical algorithm in robotics that enables a robot to build a map of an unknown environment while simultaneously determining its position within it [37]. SLAM integrates sensor data, such as lidar, cameras, or ultrasonic sensors, to create a representation of the environment in real time. A key component of SLAM is solving the data association problem, which involves matchingcurrent sensor observations with previously recorded data to ensure map accuracy. Modern SLAM algorithms leverage techniques like probabilistic methods, such as particle filters or extended Kalman filters, to account for uncertainty in sensor data and robot motion. SLAM is widely used in applications like autonomous vehicles, drones, and mobile robots, where accurate navigation in dynamic environments is essential. Recent advancements in SLAM, including visual SLAM and deep learning-based approaches, have further enhanced its robustness and efficiency in complex and large-scale environments. For an intelligent mobile robot to generate a map on its own, it must utilize the SLAM algorithm. The environment map generated by the SLAM algorithm primarily employs an occupancy grid-type map. Occupancy grid maps are widely used in mobile robots for mission planning and navigation due to their ability to represent an environment with fine-grained spatial details. One key advantage is their flexibility, as they can accurately represent both free spaces and obstacles by dividing the environment into small grid cells. This makes them particularly effective for algorithms that require precise path planning, such as A* or Distance Transform. Additionally, occupancy grids are straightforward to update with new sensor data, allowing for incremental map-building in static or semi-dynamic environments. The occupancy grid method involves dividing the entire target space into a grid and classifying each cell as Free (empty space), Occupied (obstacle), or Unknown (unexplored area). However, there are notable limitations to using occupancy grid maps [38]. High-resolution grids require significant memory, which can be a challenge for embedded systems or robots with limited resources. The computational complexity of processing these maps increases with their size, making real-time performance in large-scale environments difficult to achieve. Moreover, occupancy grids struggle with dynamic obstacles, as constant updates to the grid can be computationally expensive. Another drawback is that these maps often lack higher-level abstraction, such as connectivity or semantic information, which can be useful for long-term planning. Despite these challenges, occupancy grids remain a reliable choice for many robotic applications due to their simplicity and accuracy. Topological decomposition maps are an efficient approach to address some limitations of occupancy grid maps in mobile robot navigation [17; 39]. These maps rely on extracting key environmental features, such as walls, corners, and obstacles, to build a graph-based representation of the environment. One major advantage is their reduced memory requirement, as they do not store fine-grained spatial data but rather abstract connections between significant features. This results in faster computation for path planning, making them ideal for large-scale environments where computational efficiency is critical. Additionally, topological maps simplify navigation tasks by focusing on connectivity between nodes, which ensures that the robot can move along predefined paths with less processing overhead. Despite these advantages, topological decomposition maps have certain limitations. Since they focus on abstract representations, they lack the precision needed to accurately depict the surrounding environment. This can lead to challenges in navigation, especially in tight spaces or areas with complex obstacles.