Pathfinding A*

[marcode]

 En ocasiones puede ocurrir que el nodo que aparentemente está más cerca del destino te lleve por un camino enrevesado que al final acaba dando un montón de vueltas, en cambio un nodo que parece que se aleja y que se piensa que es el peor acaba siendo el camino más corto.

¿Como se soluciona esto?, se supone que el A* busca siempre primero los nodos que se consideran mejores. En una cuadrícula de nodos tiene más sentido, pero en un grafo no tienen porque ser los mejores los que así lo parezca ¿no?.

¿como me puedo fiar de la heurística por la distancia? ¿si la quito dejaría de ser llamarse A*?

Todo esto lo digo porque he tenido que prescindir de ordenar la lista para elegir al "mejor" candidato a ser calculado, porque no me compensa perder el tiempo de saber cual está más cerca del destino, para la poca mejora que obtengo, al menos en grafos no muy grandes, y más aún si luego creo que puede ser un "fraude" el sistema.

Lo único que hago es descartar aquellos nodos que superan el coste del mejor camino encontrado hasta el momento, por lo demás es una simple búsqueda en anchura.

Pues eso, a ver que opináis.

[marcode]

 Otra duda sobre su eficiencia es que no siempre el coste es igual a la distancia.

Por ejemplo, sabemos que por el ascensor llegaremos antes a la planta 20 que por la escalera, aunque estemos al lado de la escalera y haya que andar 100 metros hasta llegar al ascensor desde el lugar que nos encontramos.

Desde este planteamiento el algoritmo se perdería por las escaleras y pasillos buscando el destino, cuando el mejor posible es ir al ascensor.

Vamos que si el A* es así en el sentido de fiarse por las distancias no me sirve para grafos, paso de él, pero quizás estoy equivocado por eso quiero escuchar opiniones.

pd: he editado y añadido unas frases a este mensaje para ser más explícito.

[Elvis Enmanuel]

 ¿Has probado el algoritmo de dijkstra?

[marcode]

 Pues la verdad no se como es, el caso es que toda heurística basada en el ordenamiento de la lista de nodos a buscar perjudica considerablemente el rendimiento (reitero que es para un grafo de como mucho unos cientos de nodos).

Me sale más a cuenta el expandir el árbol de búsqueda por igual cogiendo el primer elemento hasta que una rama encuentra el nodo destino, a partir de ahí se descarta cualquier rama que le supera en coste por lo que se finaliza pronto el proceso de búsqueda.

De esta forma en el ejemplo anterior del ascensor, se expandiría por igual el grafo hacia el ascensor y hacia la escalera (y hacia otros puntos), y como el coste del camino es mayor por la escalera a partir de la planta 5 (por ejemplo) que yendo por el ascensor, el proceso de búsqueda se cortaría en ese punto, y no recorrería todo el edificio buscando la habitación de la planta 20 (para luego encima no ser el mejor camino)

¿Podrías explicar un poco por encima en que consiste el dijkstra?

[Vicente]

 Djijkstra es un A* donde la heurística es siempre 0.

Edit: estás seguro que te es más rentable expandir tooodos los nodos de cada nivel que ordenar los que necesita A*? Ten en cuenta que A* expande los mínimos nodos posibles por definición, con lo cual tampoco tienes tanto que ordenar...

Un saludo!

Vicente

Otro edit :P -> Creo que tu problema es la heurística: una heurística euclidea no puede tener en cuenta el ascensores, teletransportadores y demás, deberías elegir otra.

[Daemon]

 Un A* es una combinacion de busqueda por profundidad y anchura, y es un alqoritmo optimo (encuentra la mejor solucion) y completo (si hay solucion siempre te la dara), siempre y cuando se cumplan ciertos requisitos para la funcion heuristica, y es que esta sea admisible, es decir que su estimación de lo que queda para llegar al destino a partir de un nodo determinado sea menor que el coste real de llegar al destino desde ese nodo.

Si no te esta dando el resultado que tu esperas (tanto si es en eficiencia o en el camino que buscas), es por que tu funcion de coste y/o funcion heuristica no son adecuadas al problema que te le planteas.

Un saludo.

[Mars Attacks]

 Entonces le darías al "camino" ascensor un valor inversamente proporcional a la distancia a la que te encuentres de él, y directamente proporcional al piso al que vayas.

[marcode]

 No es que sea más lento, en muchas circunstancias es más rápido sobre todo para nodos lejanos, aunque en otras es más lento. Por eso digo que no me compensa el esfuerzo si luego no es totalmente efectivo y el principal problema que veo es que no siempre el coste está asociado a la distancia.

Y ya digo que es para cientos de nodos, si es para muchos miles o millones, si que sería una locura no usar ningún tipo de heuristica.

Por ejemplo, otro "fallo" que he detectado en el A* (o que quizás es mío), es que no siempre encuentra el mejor camino si supuestamente la búsqueda se finaliza una vez que se ha encontrado el destino, intentaré poner un ejemplo.

->  ----(1)-----------(2)------------(3)
             \                                  /
              \                              /
               (4)--------(5)------ (x)  destino
               

A* se encuentra en el nodo (1) y entiende que el mejor nodo es el (2) porque está mas cerca del destino que el 4 (x),  el siguiente nodo que creerá que el mejor es el (3) porque también está más cerca que el (4), finalmente encuentra la (x) y el camino elegido es 1,2,3,4, cuando el correcto era el 1,4,5.

Por favor sacadme de dudas porque hay algo que no hago bien seguro, y si la cosa es más compleja a nivel de cálculos si que empeoraría el tema de velocidad.

Mars:
Entonces le darías al "camino" ascensor un valor inversamente proporcional a la distancia a la que te encuentres de él, y directamente proporcional al piso al que vayas.

¿Pero como puede saber que el camino por el ascensor va ser mejor que por la escalera si todavía no ha sido recorrido?, el A* tiraría para arriba por la escalera, el ascensor ni se lo plantearía ya que queda aparentemente lejos (seguro que el A* no sabe lo que jode subir 20 pisos).

Realmente ¿a quién no le ha pasado?, sobre todo yendo por el campo que quieres atajar por un sitio y la cagas porque era un asco de camino. Pues es lo que me parece que le ocurre al A*.

Daemon:
Si no te esta dando el resultado que tu esperas (tanto si es en eficiencia o en el camino que buscas), es por que tu funcion de coste y/o funcion heuristica no son adecuadas al problema que te le planteas.

¿Y cual sería la heurística adecuada a este problema desde tu punto de vista?, es que por lo que he podido comprobar para un número no muy elevado de nodos apenas compensa liarse en cálculos, y te hablo de grafos en 3D, con nodos esparcidos a cualquier distancia y sin más lógica que la del propio mundo en la que está inmerso.

[marcode]

 

Daemon:
...que sea admisible, es decir que su estimación de lo que queda para llegar al destino a partir de un nodo determinado sea menor que el coste real de llegar al destino desde ese nodo.

Coño!, releyendo esto veo que es lo que hago yo  :) . Solo que para saber la distancia al destino primero tengo que expandirlo en anchura. Después descarto aquellos nodos que nunca serán mejores por haber superado su coste más el mínimo que les queda.

Pero en ningún momento uso expansión en profundidad.

[Vicente]

 Hola,

tienes un par de lios:

Código [Seleccionar] Expand


->  ----(1)-----------(2)------------(3)
           \                                  /
             \                              /
             (4)--------(5)------ (x)  destino


A* expandiría: 1, 2, 3, 4, 5, X y devolvería el camino 1-4-5-X (ni siquiera estoy seguro si expandiría 3, yo creo que despues de 2 expandiría 4 y 5).

No expandiria 3-X porque la suma de la distancia de llegar hasta 3 más la de llegar a X es mayor que la de llegar a 4 más la distancia estimada de 4 a X.

A* es la distancia hasta ahora más una estimación de lo que me queda.  Estimación no es lo que te queda por que lo dice el grafo, es eso, estimación. Por ejemplo, en tu dibujito usa como estimación la distancia en linea recta desde el nodo a la X, verás como nunca elige el camino que has dicho.

Relee lo que te ha comentado Daemon: la heurística es una aproximación, no nada real, simplemente es lo que cree el algoritmo que le va a costar llegar desde un punto a la meta. Normalmente se usa la heurística euclídea (la distancia en linea recta de un punto al otro). Dijsktra por ejemplo es con heurística 0: esto es, no estima nada y lo que hace es explorar tooodos los nodos como un algoritmo avaricioso. Otra heurística es la de Manhattan (se usa en juegos por casillitas), etc etc...

Tu en cambio como dices estás calculando la distancia, ese es tu problema, A* no calcula, se imagina cual será la distancia. Esa imaginación de la distancia (la heurística), si cumple ciertas propiedades (las que ha dicho Daemon), te garantiza que A* encontrará la mejor solución si es que existe y expandirá menos nodos que cualquier otro algoritmo que te puedas inventar tu. En teoría nada puede ser mejor que A* (esto está demostrado ;)).

Luego en la práctica las cosas son más graciosas claro :P Un saludo!

Vicente

 

No expandiria 3-X porque la suma de la distancia de llegar hasta 3 más la de llegar a X es mayor que la de llegar a 4 más la distancia estimada de 4 a X.

De acuerdo, no lo entiendo bien pero olvida el lío uno, recuerdo que el fallo solo me daba en el último nodo, como ya dije quizás era fallo mío, aún así intentaré poner el problema que recuerdo que tenía, más concretamente en un futuro.

Por lo demás sigo sin saber que tipo de heurística debo usar para acelerar el algoritmo, el de la distancia euclídea no sirve porque a veces se pierde en estimaciones falsas y no soluciona el problema de distancias cortas con costes altos y viceversa, el de manhattan tampoco, no es el caso.

Otra cosa que me gustaría saber es que coño de algoritmo estoy usando yo, en principio es el de Dijsktra porque expande avariciosamente a todos los nodos, pero con un añadido que hace que una vez encontrado el nodo destino, dejen de expandirse aquellos nodos cuyo coste sea superior al del menor coste encontrado hasta el momento. Esto garantiza que siempre encuentra exactamente el camino de menor coste, que no siempre tiene que ser igual el camino de menor distancia, en un tiempo razonable.

Intenté optimizar el algoritmo para que encontrase lo más rápido posible el nodo destino a partir de la distancia euclídea, pero el cálculo de hallar la distancia euclídea en cada nodo y tener que ordenar la lista para escoger la mejor estimación lo enlentecía.

Por lo tanto no tengo ningún problema (si acaso lo tiene A* conmigo (twist)), porque va de maravilla, y el cálculo más dificil que hace en cada paso es el de sumar costes a cada nodo y compararlos, y me gustaría saber si puedo encontrar un algoritmo o algún tipo de heurística más eficaz que me sirva para acelerar el cálculo.

Otra pregunta, ¿como podría comparar la velocidad de mi algoritmo con la velocidad de otros algoritmos?, a partir de alguna tabla de referencia que compare la velocidad en un grafo dado o algo parecido. Bueno, la verdad es que esto ya es casi misión imposible.  

[marcode]

 Perdón, era yo el anterior, pensaba que requería identificarse para escribir en este foro.

[Vicente]

 Hola,

no es el de Djisktra porque Djisktra asegura que una vez que has encontrado un camino para llegar a un nodo, ese es el camino más corto (es como A*, pero Djisktra expande muuuucho más nodos).

Si te lias en el último nodo, quizás es porque lo estás tratando de manera especial. A* lo que hace es lo siguiente: tiene una lista de nodos a los que puede ir, y decide ir al nodo que minimiza la suma de

- Distancia actual (usease los arcos del grafo para llegar del inicio a él)
- Distancia estimada hasta el final (la heurística)

El nodo que tiene ese valor mínimo es el que se expande.  Si luego además resulta que es el destino pues premio, has terminado ;)

Me lío con lo que dices de coste y distancia: si es un grafo para moverse por un mapa, esos dos valores son iguales, no tiene sentido que sean diferentes...  (o no se lo encuentro). Respecto a velocidades, implementa A* y Djisktra y ponlos en mapas junto con tu algoritmo a ver que sale. Compara velocidad, uso de memoria y nodos expandidos. A* debería ser el mejor por goleada ;)

Podrías poner un pseudocódigo de tu algoritmo para ver si me entero mejor? :) Un saludo!

Vicente

[senior wapo]

 

Me lío con lo que dices de coste y distancia: si es un grafo para moverse por un mapa, esos dos valores son iguales, no tiene sentido que sean diferentes...  (o no se lo encuentro).

No es lo mismo llegar al destino por carretera que cruzando un barrizal, atravesando un campo de minas, por carretera pública o de peaje, por las calles con más riesgo de que te atraquen en lugar de por las más seguras...

Según la implementación tanto coste como distancia entre dos nodos cualquiera pueden ser fijas o variables a lo largo del tiempo, conjunta o separadamente. De ahí que hay quien los combine y quien los trate por separado.

Hay quien llama distancia al producto final distancia*coste (lo deseable que es un tramo) y quien llama distancia solamente a la separación espacial y considera el coste como variable aparte. Suponiendo que hablamos de grafos espaciales, claro. Diferentes nombres para la misma cosa: valor del arco que une los nodos. Mismo perro con distinto collar, como dicen por ahí.


Si no es a eso a lo que os referís haced como que no he dicho nada :P

[Vicente]

 Mmmmm, en lo que dices por ejemplo no estás buscando el camino más corto tradicional :P Es como el thief que se movía por las zonas donde menos ruido hacía (o eso creo). Tu estás buscando el camino más corto (en distancia) teniendo en cuenta otra cosa (la seguridad en el ejemplo de los atracos). En eso si que tiene sentido distancia y coste. Pero en lo de las escaleras y el ascensor que solo busca el camino más corto (usease una suma de arcos de un grafo) sin ninguna otra consideración (creo). Así que la distancia y el coste deberían ser el mismo valor. Otra cosa es la distancia "física", pero es que eso no debería ser lo que hay en los arcos del grafo (si no te tendrás que buscar otra manera de que se de cuenta que existe el ascensor).

Un saludo!

Vicente