A FAST PATH-PLANNING ALGORITHM BY SYNCHRONIZING MODIFICATION AND SEARCH OF ITS PATH GRAPH

摘要

Determination of the shortest collision- free path for a mobile robot between start and goal positions in a workspace is central to design of an autonomous mobile robot. This paper presents a feasible path-planning algorithm which runs on the quadtree representation via a path graph. The quadtree representing the workspace is obtained from fast conversion of a real image taken through a camera on the ceiling. Thus, the algorithm can run even when obstacles in the workspace are shifted frequently. The quadtree also integrates both obstacle regions and other regions in the workspace with a hierarchical structure in positioning. By using the hierarchical structure, the mobile robot is reduced to a point and then the forbidden regions where the point robot cannot enter into are also understood in the quadtree. Hence, the algorithm can select the shortest collision-free path out of the quadtree, which is to be a line between given two positions. Moreover, the algorithm searches in the quadtree by way of a path graph when it selects the shortest collision-free line out of the quadtree. Namely, the path graph is initially defined by an arc with start and goal position's nodes, and the proposed algorithm gradually builds the path graph on the quadtree by the following processes synchronously: 1) Selection of the shortest path out of the path graph; and 2) Expansion of a part of the path graph along the shortest path so as to avoid the forbidden regions in the quadtree. By this synchronism, the algorithm can keep the size of the path graph as small as possible in connection with given two positions, and consequently it runs fast enough to be used practically even in any cluttered workspace. Finally, several experimental results show that the proposed algorithm is superior to some conventional algorithms in respect of calculation time.