# Global Approach To Potential-Guided Path Planning

## Abstract

This work has been been submitted as a term paper in the course: Robot Motion Planning (ME766, Instructor: Dr. Bhaskar Dasgupta).

In this term paper we attempt to do Path Planning by generating local minima free Potential Function values for given Work-cells. These functions are the solutions of the Laplace's equation and are called harmonic functions. These functions are complete (up to discretization error), analytic and free from spurious local minimas. Though generation of such functions is computationally very expensive, yet they can be used for real time navigation by pre-generating a database of such functions for all possible goal points in a given Workcell.

## Problem Formulation

Potential field methods, introduced by Khatib , are widely used for real time collision free Path Planning. The attraction of a Potential Field method is its being a fastest optimization procedure. However such functions are usually plagued by local minimas. That is the robot may get stuck at a local minima before attaining the goal configuration.

The issue can be addressed at two levels:

1.In definition of potential function by specifying a function with no or few local minima.

2.In the design of search algorithm , by including the appropriate techniques for escaping from local minima

" So the need is to find potential function with no or few local minima and by using it to develop a path planning method"

## Approach

Laplace's Equations, along with appropriate boundary conditions, are solved to get the desired navigation Functions.

### Laplace's Equations:

In 1990 Connolly  proposed the use of local minima free Harmonic Functions for Path Planning .

A harmonic function is on a domain is a function which satisfies the laplace's equations: Harmonic functions satisfy the min-max principle: spontaneous creation of local minima within the region is impossible if laplace's equation is imposed as constraint on the function used.

So if a function satisfies the laplace's equation on some region , then attains its minimum and maximum values only on the boundary of .

Any critical points of the function in the interior of this region must be saddle points, since local extrema of the function are not possible there.

If the effector reaches a saddle point, and it is not near the goal, then there must be a way out. The exit from this critical point can be found out by performing a search in the neighborhood of the critical point.

Though Harmonic Functions are free from local minimas, they are not fully Global. Using the Poincare-Hopf theorem Koditschek  showed that in the presence of C-obstacles, a global navigation function does not exist in general. For a two dimensional C-space with q disjoint C-obstacles, each homeomorphic to a closed unit disc, a potential function U must possess at least q saddle points.

### Boundary Conditions:

Boundary Conditions are required for solving the Laplace's equations. Any of the following two boundary conditions can be used:

#### Dirichlet boundary conditions:

If is the harmonic function and represents the boundary of the C-obstacles, then the Dirichlet boundary condition is: where c is a constant. In this case the boundary is held fixed at a particular potential. Since the boundary conditions are fixed, the flow must be along the outward normal of the obstacle surface. The gradient of the harmonic solution, therefore, tends to depart from C-space obstacle boundaries.

#### Neumann boundary conditions:

Neumann boundary conditions are described by: where c is a constant and is usually fixed to 0 so that the flow is tangential to the obstacle. But the tangential-flow behavior exhibited by a Neumann solution can result in a tendency for a robot to stay close to C-space obstacle surfaces.

#### Superposition of two boundary conditions:

If f d represents the solution obtained from Dirichlet boundary conditions and f n represents the solution obtained from Neumann boundary conditions, then a new harmonic function can be constructed by taking the linear combination of the two: ,

where k [0, 1]. This composition preserves the harmonic solutions to obtain a harmonic constraint and therefore guarantees no local minima and collision-free paths.

If k < 0.5, then shallow gradients found in the Dirichlet solution can be avoided.

If a path between the current state and the goal exists, then it will be found using this formulation.

## Implementation

### Method to solve Laplace's equation:

Numerical solutions for laplace's equation have been obtained from finite difference methods. Let be the function which satisfies the , and let represent a discrete regular sampling of on a grid. A central difference formula for the second derivatives of are:  where : step size in x-direction and, : step size in y-direction.

This is a second order accurate scheme.

If = = h then laplace's equation in discrete form: The easiest way to solve a laplace's equation is to solve another equation which give the same solution at the steady state. We use a "parabolic type equation" :

(for Laplace's equation)

This is an unsteady analog which gives the as the steady state.

Finite difference in time/central difference in space: For = and using the condition for "numerical stability" i.e. Using this condition we get which gives So we start from some arbitrary initial field and time step according to the formula for finding the interior points.

### For the boundary points:

At this point we use the two boundary conditions (Dirichlet boundary condition and Neumann boundary condition) as discussed previously to specify the 'u' value at boundary points at each time step.

### Algorithm :

1. Assume a field and the initial values of at each of the node points.

2. Using formula we get the values at each interior points.

3.Using boundary conditions we get the values at each boundary point.

4. If || - || < = , STOP (where )

Else = and GO TO step-2

This method is easily extendable to 3-D and higher dimensions.

Once the array u has been computed to necessary precision, path can be computed simply by following the gradient from the starting point. The path must end at the goal point (or set) .

## Results: PROBLEM-1 (IN 2-D) Using Dirichlet Boundary Condition
(Grid Size=100x100 , Sink f =-108 , Boundary f = 1)
( Accuracy = 10-4 , Total Iterations = 647 ) PROBLEM-1 (IN 2-D) Using Neumann Boundary Condition
(Grid Size=100x100 , Sink f =-0.5 )
( Accuracy = 10-6 , Total Iterations =7485 ) PROBLEM-2 (IN 2-D) Using Dirichlet Boundary Condition
(Grid Size=100x100 , Sink f =-108, Boundary f = 1)
( Accuracy = 10-5 , Total Iterations = 573 ) PROBLEM-2 (IN 3-D) Using Dirichlet Boundary Condition
(Grid Size=100x100x100, Sink f =-108, Boundary f = 1)
( Accuracy = 10-5 , Total Iterations = 1278 ) PROBLEM-2 (IN 3-D) PROJECTION IN Y-Z PLANE PROBLEM-2 (IN 3-D) PROJECTION IN X-Y PLANE PROBLEM-1 (IN 3-D) Using Dirichlet Boundary Condition
(Grid Size=100x100x100 , Sink f =-108, Boundary f = 1)
(Accuracy = 10-6 , Total Iterations = 2138) PROBLEM-1 (IN 3-D) PROJECTION IN X-Z PLANE PROBLEM-1 (IN 3-D) PROJECTION IN X-Y PLANE

## Inferences

Harmonic functions worked out for the cases shown, were free from local minimas. All paths starting from the initial point led to the goal point. However following problems were observed while working out the cases shown:

• As compared to other Potential field methods, this is computationally very expensive, and becomes unmanageable for larger grid size and higher dimension. It took hours to get results for the 3-D cases.

• In the case of Dirichlet boundary conditions, many patches with nearly zero values of |Ñ f | were found in the Cfree as seen the following f (harmonic solution from laplace's equation) plot for thfirst 2-D case shown in the results. While Neumann conditions give better navigation functions as is clear from the following plot of f for the same case: • Neumann boundary conditions causes the robot to graze past the obstacles in their way to the goal (as shown in Results: Problem 1, Neumann boundary conditions).

• Inspite of the above problem, for higher dimensions and higher grid size, Dirichlet boundary conditions give more convincing results than Neumann boundary conditions.

## Conclusion

Though free from local minimas, the charm of such potential functions would be lost if its computation cost hinders its on-line application. However one can see that for a given configuration space and a goal point, harmonic functions are same for all starting points in the configuration space. This fact can be used for online navigation. For this one has to maintain a database of harmonic functions for all possible goal points. Thus during navigation, when the goal point is usually fixed, one can initially(when the goal point is set) access the harmonic function corresponding to that goal point from the database and use it throughout to navigate from any point in the C-space to the goal point using a steepest descent search routine.

## References

1. Khatib, O. Real-time obstacle avoidance for manipulators and mobile robots. Int. Journal of Robotics Research, 5(1), 90-98 ,1986.

2. Connolly C.I., J. B. Burns and R. Weiss. Path Planning Using Laplace?s Equation. In the proceedings of the 1990 IEEE Robotics and Automation Conference, 2102-2106.

3. Koditschek, D.E. Exact Robot Navigation by Means of Potential functions. In the proceedings of the 1987 IEEE Robotics and Automation Conference, 1-6.

4. Connolly C.I. Applications of Harmonic Functions to Robotics. In proceedings of the 1992 International Symposium on Intelligent Control, March 26,1992.

5. Analogue computation of collision-free paths. In the proceedings of the 1991 IEEE Robotics and Automation Conference, April 1991.
6. Latombe J.C. Robot Motion Planning. Kluwer Academic Publications, 1991.

mitul@robotics.stanford.edu