¿Cómo acelerar el algoritmo A * a grandes escalas espaciales?

Desde http://ccl.northwestern.edu/netlogo/models/community/Astardemo , codifiqué un algoritmo A * usando nodos en una red para definir rutas de menor costo. El código parece funcionar, pero es demasiado lento cuando lo uso a grandes escalas espaciales. Mi paisaje tiene una extensión de 1000 parches x 1000 parches con 1 parche = 1 píxel. Incluso si lo reduzco a 400 parches x 400 parches con 1 parche = 1 píxel, es demasiado lento (no puedo modificar mi paisaje por debajo de 400 parches por 400 parches). Aquí está el código:

to find-path [ source-node destination-node] let search-done? false let search-path [] let current-node 0 set list-open [] set list-closed [] let list-links-with-nodes-in-list-closed [] let list-links [] set list-open lput source-node list-open while [ search-done? != true] [ ifelse length list-open != 0 [ set list-open sort-by [[f] of ?1 < [f] of ?2] list-open set current-node item 0 list-open set list-open remove-item 0 list-open set list-closed lput current-node list-closed ask current-node [ if parent-node != 0[ set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed ] ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)] [ set search-done? true ] [ ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ] [ if not member? self list-open and self != source-node and self != destination-node [ set list-open lput self list-open set parent-node current-node set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node) set g sum (map [ [link-cost] of ? ] list-links) set h distance destination-node set f (g + h) ] ] ] ] ] [ user-message( "A path from the source to the destination does not exist." ) report [] ] ] set search-path lput current-node search-path let temp first search-path while [ temp != source-node ] [ ask temp [ set color red ] set search-path lput [parent-node] of temp search-path set temp [parent-node] of temp ] set search-path fput destination-node search-path set search-path reverse search-path print search-path end 

Lamentablemente, no sé cómo acelerar este código. ¿Existe una solución para calcular rutas rápidamente de menor costo a grandes escalas espaciales?

Muchas gracias por su ayuda.

Era curioso, así que probé el mío A * y aquí está el resultado mío

Laberinto 1280 x 800 x 32 bits píxeles

Una prueba

  • como puedes ver, tomó ~ 23ms
  • sin multihilo (AMD 3.2GHz)
  • Aplicación C ++ de 32 bits (BDS2006 Turbo C ++ o Borland C ++ builder 2006 si quieres)
  • el camino más lento que encontré fue ~ 44ms (llenar el mapa casi completo)

Creo que eso es lo suficientemente rápido …

Aquí está la fuente para la clase A * de la mina:

 //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- const DWORD A_star_space=0xFFFFFFFF; const DWORD A_star_wall =0xFFFFFFFE; //--------------------------------------------------------------------------- class A_star { public: // variables DWORD **map; // map[ys][xs] int xs,ys; // map esolution xs*ys<0xFFFFFFFE !!! int *px,*py,ps; // output points px[ps],py[ps] after compute() // internals A_star(); ~A_star(); void _freemap(); // release map memory void _freepnt(); // release px,py memory // inteface void resize(int _xs,int _ys); // realloc map to new resolution void set(Graphics::TBitmap *bmp,DWORD col_wall); // copy bitmap to map void get(Graphics::TBitmap *bmp); // draw map to bitmap for debuging void compute(int x0,int y0,int x1,int y1); // compute path from x0,y0 to x1,y1 output to px,py }; //--------------------------------------------------------------------------- A_star::A_star() { map=NULL; xs=0; ys=0; px=NULL; py=NULL; ps=0; } A_star::~A_star() { _freemap(); _freepnt(); } void A_star::_freemap() { if (map) delete[] map; map=NULL; xs=0; ys=0; } void A_star::_freepnt() { if (px) delete[] px; px=NULL; if (py) delete[] py; py=NULL; ps=0; } //--------------------------------------------------------------------------- void A_star::resize(int _xs,int _ys) { if ((xs==_xs)&&(ys==_ys)) return; _freemap(); xs=_xs; ys=_ys; map=new DWORD*[ys]; for (int y=0;yWidth,bmp->Height); for (y=0;yScanLine[y],x=0;xSetSize(xs,ys); for (y=0;yScanLine[y],x=0;x>1)&0x7F)+0x00404040; p[x]=c; } } //--------------------------------------------------------------------------- void A_star::compute(int x0,int y0,int x1,int y1) { int x,y,xmin,xmax,ymin,ymax,xx,yy; DWORD i,j,e; // [clear previous paths] for (y=0;y=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymin>yy) ymin=yy; } yy=y+1; xx=x; if ((yy=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmin>xx) xmin=xx; } yy=y; xx=x+1; if ((xx=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; } yy=y+1; xx=x; if ((yy=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; } yy=y; xx=x+1; if ((xx=0;i--,j--) { px[i]=x; py[i]=y; if ((y> 0)&&(map[y-1][x]==j)) { y--; continue; } if ((y 1)&&(map[y][x-1]==j)) { x--; continue; } if ((x 

Sé que es demasiado código pero está completo. Lo importante es en el compute función miembro para buscar [A* changed points list] . El A* procesado (rem-ed) es aproximadamente 100 veces más lento.

Usa el bitmap de Borland VCL para que, si no lo tienes, ignore las funciones get,set configúralo y reescríbelo a tu entrada / salida gfx style. Simplemente cargan el map del map de bitmap y dibujan el map calculado de nuevo en el bitmap de bitmap

Uso:

 // init A_star map; Graphics::TBitmap *maze=new Graphics::TBitmap; maze->LoadFromFile("maze.bmp"); maze->HandleType=bmDIB; maze->PixelFormat=pf32bit; map.set(maze,0); // walls are 0x00000000 (black) // this can be called repetitive without another init map.compute(x0,y0,x1,y1); // map.px[map.ps],map.py[map.ps] holds the path map.get(maze,0); // this is just for drawing the result map back to bitmap for viewing 

A * es dos heurísticas; Algoritmo de Djikstra y búsqueda codiciosa. El algoritmo de Djikstra busca la ruta más corta. The Greedy Search busca la ruta más barata. El algoritmo de Djikstra es extraordinariamente lento porque no toma riesgos. Multiplique el efecto de la Búsqueda codiciosa para asumir más riesgos.

Por ejemplo, si A* = Djikstra + Greedy , entonces un A* = Djikstra + 1.1 * Greedy más rápido A* = Djikstra + 1.1 * Greedy . No importa cuánto optimice su acceso a la memoria o su código, no solucionará un mal enfoque para resolver el problema. Haga que su A * sea más codicioso y se enfocará en encontrar una solución, en lugar de una solución perfecta .

NOTA:

 Greedy Search = distance from end Djikstra's Algorithm = distance from start 

en el estándar A *, buscará soluciones perfectas hasta llegar a un obstáculo. Este video muestra las diferentes heurísticas de búsqueda en acción; fíjate qué tan rápido puede ser una búsqueda golosa (salta a 2:22 para A *, 4:40 para Greedy). Yo mismo tuve un problema similar cuando comencé con A * y el esquema modificado A * I anterior mejoró exponencialmente mi rendimiento. Moraleja de la historia; usa la herramienta correcta para el trabajo.

TL; DR: ¡Incluye en tu lista de nodos (gráfico) solo los parches (o agentes) que son importantes!

Una forma de acelerar las cosas es no buscar en cada espacio de la cuadrícula. A * es una búsqueda de gráficos, pero parece que la mayoría de los codificadores simplemente vuelcan cada punto de la grilla en el gráfico. Eso no es requerido. Usar un gráfico de búsqueda disperso, en lugar de buscar cada punto en la pantalla, puede acelerar las cosas.

Incluso en un laberinto complejo, puede acelerar incluyendo solo esquinas y uniones en el gráfico. No agregue cuadrículas de pasillo a la lista abierta – busque con anticipación para encontrar la siguiente esquina o cruce. Aquí es donde el preprocesamiento de la pantalla / cuadrícula / mapa para construir el gráfico de búsqueda puede ahorrar tiempo más tarde.

Como puede ver en esta imagen de mi (bastante ineficiente) modelo A * en turtlezero.com, un enfoque ingenuo crea muchos pasos adicionales. Cualquier nodo abierto creado en un largo corredor recto se desperdicia:

Ejemplo de laberinto resuelto con una a-estrella ingenua

Al eliminar estos pasos del gráfico, la solución podría encontrarse cientos de veces más rápida.

Otra técnica de gráficos dispersos es usar un gráfico que es gradualmente menos denso cuanto más lejos del andador. Es decir, haga que su espacio de búsqueda esté detallado cerca del andador, y escaso (menos nodos, menos precisos con respecto a los obstáculos) lejos del andador. Esto es especialmente útil cuando el andador se mueve a través de un terreno detallado en un mapa que está cambiando o hacia un objective que se está moviendo y la ruta debe volver a calcularse de todos modos.

Por ejemplo, en una simulación de tráfico donde las carreteras pueden estancarse, o pueden ocurrir accidentes. Del mismo modo, una simulación en la que un agente persigue a otro agente en un paisaje cambiante. En estos casos, solo los próximos pasos deben trazarse exactamente. La ruta general al destino puede ser aproximada.

Una forma simple de implementar esto es boost gradualmente el tamaño del paso del andador a medida que la ruta se hace más larga. Haga caso omiso de los obstáculos o realice una prueba rápida de intersección de línea o tangente. Esto le da al caminante una idea general de a dónde ir.

Se puede volver a calcular una ruta mejorada con cada paso, o periódicamente, o cuando se encuentra un obstáculo.

Puede que solo se guarden milisegundos, pero los milisegundos desperdiciados en el final del camino que pronto se cambiará podrían utilizarse mejor, proporcionando cerebros para más andadores, mejores gráficos o más tiempo con su familia.

Para obtener un ejemplo de un gráfico disperso de densidad variable, consulte el capítulo 8 de la Progtwigción avanzada de Java Por David Wallace Croft de APress: http://www.apress.com/game-programming/java/9781590591239

Él usa un gráfico circular de creciente escasez en un juego de tanques demo con un algoritmo a * que maneja los tanques enemigos.

Otro enfoque de gráficos dispersos es poblar el gráfico con solo puntos de interés. Por ejemplo, para trazar una ruta a través de un campus simple de edificios, solo las entradas, salidas y esquinas son importantes. Los puntos a lo largo del costado de un edificio o en el espacio abierto entre ellos no son importantes, y pueden omitirse del gráfico de búsqueda. Un mapa más detallado podría necesitar más puntos de referencia, como un círculo de nodos alrededor de una fuente o estatua, o donde los caminos pavimentados se cruzan.

Aquí hay un diagtwig que muestra las rutas entre los puntos de referencia.

Muestra de puntos de referencia de esquina de edificio para la optimización de búsqueda de ruta

Esto fue generado por el modelo campus-buildings-path-graph por mí en turtlezero.com: http://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph

Utiliza consultas de parches de netlogo simples para encontrar puntos de interés, como esquinas exteriores e interiores. Estoy seguro de que un conjunto de consultas algo más sofisticado podría tratar con elementos como muros diagonales. Pero incluso sin una mayor optimización, el espacio de búsqueda A * se reduciría en órdenes de magnitud.

Lamentablemente, dado que ahora Java 1.7 no permitirá los applets sin firmar, no puede ejecutar el modelo en la página web sin modificar la configuración de seguridad de Java. Lo siento por eso. Pero lee la descripción.

Si planea reutilizar el mismo mapa varias veces, alguna forma de preprocesamiento suele ser óptima. Efectivamente, calcula las distancias más cortas entre algunos puntos comunes y los agrega a los gráficos como bordes, esto generalmente ayudará a * encontrar una solución más rápidamente. Aunque es más difícil de implementar.

Por ejemplo, puede hacer esto para todas las rutas de autopistas en un mapa del Reino Unido, por lo que el algoritmo de búsqueda solo tiene que encontrar una ruta a una autopista, y desde los cruces de autopistas a su destino.

No puedo decir cuál podría ser la causa real de la lentitud observada. Tal vez solo se deba a deficiencias en la eficiencia impuestas por el lenguaje de progtwigción en cuestión. ¿Cómo midiste tu rendimiento? ¿Cómo podemos reproducirlo?

Además de eso, la heurística (medición de distancia) que se utiliza tiene una gran influencia en la cantidad de exploración que se realiza para encontrar la ruta óptima y, por lo tanto, también influye en la eficiencia percibida del algoritmo.

En teoría, debe usar una heurística admisible, es decir, una que nunca sobreestime la distancia restante. En la práctica, dependiendo de la complejidad del laberinto, una opción conservadora para un laberinto en cuadrícula 2d, como la distancia de Manhattan, podría subestimar significativamente la distancia restante. Por lo tanto, se realiza una gran cantidad de exploración en áreas del laberinto lejos de la meta. Esto conduce a un grado de exploración que se asemeja mucho más al de una búsqueda exhaustiva (por ejemplo, búsqueda de primer orden), que lo que uno esperaría de un algoritmo de búsqueda informada.

Esto podría ser algo para investigar.

También eche un vistazo a mi respuesta relacionada aquí:

Allí he comparado diferentes heurísticas utilizadas con el algoritmo básico A-Star y visualicé los resultados. Puede que le resulte interesante.

    Intereting Posts