Here's homework #3

You can find the source code here, 
and it's zipped up with the necessary make files here.
(The links to the source codes are temporarily disconnected from this page.)

i'll start with the eye candy:

Successfull planning MOVIE.
MOVIE of a failure due to a local minima.


SUCCESS!

Darker pixels have lower value, brighter pixels have higher value.  50% size images. Full size here.
I like how it avoids the obstacle corner right near the goal.


Implementation steps:
1. Create a world with obstacles, start, and goal position
2. Discretize the world into a 400 x 400 cell grid (1 px per grid, color representing the value)
3. Create 5 400 x 400 grids, ObstacleGird, BrushFireGrid, DistanceGrid, PotentialFnGrid, and PathGrid.
4. Fill the ObstacleGrid pixels which lie in the obstacles with "1", others with zero.
5. Copy this grid and do a cutom written "brushfire()" to get the BrushFireGrid (distance to nearest obstacle).
6. Check each cell in the DistanceGrid for the (Euclidean) distance to goal and store that value in each cell
7. Create a total Potential Function from the BrushFireGrid and DistanceGrid
     - PotentialFnGrid.value[xx][yy] = P * DistanceGrid.value[xx][yy] + N * Math.pow((1/obstaclesGrid.value[xx][yy]),3)
     - The constants P,N should be tweaked so that the path doesn't pass through obstacles
     - I ended up using P = 20, N = 1000000 to really avoid going into obstacles, but is pulled toward the goal enough.
     - I also used (1/obstacle distance) to the power 3 to make the effect fall off quickly from the obstacles
8. Do an 8-cell gradient descent from the start to the goal on the PotentialFnGrid.
		 - Fill in the current cell before moving on.
		 - Terminate when all nearest neighbors have a greater value than the current cell.  (local minimum)

9.  Maybe you made it, maybe you didn't.

You can see that the potential function does a good job of making the obstacles very 'negatively charged', their
borders are bright red in the total potential function images.  The total potential function is close to zero near the goal.


FAILURE! - Terminate in a local minimum

Darker pixels have lower value, brighter pixels have higher value. 50% size images.  full size here.

This was way too easy to encounter (this isn't a very successful path planner).


Mike Murphy