Pathfinding A*

[marcode]

 Aquí está el seudocódigo (supongo que lo habré puesto bien)

Código: [Seleccionar]

Tenemos una lista abierta donde introduciremos los nodos, al comienzo contiene un único elemento, el nodo origen.

while (hasta vaciar la lista)
{
     se extrae el primer elemento de la lista al que llamaremos N.

     if (N es el destino)
          se almacena el coste del trayecto en C como el mejor camino.

     if (el coste de N supera al de C)
           (continue;) se salta, ya que yendo por N nunca se encontrará un camino mejor.

     for (cada uno de los nodos sucesores de N que llamaremos S)
     {
           if (S es padre de N)
                (continue;) no se le expande por lo que se pasa al siguiente S

           if (S ya ha sido visitado)
           {
                if (el coste de N + el coste de N a S es menor del coste actual de S)
                {
                      // el nodo S tiene un camino mejor pasando por N
                      if (S no está en la lista)
                      {
                         se le añade al final de la lista.
                      }
                      se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
                 }
           }
           else (S nunca ha sido visitado)
           {
                se le añade al final de la lista
                se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
           }
     }
}

si el destino tiene padre se encontró el camino, por lo que se recorre toda la lista de antecesores para guardar el camino encontrado.

He revisado la implementación de la heurística según la distancia euclídea y ha mejorado el tiempo de cálculo aunque tampoco excesivamente.

El problema es que el calcular la distancia y posterior comparación para elegir la posible mejor ruta resta velocidad al algoritmo, y lo que se gana por un lado se pierde por otro aunque ahora sí, siempre es mejor con heurística que sin ella.

Aquí está el pseudocódigo

Código: [Seleccionar]

while (hasta vaciar la lista)
{
     se extrae el nodo de la lista cuyo coste actual mas la distancia euclídea con el nodo destino sea menor
     se desplazan los nodos posteriores hacia atrás en la lista

     if (se alcanza el destino)
           (break); se termino la búsqueda

     for (cada uno de los nodos sucesores de N que llamaremos S)
     {
           if (S es padre de N)
                (continue;) no se le expande por lo que se pasa al siguiente S

           if (S ya ha sido visitado)
           {
                if (el coste de N + el coste de N a S es menor del coste actual de S)
                {
                      //el nodo S tiene un camino mejor pasando por N
                      if (S no está en la lista)
                      {
                         se le añade al final de la lista.
                      }
                      se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
                 }
           }
           else (S nunca ha sido visitado)
           {
                se le añade al final de la lista
                se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
                se obtiene y se guarda la distancia euclídea al nodo destino para posteriores comprobaciones
           }
     }
}


Lo de los costes y distancias que me refería anteriormente es lo que dice Senior, no siempre el camino de menor distancia aparente es el camino más corto.

Vicente, ¿podrías poner el pseudocódigo de como lo has hecho tu para compararlo?.

[Vicente]

 Hola,

mi A* (del libro de Mat Buckland, normalmente la nomenclatura es con lo de lista cerrada y abierta, no así):

Código: [Seleccionar]

while(lista no esta vacia)
{
   N = primer nodo del heap
   camino_mas_corto[N] = frontera[N] //la forma más corta de llegar a N es la frontera de N (el arco del grafo que nos lleva a N con menor coste)

   si N == destino
      return;

   for (sucesores de N llamados S)
   {
       h = heuristica(S, destino)
       g = costesG[N] + arco(N, S)

       if (arco(N, S) no está en la frontera) //frontera[arco(N,S)] == null
      {
           costesF[S] = h+g
           costesG[S] = g

           añadimos S al heap
           frontera[S] = arco(N, S)
      }

      else
      {
          if (g < costesG[S] && camino_mas_corto[N] == null)
          {
              costesF[S] = h+g
              costesG[S] = g

              modificamos la prioridad de S en el heap
              frontera[S] = arco(N, S)
          }
      }
   }
}

El heap es una cola de prioridad indexada por costesF (g+h). Todas las operaciones en el heap son O(lg d).

Espero que ayude! Un saludo,

Vicente

P.D.: si no ta mu claro lo explico paso por paso

[Daemon]

 Aparte del algoritmo, dices que la heuristica de la distancia no es la más adecuada a tu problema, ¿no? Y por lo que creo entender tambien tienes una funcion de coste (llamada como arco(N, S) en el algoritmo de Vicente) que no trata únicamente la distancia entre nodos, si no que tiene en cuenta mas cosas. Realmente es dificil ayudarte en esto, si no nos dices en base a qué criterios estas intentando optimizar el camino.

Te doy una directriz de busqueda via Google: algoritmos multiobjetivo, como Senior wapo dijo, se usan para encontrar aquella solucion que encuentra los valores optimos de varios criterios de busqueda. Son útiles sobre todo cuando estos criterios no son uniformes, es decir unos son criterios a maximizar y otros a minimizar (distancia, claramente a minimizar, confort o seguridad del camino a maximizar). A veces combinar estos criterios en una sola función heuristica para el A* no es lo mejor que se puede hacer.

En cualquier caso a veces las buenas heuristicas pueden ser dificiles de obtener.

Un saludo.

P.D.: tampoco soy un experto en este tipo de algoritmos, pero si crees que te pueden servir, puedo preguntar a ver que me cuentan sobre ellos.

 Parece que es igual, pero, ¿cómo ordenas la lista?, es decir, ¿donde y cómo decides que N es mejor?.

[Vicente]

 Hola,

supongo que eres marcode El heap (la cola de prioridad) se ordena al insertar, sacar o modificar un elemento , siempre está primero el nodo cuyo costesF es menor (g+h) (el resto de los elementos excepto el primero no están del todo ordenados).

Un saludo!

Vicente

[Daemon]

 Creo que ya lo ha dicho, el heap es una cola ordenada por prioriad en base al valor de f (g+h)

[EDIT]

Upps... Perdon,  olvidad lo que he dicho, Vicente y yo estabamos escribiendo al mismo tiempo y el respondio antes...  

[/EDIT]  

[Vicente]

 Jejeje

Semi-OT: En la implementación de Mat usa cola indexada de prioridad, esto es, la cola no tiene valores, tiene índices a una tabla que es donde están los valores. Para implementarla se usan 2-way heaps (o d-way heaps). En la STL los tienes implementados ya (a mi en C# me toco buscar un heap en codeproject y cacharrear con él...). El heap usa dos listas: una con los valores que usa para ordenar y otra que indica la posición de cada índice en la cola (esto es, donde está ahora mismo el índice 5 en el heap? Se usa para poder modificar elementos).

Un saludo!

Vicente

 Gracias Daemon. Pero creo que he salido de mi principal duda, que era que el *A podía no darme el resultado correcto si entendía que el mejor camino era el de menor distancia.

Pero me he dado cuenta de que si los trayectos tienen unos costes asociados y estos son los que se comprueban, nunca puede fallar, como bien dijiste antes tú o alguien *A solo busca la estimación, no te encuentra el camino que él cree.

Entonces creo que en el peor de los casos (poniéndoselo difícil con ascensores y historias raras) lo único que haría sería tardar un poco más en encontrar el mejor camino, pero por las pruebas que he hecho nunca es mayor el tiempo que tardaría, que en una búsqueda en anchura común. Aunque a veces se aproxima.

Entonces creo que lo que debería hacer es algún tipo de optimización para seleccionar el nodo a expandir lo más rápido posible y creo que el meter alguna heurística especial perjudicaría más que beneficiaría. Ya que por lo general las distancias suelen estar asociadas a su coste.

Actualmente compruebo de toda la lista cual es el más probable para extraerlo, y seguidamente desplazo el resto de nodos para "tapar" el hueco.

Ahora mientras escribo esto se me acaba de ocurrir por ejemplo que podría mover el último para tapar ese hueco, quizás gano algo de tiempo, voy a probar!!!
 

[marcode]

 sí, soy yo  

Me creo que estoy identificado y luego no.

Lo peor es que no puedo editar  (grrr)  

[marcode]

 De todos modos tendré que hacer más pruebas para salir de dudas.

Un ejemplo claro de caminos con diferentes costes es un mapa de carreteras.
La carretera de menor distancia no siempre es la mejor, las autovías deben tener mucho menos coste que las comarcales a igual recorrido.

Entonces si A* encuentra un camino de cabras como mejor recorrido mal vamos.

[Vicente]

 Hola,

a ver, A* se basa en una heurística, y esa heurística te dice el COSTE estimado para llegar a un nodo. La heurísitca euclídea usa la DISTANCIA para estimar el COSTE. Otra heurística podría ser generar un número al azar y multiplicarlo por 23, otra usar el índice del nodo en la lista de nodos del grafo, etc etc etc. Vamos, lo que te de la gana A* también te dice que si el coste que te da la heurística es siempre menor que el coste real, entonces A* encontrará el mejor camino.

Si tienes ascensores y cosas extrañas (teleportadores, etc etc), está claro que la heurística euclídea de por si no te vale. Deberías hacer otra cosa para acomodar esos "caminos" extraños.

Así que no te lies con las distancias y los costes. En un mapa con terrenos (como el que comentas de las carreteras), donde por ejemplo el coste de un nodo a otro es: coste arco = (distancia * el coste del terreno), la heurística euclídea te va a funcionar (y el A* va a ir por carreteras). Ten en cuenta que A* no entiende de distancias, entiende de costes: si le sale más barato ir por la carretera que por el camino de cabras aunque el camino de cabras tenga menos distancia real, va a ir por la carretera, porque para decidir usa dos valores: el coste real para llegar a un punto y el coste estimado para llegar de ese punto al final. Puede que el camino de cabras tenga un coste estimado menor (por la euclídea), pero su coste para llegar real es mayor que el de las carreteras, con lo cual, se va por las carreteras.

Mira un ejemplo: queremos ir de I (inicio) a F (final). Usamos la euclídea. Cada número es el coste para movernos a ese nodo en el grafo.

Código: [Seleccionar]

I 10 10 F
1 10 10 1
1 10 10 1
1 10 10 1
1 10 10 1
1  1   1  1

Aunque el camino con menos distancia es I -> 10 -> 10 -> F, A* va a ir por la fila de 1 que rodean a los 10. Y eso que tu estimas el coste con la distancia! Pero es que no solo es la estimación, es lo que te cuesta moverte de verdad, y cuesta más moverse por dos 10s (2x10 = 20, tu camino de cabras) que por doce 1s (12x1 = 12, las autopistas).

A ver si así queda más claro Un saludo!

Vicente

[marcode]

 Sí, si supongo que tendrás razón (más te vale (twist))

La intención es hacer un algoritmo genérico que sirva para cualquier tipo de caminos y creo que la mejor heurística posible es la de la distancia euclídea, ya que por lo general (a no ser que sea un mundo muy extraño) las distancias están muy relacionadas con sus costes.

Claro que en un mundo 3D se pueden dar infinidad de casos en los que no siempre sea así, como tipos de terreno, escaleras, teleportadores, diferentes medios de transporte, lugares donde hay que dar una serie de palancas o usar llaves y en las que por lo tanto hay un coste añadido. Y tenía mi temor de que pudiera fallar en alguna circunstancia la heurística por distancia suponiendo que añadiera o quitara costes a algunos arcos, en cuyo caso tiraría por tierra el algoritmo.

Entonces, ya tengo implementado A* correctamente, el principal lastre que tenía (entre otros) era el del calculo de las distancias, ya que usaba la fórmula de la raíz cuadrada de la suma de las distancias al cuadrado. Pero he podido comprobar que funciona sin hallar la raíz cuadrada ya que al usarse para comparar si es mayor o menor, se puede hacer aunque estén elevadas al cuadrado (es un truco que suelo usar, supongo que lo conoceréis), el caso es que ahora sí que va rápido y creo que lo podré optimizar aún más.

La forma de tratar la lista lo hago con una lista de punteros, extraigo el nodo de menor distancia que he calculado y guardado previamente la primera vez que fue expandido, meto en el hueco el último, y reduzco en 1 el tamaño de la lista.

Voy a intentar hacerlo como tú para ver si mejora la velocidad, aunque creo que el mayor tiempo se lo lleva el cálculo de la distancia euclídea entre nodos.

[Vicente]

 Hola,

como bien dices, hay multitud de casos raros que pueden hacer que A* no valga para tu problema (los tipos de terreno no veo porque, pero si ascensores, teleportadores, etc etc). Seguramente para tu problema en concreto tendrás que cacharrear con el algoritmo básico para que haga lo que quieres exactamente.

Respecto a la velocidad, yo supongo que la mejor forma de optimizar el algoritmo es reduciendo el número de nodos que expande: a menos nodos menos operaciones Respecto a la lista, si lo he entendido bien tu usas una lísta y buscas línealmente el siguiente elemento a extraer no? Mientras que para añadir un elemento simplemente lo pones en la lista y fin (o eso he creido entender). Tu tienes O(d) para sacar algo de la lista y O(1) para insertarlo. Con una cola de prioridad implementada como un heap tienes O(lg d) para insertar y extraer. Ya es cuestión de hacer números

Otra cosa, no se el problema que tienes, pero A* es muy pesado en memoria normalmente. Otro aspecto que a lo mejor te interesa optimizar (claro que si el grafo es pequeño da igual).

Ya nos contarás los resultados Un saludo!

Vicente

P.D.: la optimización de la euclídea de usar las distancias al cuadrado para evitarse una raíz cuadrada es útil también sip

[marcode]

 

como bien dices, hay multitud de casos raros que pueden hacer que A* no valga para tu problema (los tipos de terreno no veo porque, pero si ascensores, teleportadores, etc etc). Seguramente para tu problema en concreto tendrás que cacharrear con el algoritmo básico para que haga lo que quieres exactamente.

No tengo pensado hacer nada especial para ningún problema en concreto, simplemente con el algoritmo A* con heurística por distancias, pero teniendo en cuenta que en algunos casos (o en muchos) puede no ser siempre el mejor camino la distancia mas corta por lo que no debe fallar.

Lo de los tipos de terreno te pongo un ejemplo: Imagina que estás en un extremo de una piscina o lago, y quieres ir al otro lado, la distancia más corta es atravesarlo a nado, recto, sin embargo la de menor coste (la mejor) es dar un rodeo por el borde.

Se me ocurren montones de situaciones en las que puede darse este problema, uno de ellos que no he comentado antes y que es muy habitual, es cuando por ejemplo en un camino hay unos bichos que le van a hacer perder un tiempo valioso a todo el que vaya por ahí (siendo el mejor camino). En ese caso el trayecto más corto (de tiempo) puede estar yendo por otro lado.

[Vicente]

 El de la piscina es como el ejemplo que te he puesto arriba con los 1s y los 10s. Prueba tu A* usando la distancia euclídea con ese problema y verás como no falla En el ejemplo de tu piscina también funciona, con los bichos también funciona,... Simplemente es que pongas bien los costes a los arcos de los nodos.

El A* vale para muchas cosas, olvidate de la distancia (por ejemplo, con las heurísticas adecuadas se usa para resolver el cubo de rubrick ).

Un saludo!

Vicente