PDE-Based Path Planning

Introduction:

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.

Goal:

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.

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, (b) Safest Path

Research Team:

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:

We would like to thank the US-Army for their sponsorship.


News