how can i use particle swarm optimisation algorithm for to find optimal path interms of shortest distance between start and goal point to be followed by mobile robot?

I have shown my working environment in the image. In this image, the circular object considered as a obstacle. The white line considered as path for mobile robot. The mobile robot is move with interpolate the nodes (shown as red small circle). In this image, totally 14 nodes (co-ordinate points) are there. Among that i consider a start and goal point and it has various path between start and goal point. How can i find optimal path without hitting obstacle using particle swarm optimisation. The co-ordinate points of nodes (interms of pixels) are (135,137),(295,137),(510,146),(678,152),(139,287),(211,323),(298,237),(403,278),(509,233),(678,298),(591,336),(579,396),(402,402).

Answer 1

[Walter Roberson]

This is a Shortest Path or Traveling Salesman problem.

http://stackoverflow.com/questions/19755397/shortest-path-using-particle-swarm-optimisation

[LAKSHMANAN ADAIKKAPPAN]

Thank you for your guidance sir. I will see this link. In this, they solve traveling salesman problem and they do not consider obstacles. But, in my case obstacles are considered. so can i know how to avoid these obstacles with interpolating given nodes?

[Walter Roberson]

You do not need to worry about obstacles. All you need to do is populate your graph only with the links that are known to be valid. If there is an obstacle in the way of connecting node A and node B then do not connect A and B in the adjacency matrix.

The situation would be slightly different if you were starting with just a space and the positions of the obstacles and the distinguished nodes and you did not have those white lines that constrain your path (they look like computed Veroni lines to me.) In such a case you would want some form of constrained PSO. You might want to have a look at http://www.mathworks.com/matlabcentral/fileexchange/25986-another-particle-swarm-toolbox for that. I did not look closely enough to determine whether that could handle constraints on traveling through a point, or if it could only handle constraints on where the particles would end up.

Shortest path on an image can be handled deterministically using techniques such as bwdistgeodesic. To use that, you would use a mask which is the binary version of your image. You would ask for the distance for each point to one of the endpoints and you would ask for the distance for each point to the other endpoint and then you would add the two matrices together. Then starting at one endpoint you would follow the path of local minima to the other endpoint.

[LAKSHMANAN ADAIKKAPPAN]

Thank you for your guidance sir. I read this link. But in this matlab code, there is no constraints for traveling through a points.

[LAKSHMANAN ADAIKKAPPAN]

Is the same problem possible to solve using ant colony algorithm or other evolutionary algorithm?

[Walter Roberson]

For the alternative approaches, see http://www.mathworks.com/matlabcentral/fileexchange/?term=tag%3A%22tsp%22

At the TSP level, you do not need to worry about constraints about traveling through a point. If there is an obstacle between two points, do not connect them in the adjacency matrix.

NN = 14;
edges = [1 2
         1 5
         2 3
         2 7
         3 4
         3 9
         4 11
         5 6
         6 7
         6 12
         7 8
         8 9
         8 13
         9 10
         10 11
         10 14
         12 13
         13 14];
  adj = zeros(NN, NN);
  adj( (edges(:,2) - 1) * NN + edges(:,1) ) = 1;
  adj( (edges(:,1) - 1) * NN + edges(:,2) ) = 1;

Now adj is your adjacency matrix. For TSP purposes you will probably want to use a distance matrix.

Possibly when you said "in this matlab code, there is no constraints for traveling through a points" perhaps you were referring to the link I posted about constrained PSO. That was only for the case where you were starting without the white paths. Myself, I would not use PSO for that at all, as there are deterministic solutions.

Answer 2

[engesraa]

how can i find the shortest path between two point ??

[Walter Roberson]

What input are you starting with? Are there constraints on what form the path can take?

[engesraa]

start point (0,0) 
target point (10,10)
xlim([0 10])
ylim([010])

[Walter Roberson]

The shortest path is to go directly from (0,0) to (10,10), which is "free" under the conditions you have given us.

[engesraa]

if i have some obstacles in the environment how can i avoid them ??

[Walter Roberson]

See my above comment https://www.mathworks.com/matlabcentral/answers/263094-how-can-i-use-particle-swarm-optimisation-algorithm-for-to-find-optimal-path-interms-of-shortest-dis#comment_334344