A feasible motion-planning algorithm for a mobile robot based on a quadtree representation

A motion-planning algorithm is proposed which fulfils its function fast even if shapes of the robot and its obstacles are complicated. Considering the global obstacle allocation in the robot workspace, the proposed algorithm selects intermediate positions where the mobile robot should pass from a start position to a goal position. Using a systematic motion generation method based on the closest points between the robot and its obstacles, the algorithm generated collision-free robot motions to joint the intermediate positions successively. The algorithm runs on the quadtree representation, obtained from fast conversion of a real image taken through a camera on the ceiling of the workspace. The algorithm can generate collision-free motions while following a change of obstacle allocation. In a comparison with several motion-planning algorithms, it is shown that the proposed algorithm generates fast collision-free robot motions