Astar on Voronoi

[ARITA]

Hi my name is Aracely, I have a problem with the A Star Plan function (A*); "Astar on Voronoi" is a Labview example for Path planning. This example computes a random collection of obstacles on a map, and uses the Voronoi algorithm to compute the list of all possible paths between those obstacles.  Random start and goal points are chosen, and the A* algorithm is used to compute the shortest path from the start node and the goal node.
Drag the cursors on the graph to set new start and goal nodes.  The VI will automatically recalculate the optimal path from start to goal.

Now I´m doing my thesis and this example could help me a lot but I have a problem, in the example I have random points as obstacles and when I change

these random points for a matrix that contains points that I want to have in the map, the A* doesn´t work and I never obtain the path. It just works if the path is short but if it is longer the A* never compute the path. I don´t understand what is the problem because I am just changing the random points for a matrix of points and I think it is the same, I´m not changing anything else in the example. If someone could help thank you very much. I don´t know what to do. I attach the example with the changes.

Mi nombre es Aracely, tengo un problema con el algoritmo A* del toolkit de Robotica; Labview presenta un ejemplo denominado "Astar on Voronoi" en el cual se ingresan obstáculos como puntos aleatorios en un mapa y se utilizan diagramas de Voronoi para obtener las posibles trayectorias, una vez q se obtiene el diagrama de voronoi se utiliza el algoritmo A* para obtener la trayectoria más corta desd un punto de partida hasta un punto de llegada. Al momento me encuentro realizando mi tesis y este ejemplo me sería de muchísima ayuda, el problema se presenta cuando yo ingreso puntos conocidos en una matriz (ya no lo hago aleatoriamente), el diagrama de voronoi si lo obtengo pero el momento de generar la mejor trayectoria, la función A* no trabaja y es como si se colgará porq los datos entran pero nunca nada sale de la función. Obtengo una trayectoria si la misma es corta, pero si los puntos de partida y llegada están más alejados la función se cuelga y jamás obtengo una trayectoria. En realidad no sé que podría hacer, si alguien me pudiese ayudar muchísimas gracias. Adjunto el ejemplo con los cambios.

[Lucianogob]

Hello,

What version of LabVIEW are you using?

Could you please describe in a better way the path problem?

I could not open the file you've attached here. I have LabVIEW 2010.

Thanks.

Best Regards

[ARITA]

Hello

Thank you for your response. I´m using LABVIEW Robotics 2009

I´m going to try to describe in a better way my problem.

You can find "Astar on Voronoi" in Help>Find examples>Robotics>Path Planning>Astar on Voronoi.

This example computes a random collection of obstacles on a map, and uses the Voronoi algorithm to compute

the list of all possible paths between those obstacles. Random start and goal points are chosen, and the A* algorithm

is used to compute the shortest path from the start node and the goal node. If you
drag the cursors on the graph to set new start and goal nodes, the VI will automatically recalculate the optimal path from start to goal.

Now I´m working on my thesis, and I need this example for it, specially the algorithm A* and the Voronoi algorithm.

My application maybe is a little more complex than the Labview example because my obstacles are polygons and I

can obtain the Voronoi diagram of my map. But when I want to obtain the shortest path I couldn´t. Then I tried to figure out and

I  noticed that the problem was in the A* algorithm. After that, I analized the original Labview example and I noticed that happen

the same with my thesis, the problem is in the A* algorithm. Because of that, I try to explain you the problem with

the original Labview example instead of my thesis.

In the Labview example the obstacles are random points and when I change these random points for

a matrix that contains points that I want to have in the map, the A* doesn´t work and I never obtain the path.

It just works if the path is short but if it is longer the A* never compute the path. I don´t understand what is the problem

because I am just changing the random points for a matrix of points and I think it is the same, I´m not changing anything else in the example.

I attach the example again with the changes, but if you can't open it, you could try this:

In the example we have  this code in the mathscript node:

x = rand(n, 1)*5;
y = rand(n, 1)*5;
[vx, vy] = voronoi(x,y);

You could change this code for:

x = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2 4.4 4.6 4.8 4 1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3 3.1 3.2 3.3 3.4 3.5 3.4 3.3 3.2 3.1 3 2.9 2.8 2.7 2.6 2.5 2.4 2.3 2.2 2.1 2 1.9 1.8 1.7 1.6];
y = [0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2 4.4 4.6 4.8 5 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2 4.4 4.6 4.8 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1.9 1.8 1.7 1.6 1.5 1.4 1.3 1.2 1.1 1 1.3 1.6 1.9 2.2 2.5 2.8 3.1 3.4 3.7 4 3.9 3.8 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3 2.9 2.8 2.7 2.6 2.5 2.4 2.3 2.2 2.1 ];
[vx, vy] = voronoi(x,y);

The difference between both is that in the second one I'm entering the points that I want in a matrix.

I have checked it in many ocassions but I can´t find what is wrong. First I thought that was my computer

but I probed the example in another computer and It happens the same. I don´t think that the number of

points is the problem because when I generated it randomly I could enter 300 points and the example works very well

and the number of points that I´m entering in the second one is less than 300.

I speak Spanish and I hope you understand my english and you could help me.

Thank you very much.

Aracely Yandún

Escuela Politécnica Nacional

[ARITA]

Here is the file.

[altenbach]

It is difficult to tell what's going on, because you forgot to include all the subVIs. We cannot test!

Is this from a toolkit? Robotics?

EDIT: Ah sorry, I did not see your two posts above. I guess I had my browser open for longer than I thought ;))

[ARITA]

Yes it is the Robotics toolkit

And I didn´t attach the subVIs because if you have

the toolkit you must have the subVIs.

If you need the subVIs please ask me

Thank you