Recapping ICAPS 2021

Amii researchers had their work featured recently at the 2021 International Conference on Automated Planning and Scheduling (ICAPS), which was hosted virtually in Guangzhou, China from August 2-13. ICAPS is the premier forum for exchanging news and research results on theory and applications of intelligent and automated planning and scheduling technology.

People's Choice Silver Medalist

Presenting virtually at ICAPS 2021, Nathan Sturtevant, Fellow and Canada CIFAR AI Chair at Amii, has been awarded a silver medal in the People’s Choice Best System Demonstration Award for his work developing Demos for a Course in Single-Agent Heuristic Search. Sturtevant developed the demos as part of a graduate course taught at the University of Alberta, where Sturtevant is a Professor of Computing Science and Director of the Amii centre at UAlberta. He has made demos, the course outline and course videos available online through his Moving AI Lab website and will continue to update the materials going forward.

Watch a summary of the award-winning system demonstration below:

Access the full course materials at https://www.movingai.com/SAS/

“Search methods have a variety of uses, including puzzle solving, planning and pathfinding, among others. Heuristic search underpins many key advancements and applications in the field of AI. By making these demos and course materials freely available for anyone with an internet connection, I hope to provide useful resources for instructors and learners alike who are interested in diving into the world of Single-Agent Search,” explains Sturtevant.

Sturtevant also had a number of papers published at the conference, introducing new algorithms that improve methods in single-agent heuristic search and also tackle key problems facing the field.

Accepted Papers

*indicates an Amii researcher or alum

Jump Point Search with Temporal Obstacles
Shuli Hu, Daniel Harabor, Graeme Gange, Peter Stuckey, Nathan Sturtevant*

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

Iterative-deepening Bidirectional Heuristic Search with Restricted Memory
Shahaf Shperberg, Steven Danishevski, Ariel Felner, Nathan Sturtevant*

The field of bidirectional heuristic search has recently seen great advances. However, the subject of memory-restricted bidirectional search has not received recent attention. In this paper we introduce a general iterative deepening bidirectional heuristic search algorithm (IDBiHS) that searches simultaneously in both directions while controlling the meeting point of the search frontiers. First, we present the basic variant of IDBiHS, whose memory is linear in the search depth. We then add improvements that exploit consistency and front-to-front heuristics. Next, we move to the case where a fixed amount of memory is available to store nodes during the search and develop two variants of IDBiHS: (1) A*+IDBiHS, that starts with A* and moves to IDBiHS as soon as memory is exhausted. (2) A variant that stores partial forward frontiers until memory is exhausted and then tries to match each of them from the backward side. Finally, we experimentally compare the new algorithms to existing unidirectional and bidirectional ones. In many cases our new algorithms outperform previous ones in both node expansions and time.

Conflict-Based Increasing Cost Search
Thayne T. Walker*, Nathan Sturtevant*, Han Zhang, Jiaoyang Li, Sven Koenig, Ariel Felner, T. K. Satish Kumar

Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.

Demos for a course in Single-Agent Heuristic Search
Nathan Sturtevant*

This paper describes educational material available from a graduate course on single-agent search. The material currently includes 25 interactive demos that illustrate different algorithms and concepts in heuristic search. Coupled with each demo is material from one or more recorded lectures that relate to the work shown in the demo. Together these can be used as a reference or for teaching many foundational topics in single-agent heuristic search.

Richard Sutton Delivers Invited Talk on Reinforcement Learning

Amii’s Chief Scientific Advisor, Richard S. Sutton, who is also a Fellow and Canada CIFAR AI Chair at Amii, delivered an invited talk entitled Gaps in the Foundations of Planning with Approximation. In the talk, Sutton briefly assesses the challenges of extending dynamic-programming-style planning and suggests expectation models, metadata, and representation search as general strategies for learning approximate environment models suitable for use in planning.

In 2022, ICAPS will be hosted in Singapore with conference dates still to be determined.

Learn how Amii advances world-leading artificial intelligence and machine learning research: visit our Research page.