Efficient collision-free paths in an uncertain dynamic environment
Jay Mookherje · 1996
Path planning deals with moving a given three dimensional object from a given initial configuration to a desired final configuration. Given a set of objects with their initial locations and their goal locations, a set of static obstacles, and a set of dynamic obstacles moving arbitrarily in a three-dimensional space, the problem is to find an optimal continuous path for each object from its initial position to its goal position without colliding with obstacles and other objects along the way. This problem of searching for an optimal collision-free path of moving objects has been shown to be NP complete. In this dissertation a real time solution has been obtained by grouping obstacles into clusters, approximating three dimensional objects to two dimensional projections, and using heuristic search strategies. An efficient data structure is designed to enhance the process of interference detection among these objects and between objects and other unpredictably moving obstacles. Each object computes its own static path which avoids collisions with only static obstacles. Each object then follows its own static path until there is a chance of a collision with a dynamic obstacle or another object, whence local path planning is invoked to maneuver that object without collision. The system has been implemented on Silicon Graphics IRIX platform. The performance of the system has been studied and the experimental results are presented.