Recherche de points de saut avec obstacles temporels

Résumé :

Dans le cadre de la planification d'une trajectoire basée sur une grille à quatre connexions, il faut souvent tenir compte des obstacles temporels et mobiles : ceux qui apparaissent, disparaissent et peuvent empêcher l'agent d'atteindre sa cible. De tels problèmes sont courants dans une variété de contextes (jeux, robotique, etc.) et peuvent être étonnamment difficiles à résoudre. Premièrement, parce que l'aspect temporel augmente la taille de l'espace de recherche ; deuxièmement, parce que l'espace de recherche contient de nombreux chemins symétriques, indiscernables les uns des autres sauf par l'ordre dans lequel les mouvements de la grille apparaissent. Pour résoudre de tels problèmes, nous considérons un nouvel algorithme optimal - dans le style de la recherche par points de saut - qui peut identifier et briser ces symétries et ainsi améliorer les performances ; de plusieurs facteurs à plus d'un ordre de grandeur par rapport à SIPP, sans doute la référence de référence dans le domaine.