Real-time path planning in a dynamic 3-D environment

Abstract

We propose a real-time algorithm for path planning in a dynamically changing 3-D environment where the motion of the obstacles cannot be predicted. The method represents everything in the environment (an arbitrarily shaped robot and static/dynamic obstacles) with an octree that makes no distinction of the movability of objects. A collision free path for a robot with arbitrary motion (translation and rotation) in a dynamic 3-D environment is efficiently sought by using the real-time A* algorithm and the potential field generated from each black cell of the octree. Parallel computation is used to speed up the generation of the potential field. Finally, the experimental results demonstrate the efficiency of the proposed path planning method for a dynamically-changing 3-D environment with arbitrary motion.