Dynamic path planning

Abstract

Path planning is dynamic when the path is continually recomputed as more information becomes available. A computational framework for dynamic path planning is proposed which has the ability to provide navigational directions during the computation of the plan. Path planning is performed using a potential field approach. We use a specific type of potential function-a harmonic function-which has no local minima. The implementation is parallel and consists of a collection of communicating processes, across a network of SPARC & SGI workstations using a message passing software package called PVM. The computation of the plan is performed independently of the execution of the plan. A hierarchical coarse-to-fine procedure is used to guarantee a correct control strategy at the expense of accuracy. We have successfully navigated a Nomad robot around our lab space with no a priori map in real-time. The result of the described approach is a parallel implementation which permits dynamic path planning using available processor resources.