Les travaux des chercheurs d'Amii ont été présentés récemment lors de la 2021e conférence internationale sur la planification et l'ordonnancement automatisés (ICAPS). 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. 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
Présentation virtuelle à ICAPS 2021, Nathan SturtevantFellow et titulaire de la chaire d'IA du CIFAR au Canada à Amii, a reçu le prix de l'ICAPS 2021. récompensé une médaille d'argent dans la catégorie People's Choice Best System Demonstration Award pour son travail de développement de démonstrations pour un cours sur la recherche heuristique mono-agent. Démonstrations pour un cours sur la recherche heuristique mono-agent. Sturtevant a développé les démonstrations dans le cadre d'un cours de troisième cycle dispensé à l'Université de l'Alberta. Université de l'Albertaoù Sturtevant est professeur d'informatique et directeur du centre Amii à l'Université de l'Alberta. Il a mis en ligne les démonstrations, le plan du cours et les vidéos du cours sur son site web du Moving AI Lab et continuera à mettre à jour le matériel à l'avenir.
Regardez ci-dessous un résumé de la démonstration du système primé :
Accédez au matériel de cours complet à l'adresse suivante https://www.movingai.com/SAS/
"Les méthodes de recherche ont de multiples usages, notamment la résolution d'énigmes, la planification et la recherche de chemins, entre autres. En mettant ces démonstrations et ces supports de cours à la disposition de tous ceux qui disposent d'une connexion Internet, j'espère fournir des ressources utiles aux formateurs et aux apprenants qui souhaitent se plonger dans le monde de la recherche par agent unique", explique M. Sturtevant.
En mettant ces démonstrations et ces supports de cours à la disposition de tous ceux qui disposent d'une connexion Internet, j'espère fournir des ressources utiles aux formateurs et aux apprenants qui souhaitent se plonger dans le monde de la recherche d'un agent unique.
Nathan Sturtevant, boursier et titulaire de la chaire AI de l'ICAR Canada
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 des obstacles temporels Shuli Hu, Daniel Harabor, Graeme Gange, Peter Stuckey, 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 et approfondie 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 sur la recherche heuristique mono-agent 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 CIFAR d'IA au Canada à Amii, a présenté une conférence invitée intitulée Lacunes dans les fondements de la planification avec approximation. Dans son exposé, M. Sutton évalue brièvement les défis posés par l'extension de la planification de type programmation dynamique et propose des modèles d'attentes, des métadonnées et la recherche de représentations comme stratégies générales pour l'apprentissage de modèles d'environnement approximatifs utilisables dans la planification.
En 2022, l'ICAPS se tiendra à Singapour, les dates de la conférence restant à déterminer.