Vés al contingut

Algorisme de cerca A*

De la Viquipèdia, l'enciclopèdia lliure

L'algorisme de cerca A* (en anglès, A-star algorithm) és un algorisme heurístic de cerca del camí més curt, molt eficient i generalitzable,[1] motiu pel qual s'utilitza sovint en molts camps de la informàtica, com ara en la robòtica o en aplicacions com ara videojocs.[2]

Peter Hart, Nils Nilsson i Bertram Raphael de l'Institut de Recerca de Stanford (ara SRI International) van publicar l'algorisme per primera vegada el 1968.[3] Es pot veure com una extensió de l'algorisme de Dijkstra, però amb un millor rendiment mitjançant l'heurística per guiar la cerca en direcció a l'objectiu, és a dir, emprant mètodes com la distància de Manhattan, la distància de Txebixov, la distància euclidiana o bé la distància d'octils.[4]

Funcionament

[modifica]

Es comença amb un node inicial i un node objectiu (final). Per cada node veí de l'actual es calcula el cost a moure's a aquest, el qual correspon a la suma entre la distància a l'actual i la distància a l'objectiu.

Això es pot representar com:

on és el següent node, el cost de la ruta des del primer node fins a , i és una funció heurística que estima el cost de la ruta més curta des de fins a l'objectiu. Llavors, s'avança al node no explorat amb un cost més baix de tots els calculats fins ara, i es repeteix el procés. Si més d'un node té el mateix valor, es tria el més proper a l'objectiu. Cal tenir en compte que un node ja explorat com a possible veí pot actualitzar el seu valor a un de més baix si es troba una ruta més ràpida per arribar a aquest. Tot i això, es pot ponderar la memòria màxima necessària de l'algorisme, de manera que per evitar excedir-la els nodes amb valor més alt són eliminats d'aquesta.[5]

Variants

[modifica]

A* bidireccional

[modifica]

Una A* bidireccional aplica l'algorisme A* des del node inicial fins al final i, alhora, des del node final fins a l'inicial, amb l'objectiu de trobar-se al mig. Això permet major eficiència en alguns casos, tot i que cal tenir especial cura en el criteri d'aturada de l'algorisme.[6][7]

A* ponderada

[modifica]

Es pot sacrificar l'optimitat de l'algorisme per tal d'obtenir un temps d’execució més ràpid inflant l'heurística, i per tant expandint un menor nombre de nodes.[8]

on és la ponderació, major que 1.

A més, es pot utilitzar un algorisme anytime, el qual consisteix a calcular la A* ponderada per cada cop més baixes fins a arribar a 1, introduint una manera d'actualitzar la ruta sense haver de descartar tota la memòria generada per cada nova .[9]

A* dinàmica

[modifica]

Els algorismes de cerca heurística incremental combinen la cerca incremental i heurística per optimitzar el temps computacional necessari de cerca en dominis que només es coneixen incompletament o que canvien dinàmicament. Dins d'aquest grup hi ha algorismes on la cerca actual deriva de l'anterior (Fringe Saving A* ),[10] actualitzen els valors de la cerca anterior durant la cerca actual per fer-los més informats (Generalized Adaptive A* ,[11] Reduced A* ),[12] o bé actualitzen quan és necessari, cosa que es pot interpretar com una transformació de l'arbre de cerca generat per l'A* inicial (Lifelong Planning A* ,[13] D* ,[14] D* Lite).[15]

L'algorisme D* (també anomenat A* dinàmica) és un dels algorismes de cerca incremental més utilitzats. Funciona de manera similar a l'algorisme A*, però només s'analitza el terreny proper del lloc inicial, i es fan suposicions sobre la resta de terreny inexplorat fins a arribar a l'objectiu, per tal d'obtenir la ruta. Al pas següent s'obté nova informació del terreny, i si és necessari, es recalcula la ruta.[16][14]

L'algorisme A* també es pot adaptar per trobar el camí més curt entre dos nodes en un graf o arbre ponderat, combinant-lo amb una cerca en profunditat o una cerca en amplada i aplicant-lo de forma iterativa. A cada iteració es realitza aquesta cerca en arbre, tallant una branca quan el cost total supera un llindar determinat. El llindar utilitzat per a la següent iteració és el cost mínim de tots els valors que han superat el llindar actual, el qual és calculat de forma heurística emprant l'algorisme A*.[17]

Planificació de camins basada en angles

[modifica]

Els algorismes de planificació de camins de qualsevol angle són un subconjunt d'algorismes que cerquen un camí entre dos punts de l'espai i permeten que els girs del camí tinguin qualsevol angle. El resultat és un camí que va directament cap a la meta i té relativament pocs girs. Alguns d'ells estan basats en l'algorisme A*, i es llisten a continuació.

  • Field D* és un algorisme que combina D* i A* ponderada utilitzant la interpolació durant cada expansió del node i trobant camins gairebé òptims a través de quadrícules de costos no uniformes.[18][19]
  • Block A* genera una base de dades de distància local que conté tots els camins possibles en una petita secció de la quadrícula. Fa referència a aquesta base de dades per trobar ràpidament camins de qualsevol angle a mida.[20]
  • Theta* utilitza el mateix cicle que A* però per cada expansió del vèrtex comprova si hi ha una línia de visió entre el node parent i el successor d'aquest.[21] També té una versió incremental Phi* , més eficient en entorns desconeguts bidimensionals.[22]

Cerca de punt de salt

[modifica]

La cerca de punt de salt és una optimització de l'algorisme A* per graelles amb cost uniforme. Redueix les simetries en el procés de cerca mitjançant l'eliminació d'alguns nodes basant-se en suposicions respecte als veïns del node actual, sempre que les condicions generals imposades en la graella siguin satisfetes. El resultat és un algorisme que pot realitzar "salts" llargs en els trajectes lineals de la graella, enlloc de fer petits passos d'una posició a una altra tal com passa amb l'algorisme A*.[23]

Referències

[modifica]
  1. ↑ Zeng, W.; Church, R. L. «Finding shortest paths on real road networks: the case for A*». International Journal of Geographical Information Science, 23, 4, 2009, pàg. 531-543.
  2. ↑ Russell, Stuart J. Artificial intelligence: A modern approach. 4a ed.. Boston: Pearson, 2018. ISBN 978-0134610993. OCLC 1021874142. 
  3. ↑ Hart, P.; Nilsson, N. J.; Raphael, B. «A Formal Basis for the Heuristic Determination of Minimum Cost Paths». IEEE Transactions on Systems Science and Cybernetics, 4, 2, 1968, pàg. 100–107. DOI: 10.1109/TSSC.1968.300136.
  4. ↑ Zhang, An; Li, Chong; Bi, Wenhao «Rectangle expansion A∗ pathfinding for grid maps». Chinese Journal of Aeronautics, 29, 5, 2016, pàg. 1385-1396. DOI: 10.1016/j.cja.2016.04.023 [Consulta: 9 setembre 2021].
  5. ↑ Russell, S. (1992). "Efficient memory-bounded search methods". : 1–5, Vienna, Austria: John Wiley & Sons, New York, NY 
  6. ↑ «Efficient Point-to-Point Shortest Path Algorithms». Princeton University.
  7. ↑ Pijls, Wim; Post, Henk «Yet another bidirectional algorithm for shortest paths». Econometric Institute Report, 2009.
  8. ↑ Pohl, Ira «First results on the effect of error in heuristic search». Machine Intelligence, 5, 1970, pàg. 219-236.
  9. ↑ Krause, Alex «Anytime Dynamic A*: An Anytime, Replanning Algorithm». Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling, 2005.
  10. ↑ Sun, X.; Koenig, S. «The Fringe-Saving A* Search Algorithm - A Feasibility Study». Proceedings of the International Joint Conference on Artificial Intelligence, 2007, pàg. 2391-7.
  11. ↑ Sun, X.; Keonig, S.; Yeoh, W. «Generalized Adaptive A*». In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008, pàg. 469-476.
  12. ↑ R. Fareh, M. Baziyad, M. H. Rahman, T. Rabie, M. Bettayeb «Investigating Reduced Path Planning Strategy for Differential Wheeled Mobile Robot». Cambridge University Press, 38, 2, 2020, pàg. 235-255. DOI: 10.1017/S0263574719000572.
  13. ↑ Koenig, S.; Likhachev, M.; Furcy, D. «Lifelong Planning A*». Artificial Intelligence, 155, 1-2, 2004, pàg. 93-146.
  14. ↑ 14,0 14,1 Stentz, Anthony «The Focussed D* Algorithm for Real-Time Replanning». Proceedings of the International Joint Conference on Artificial Intelligence, 1995, pàg. 1652-9.
  15. ↑ Koenig, S.; Likhachev, M. «Fast Replanning for Navigation in Unknown Terrain». Transactions on Robotics, 21, 3, 2005, pàg. 354-363.
  16. ↑ Stentz, Anthony «Optimal and Efficient Path Planning for Partially-Known Environments». Proceedings of the International Conference on Robotics and Automation, 1994, p. 3310–3317.
  17. ↑ Korf, Richard E. «Depth-first Iterative-Deepening: An Optimal Admissible Tree Search». Artificial Intelligence, 27, 1985, pàg. 97–109. DOI: 10.1016/0004-3702(85)90084-0.
  18. ↑ David Ferguson, Anthony Stentz, "The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments," tech. report CMU-RI-TR-05-19, Robotics Institute, Carnegie Mellon University, June, 2005
  19. ↑ Mitchell, J. S. B.; Papadimitriou, C. H. «The weighted region problem: Finding shortest paths through a weighted planar subdivision». Journal of the ACM, 38, 1991, pàg. 18–73. DOI: 10.1145/102782.102784.
  20. ↑ P. Yap, N. Burch, R. Holte, and J. Schaeffer, Block A*: Database-Driven Search with Applications in Any-angle Path-Planning. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
  21. ↑ A. Nash, K. Daniel, S. Koenig and A. Felner. Theta*: Any-Angle Path Planning on Grids. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1177–1183, 2007.
  22. ↑ Nash, A.; Koenig, S.; Likhachev, M. «Incremental Phi*: Incremental Any-Angle Path Planning on Grids». Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2009, pàg. 1824–1830.
  23. ↑ ; Grastien, Alban«Improving Jump Point Search». Association for the Advancement of Artificial Intelligence.

Vegeu també

[modifica]

Enllaços externs

[modifica]
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Algorisme_de_cerca_A*&oldid=32884798»