Regarding my project work, I have to write an algorithm for mobile robot planning. For that, I have chosen Genetic algorithm. Is it good for mobile robot path planning? If it is, then where can I start from and get some guidelines?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The short answer is no -- genetic algorithms are not good for path planning.
The longer answer is that while a genetic algorithm is very likely capable of solving a path planning problem, it's a very inefficient way to do so. Genetic Algorithms are preferred in problems where there are many input variables and the interaction between those variables is complicated. (A popular example of a Genetic Algorithm problem is the antenna shape that was "evolved" to produce the proper radiation pattern.)
Rather than trying to maximize the "fitness" of a set of inputs (as Genetic Algorithms do), in path planning you are trying to minimize the "cost" of getting to your end state -- finding a set of movements (the length of which is unknown at the start) to accomplish that goal.
If, on the other hand, you were trying to find an algorithm that could help a robot learn how to move, then the evolutionary approach is fine. The example that comes to my mind is the robot from Cornell that can teach itself to limp when it stops being able to walk (PDF of some of their work is here).
$\begingroup$
$\endgroup$
This question is pretty general.
There is an online course available at edx:
https://courses.edx.org/courses/TUMx/AUTONAVx/2T2014
Where they explain different possible solutions and their implementations. This course is pretty good
$\begingroup$
$\endgroup$
My feeling is that a genetic algorithm wouldn't be a good way to do path planning. GAs are better at searching crazy multi-dimensional discontinuous spaces. On the other hand, path planning for a mobile robot just isn't that hard.
You didn't say what kind of robot this was going to be, but for 2D mobile robots, there are already several excellent path planning algorithms around, like A*.
My preferred robot path planning method starts with something like A* to generate a first path through the map. Then I would convert that into a piecewise linear path, and use an iterative algorithm on the path to straighten it out, and adjust the velocity, acceleration and jerk along the path to optimise it.
Having said that, people clearly are using GAs for path planning.
answered Aug 13, 2014 at 21:18