PDE-Based Path Planning
 |
In robotic navigation, path planning is aimed at getting the optimum collision-free path between a starting and target locations. The planned path is usually decomposed into line segments between ordered sub-goals or way points. In the navigation phase, the robot follows those line segments toward the target. The navigation environment is usually represented in a data structure called the "configuration space. Depending on the surrounding environment and the running conditions, the optimality criterion for the path is determined. For example, in most of indoor navigation environments, the optimum path is the safest one, i.e. being as far as possible from the surrounding obstacles, whereas for outdoor navigation, the shortest path is more recommended. The aim of this project is to compute the collision-free optimum path between a start and a target point in a given navigation map. |
Research Team
Methods
We have developed a general, robust, and fast robotic
path planning framework using level sets [1,2]. The framework can be applied
to both 2D and 3D environments, in a whole configuration space or a portion
of it. Under global safest planning, we compute the entire map centerlines
in the form of a tree graph. The key idea is to propagate from a centerline
point, wave fronts of different speeds. The first front propagates with a
moderate speed to capture the map topology, while the second one propagates
much faster at central points such that centerlines intersect the
propagating fronts at those points of maximum positive curvature, which are
identified by solving an ordinary differential equation (ODE). The motion of
the front is governed by a nonlinear partial differential equation (PDE),
which is efficiently solved using robust level set methods.
Under local safest planning, we propagate a fast front from the starting
point until the target is reached, then identify the path between them by
solving again the same ODE. The speed model of the front is controlled by a
single parameter, which controls the path extraction procedure to be the
safest, the shortest, or even a hybrid path in between. The hybrid path is
safer than the shortest path but less safe than the safest one.
Results
Global Path Planning
Local Path Planning (a) Shortest Path
Local Path Planning (a) Safest Path
Publications
1. Aly A. Farag, M. Sabry Hassouna and Alaa E. Abdel-Hakim “PDE-Based Robust Robotic Navigation,” Proc. 2nd Canadian Conference on Computer and Robot Vision (CRV 2005),Victoria, British Colombia Canada, May 2005, to appear.
2. M. Sabry Hassouna, A.A. Farag, and Alaa Abdel-Hakim, "Robust Robotic Path Planning Using Level Sets," Proc. of IEEE International Conference on Image Processing (ICIP'05), Genova, Italy, September 11-14, 2005, to appear.
Acknowledgement
/ Sponsors