ICAPS Influential Paper Award 2020
Winners:
Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?
M. Helmert and C. Domshlak
In their seminal work, Helmert and Domshlak classify the main admissible heuristics for optimal planning and study how the different classes of heuristics compare to each other through a notion of dominance under polynomial-time reductions. This is one of the first theoretical studies on how different heuristics compare, and sheds light on where the most promising lines of research locate. During the investigation, the authors come up with the landmark-cut (LM-Cut) heuristic, show empirically that it is an excellent polynomial-time computable lower bound on the intractable optimal delete relaxation heuristic, and how an standard A* algorithm equipped with it is far better than the state of the art in optimal planning. The LM-Cut heuristic became for many years the undisputed best heuristic for optimal planning, a source of motivation and baseline for comparison for follow up work in optimal planning, and it also has been used in areas beyond optimal classical planning.
Breadth-First Heuristic Search
R. Zhou and E. Hansen
This paper, published in ICAPS 2004 and later in Artificial Intelligence, showed that the memory requirements of divide-and-conquer path reconstruction methods can be significantly reduced by using a breadth-first search strategy instead of a best-first search strategy due to the resulting reduction in the number of boundary nodes that need to be retained in memory. It introduced a family of such breadth-first heuristic search algorithms that includes Breadth-First Branch-and-Bound, Breadth-First Iterative-Deepening A*, and the approximate but efficient Divide-and-Conquer Beam Search, and then influenced other algorithms like the anytime Beam-Stack Search. The algorithms were evaluated not just on typical search benchmarks but also on several domain-independent STRIPS planning benchmarks, demonstrating both the ease of implementing the algorithms, the resulting reduction in memory consumption, and other advantages — a research direction that inspired the search and planning research communities.
ICAPS Best Dissertation Award 2020
Winners:
Counterexample-Guided Cartesian Abstraction Refinement and Saturated Cost Partitioning for Optimal Classical Planning
Jendrik Seipp
The dissertation is a thorough and comprehensive journey over abstractions of transition systems, effective methods to compute high-quality cost partitionings, and sophisticated yet well-founded engineering methods and techniques for obtaining novel state-of-the-art heuristics for optimal planning. The thesis makes important contributions in different areas: a novel type of abstraction, Cartesian abstraction, provides a finer level of granularity than the standard projections and domain abstractions but still supports an efficient management of the abstraction, a novel method for computing high-quality cost partitionings without the need to simultaneously maintain all the heuristics in memory, and ingenious ways to generate collections of different and diverse Cartesian abstractions that are then admissibly combined through saturated cost partitionings. All this results in planners that exhibit superior performance in optimal classical planning, an achievement that is quite difficult now days given the highly developed state of the art.
Abstractions in Reasoning for Long-Term Autonomy
Kyle Wray
The dissertation is a well-rounded enterprise for designing and deploying control solutions for autonomous vehicles based on decision theoretic planning. It shows how to develop and successfully deploy such solutions, and presents novel contributions in different areas: hierarchical MDP/POMDP planning, design of controllers, multi-objective decision making, semi-autonomous systems, and scalable online decision making. For hierarchical planning, the thesis introduces policy networks that permit a unified and clear integration of subproblems and their solutions, resolving the problem of transferring control between subproblems. In design of controllers, the belief-infused finite-state controller for POMDPs are introduced. In multi-objective decision making problems, the thesis develops the topological MDP model together with scalable algorithms. In the semi-autonomous setting (SAS), the dissertation proposes a model for semi-autonomous that is used to decide when help from the human is required together with analyses of its properties in terms of safety and operation. Finally, in scalable online decision making, the dissertation presents a technique called MODIA that permits an effective solution for the so-called intersection problem for autonomous vehicles which presents itself when the vehicle arrives at an intersection where other uncontrollable entities are found.
Honorable Mention:
Goal Recognition Design
Sarah Keren
The dissertation introduces the problem of Goal Recognition Design (GRD) together with a well-founded theoretical model and algorithms based on heuristic search and automated planning. GRD is the problem of how to modify an existing model or environment to facilitate a predefined goal recognition task. The dissertation presents the worst case distinctiveness (WCD) measure that is used to rank the different modifications for the environment, and transform the GRD task into an optimization problem. Algorithms for effectively computing the WCD measure are presented in the form of search-based algorithm or as compilations into planning problems.
ICAPS 2020 Conference Awards
Outstanding Paper Award:
Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks
Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt
Outstanding Paper Award Honorable Mention:
Through the Lens of Sequence Submodularity
Sara Bernardini, Fabio Fagnani, Chiara Piacentini
Outstanding Student Paper Award:
Multi-Agent Pathfinding with Mutex Propagation
Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, T. K. Satish Kumar
Outstanding Student Paper Award Honorable Mention:
Integrating Acting, Planning, and Learning in Hierarchical Operational Models
Sunandita Patra, James Mason, Amit Kumar, Malik Ghallab, Paolo Traverso, Dana Nau