Awards
ICAPS 2022 Best Dissertation Award
Winners
-
Star-Topology Decoupled State-Space Search in AI Planning and Model Checking.
Daniel Gnad
The dissertation introduces “star decoupled search”, a novel way to carry forward state searches more effectively, making use and exploiting conditional independence relations that can be observed in the causal graph of the planning domain. Like partial order reduction techniques, and in particular, symbolic search methods, the idea is to represent sets of states in a suitable factorized manner that can provide exponential savings in both time and space. The dissertation formulates and studies this novel search technique, theoretically and experimentally, and shows how it can be used in combination with other techniques such as partial order reduction, symmetry breaking, and dominance pruning. The effectiveness of star decoupled search is not only demonstrated in the context of planning where a goal state of affairs is to be reached, but also in the setting of model checking for safety and liveness properties. Substantial savings of star decoupled search are shown clearly in both cases.
-
Online Spatio-Temporal Demand Supply Matching.
Meghna Lowalekar
The dissertation develops comprehensive solutions for effective online matching of demand to shared resources such as cars, food, or bikes, while accounting for potential future supply and demand. The contributions include novel algorithms for online matching that can efficiently handle tens of thousands of shared resources and thousands of demand requests per minute, theoretical guarantees on solution quality for single capacity and multi-capacity resources, and extensive empirical evaluation of the approach on real datasets and real systems at scale showing substantial performance gains. The effectiveness of the developed approaches has been demonstrated in real-world settings to match taxis to customers and to match security resources to potential threats and are being adopted for future use in several other application areas.
This award was presented live during the conference. The talk is part of the recorded live stream. Please select the plenary track on June 24th; the presentation starts around 8:14:00.
Runner-Up Awards
-
Synthesis of Interpretable and Obfuscatory Behaviors in Human-Aware AI Systems.
Anagha Kulkarni
The dissertation studies behavior synthesis algorithms whose objective is to improve the interpretability of the behavior of an intelligent agent in the presence of a human observer. In addition, it studies how environment redesign strategies can be leveraged to improve the overall interpretability of the agent’s behavior. To this end, it considers comprehensive assumptions about the entities present in the agent’s environment; namely, that such entities are cooperative, adversarial (i.e., attempt to infer information from the agent’s behavior) or a combination of both. In adversarial settings, the agent generates obfuscatory behavior that prevents sensitive information from falling into the hands of the adversarial entities. The dissertation shows that it is possible to synthesize interpretable as well as obfuscatory behaviors using a single underlying algorithmic framework. These results made significant contributions to the rapidly growing area of explainable planning.
-
Symmetry Breaking and Operator Pruning in Classical Planning and Beyond.
Alexander Shleyfman
The dissertation is devoted to the study of graph automorphisms as a tool for symmetry-based search pruning and heuristic enhancements for deterministic forward-search planning. The contributions significantly expand the existing knowledge in this area, including new ways to exploit strictly larger symmetry groups, extensions of A* that reduce search effort and increase the number of problems solved, a study of graph automorphisms for state-space pruning in satisficing planning, comprehensive analysis of the symmetry properties of several popular existing heuristic functions , and how they can be used to enhance heuristic estimates, and an integration of partial order reduction and symmetry elimination for cost-optimal classical planning. The formal analysis of the concepts and algorithms is rigorous, and the empirical analysis shows that substantial computational gains can be achieved, especially in optimal planning.
ICAPS 2022 Influential Paper Awards
Winners
-
Improved Non-deterministic Planning by Exploiting State Relevance (ICAPS 2012)
Christian Muise, Sheila McIlraith, Christopher Beck
This paper introduced the main techniques that form the foundation of the PRP planner, one of the very best planners for computing plans—particularly conditional plans with loops or policies—for fully observable non-deterministic (FOND) planning problems under stochastic fairness. Thanks to these techniques, PRP had the potential to compute plans in FOND domains up to several orders of magnitude faster than previous approaches. The effectiveness of these techniques encouraged significant follow up research on non-deterministic planning domains. Among others, it gave impetus to the research on relating planning in Artificial Intelligence and automated synthesis in Formal Methods.
Runner-Up Awards
-
Temporal Planning with Preferences and Time-Dependent Continuous Costs (ICAPS 2012)
J. Benton, Amanda Coles, Andrew Coles
This highly-cited, seminal paper in the area of temporal planning describes the temporal planning system OPTIC, which allows to express preferences that are not directly coupled with makespan. It uses mixed integer programming to reason about soft and hard constraints and it allows to use continuous functions to express soft constraints. These developments represent significant advances beyond what planning systems at that time were able to support. It is still used as a key reference system in the temporal planning area and it is often used in implemented systems when the need for temporal planning arises.
ICAPS 2022 Conference Awards
Best Paper Award:
Best Paper Runner-Up Award:
Best Student Paper Award:
Best Student Paper Runner-Up Award:
Best Industry and Applications Track Paper Award:
Best Undergraduate Student Paper Award:
ICAPS 2022 Outstanding PC and SPC Awards
Outstanding Senior Program Committee Members:
- Pascal Bercher
- Ronen Brafman
Outstanding Program Committee Members:
- Malte Helmert (Main Track)
- Florian Geisser (Industry and Applications Track)
- Masataro Asai (Planning and Learning Track)
- Sandhya Saisubramanian (Human-Aware Planning and Scheduling Track)