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. >

Authors

• Kikuo Fujimura
• Hanan Samet

Keywords

• Path planning
• Indexing
• Mobile robots
• Navigation
• Acceleration
• Computer science
• Robotics and automation
• Educational institutions
• Spatial indexes
• Computer simulation
• Spatial Index
• Centrifugal Force
• Mobile Robot
• Two-dimensional Plane
• Acceleration Range
• Temporal Dimension
• Search Space
• Points In Space
• Constant Speed
• Polyhedral
• Velocity Values
• Third Dimension
• Current Point
• Search Procedure
• Robot Motion
• Collision Detection
• Acceleration Values
• Three-dimensional Objects
• Part Of Trajectory
• Velocity Of The Robot
• Collision-free Path
• Tree Index
• Destination Point
• Goal Position
• Time-varying Environment
• Optimal Path
• Start Position