A hierarchical strategy for path planning among moving obstacles

Abstract

Absrracr-A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, we focus on generating a path for a mobile robot that navigates in the twodimensional plane. Our methodology is to include time as one of the dimensions of the model world. This allows us to regard the moving obstacles as being stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles, and, also, it must navigate without exceeding the predetermined range of velocity, acceleration, and centrifugal force. We investigate an appropriate model to represent the extended world for the path planning task, and give a time-optimal solution using this model.