|
People:
Moslem Kazemi (moslemk@sfu.ca) and
Mehran Mehrandezh (mehran.mehrandezh@uregina.ca)
A new
hybrid robot path 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 the Potential Field (PF) approach
based on HFs (known as harmonic potential fields). The crux of our
approach is to identify narrow passages using HFs and pass them over to
a PRM-like method to build a roadmap which efficiently captures the
connectivity of 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 ([1]) where HFs are computed over the explicit representation
of the robot's C-space, and (2) the Incremental HFPRM (IHFPRM) technique
([2]), as an extension of the original HFPRM, where no explicit
representation of the C-space is required.
Original HFPRM Technique
The HFPRM technique comprises three phases: in
phase one, the Laplace's equation, pertinent to the potential flow, in
an environment cluttered with obstacles is solved. In phase two, a PRM
with a novel sampling scheme is constructed based on the information
obtained about the environment topology through the HF technique
developed in phase one. The roadmap is then searched for the shortest
path connecting the start and goal configurations in phase three.
Promising results are obtained using this technique for solving
shortest-path problem in difficult scenarios. For more details one can
refer to [1].
Incremental HFPRM Technique
The IHFPRM technique works as follows: first a
roadmap is initialized in robot's C-space by generating a pre-defined
number of random nodes (the start and the goal configurations included).
The neighboring nodes are then connected via straight lines. The metric
used is the Euclidean distance. Then in an iterative scheme the roadmap
is enhanced and searched for the shortest path. At each iteration the
Laplace's equation, pertinent to potential flow, is solved over the
current representation of the C-space using Finite Element Method (FEM)
and the velocity of the flow is calculated at each node of the roadmap.
The roadmap is then enhanced using a new, yet simple, random sampling
scheme based on information obtained about the C-space topology with a
{\it velocity thresholding} technique. This yields a roadmap with better
coverage in regions associated with higher velocities (i.e. narrow
regions). At the final stage the roadmap is searched by a local planner
for the shortest path connecting the start and the goal configurations.
The enhancement ends either after a maximum number of iterations has
been reached or a collision-free path has been found. For more details
one can refer to [2].
Inspired
by the promising results obtained through the original HFPRM and
incremental update of it, we present a sensor-based motion planning
technique for mobile robot navigation in environments not known a priori
([3]). The main idea of the proposed technique is to utilize the
information obtained through the HFs to prioritize different regions in
the workspace at the scan planning stage of a sensor-based PRM. The
proposed technique was implemented to navigate a real mobile robot in
environments not known a priori.
For more details one can refer to [3].
Related Publications
[1] Robotic Navigation Using Harmonic Function-based Probabilistic Roadmaps
M. kazemi, M. Mehrandezh
Proceedings of IEEE International Conference on Robotics and Automation (ICRA)
New Orleans, LA, Apr. 2004, pp. 4765-4770.
[2] An Incremental Harmonic Function-based Probabilistic Roadmap Approach to Robot Path Planning
M. Kazemi, M. Mehrandezh, K, Gupta
Proceedings of IEEE International Conference on Robotics and Automation (ICRA)
Barcelona, Spain, Apr. 2005, pp. 2148-2153
[3] Sensor-based Robot Path Planning Using Harmonic Function-based Probabilistic Roadmaps
M. Kazemi, M. Mehrandezh, K. Gupta
Proceedings of International Conference on Advanced Robotics (ICAR)
Seattle, WA, USA, July 2005, pp.84-89
[4] Robot Path Planning Using Harmonic Function-based Probabilistic Roadmaps
M. Kazemi, M. Mehrandezh, K. Gupta
Journal paper in prepration
|