A quadtree‐based path‐planning algorithm for a mobile robot

Abstract To enable a mobile robot to select automatically a collision‐free path in a given workspace, design of a path‐planning algorithm which must work efficiently in real‐time is crucial. This article proposes a path‐planning algorithm that selects a reasonable collision‐free path tying start and goal points out of a quadtree representation of the robot workspace. The quadtree is obtained from fast conversion of a real image taken through a camera on the ceiling. It represents obstacles and their allocation in the workspace in good time and hence the algorithm is able to find a collision‐free path while following the change of obstacles and their allocation. The algorithm is designed on the basis of “small‐is‐quick” principle. That is, the smaller a search space of the algorithm is, the faster the algorithm selects the shortest path out of the search space. To put the principle in practice, the algorithm investigates a path graph instead of the quadtree while spreading the path graph on the quadtree as small as possible, and selects fast the shortest collision‐free path out of the path graph as a reasonable collision‐free path. Thus the algorithm fulfils its function fast even in a workspace that has a number of obstacles with complicated shape. In comparison with several conventional path‐planning algorithms presented so far, it is shown from experimental results that the proposed algorithm selects faster a reasonable collision‐free robot path than others.