|
Ross Hatton
September 24, 2007
The robot is attracted to the goal by a conic/parabolic potential function and pushed away from the obstacle by an inverse-distance potential function. At each time step, the vector sum of the two potentials is calculated, then normalized to generate a direction vector for the robot to follow. The robot then takes a step along this direction vector by a predetermined step size or by the magnitude of the original vector sum, whichever is smaller. The program ends when the robot has either reached the goal or has determined that it is either not moving or is chattering between a small number of states.
Distance and direction to the nearest point on the obstacle is determined by first finding the nearest vertex on the obstacle, then finding the closest point on the two edge segments touching that vertex (which are highlighted in red in the movies). A sufficiently thin object will foil this strategy if the robot approaches it from a long, flat, side which has a vertex from the opposite side near its midpoint, but this weakness could be avoided by searching a larger set of line segments for the nearest point.
For each line segment checked, the robot's position is tested for being outside from that line segment and inside from the two neighboring segments. If this condition is met, the robot's position is projected orthogonally onto the line segment, generating the closest point on the obstacle to the robot. If this condition is not met for either of the tested line segments, then the closest point is deemed to be the vertex between them.
Function list:
end+1 is equivalent to 1.