Robotic navigation using harmonic function-based probabilistic roadmaps

A new hybrid motion planning approach based on Harmonic Functions (HF) and Probabilistic Roadmaps (PRM) is presented. The proposed approach consists of building a Probabilistic Roadmap using information obtained about the workspace topology through a Fluid Dynamic (FD) paradigm based on HFs. The crux of our approach is to identify narrow passages using a FD paradigm and pass them over to a PRM method to build a roadmap that efficiently captures the connectivity of the free configuration space (C-space) especially in narrow regions. We present two techniques to implement the proposed approach: (1) the original Harmonic Function-based Probabilistic Roadmap (HFPRM) technique where HFs are computed over the explicit representation of the robot's C-space, and (2) the Incremental HFPRM (IHFPRM) technique which is an extension of the original HFPRM, and can be applied to virtually any type of robot. Simulation results obtained using these techniques show that the combination of the HF and the PRM works better than each individual in terms of finding a collision free path in environments where narrow passages exist. Inspired by the promising results obtained through the original HFPRM and incremental update of it, we also present a sensor-based motion planning technique for robotic navigation in environments not known a priori. Experimental results obtained using this technique for a mobile robot equipped with ultrasonic range finders moving in an unknown environment are also presented.