An efficient, hierarchical, two-dimensional (2D) path-planning method for large complex environments is presented in this paper. For mobile robots moving in 2D environments, conventional path-planning algorithms employ single-layered maps; the proposed approach engages in hierarchical inter- and intra-regional searches. A navigable graph of an environment is constructed using segmented local grid maps and safe junction nodes. An inter-regional path is obtained using the navigable graph and a graph-search algorithm. A skeletonization-informed rapidly exploring random tree* (SIRRT*) efficiently computes converged intra-regional paths for each map segment. The sampling process of the proposed hierarchical path-planning algorithm is locally conducted only in the start and goal regions, whereas the conventional path-planning should process the sampling over the entire environment. The entire path from the start position to the goal position can be achieved more quickly and more robustly using the hierarchical approach than the conventional single-layered method. The performance of the hierarchical path-planning is analyzed using a publicly available benchmark environment.
This paper presents an efficient revisiting algorithm for landmark-based simultaneous localization and mapping (SLAM). To reduce SLAM uncertainty in terms of a robot’s pose and landmark positions, the method autonomously evaluates valuable landmarks for the data associations in the SLAM algorithm and selects positions to revisit by considering both landmark visibility and sensor measurement uncertainty. The optimal path among the selected positions is obtained by applying the traveling salesman problem (TSP) algorithm. To plan a path that reduces overall uncertainty, the cost matrix associated with the change in covariance between all selected positions of all pairs is applied for the TSP algorithm. From simulations, it is verified that the proposed method efficiently reduces and maintains SLAM uncertainty at the low level compared to the backtracking method.