how to develop genetic algorithm for autonomous vehicle static path planning

my project is based on designing a genetic algorithm for autonomous vehicle static path planning. e.g a robot that can navigate around a work space (grid map) and avoid static obstacles as it moves from a start position to its destination.

[Geoff Hayes]

Ibrahim - the first thing you will need is the fitness function that you are trying to optimize (minimize). Presumably, you want the robot to find the shortest path from the start to the destination, subject to the obstacles that must be avoided. You will need to define all input variables into the fitness function that will then output a (scalar) fitness/cost value for those inputs.

[ibrahim]

Thanks Geoff for taking your time to respond to my question but my problem is complex than just fitness function. I'm just using matlab for the first time and its really difficult for me to design a genetic algorithm upon which my project is based. Please can you simplify the explanation in your response and if possible add more steps to it so i can fully comprehend and make use of it.

[Geoff Hayes]

Ibrahim - to get a good idea about genetic algorithms, I suggest that you read the book Genetic Algorithms in Search, Optimization, and Machine Learning by David E. Goldberg.

If you have the (MATLAB) Global Optimization Toolbox, then check out this link GA.

At the moment, your question is much too broad to answer. If you are basing your project on a GA, then you need to research how this optimization technique works in order to understand how it is applicable to your vehicle static path planning problem.

[ibrahim]

Thanks Geoff, i have done quite some literature reviews on genetic algorithm but my problem is using matlab to design it. please have you got the code for genetic algorithm or maybe other search algorithm which i can use for solving path planning problem?

thanks.

[Geoff Hayes]

Ibrahim - what have you tried so far? Have you coded up the fitness function, which should be the first step for this optimization problem? If there is a problem with the code that you have written, then please post it so that someone can take a look and offer some guidance.

And...will you be using the GA code from the Global Optimization Toolbox, or are you designing it all from scratch?

[ibrahim]

Yes please, i'm designing it from scratch and yes i will be using the GA code from the Global Optimization Toolbox. Honestly i'm very new to matlab and i don't have a very good idea on how to start. Any help offered will be highly appreciated. Thanks Geoff.

[ibrahim]

My idea seems cheesy but it involves developing a 10*10 grid map whereby the grid map will be divided into 100 equal grid cells with each cell represented by a unique number eg. 0 from the top left cell to 9 at the end of the row and so on till it reaches 100 at the bottom right. This will represent the workspace and therefore i can have let say cell 3 as my starting position of autonomous vehicle which will have to navigate its way to a target position say cell 82 while avoiding some of the other cells (static obstacle) within the grid map. All of this using GA from the Optimization Toolbox. If you understand my idea, can you please offer some help on how to give me a headway. Thanks

[Geoff Hayes]

Will you have some sort of 10x10 cost matrix associated with this grid? i.e. if the vehicle is at row 2 cell 3 (this should correspond to 12 in the workspace) do you have a variety of costs to go from this cell to any of the neighbouring cells? What defines a neighbour - any cell adjacent to the current cell (north,south,east,west) and those at the corners (northeast,northwest,southeast,southwest)?

Are you expecting the genetic algorithm to determine a path from the start cell to the end cell that minimizes the overall cost?

[ibrahim]

Thanks for the follow Geoff,

The 10*10 matrix will serve as the search area for which the genetic algorithm (autonomous vehicle) will find a feasible path with the lowest cost from its initial point to its final destination.

Yes, the costs to consider are shortest time, unnecessary turning and shortest distance.

Exactly, the function of the GA will be to find the optimal path from the start cell cell to its destination while avoiding any obstacle in its path.

does this answer the questions?

[Geoff Hayes]

Yes, the costs to consider are shortest time, unnecessary turning and shortest distance.

So you have a function that does all this for you, right? i.e. given a path from the start point to the end point, the cost for that path will be computed. Because this will be the function that you are trying to minimize, and so will be the fitness function for the GA.

The tricky part will be to define the variables that the GA will use to combine from one parent with another to produce children, and hopefully, a better solution. How have you decided to do that?

What code have you written so far?

[ibrahim]

Those are just ideas of what i intend to do. So far, i haven't got any code and the problem is i don't know where to start. Any idea on to develop the codes? Thanks

[Geoff Hayes]

Look at the paper A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment and start with that. Decide on how you are going to represent your gaming area, the method of movement for the autonomous vehicle, and your cost function (which will end up being the fitness function for the GA to minimize).

[ibrahim]

Hi Geoff, i think now i've understood what i've been trying to do. Could you please help with initialising a 10*10 grid environment with obstacles located while also generating random numbers within the grid?

thanks

[Geoff Hayes]

Ibrahim - please don't ask another question here only to duplicate it at http://www.mathworks.com/matlabcentral/answers/151784-please-somebody-tell-me-how-i-can-initialise-a-10-10-grid-environment-with-obstacles-located-while.

It seems that you have also duplicated that one with http://www.mathworks.com/matlabcentral/answers/151055-please-somebody-help-me-with-how-to-plot-a-10-10-grid-map-and-how-to-number-the-grid-cells.

Given the responses to these two (other) questions, try writing the code yourself. If you have a problem with the code (doesn't do what you expect, error message, etc.) then by all means post a question and we will all try to help you out. But you have to make an attempt...

[ibrahim]

Okay, thanks for the help so far.

Answer 1

[Matt J]

Instead of a genetic algorithm, maybe a known shortest path algorithm would be appropriate, e.g.,

http://www.mathworks.com/matlabcentral/fileexchange/12850-dijkstra-s-shortest-path-algorithm

[ibrahim]

Hey Matt, thanks for the valuable information but i have to use genetic algorithm to solve the problem. i will really appreciate if by any means you can send me a code for genetic algorithm so i can can carry on thereafter.

Thanks.