Potential Fields
Colin Green (cjgreen@cmu.edu)
16-735
HW3 - 9/25/2006
The Matlab implementation of this assignment can be found here.
Movies: (You might need to save these to disk before playing them)
Success - 2D 3D
Failure - 2D 3D
Just as for assignment 2, my world consists of obstacles constructed
from lines. The obstacles are all defined by points running clockwise
forming a closed chain. See the include createWorld.m file for a
convenient method of creating new world (instructions included
previously here).
I implemented the attractive repulsive potential field as described in the class textbook (Principles of Robot Motion: Theory, Algorithms, and Implementations
- Howie Choset, et al.) in section 4.1. The potential field consists of
an attractive function pulling towards the goal and a repulsive
function pushing away from obstacles. The attractive field is equation
4.2 in the book and is basically linear in distance when far from the
goal and quadratic in distance close to the goal.
The repulsive function is computed by finding the closest point on each
obstacle. This is typically one minimum per obstacle for convex
obstacles, and multiple minimum for non-convex obstacles (each face of
a non-convex obstacle is considered as a separate obstacle when inside
the obstacle). A field is computed for each of these points by using
equation 4.5 from the book. These were founding using the technique
discussed in class for finding the distance between a point and a
polygon.
The gradient of the potential function is computed numerically (I was
computing it closed form, but I was trying a few different things with
the potential function and it was too much trouble to compute the
direction by hand). The algorithm then simply follows the negative
gradient, taking small steps until a minimum is reached. If it
terminates at the goal then the planning was a success. Otherwise it
was a failure.
I tried a few different things with the potential field, to improve its
success rate. One interesting improvement I made was to try to improve
the distance estimate by not just using the strait line distance to
goal. Instead I estimated the distance to goal by looking at whether
the path between the current location and the goal intersected an
obstacle. If it did, I included in its distance estimate to cost of
traveling along the boundary of that obstacle until the path to the
goal was once again clear then continuing to the goal from there. This
is not done recursively for future obstacle intersections. This is
something like the bug algorithms (basically a slight modification of
part of the bug2 algorithm, so it might be consisted cheating (the
potential field is no longer a mathematical function at this point),
but its fun none the less. This has the effect of allowing the
potential field to increase as it approaches a non-convex obstacle.
Although it does not allow the potential inside of a non-convex
obstacle to decrease as it exits the obstacle (as shown in the move
below).
Movies:
Success - 2D 3D
Failure - 2D 3D