Jump point search
Le terme anglais : Jump Point Search (JPS (Harabor et Grastien 2012), littéralement « Recherche du point par saut ») un algorithme de recherche de chemin. C'est une variante de l'algorithme A*, optimisée pour le cas des grilles à coût uniforme.
L'évolution, JPS+ (Harabor et Grastien 2014), réduit les symétries dans la procédure de recherche, en supprimant des parties non nécessaire du graphe d'après une de leurs recherches de 2011[1].
Si cette technique est avant tout utilisée pour l'intelligence artificielle, en particulier dans les jeux vidéo, d'autres auteurs ont proposé de les utiliser pour la construction des immeubles de grande hauteur, afin d'en améliorer la productivité[2].
Améliorations
Il existe également différentes autres variantes, JPS+ Bucket, BLJPS, BLJPS2, BLJPS_Subgoal[3] - [4]
La technique de compression RLE des tables de chemins optimaux (anglais : Compressing Optimal Paths with Run Length Encoding (Strasser, Botea et Harabor 2015)), permet également d'améliorer l'efficacité de tous ces algorithmes en compressant la table de pré-calcul, permettant l'utilisation de moins de ressources mémoires et un accès plus court aux informations.
Annexes
Notes et références
- (Harabor et Grastien 2011)
- (Kwon, Kim et Kang 2016)
- Nathan R. Sturtevant « The Grid-Based Path Planning Competition -or- Contractions, contractions everywhere » () (lire en ligne)
—Symposium on Combinatorial Search - (Strasser, Botea et Harabor 2015, p. 619)
Bibliographie
- (en) Daniel Harabor, Alban Grastien « Online Graph Pruning for Pathfinding on Grid Maps » ()
—25th National Conference on Artificial Intelligence (lire en ligne) - (en) Harabor et Grastien « The JPS Pathfinding System » ()
—Proceedings of the 5th Symposium on Combinatorial Search (lire en ligne) - (en) Bryan Tanner, « Jump Point Search Analysis », ?, Florida State University, (lire en ligne)
- (en) Daniel Harabor, Alban Grastien, « Improving Jump Point Search », Proceeding, Portsmouth, New Hampshire, USA, NICTA and The Australian National University / AAAI Press, , p. 128-135 (lire en ligne)
- (en) T. Uras, S. Koenig et C. Hernàndez, « Subgoal graphs in for optimal pathfinding in eight-neighbour grids », ICAPS, (lire en ligne)
- (en) Sanjay Renukamurthy, « Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS », www1.uwindsor.ca, Lamblon Tower, Université de Windsor, (présentation en ligne)
- (en) Jason Traish, James Tulip et Wayne Moore, « Optimization Using Boundary Lookup Jump Point Search », IEEE Transactions on Computational Intelligence and AI in Games, vol. 8, no 3, , p. 268 — 277 (DOI 10.1109/TCIAIG.2015.2421493, présentation en ligne)
- (en) Ben Strasser, Adi Botea et Daniel Harabor, « Compressing Optimal Paths with Run Length Encoding », Journal of Artificial Intelligence Research, vol. 54, , p. 593-629 (DOI 10.1613/jair.4931, lire en ligne)
- (ko) 권재범 (Kwon Jaebeom), 김태훈 (Kim Taehoon) et 강경인 (Kang Kyung-In), « 초고층 건축공사의 생산성 향상을 위한 Jump Point Search 기반 작업층 자재배치 최적화 모델 », Journal of Advanced Engineering and Technology, vol. 9, no 2, , p. 143~150 (www.chosun.ac.kr/common/downLoad.do?siteId=riet&fileSeq=200158) (Floor-level Layout Planning Optimization Model using Jump Point Search for Improving Productivity of Tall Building Construction)
Articles connexes
- Algorithme A* ;
- Any-angle path planning (en) ;
- Rapidly-exploring random tree (en).
Liens externes
- https://github.com/SteveRabin/JPSPlusWithGoalBounding — Exemple d'implémentation de JPS+ avec une limitation par le but (Goal bounding).