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.

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 by saturated cost partitioning. All this results in planners that exhibit superior performance in optimal classical planning, an achievement that is quite difficult nowdays 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.

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 state-space 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 and optimizing it are presented in the form of search-based algorithms or as compilations into planning problems.

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks

Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

Through the Lens of Sequence Submodularity

Sara Bernardini, Fabio Fagnani, Chiara Piacentini

Multi-Agent Pathfinding with Mutex Propagation

Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, T. K. Satish Kumar

Integrating Acting, Planning, and Learning in Hierarchical Operational Models

Sunandita Patra, James Mason, Amit Kumar, Malik Ghallab, Paolo Traverso, Dana Nau

D3WA+: A Case Study of XAIP in a Model Acquisition Task

Sarath Sreedharan, Tathagata Chakraborti, Christian Muise, Yasaman Khazaeni, Subbarao Kambhampati

IBM Scenario Planning Advisor: A Neuro-Symbolic ERM solution

Mark Feblowitz, Oktie Hassanzadeh, Michael Katz, Shirin Sohrabi, Kavitha Srinivas, Octavian Udrea