Path planning among moving obstacles using spatial indexing

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, a path is generated for a mobile robot that navigates in the two-dimensional plane. Time is included as one of the dimensions of the model world. This allows the moving obstacles to be regarded as stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles and must navigate within the predetermined range of velocity, acceleration, and centrifugal force. A spatial index is used to facilitate geometric search for the path-planning task. Computer simulation results are presented to illustrate the feasibility of this approach