ASTAR ALGORITHM

[ARITA]

Buenos días he escrito unas semanas atrás sin obtener respuesta.

Mi nombre es Aracely, soy tesista de la Escuela Politécnica Nacional, 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.

Hello my name is Aracely, I wrote you weeks ago but I don´t have a 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]

Hello my name is Aracely, I wrote you weeks ago but I don´t have a 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

[Jchinchi]

Hola.

Revisé tu codigo y parece funcionar bien con los puntos iniciales del algoritmo original (el que viene con el ejemplo de NI). Cuando uso los puntos fijos que tu ingresas, la búsqueda del patch no funciona bien. El problema parece que el algoritmo no permite o entra en una iteracción muy larga al usar puntos sobre el eje X. Por ejemplo si remuevo algunos puntos del eje X se tiene:

Como ves ya trabaja mejor pero el path no funciona en todas las posiciones. Ahora si remueves todos los puntos de ese eje ya funciona como debe ser:

Estos son los juegos de puntos: 

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 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 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 ];

Hice la prueba moviendo todos los puntos sobre el eje X de 0 -> 1 y si funciona pero depende de ud ver si le sirve en esa configuración. Este es el resultado:

[ARITA]

Muchísimas gracias!!!!

esa opción no se me había ocurrido, de verdad gracias,

creo q si voy a poder utilizar esa solución en mi aplicación..

Ya la voy a probar!!!!

Aunq creo q el algoritmo Astar deberia funcionar bien

a pesar de cuales fuesen los puntos...

Gracias

[zhoudeng]

sorry for not understanding your language. but the pictures u uploaded here is very interesting.. I have tried the A star on voronoi but I am not able to change the given maps.

pleaseeee tell me how did you manage to input a map..

can u please attache the code as well if possible..

a lot of  thanks ...

[zhoudeng]

can understand your spanish now.. thanks to Google translate.

and the code is running well now.

Now my question is how i can apply the map generated by this program to the mobile robot that i am using... 

in other words, what is the output of this program... how can i use this output to drive 2 motors(differential motors) so that the robot can navigate just as the path(generated by this program) suggests.

thank you very much and u r free reply  in Spanish... 

[ARITA]

Hola

Prefiero escribir en español porque se me hace mucho más fácil que hacerlo en inglés, si algo no me entiendes me avisas para explicarte en inglés. Por el momento en mi laptop no tengo instalado el Labview, y ya es más de un año que yo acabé mi tesis. El programa que adjunté a este foro, no recuerdo hasta que punto se halla desarrollado, pero si no me equivoco, el "output" del programa son los puntos de las líneas rectas que forman parte de la trayectoria. Como puedes observar, la trayectoria que se obtiene es un conjunto de líneas rectas, y la salida que se obtiene son 2 puntos por cada recta. Lo que yo hice para que mi robot siga la trayectoria es, hallar la distancia entre 2 puntos a  través de la fórmula de la "distancia euclídea" y al tener 2 puntos también, pude hallar el ángulo de giro a través de la fórmula de tg -1. Esto hice, ya que mi robot poseía encoders para contar los grados de giro así como la distancia recorrida, y la lógica de movimiento que yo apliqué fue la que se me hizo más sencilla aplicarla. Para que me entiendas mejor, adjunto el link donde se encuentra mi tesis, auí explica la lógica de movimiento empleada para que el robot siga la trayectoria generada.

http://bibdigital.epn.edu.ec/handle/15000/3772

Saludos

[zhoudeng]

thank

---

@ARITA wrote:

Hola

Prefiero escribir en español porque se me hace mucho más fácil que hacerlo en inglés, si algo no me entiendes me avisas para explicarte en inglés. Por el momento en mi laptop no tengo instalado el Labview, y ya es más de un año que yo acabé mi tesis. El programa que adjunté a este foro, no recuerdo hasta que punto se halla desarrollado, pero si no me equivoco, el "output" del programa son los puntos de las líneas rectas que forman parte de la trayectoria. Como puedes observar, la trayectoria que se obtiene es un conjunto de líneas rectas, y la salida que se obtiene son 2 puntos por cada recta. Lo que yo hice para que mi robot siga la trayectoria es, hallar la distancia entre 2 puntos a  través de la fórmula de la "distancia euclídea" y al tener 2 puntos también, pude hallar el ángulo de giro a través de la fórmula de tg -1. Esto hice, ya que mi robot poseía encoders para contar los grados de giro así como la distancia recorrida, y la lógica de movimiento que yo apliqué fue la que se me hizo más sencilla aplicarla. Para que me entiendas mejor, adjunto el link donde se encuentra mi tesis, auí explica la lógica de movimiento empleada para que el robot siga la trayectoria generada.

http://bibdigital.epn.edu.ec/handle/15000/3772

Saludos

---

thank you very much. i now can understand the program much better. and I actually found out that for each turning point, the position information (in (x,y) form) is provided in one of the subVIs.

Thank you very much