5

I have some time occupying myself with motion planning for robots, and have for some time wanted to explore the possibility of improving the opportunities as "potential field" method offers. My challenge is to avoid that the robot gets trapped in "local minimum" when using the "potential field" method. Instead of using a "random walk" approach to avoid that the robot gets trapped I have thought about whether it is possible to implement a variation of A* which could act as a sort of guide for precisely to avoid that the robot gets trapped in "local minimum".

Is there some of the experiences of this kind, or can refer to literature, which avoids local minimum in a more effective way than the one used in the "random walk" approach.

Jon Seigel
  • 12,251
  • 8
  • 58
  • 92
nesmoht
  • 125
  • 8

2 Answers2

5

A* and potential fields are all search strategies. The problem you are experiencing is that some search strategies are more "greedy" than others, and more often than not, algorithms that are too greedy get trapped in local minimum.

There are some alternatives where the tension between greediness (the main cause of getting trapped on local minimum) and diversity (trying new alternatives that don't seem to be a good choice in the short term) are parameterized.

A few years ago I've researched a bit about ant algorithms (search for Marco Dorigo, ACS, ACO) and they have a family of search algorithms that can be applied to pretty much anything, and they can control the greediness vs. exploration of your search space. In one of their papers, they even compared the search performance solving the TSP (the canonical traveling salesman problem) using genetic algorithms, simulated annealing and others. Ant won.

I've solved the TSP in the past using genetic algorithms and I still have the source code in delphi if you like.

Padu Merloti
  • 3,219
  • 3
  • 33
  • 44
  • I would very much like to see your code, and if you have some text about the approach you use in your code - it would be really good so I can get a better understanding of your solution to the TSP. My email is nesmoht"at sign"gmail.dk - thanks ... – nesmoht Feb 05 '10 at 08:24
1

Use harmonic function path planning. Harmonic functions are potential functions that describe fluid flow and other natural phenomena. If they are setup correctly using boundary conditions, then they have no local minima. These have been in use since the early 90s by Rod Grupen and Chris Connolly. These functions have been shown to be a specific form of optimal control that minimizes collision probabilities. They can be computed efficiently in low dimensional spaces using difference equations (i.e. Gauss-seidel, successive over-relaxation, etc.).

thealmightygrant
  • 701
  • 1
  • 5
  • 11