Motion Planning HW #3
Due : Sept/24/2007
Problem
For a two-dimensional configuration space, implement the attractive/repulsive potential function of your choice.
On your web page, show at least two movies - one that illustrates a successful planning episode, and one that fails due to local minima. Include on your web page a brief description (pdf file or html ONLY) of your approach. This report should include all relevant equations and algorithm descriptions, along with a description of any parameters used by your algorithm.
In addition to the required explanations, explain why you chose this particular potential function algorithm.
Solution
I implemented the algorithm which has attraction/repulsive potential function.
Workspace Description : Workspace has 2-Dimension and bug has 2 DOF which is position.
- Algorithm details
Potential function algorithm consists of two functions which are attractive function and repulsive function. Attractive function describes configuration of current position with respect to goal position. In constrast, repulsive function is about how far away from obstacles. Thus the sum of two function stands for how the altitude of geometry of workspace looks like.
- Attractive potential function
this attractive potential function field is composed of conic and quadratic potentials because the needed velocity around goal and far away from goal is a little different. Conic potential attracts the robot when it is very distance from q_goal and quadratic potential attracts near the q_goal. If quadratic potential attracts where very distant from q_goal may cause too large velocity. On the other hand, if the conic function attracts near goal the gradient vector can't be defined where very close around q_goal. From the potential function the gradient vector field is expressed as below
The potential function around threshold is defined as being continuous with respect to gradient field as well as itself.
- Repulsive potential function
The repulsive potential function also contains two parts which are devieded by threshold of distance from obstacles. If the distance from obstacles are larger than threshold, then there is no effect of obstacles to the robot. However, if the distance is shorter than threshold which stands for the obstacles are in sensory range of the robot, the repulsive value of potential function increase highly proportional to inverse of distance. The closer to obstacle, the large value of potential function which means, the direction of gradient vector tends to indicate highly to the obstacle. Thus, since the robot follows direction of negated gradient vector, the robot tends to avoid the obstacle automatically.
These potential functions does not guarantee absense of local minima because sometimes, the value of attractive function and repulsive function balance which leads to zero gradient vector(no direction). So it falls in local minima which makes result as mission failure. Following examples describe the successful access to goal and failure of the algorithm.
In my algorithm, I set the gain of attractive function and repulsive as 100 and 0.0001 correspondingly, say zeta = 100, eta = 0.0001. These gains are obtained by several numerical verification using MATLAB. These gains depends on user preference and workspace unit. Since the range of my workspace is from zero to one, in near of obstacle, the value of one over distance is really large so gain should be lessen as much as balancing with attractive gradient vector.
Please note the velocity of robot when the robot approaches to the local minima, because near the local minima, the magnitude of gradient vector field is quite small so that the velocity of the robot becomes slow. This also happens near goal because the slope of quadratic function is getting smaller comparing with distant from goal position.
- Closest point of obstacle to the robot.
In order to measure the distance from the robot and obstacles, the closest point of obstacle to the robot should be well defined. I used to normal vector which perpendicular to the closest each of line of polygon shown in below and also discussed in class
.
Eventually the robot finds out where the closest point is and based on these data, it computes the gradient vector. In the case of several ranges overlaped(if the obstacle is concave or there are adjacent two obstacles), the robot superpositions the corresponding gradient vectors.
The reason why I choose this potential function to generate negated gradient motion was this is very straightforward and has exactly analytic form of gradient vector. In many cases, the potential functions are described in discretized workspace so that the gradient motion cannot be analytic form but searching unit of neighbor of current position which is quite numerical. Using numerical way may takes a lot of time to compute at each single step in MATLAB. So I left it as a future work.
- Future works
There are several ways of constructing potential field such as Brushfire algorithm. Also I read paper by preparing paper presentation, which explains how to construct local minimum free workspace. Also there are several ways to escape from local minima. In spite of complexity of these methods, local minima free potential function in workspace should be built. Furthermore, in realistic sense, discretized workspace algorithm should be accomplished.
- Reference
H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun,
Principles of Robot Motion: Theory, Algorithms, and Implementations,
MIT Press, Boston, 2005.