Récapitulatif de l'ICAPS 2021

Les chercheurs d'Amii ont récemment présenté leurs travaux lors de la 2021e Conférence internationale sur la planification et l'ordonnancement automatisés (ICAPS), qui s'est tenue virtuellement à Guangzhou, en Chine, du 2 au 13 août. L'ICAPS est le principal forum d'échange d'informations et de résultats de recherche sur la théorie et les applications des technologies de planification et d'ordonnancement intelligentes et automatisées.

Médaille d'argent du choix du public

Lors d'une présentation virtuelle à ICAPS 2021, Nathan Sturtevant, boursier et titulaire de la chaire d'IA de l'ICAR à Amii, a reçu une médaille d'argent dans le cadre du People's Choice Best System Demonstration Award pour son travail de développement de démos pour un cours sur la recherche heuristique à agent unique. Sturtevant a développé les démos dans le cadre d'un cours de deuxième cycle enseigné à l'Université de l'Alberta, où Sturtevant est professeur d'informatique et directeur du centre Amii à UAlberta. Il a mis à disposition les démos, le plan du cours et les vidéos du cours en ligne sur son site Web Moving AI Lab et continuera à mettre à jour le matériel.

Regardez ci-dessous un résumé de la démonstration du système primé :

Accédez au matériel de cours complet sur https://www.movingai.com/SAS/

"Les méthodes de recherche ont des usages variés, notamment la résolution d'énigmes, la planification et la recherche de chemin, entre autres. La recherche heuristique est à la base de nombreuses avancées et applications clés dans le domaine de l'IA. En mettant ces démonstrations et ces supports de cours gratuitement à la disposition de toute personne disposant d'une connexion Internet, j'espère fournir des ressources utiles aux instructeurs et aux apprenants qui souhaitent se plonger dans le monde de la recherche à agent unique", explique M. Sturtevant.

Sturtevant a également publié un certain nombre d'articles lors de la conférence, présentant de nouveaux algorithmes qui améliorent les méthodes de recherche heuristique à agent unique et s'attaquent également à des problèmes clés dans ce domaine.

Articles acceptés

*indique un chercheur ou un ancien élève d'Amii

Recherche de points de saut avec obstacles temporels
Shuli Hu, Daniel Harabor, Graeme Gange, Peter Stuckey et Nathan Sturtevant*.

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.

Recherche heuristique bidirectionnelle itérative d'approfondissement avec mémoire restreinte
Shahaf Shperberg, Steven Danishevski, Ariel Felner, Nathan Sturtevant*.

Le domaine de la recherche heuristique bidirectionnelle a récemment connu de grandes avancées. Cependant, le sujet de la recherche bidirectionnelle restreinte par la mémoire n'a pas reçu d'attention récente. Dans cet article, nous présentons un algorithme général de recherche heuristique itérative d'approfondissement bidirectionnel (IDBiHS) qui recherche simultanément dans les deux directions tout en contrôlant le point de rencontre des frontières de recherche. Nous présentons d'abord la variante de base d'IDBiHS, dont la mémoire est linéaire dans la profondeur de recherche. Nous ajoutons ensuite des améliorations qui exploitent la cohérence et l'heuristique front-to-front. Ensuite, nous passons au cas où une quantité fixe de mémoire est disponible pour stocker les nœuds pendant la recherche et nous développons deux variantes de IDBiHS : (1) A*+IDBiHS, qui commence avec A* et passe à IDBiHS dès que la mémoire est épuisée. (2) Une variante qui stocke des frontières partielles vers l'avant jusqu'à ce que la mémoire soit épuisée et qui essaie ensuite de correspondre à chacune d'entre elles à partir de la partie arrière. Enfin, nous comparons expérimentalement les nouveaux algorithmes aux algorithmes unidirectionnels et bidirectionnels existants. Dans de nombreux cas, nos nouveaux algorithmes sont plus performants que les précédents, tant en termes d'expansion de nœuds que de temps.

Recherche à coût croissant basée sur les conflits
Thayne T. Walker*, Nathan Sturtevant*, Han Zhang, Jiaoyang Li, Sven Koenig, Ariel Felner, T. K. Satish Kumar

Deux solveurs populaires basés sur la recherche optimale pour le problème MAPF (multi-agent pathfinding), le Conflict-Based Search (CBS) et le Increasing Cost Tree Search (ICTS), ont été étendus séparément pour les domaines temporels continus et la rupture de symétrie. Cependant, une approche de la rupture de symétrie dans les domaines temporels continus est restée insatisfaisante. Dans ce travail, nous introduisons un nouvel algorithme, Conflict-Based Increasing Cost Search (CBICS), qui est capable de briser la symétrie dans les domaines temporels continus en combinant les forces de CBS et ICTS. Nos expériences montrent que CBICS trouve souvent des solutions plus rapidement que CBS et ICTS dans les domaines du temps unitaire et du temps continu.

Démonstrations pour un cours de recherche heuristique à agent unique
Nathan Sturtevant*

Cet article décrit le matériel pédagogique disponible dans le cadre d'un cours de troisième cycle sur la recherche à agent unique. Ce matériel comprend actuellement 25 démos interactives qui illustrent différents algorithmes et concepts de recherche heuristique. Chaque démo est accompagnée de matériel provenant d'un ou plusieurs cours enregistrés qui se rapportent au travail présenté dans la démo. L'ensemble peut être utilisé comme référence ou pour l'enseignement de nombreux sujets fondamentaux de la recherche heuristique par agent unique.

Richard Sutton donne une conférence invitée sur l'apprentissage par renforcement.

Le conseiller scientifique en chef d'Amii, Richard S. Sutton, qui est également membre et titulaire de la chaire d'IA du CIFAR à Amii, a présenté un exposé invité intitulé Gaps in the Foundations of Planning with Approximation. Dans son exposé, M. Sutton évalue brièvement les défis que pose l'extension de la planification par programmation dynamique et propose des modèles d'attente, des métadonnées et la recherche de représentations comme stratégies générales d'apprentissage de modèles d'environnement approximatifs pouvant être utilisés dans la planification.

En 2022, l'ICAPS se tiendra à Singapour, les dates de la conférence restant à déterminer.

Découvrez comment Amii fait progresser la recherche de pointe en matière d'intelligence artificielle et d'apprentissage automatique : visitez notre page Recherche.