Multi-layer Patching Algorithm for Skeleton-based Path Planning

Abstract

This study proposes an optimal path planning algorithm for autonomous mobile robot navigation in a known environment, whereas avoiding possible unknown obstacles. The algorithm incorporating an off-line and an on-line locomotion mechanisms. The off-line path planning is based on skeleton extraction to establish a medial axis graph. With the use of the skeleton graph, the shortest path can be generated. In this study, a multi-layer patching algorithm is proposed to record information required in the on-line stage when unknown obstacles block the pre-determined path. Taking advantages of the Dijkstra’s algorithm and the skeleton graph, the proposed multi-layer patching algorithm is capable of avoiding obstacle and overcoming the local minima problem. From the simulation results, the feasibility of the proposed algorithm is confirmed in several experimental results.