ICAPS Awards

The ICAPS Influential Paper Awards honor significant and influential papers published at least ten years earlier in a planning and scheduling conference. The ICAPS Best Dissertation Awards honor outstanding PhD theses in any area of automated planning and scheduling.

Awards presented at ICAPS 2024

Awards committee: Siddharth Srivastava (chair), Nir Lipovetzky, Ron Petrick, Shirin Sohrabi

ICAPS Influential Paper Award 2024

• Winner
  • Florian Pommerening, Gabriele Röger, Malte Helmert, Blai Bonet. LP-Based Heuristics for Cost-Optimal Planning (ICAPS 2014)
    “This paper introduced groundbreaking techniques in heuristic search for cost-optimal planning problems. By leveraging Linear Programming formulations, the authors created a novel framework for deriving admissible heuristics using combinations of constraints representing known heuristic families. The resulting framework enhanced the efficiency of optimal planning algorithms and uncovered new theoretical results. The methodologies presented in this work laid the foundations for a renewed interest in classic optimisation techniques for planning, significantly advancing the state of the art in cost-optimal planning.”

ICAPS Best Dissertation Award 2024

• Winners
  • Daniel Höller for his dissertation Hierarchical Planning : Expressivity Analysis, Solving Techniques, and Problem Compilations.
    “This dissertation presents multiple novel contributions advancing the foundations and the state of the art in Hierarchical Task Network (HTN) planning, paving the way towards making hierarchical planning more usable in practice. The thesis includes a comprehensive study of structural expressivity and complexity of HTN planning and classical planning, supporting efficient computation of solutions, as well as plan verification, plan recognition, and plan repair. Additionally, the thesis proposes an extension to PDDL, called the Hierarchical Domain Definition Language (HDDL), which is rapidly emerging as a standard for HTN planning. Furthermore, the thesis demonstrates for the first time that classical planning heuristics can be consistently used in hierarchical planning. Empirical analysis conducted as a part of the dissertation shows that these methods lead to grounded models with significantly smaller sizes and computational complexities than those of existing approaches.”
  • David Speck for his dissertation Symbolic Search for Optimal Planning with Expressive Extensions.
    “This dissertation is an innovative work that significantly advances the use of symbolic search for optimal planning and opens up new directions for future research based on these techniques. A key result of this work is an analysis of the connection between heuristics and symbolic search, which provides support for the conclusion that even perfect heuristics are not always beneficial to search performance compared with blind search, particularly with bidirectional search methods. The dissertation also extends symbolic search methods to natively deal with axioms/derived variables and state-dependent action costs; it provides a sound, complete, and optimal approach to oversubscription planning; and it develops a technique for generating top-k plans using symbolic search. In each case, new theoretical and algorithmic results are established, with experimental results that challenge the state of the art.”
• Honorable Mention
  • Maayan Shvo for his dissertation Theory of Mind Reasoning in Explanation, Plan Recognition, and Assistance: Theory and Practice.
    “This dissertation investigates and formalizes the connections between theory of mind (ToM), goal/plan recognition (GR), and explainable AI (XAI) to improve social interactions between AI agents and humans. It provides a novel classification of explanations under the lens of ToM, using epistemic logic and planning to formalize and demonstrate formal properties of explanations. This analysis informs the definition of epistemic GR problems, showing how inadequate knowledge and beliefs can be addressed via a transformation to multi-agent epistemic planning. In addition, the thesis shows how discrepancies in plan validity across multiple agents can be addressed using ToM and XAI. These concepts were also deployed and evaluated using a robotic platform that provides a human with proactive assistance. Results indicate that ToM, GR and XAI can substantially improve the quality of social interactions. Overall, this dissertation offers significant technical and foundational contributions addressing the critical problems of human-agent alignment and interaction.”

Awards presented at ICAPS 2023

Awards committee: Giuseppe De Giacomo (chair), Sebastian Sardina, Siddharth Srivastava, Shirin Sohrabi

ICAPS Influential Paper Award 2023

• Winner
  • Michael Katz, Carmel Domshlak. Optimal Additive Composition of Abstraction-based Admissible Heuristics (ICAPS 2008)
    “This paper presented seminal contributions on heuristic search in optimal planning. It broke out of the all-or-none accounting for actions costs in heuristic ensembles. While it took time for the impact of the theoretical contributions of this work to be developed into powerful practical results, they have had a profound longer term impact. Formalization and methods developed in this paper constitute the foundations for most modern approaches to heuristic-search based optimal planning. They have also inspired and empowered several recent award-winning publications and dissertations in the community.”
• Honorable Mention
  • Maria Fox, Alfonso Gerevini, Derek Long, Ivan Serina. Plan Stability: Replanning versus Plan Repair (ICAPS 2006)
    “This paper made a strong case for repairing an existing pre-computed plan in dynamic settings where the executor may find that the current context deviates from what was expected. The work proposed a plan stability metric (closer to the original plan) and a computational technique based on local-search that, under plausible assumptions, takes advantage of the original plan at hand to produce a new plan that works effectively under the new context. Both the notion of plan stability and the resulting adaptive planning system LPG-Adapt have been used extensively in later research. This work represents a significant step beyond offline planning and is still used as a key reference in works that deal with planning in the context of actual execution or deployment.”

ICAPS Best Dissertation Award 2023

• Winners
  • Alberto Camacho for his dissertation Automata-Theoretic Synthesis of Plans and Reactive Strategies.
    “The dissertation investigates the connections between automated planning in fully observable nondeterministic domains (FOND) with temporally extended goals and temporal synthesis with respect to logical specifications expressed in linear temporal logics on finite and infinite traces. It employs concepts from Formal Methods along with techniques and tools from AI planning. Automated planning and temporal synthesis have been two closely related research areas for decades. Historically, temporal synthesis has been pursued by Formal-Methods researchers, while automated planning has been pursued by the AI community. The dissertation offers significant contributions of both foundational and practical nature, with long-term impacts on planning and temporal synthesis. It represents a substantial advance in comprehending the connections between these two fields.”
  • Jiaoyang Li for her dissertation Efficient and Effective Techniques for Large-Scale Multi-Agent Path Finding.
    “This dissertation pushes the limits of Multi-agent Path Finding (MAPF) solving. It does so by effectively addressing the main shortcomings of state-of-the-art search techniques for MAPF: limited scalability, costly solutions, or plain failure on hard instances. The thesis significantly improves the current state-of-the-art in optimal and bounded-suboptimal MAPF solving, by developing admissible heuristics, symmetry breaking constraints, and learned inadmissible heuristics for conflict-based style search approaches. In addition, the thesis develops an algorithm-independent any-time framework based on Large Neighborhoods Search (LNS) to obtain suboptimal solutions for hard MAPF instances. The resulting approach is able to solve a significantly greater number of hard instances while yielding better quality solutions when compared with the best existing non-optimal planning systems. All in all, this dissertation sets new standards for Multi-agent Path Finding.”
• Honorable Mentions
  • Sarath Sreedharan for his dissertation Foundations of Human-Aware Explanations for Sequential Decision-Making Problems.
    “This dissertation presents a comprehensive and remarkable contribution to the field of explainable AI from a distinctively planning oriented perspective. The thesis develops broad technical frameworks for addressing an aspect of real-world planning that can limit the utility of planning, but is often overlooked from a technical perspective: how users would understand and utilize AI planning systems in practice. The dissertation crystallizes multiple aspects of this problem with technical formulations and solution approaches in a variety of settings, including those where users may have limited knowledge, limited vocabularies, or limited inferential capabilities. It shows that abstraction can be used as an effective mechanism for computing explanations of unexpected planner behavior as well as for explaining the unsolvability of planning problems and for summarizing complex solution policies. It also develops methods for computing self-explanatory plans that are inherently more understandable to users. In addressing these questions, the dissertation develops technical formulations that can empower a wealth of new applications as well as new threads of research.”
  • Rodrigo Andrés Toro Icarte for his dissertation Reward Machines.
    “This dissertation introduces the notion of Reward Machines (RM), an automata structure used to represent the reward function, which can serve as an effective tool to address sample efficiency and partial observability, two challenges that reinforcement learning faces. To that end, the thesis proposes a number of different approaches to policy learning in both tabular and deep learning settings and shows, through experiments, that reinforcement learning with RMs can find high quality policies with significant decrease in sample requirements. The thesis also proposes to learn the RM, using it as a form of external memory that is shown effective under partial observability. The dissertation is highly creative, novel, and elegant, both theoretically and experimentally. While the thesis makes strong contributions to reinforcement learning, it also demonstrates the value of using AI Planning techniques to the study of reinforcement learning. As such the dissertation has significant value in that it serves as an important connection between symbolic techniques and sequential decision making in machine learning.”

Awards presented at ICAPS 2022

Awards committee: Shlomo Zilberstein (chair), Jorge Baier, Giuseppe De Giacomo, Bernhard Nebel

ICAPS Influential Paper Award 2022

• Winner
  • Christian Muise, Sheila McIlraith, Christopher Beck. Improved Non-deterministic Planning by Exploiting State Relevance (ICAPS 2012)
    “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.”
• Honorable Mention
  • J. Benton, Amanda Coles, Andrew Coles. Temporal Planning with Preferences and Time-Dependent Continuous Costs (ICAPS 2012)
    “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 Best Dissertation Award 2022

• Winners
  • Daniel Gnad for his dissertation Star-Topology Decoupled State-Space Search in AI Planning and Model Checking.
    “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.”
  • Meghna Lowalekar for her dissertation Online Spatio-Temporal Demand Supply Matching.
    “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.”
• Honorable Mentions
  • Anagha Kulkarni for her dissertation Synthesis of Interpretable and Obfuscatory Behaviors in Human-Aware AI Systems.
    “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.”
  • Alexander Shleyfman for his dissertation Symmetry Breaking and Operator Pruning in Classical Planning and Beyond.
    “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.”

Awards presented at ICAPS 2021

Awards committee: Alfonso Gerevini (co-chair), Sven Koenig (co-chair), Jorge Baier, Shlomo Zilberstein

ICAPS Influential Paper Award 2021

Sungwook Yoon, Alan Fern, and Robert Givan. FF-Replan: A Baseline for Probabilistic Planning (ICAPS 2007)

“This highly-cited paper presents an easy-to-implement approach for probabilistic planning based on determinization that exploits the efficiency of planning in deterministic domains to solve a simplified version of the probabilistic planning problem, and replans whenever a state not covered by the current plan is reached. The algorithm won the first international probabilistic planning competition in 2004 using single-outcome determinization, and outperformed the winner of the second probabilistic planning competition in 2006 using all-outcome determinization.  It subsequently inspired the development of numerous other planners, such as FF-HINDSIGHT and RFF, and other techniques that use simplified models.  Despite initial skepticism within the community, determinization proved to be an important concept in the development of efficient planners for complex stochastic domains.”

ICAPS Best Dissertation Award 2021

• Winner
  • Hang Ma for his dissertation Target Assignment and Path Planning for Navigation Tasks with Teams of Agents.
    “The dissertation explores multiple versions of the multi-agent pathfinding (MAPF) problem, offering both analytical results and efficient algorithmic solutions that are tested on realistic application domains. Using automated warehouses as the main motivating application, the dissertation examines the combined target-assignment and path-planning (TAPF) problem. The main contributions include a unified NP-hardness proof structure for analyzing the complexity of different TAPF problems, complete and optimal search algorithms for the TAPF problem, complete and deadlock-free search algorithms for the multi-agent pickup and delivery (MAPD) problem in an online lifelong setting, and techniques to account for kinematic constraints of agents when solving MAPD problems. The dissertation brings together techniques from automated planning, search, constraint reasoning, optimization, and robotics to produce effective solutions to large and realistic MAPD problems.”
• Honorable Mention
  • Erwin Walraven for his dissertation Planning under Uncertainty in Constrained and Partially Observable Environments.
    “The dissertation makes deep algorithmic contributions to the design of planning algorithms for partially observable stochastic problems. It formulates the fastest existing exact algorithm for POMDPs by introducing a vector pruning algorithm that uses a constraint generation to accelerate the underlying linear programs. It presents a novel anytime algorithm for finite-horizon POMDPs that is highly efficient and scalable, without relying on a discount factor. It presents a novel algorithm for solving constrained finite-horizon POMDPs based on a column generation technique. Building on insights from artificial intelligence and operations research, the dissertation advanced the state of the art in both constrained and unconstrained probabilistic planning. Furthermore, the dissertation demonstrates the applicability of stochastic planning to manage congestion in smart distribution grids, contributing to the important societal challenge of energy transition.”

Awards presented at ICAPS 2020

Awards committee: Blai Bonet (chair), Alfonso Gerevini, Sven Koenig

ICAPS Influential Paper Award 2020

• Winners
  • Malte Helmert and Carmel Domshlak. Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? (ICAPS 2009)
    “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.”
  • Rong Zhou and Eric Hansen. Breadth-First Heuristic Search. (ICAPS 2004)
    “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
  • Jendrik Seipp for his dissertation Counterexample-Guided Cartesian Abstraction Refinement and Saturated Cost Partitioning for Optimal Classical Planning.
    “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.”
  • Kyle Wray for his dissertation Abstractions in Reasoning for Long-Term Autonomy.
    “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
  • Sarah Keren for her dissertation Goal Recognition Design.
    “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.”

Awards presented at ICAPS 2019

Awards committee: Daniel Borrajo (chair), Blai Bonet, Alfonso Gerevini, Sven Koenig

ICAPS Influential Paper Award 2019

• Winners
  • Ronen Brafman and Carmel Domshlak. From One to Many: Planning for Loosely Coupled Multi-Agent Systems. (ICAPS 2008)
    The paper presents the first general and formal formulation for multi-agent (classical) planning (MAP) which corresponds to the task of multiple agents working cooperatively to achieve a common goal. Besides providing a clean and crisp model for MAP, the paper also contributes with novel complexity techniques and results, together with general algorithms for solving MAP problems. Brafman and Domshlak’s paper proved to be a fundational stone in the area of MAP. An area that is currently very active and relevant.
  • Alfonso Gerevini and Ivan Serina. LPG: A Planner Based on Local Search for Planning Graphs with Action Costs. (AIPS 2002)
    The paper presents the early development of the LPG family of planners. LPG is based on planning in the space of partial plans — action graphs –, using stochastic local search and a parameterized heuristic function. This work describes the planner that could handle action costs and included an anytime behavior. The initial planning system has been later augmented to be able to reason about temporal planning tasks, numerical planning, replanning, or planning with preferences. It is one of the very few planning systems that can deal with an extensive subset of the PDDL language. Therefore, apart from its success in some IPCs, the LPG family of planners has been extensively used in many applications by many different planning experts.

ICAPS Best Dissertation Award 2019

• Winner
  • Pascal Bercher for his dissertation Hybrid Planning — From Theory to Practice.
    The dissertation stands out by covering a lot of ground: 1) It formalizes and develops planning with hierarchical task networks (HTNs) toward a hybrid formalism that includes partial-order causal link planning; 2) it presents complexity results for the resulting problem classes; 3) it develops heuristics for hybrid planning; 4) it describes the implementation of a hybrid planner and its integration into a companion device that assists in the set-up of a home theater system; and 5) it performs a user study to evaluate the system. The dissertation also rekindled interest in HTN planning by putting it on firm formal ground and connecting it to recent developments in classical planning.
• Honorable Mention
  • Tathagata Chakraborti for his dissertation Foundations of Human-Aware Planning – A Tale of Three Models.
    This dissertation explores the new and very promising area of human-aware planning. It studies several aspects related to tasks that require the symbiosis of humans and computational systems for the generation and/or execution of plans. A key aspect is that the AI agents reason on two human models: task and mental. This allows for the generation of improved explanations and plans’ explicability. The dissertation covers a wide range of tasks both formally and in the form of applied solutions.

Awards presented at ICAPS 2018

Awards committee: David E. Smith (chair), Blai Bonet, Daniel Borrajo

ICAPS Influential Paper Award 2018

• Winners
  • Ari Jónsson, Paul Morris, Nicola Muscettola, Kanna Rajan, Ben Smith. Planning in Interplanetary Space: Theory and Practice. (AIPS 2000)
    This work presents one of the earliest serious applications of AI planning technology to spacecraft. It describes the development and integration of planner-driven autonomy to control the Deep Space One Spacecraft during the Remote Agent Experiment conducted in May, 1999. Important issues and techniques addressed by this work include representation and reasoning with complex temporal constraints; use of STN techniques in planning; planning under severe limits on memory and computational power; and tradeoffs between performance and modeling of control knowledge. This work has served as a model and inspiration for subsequent applications of planning and scheduling, particularly in aerospace.
  • Ronald Petrick, Fahiem Bacchus. A knowledge-based approach to planning with incomplete information. (AIPS 2002)
    This paper introduced the approach for handling incomplete information in planning that is currently known as “compilation at the knowledge level”. In this approach relevant features of the belief state for the agent are represented by a collection of propositional fluents whose truth-value expresses the validity of a fixed set of formulas in modal logic interpreted over the set of all possible worlds. Updates to the knowledge of the agent triggered by the execution of actions and sensing of observations are then translated into updates to the propositional fluents. This novel representation permits planners to avoid complex and inefficient representations of belief states, and allows the compilation of planning problems with incomplete information into deterministic classical planning problems. This representation allowed the development of several more recent powerful and efficient planners that handle incomplete information.
• Honorable Mentions
  • Denise Draper, Steve Hanks, Daniel Weld. Probabilistic planning with information gathering and contingent execution. (AIPS 1994)
    This paper describes a conditional partial-order probabilistic planner, C-Buridan, that deals with probabilistic actions and noisy sensing actions. While the partial order planning framework has since been supplanted by other methods, this paper introduced the first clear formal representation and algorithm for the treatment of probabilistic sensing actions in planning, and used a Bayesian framework for reasoning with such information. This representation and approach laid foundations for subsequent work in probabilistic planning and planning under uncertainty.
  • Jussi Rintanen. Complexity of Planning with Partial Observability. (ICAPS 2004)
    This paper provides a comprehensive and complete picture of the complexity of planning under non-determinism and partial observability for reachability goals. The paper thoroughly studies the impact of branching (as a consequence of non-deterministic actions) and the impact of beliefs (as a consequence of partial information), and then shows that branching and beliefs together result in decision problems that are 2-EXPTIME-complete to solve. The use of non-determinism to simulate Alternating Turing Machines is novel, as is the use of partial information to track structures of exponential size using only a polynomial number of bits.

ICAPS Best Dissertation Award 2018

• Winners
  • Florian Pommerening for his dissertation New Perspectives on Optimal Cost Partitioning for Classical Planning.
    This dissertation lays out, develops, and analyzes a general and powerful framework for the expression, combination, and efficient computation of existing and novel domain-independent admissible heuristics for cost-optimal planning. The framework is the LP-based framework of operator-counting heuristics in which many state-of-the-art heuristics can be expressed, as well as novel ones. These can be combined in synergistic ways in a transparent and simple manner. By analyzing the LP programs associated with some of these heuristics, new ways to construct optimal cost-partitionings are obtained and new families of heuristics are identified. The novel heuristics are among the most powerful currently available for optimal classical planning, and the framework has already been extended by others to accommodate planning models beyond the classical one.
  • Michal Štolba for his dissertation Reveal or Hide: Information Sharing in Multi-Agent Planning.
    This dissertation presents a comprehensive study of Multi-Agent Planning (MAP). It covers three distinct topics. First, it describes ways of distributing the computation of planning heuristics for MAP by generalizing state-of-the-art single-agent heuristics. Second, it shows how to combine those estimations with locally computed estimations in the context of an efficient MAP planner. Finally, it presents key and novel work on how to measure privacy in MAP. All topics are discussed using rigorous theoretical formalizations, as well as with extensive experiments and deep analysis of the results. As a side effect of the thesis, Michal was one of the organizers of CoDMAP, the first competition on MAP.
• Honorable Mentions
  • Guillem Francès for his dissertation Effective Planning with Expressive Languages.
    This dissertation develops techniques for dealing with a more expressive modeling language for classical planning. In particular, the language includes function symbols and existential quantification. The dissertation shows that this richer language allows simpler problem representation in many cases, and that existing heuristic techniques can be extended to make use of the additional language structure to do efficient planning. The dissertation also develops a width-based search technique that can allow planning with external simulators. These techniques are implemented in a novel planner called FS that exhibits state-of-the-art performance.
  • Aswin Raghavan for his dissertation Domain-Independent Planning for Markov Decision Processes with Factored State and Action Spaces.
    This dissertation systematically studies and improves the symbolic approach for solving probabilistic planning problems, either exactly or approximately. The symbolic approach is theoretically appealing as it has the potential to efficiently scale over planning problems involving huge state and action spaces. The dissertation focuses on making this approach work successfully for different model characteristics, including continuous state variables and factored action spaces, and over different solution concepts, including offline and online planning. Among the most important contributions of the dissertation are: new factored symbolic representations of value functions together with corresponding backup operators; novel symbolic dynamic programming algorithms for offline and online planning that use these representations; and novel extensions of the RDDL language to efficiently express complex planning domains. Besides the standard experimental evaluation on benchmark problems, the theory and methods developed are tested on a challenging real-world task of optimizing the response of fire and emergency services in a real city.

Awards presented at ICAPS 2017

Awards committee: Scott Sanner (chair), Daniel Borrajo, David E. Smith

ICAPS Influential Paper Award 2017

• Winner
  • Maxim Likhachev, David I. Ferguson, Geoffrey J. Gordon, Anthony Stentz, Sebastian Thrun. Anytime Dynamic A*: An Anytime, Replanning Algorithm. (ICAPS 2005)
    Computing paths for robots in dynamic environments is a key application of search and planning techniques. Similarly to most search tasks, correctly balancing computation time and quality of solutions is one of the critical decisions to be made.  The technique presented in this paper, Anytime Dynamic A*, smoothly integrates an anytime behavior with replanning methods, with bounded suboptimal guarantees. Among other real-world applications, it was successfully used in Boss, the winner of the DARPA Urban Challenge. The technique and refinements of the technique are still widely used in many search and planning applications.
• Honorable Mentions
  • Ronen Brafman and Joerg Hoffmann. Conformant Planning via Heuristic Forward Search: A New Approach. (ICAPS 2004)
    This work adapted an efficient state-spaced classical planner (FF) to solve a non-classical planning problem; in this case, conformant planning, where there is uncertainty about the initial state, but the goal must be achieved with certainty. Unlike previous attempts at planning under uncertainty, this approach did not keep an explicit representation of belief states or possible worlds – instead, it encoded uncertain states more compactly using action sequences.  It reasoned about the outcome of these action sequences by using a SAT solver to rapidly compute the positively and negatively known propositions for the sequences.  The resulting planner, Conformant-FF, significantly outperformed previous conformant planners, but more importantly, it influenced other researchers to consider ways of using classical planners and classical compilations to solve non-classical planning problems.
  • Marco Pistore, Paolo Traverso, Piergiorgio Bertoli. Automated Composition of Web Services by Planning in Asynchronous Domains. (ICAPS 2005)
    This paper provides a novel solution for the composition of asynchronous web services specified in industrial standard languages for business process modeling and execution such as BPEL4WS.  The proposed planning approach finds a provably deadlock-free controller that satisfies extended goals with temporal and/or preference conditions given web service descriptions that are asynchronous, nondeterministic, and partially observable. This work is notable not only for its novel formalization and planning approach to web service composition, leveraging the planning as model-checking approach, but also for the amount of attention this work received through citations in the related semantic web and web service literature as well as much broader cross-disciplinary attention from a range of fields including formal methods, business processes, and software architecture.

ICAPS Best Dissertation Award 2017

• Winner
  • Thomas Keller for his dissertation Anytime Optimal MDP Planning with Trial-based Heuristic Tree Search.
    Thomas Keller’s thesis provides a comprehensive theoretical and empirical analysis of both existing and novel solution algorithms for MDPs. The thesis presents a new method for all-outcome determinization of factored MDPs with an exponential-to-linear space reduction over previous methods in the case of parallel probabilistic effects. The thesis also provides a theoretical and empirical analysis of the Canadian Travelers Problem and the MDP evaluation optimal stopping problem. In addition to these already strong contributions, the thesis also introduces the trial-based heuristic tree search (THTS) framework for MDP algorithms that unifies a number of diverse perspectives on MDP planning including dynamic programming, Monte Carlo Tree Search, and heuristic search algorithms such as AO*. The THTS framework provides a foundation for the theoretical and conceptual analysis of the key decisions and trade-offs among these different instantiations and also provides for the novel contribution of a THTS instance — the PROST planner — that won the International Probabilistic Planning Competitions in both 2011 and 2014.
• Honorable Mentions
  • Andrea Micheli for his dissertation Planning and Scheduling in Temporally Uncertain Domains.
    Andrea Micheli’s thesis addresses the problems of planning and scheduling with actions having durations that are not always under the control of the executor. The thesis first addresses the problem of scheduling for disjunctive temporal networks with uncertainty (DTNUs). The Satisfiability Modulo Theory (SMT) framework is used to formalize the problems of strong, weak, and dynamic controllability for DTNUs, and SMT solvers are used to provide practical solutions to these problems. The thesis moves on to consider the problem of strong temporal planning with uncontrollable durations, and develops two types of techniques for addressing this problem. The first of these explicitly deals with the uncertainty by incorporating an STNU into the temporal planner POPF. The second is a formal compilation that reduces the strong temporal planning problem with duration uncertainty into an ordinary temporal planning problem without uncertainty. The techniques are empirically compared and seem to demonstrate complementary behavior.
  • Fazlul Siddiqui for his dissertation Using Plan Decomposition for Continuing Plan Optimisation and Macro Generation.
    Fazlul Siddiqui’s thesis introduces Block decomposition, a new way of decomposing and de-ordering plans that generalizes the usual notion of partial ordering. This idea is then used to improve plan quality by performing local optimization over windows in a block de-ordered plan. The thesis introduces several heuristics for choosing appropriate optimization windows, and also uses on-line multi-armed bandit learning to apply the most promising subplanners to the most promising subplans. The thesis provides extensive empirical evaluation over a number of competition and application domains, and convincingly demonstrates significant improvement in plan quality over previous state of the art postprocessing techniques for many of these domains.
  • Glenn Wagner for his dissertation Subdimensional Expansion: A Framework for Computationally Tractable Multirobot Path Planning.
    Glenn Wagner’s dissertation defines a multi-agent path planning framework named subdimensional expansion. It dynamically switches from distributed planning to centralized planning when agents’ paths generate a conflict. This idea provides an elegant solution to the high complexity of multi-agent path finding and opens new research directions for multi-agent task planning. In discrete planning tasks, subdimensional expansion has been combined with A*, resulting in the complete and optimal M* algorithm. The dissertation also studies combinations with: other stochastic path-planning algorithms, such as PRM or RRT; constraint manifolds, when agents have to dynamically form and dissolve teams of agents to solve cooperative tasks; planning under uncertainty; and multi-agent sequential composition. The dissertation also includes extensive coverage of the theoretical aspects of the algorithms, as well as experimental results that show good performance of the algorithm in different scenarios.

Awards presented at ICAPS 2016

Awards committee: Martin Mueller (chair), Scott Sanner, David E. Smith

ICAPS Influential Paper Award 2016

• Winner
  • Malte Helmert. A Planning Heuristic Based on Causal Graph Analysis. (ICAPS 2004)
    This paper transformed our understanding and use of causal graphs. From tools used in theoretical studies of the complexity of limited fragments of classical planning, the concepts of causal graphs, domain transition graphs and SAS+ finite domain representation became the basis of powerful planning heuristics and algorithms. The CG heuristic first proposed in this work remains one of the most popular methods for constructing domain-independent heuristics. The paper has led to further very influential work such as the LAMA planner, merge-and-shrink heuristics, and new approaches to the use of pattern databases in planning. The work has motivated a substantial number of studies of the complexity of planning.
• Honorable Mentions
  • John L. Bresina, Ari K. Jonsson, Paul H. Morris, and Kanna Rajan. Activity Planning for the Mars Exploration Rovers. (ICAPS 2005)
    Many of us who do work in planning point to applications to motivate and justify our work. The work on activity planning for the Mars Exploration Rovers has served as the “poster-child” of applications for AI planning. It has given rise to simplified domains for the International Planning Competition as well as examples used in numerous talks and papers. Equally important, this work raised the awareness of a number of challenging issues for the community, including temporal constraints, exogenous events, mixed-initiative planning, and the graphical display and manipulation of complex plans.
  • Nicola Policella, Stephen F. Smith, Amedeo Cesta, and Angelo Oddi. Generating Robust Schedules through Temporal Flexibility. (ICAPS 2004)
    It has long been recognized that partial order schedules (POSs) provide greater flexibility when responding to unexpected events and circumstances. This paper analyzed two different methods of generating POSs: a least-commitment approach, and a more-grounded earliest start time (EST) approach coupled with post-processing relaxation. The paper evaluates these two approaches on RCPSP/max scheduling benchmarks using three robustness metrics, flexibility, fluidity, and disruptability. As has often been found in planning, the paper shows that the more grounded approach is faster. What’s surprising though, is that the resulting schedules are also more robust. For many practitioners, this result has changed the approach to generating flexible POSs.

ICAPS Best Dissertation Award 2016

• Winner
  • Gabriele Röger for her dissertation Planning Techniques and the Action Language Golog.
    Gabriele’s dissertation makes several significant contributions. The first part of the thesis analyzes the relation between the action language Golog and the planning language PDDL. The analysis characterizes which of the so-called Basic Action Theories can be compiled into the ADL fragment of PDDL. This deep and difficult technical work also has a practical application: state of the art action planning systems can now be used to solve problems expressed in such action theories much more efficiently. The second part of the dissertation studies the limitations of optimal planning with so-called almost perfect heuristics. Gabriele shows that for several typical planning domains, even a heuristic error of 1 leads to exponential scaling of A* search. This result has motivated work on other directions for improving planners, beyond improving heuristics. The third contribution of this thesis introduces a better way to combine heuristics in satisficing planning. The alternation approach of choosing different heuristics surpasses more traditional ways of combining heuristics. This work is very influential in the design of modern planning systems.
• Honorable Mentions
  • Daniel Harabor for his dissertation Fast and Optimal Pathfinding.
    This dissertation studies two issues for optimal pathfinding on grids: how to exploit symmetries to speed up search, and how to relax the paths to be any-angle, not just grid edges. While the topic of path finding on grids has been extensively studied, this thesis develops several novel techniques, including Rectangular Symmetry Reduction, Jump Point Search (JPS), and an optimal any-angle pathfinding algorithm, Anya. Versions of Jump Point Search were highly successful in the 2012 and 2014 Grid-Based Path Planning Competition, and the algorithm has been widely adopted by the gaming industry because of its exceptional performance with no preprocessing. The Anya algorithm answers an open question about whether an optimal online any-angle pathfinding algorithm exists. Subsequent work has demonstrated that this algorithm is competitive with, and sometimes even outperforms sub-optimal algorithms.
  • Mike Phillips for his dissertation Experience Graphs: Leveraging Experience in Planning.
    This work introduces, develops, and extensively evaluates Experience Graphs, a heuristic search technique for robotic manipulation planning. Experience Graphs use previously planned solutions to similar planning problems to focus search for future problems. While the idea of using previous experience to speed up search is not new, what distinguishes this work is that it provides guarantees on completeness and bounds on sub-optimality. The dissertation includes evaluation on an impressive range of robotics applications including single-arm, dual-arm, and full-body manipulation. The work is also being widely used in robotics labs, and on an industrial manipulation platform.
  • Álvaro Torralba for his dissertation Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning.
    Alvaro’s dissertation greatly advances the state-of-the-art in symbolic (BDD) search applied to automated planning. Among numerous significant contributions, it provides refinements to symbolic exploration (conjunction and disjunction trees, mutexes, etc.), novel symbolic search heuristics based on projections and the Merge-and-Shrink approach, an enhanced version of bidirectional symbolic search, and a thorough empirical evaluation of its contributions. The dissertation provided the technical foundations for the 1st, 2nd, and 3rd place winning planners in the Sequential Optimal track of the International Planning Competition 2014, which were all developed by Alvaro Torralba and his teams. Altogether, the dissertation and associated competition successes have helped establish symbolic search methods as the dominant approach for cost-optimal planning.

Awards presented at ICAPS 2015

Awards committee: Robert Morris (chair), Sara Bernardini, Hector Geffner, Lee McCluskey, Martin Mueller

ICAPS Influential Paper Award 2015

• There is no paper award this year due to lack of nominations.

ICAPS Best Dissertation Award 2015

• Winner
  • Christian Muise for his dissertation Exploiting Relevance to Improve Robustness and Flexibility in Plan Generation and Execution.
    This work explores the notion of relevance as a way to improve plan generation and execution. Relevance defines what is sufficient to establish the validity of plans, and three types of relevance are defined: ordering relevance among constraints between actions in a plan; temporal relevance, related to a plan’s execution history; and state relevance, which refers to aspects of the state description. This work demonstrates convincingly that taking relevance into account when representing, generating and executing plans, improves the efficiency, executability and robustness of plans. The four main contributions of the thesis each expands work previously published in the top AI venues, and shows significant improvements to the state of the art. In addition to being loaded with technical contributions, the thesis was a most pleasurable reading experience, with a writing style that is simultaneously rigorous and easy to follow. There is strong evidence that this work will have significant and broad impact on the planning research community.
• Honorable Mentions
  • Raz Nissim for his dissertation Distributed Algorithms for Privacy-Preserving Multi-Agent Planning.
    This work advances of the state of the art on Multi-Agent Planning (MAP) in several directions, including implementation of a CSP-based MAP system, a state-of-the art distributed forward-search MAP, a mechanism for decomposition and pruning for optimal classical planning, and a cost-optimal MAP for self-interested agents. The thesis shows solid research in the analysis of the state of the art, theory, implementation of algorithms, and experimental results. In general, this pioneering thesis will provide essential reading to those interested in this exciting emerging field.

Awards presented at ICAPS 2014

Awards committee: Dana Nau (chair), Carmel Domshlak, Phillipe Laborie, Florent Teichteil

ICAPS Influential Paper Award 2014

• Winner
  • Blai Bonet and Hector Geffner. Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming. (ICAPS 2003)
    By offering convergence guarantees for the simple sampling scheme offered by the popular RTDP algorithm, this paper drew a great deal of attention to heuristic search algorithms for MDPs, and led to a series of papers on variants and improvements of the RTDP algorithm. LRTDP is now a state-of-the-art baseline for solving Stochastic Shortest Path problems and related models such as imprecise MDPs or short-sighted SSPs, and has had a large influence on the development of algorithms for other kinds of MDPs.
• Honorable Mention
  • David E. Smith. Choosing Objectives in Over-Subscription Planning. (ICAPS 2004)
    This paper introduced to the ICAPS community the notion of oversubscription planning, in which there are many possible goals and the planning system must choose a subset that can be accomplished with a limited amount of time and resources. The paper motivated the importance of such problems by pointing out their prominence in many space missions, and prompted research on the subject by providing an example of how to construct heuristic for such problems. The importance of oversubscription planning has since been widely recognized, and has led to the introduction of preferences in PDDL3.

ICAPS Best Dissertation Award 2014

• Winner
  • Akshat Kumar for his dissertation Exploiting Domain Structure in Multiagent Decision-Theoretic Planning and Reasoning.
    Dec-POMDPs offer an expressive and mathematically rigorous framework for modeling and reasoning about the dynamics of multi-agent systems. Most inference techniques for Dec-POMDPs have either been relatively general but not very scalable, or relatively scalable but very specific. This state of affairs has been fundamentally altered by Akshat’s dissertation, which provides new algorithms that scale well on a large class of problems of practical importance. The dissertation has already became an important landmark in planning for multi-agent systems, and we have no doubt that it will continue influencing the area for years to come.
• Honorable Mentions
  • Andrey Kolobov for his dissertation Scalable Methods and Expressive Models for Planning Under Uncertainty.
    In his work, Andrey has accomplished three things. First, he has provided well-informed heuristics for goal-oriented MDPs by using basis functions that cleverly marry machine learning and classical planning. Second, he has dared to question the standard respected model of Stochastic Shortest Path problems and has proposed new models and algorithms for probabilistic planning with dead-ends. Third, he has revisited and modernized some famous heuristic MDP algorithms, unexpectedly demonstrating that they could seriously challenge tree-search methods in finite-horizon MDPs with large branching factors. This 3-in-1 thesis is a fine contribution to our understanding of algorithms and models for planning under uncertainty.
  • Leon Planken for his dissertation Algorithms for Simple Temporal Reasoning.
    The concept of Simple Temporal Networks (STNs) plays a very important role in scheduling, temporal planning and temporal reasoning. In these domains, the efficiency of the search algorithms depend directly on the ability of the underlying STN to quickly process queries. In his very accessible and brilliantly written dissertation, Leon provides a thorough analysis of the different types of queries, a remarkable synthesis of existing approaches and new state-of-the-art algorithms. We believe Leon’s dissertation will become an important reference work on the topic.

Awards presented at ICAPS 2013

Awards committee: Dana Nau (chair), Patrik Haslum, Philippe Laborie, Florent Teichteil

ICAPS Influential Paper Award 2013

• Winner
  • Julie Porteous, Laura Sebastia, and Jörg Hoffmann. On the Extraction, Ordering, and Usage of Landmarks in Planning. (ECP 2001)
    This paper introduced the idea of landmarks in automated planning. Landmarks have been the basis for a large body of subsequent research that has produced both theoretical breakthroughs and some of the best- performing planning systems. They are now being used in both classical and non-classical planning, and are starting to be used in research on model checking. None of that would have happened if not for this paper.

ICAPS Best Dissertation Award 2013

• Winners
  • Nir Lipovetzky for his dissertation Structure and Inference In Classical Planning.
    Nir Lipovetzky takes a new, and very original, look at automated planning: how to reason your way to a plan, instead of searching (blindly or heuristically) for it. First, he has developed a range of novel inference techniques that, combined, produce classical planners that can work with very little backtracking — in many cases none at all — and perform well enough to be awarded at two IPCs. Second, he has invented a novel measure of the hardness of a planning problem, called “width”, and has shown that by properly exploiting it, a simple blind search can do as well as the best-performing heuristic search planners.
  • Ko-Hsin Cindy Wang for her dissertation Scalable Cooperative Multi-Agent Pathfinding with Tractability and Completeness Guarantees.
    Cindy Wang’s dissertation is about massive multi-agent pathfinding: coordinated movement of thousands of agents, on maps of tens of thousands of cells. This is a scale that is both challenging and required by a variety of applications. She has developed efficient (low-order polynomial) algorithms for a practically useful subclass of these problems. Her analytical and empirical studies show that the algorithms scale well and produce high quality solutions, establishing a new state of the art both within the subclass where they are guaranteed to be well-behaved and in the general case. Her publications on this topic have already led to subsequent research by others.

Awards presented at ICAPS 2012

Awards committee: Mark Boddy (chair), Scott Sanner, Daniel Bryce, Patrik Haslum

ICAPS Influential Paper Award 2012

• Winner
  • Stefan Edelkamp. Planning with Pattern Databases. (ECP 2001)
    Stefan’s paper was the first to explore the application of pattern databases in domain-independent planning. In this paper, Stefan identified and took a first step towards addressing many of the challenges that arise in this application, including handling multi-valued rather than propositional representations, efficient storage and indexing of the pattern database, preserving admissibility with disjoint abstraction heuristics, and finally, the importance and difficulty of finding the right set of patterns, automatically and in a domain-independent way. It took several years for others in the planning community to follow up on Stefan’s work. (For that matter, it took years for the heuristic search community, where pattern databases originated, to rediscover some of his innovations.) More recently, abstraction heuristics (including PDBs and their generalisations) have been shown to be among the most powerful families of admissible heuristics, both theoretically and in implemented planning systems. As development and use of abstraction heuristics continues to grow, the significance and impact of this work grows as well.

ICAPS Best Dissertation Award 2012

• Winner
  • Silvia Richter for her dissertation Landmark-Based Heuristics and Search Control for Automated Planning.
    Silvia’s work on the LAMA planner has resulted in remarkable advances in both the understanding and performance of implemented planning systems. In her thesis, Sylvia deconstructs the LAMA planner, clearly describing each of its many innovations. These innovations include new methods for finding landmarks and their orders, the use of that information as a heuristic, the integration of preferred operators and lazy evaluation, and the use of restarts in anytime search. For each of these techniques, Sylvia identifies strengths and weaknesses, explaining how each of them contributes to the performance of the overall system, as well as how synergies among them make the whole system greater than the sum of its parts. From the in-depth analysis of cost-based search in specific planning domains, to the construction of a synthetic search space that allows controlled experiments measuring the impact of preferred operators and lazy evaluation as an effect of heuristic failures, to the extensive evaluation of different anytime search algorithms, these analyses are rigorously done and clearly presented. In addition, the practical impact of Sylvia’s work is clearly demonstrated by her repeated success in the International Planning Competition. In summary, Silvia’s thesis is an excellent example of empirical “AI systems” research leading to new theoretical insights, and thoroughly deserving of recognition.
• Honorable Mentions
  • Peng Dai for his dissertation Decision Making under Uncertainty: Scalability and Applications.
    Peng Dai’s thesis introduces several significant innovations in planning under uncertainty. First, Peng explores the use of topological value iteration and extensions, exploiting MDP structure and advanced heuristics for faster generation of exact solutions to large MDPs. For MDPs that are too large to be solved in primary memory, Peng then devises solution methods using external memory, with the crucial advance that his new methods automatically partition the problem, removing the need for manual partitioning as previously required. As a second major focus of his thesis, Peng explores the application of decision-theoretic planning to crowd-sourcing, modeling the problem as a POMDP and proposing a decision-theoretic solution. This work culminates in experimentation on Amazon’s Mechanical Turk, showing that his approach outperforms the current state of the art. In terms of both theory and application, Peng’s thesis is exceptionally strong and will influence future work in the field for years to come.
  • Emil Keyder for his dissertation New Heuristics for Planning with Action Costs.
    Emil Keyder’s dissertation advances the understanding of inadmissable heuristics for planning with action costs in several directions. These include unifying and extending additive and relaxed plan heuristics, addressing the independence assumptions used for combining plans for achieving multiple goals, establishing and exploiting a connection between delete-relaxation heuristics and Steiner Trees, formulating an algorithm for automatically deriving higher-order landmarks, and showing how soft goals can be compiled into a combination of hard goals and action costs. In addition, Emil’s work introduces and exploits for heuristic benefits a new kind of invariant called choice variables, adapting methods from the field of graphical models. Emil’s work is at the forefront of, and provides a significant contribution to, both empirical and theoretical research on planning with action costs.
  • Michele Lombardi for his dissertation Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments.
    One of the striking features of Michele Lombardi’s thesis is the range of both problems addressed and techniques integrated and extended. Working at the boundary between constraint programming and operations research, Michele’s work applies, extends, and adapts techniques drawn from constraint-based scheduling, graph theory, mathematical programming and temporal reasoning. Another remarkable feature of this work is the range of contributions made. To quote from one of the nomination letters: “There is an amazing number of original contributions in Michele’s dissertation: hierarchical logic-based Benders decomposition, new search heuristics for interleaving resource allocation and scheduling decisions, exploitation of conditional task graphs for stochastic scheduling, new resource and temporal network propagation algorithms in the presence of uncertainty, and new techniques for computing minimal critical sets, to cite only a few examples.” These contributions are relevant to a wide range of current research in planning and scheduling, particularly in the less-commonly addressed area of stochastic scheduling.

Awards presented at ICAPS 2011

Awards committee: Robert Goldman (chair), Mark S. Boddy, Patrik Haslum, Mausam

ICAPS Influential Paper Award 2011

• Winner
  • Philippe Laborie. Algorithms for Propagating Resource Constraints in AI Planning and Scheduling: Existing Approaches and New Results. (ECP 2001)
    This paper presented two new, very general algorithms for constraint propagation in flexible plans, exploiting the interaction of precedence constraints and nonunary resource constraints. Along with the follow-on AIJ paper of the same title, this work is cited by people ranging across the spectrum of planning and scheduling approaches, from almost “pure” scheduling, to more complex integrations of activity generation and scheduling and constraint-based flexible temporal planning, to more recent extensions of classical planning to address temporal and resource constraints. Laborie’s work was motivated by, and provided a real contribution to, efforts to integrate planning and scheduling techniques in the late 1990’s and the early years of the last decade. The ideas in these papers contributed significantly to successful applications of planning and scheduling techniques in real domains, ongoing to the present day.

ICAPS Best Dissertation Award 2011

• Winner
  • Michael Katz for his dissertation Implicit Abstraction Heuristics for Cost-Optimal Planning.
    Michael Katz’s dissertation combines in one excellent thesis two major research thrusts, and creates a synergy between them. First, he discovers new classes of tractable cost-optimal STRIPS planning. Second, he uses these to develop a new type of abstraction heuristics, structural pattern databases, which do not suffer from the fundamental limitation on size that restricts the power of ordinary pattern database heuristics. Finally, Michael’s thesis answers an important question, open for quite some time, by proving that the optimal combination of multiple heuristic estimates by cost partitioning can be found in polynomial time. These results are put into practice, resulting in two of the currently best-performing systems for optimal STRIPS planning.
• Honorable Mentions
  • Jorge Baier for his dissertation Effective Search Techniques for Non-Classical Planning via Reformulation.
    Jorge Baier’s thesis makes multiple contributions to the important goal of expanding the expressiveness of planners beyond STRIPS, and thus improving their practical applicability. His approach is elegantly simple: using automatic problem reformulation, or compilation, he shows how temporally extended goals, domain-specific control knowledge, and complex, program-like actions, including programs with sensing, can be compiled to classical, or conformant, planning, and thereby how existing (and future!) planners can be used to tackle more realistic problems. For planning with rich, temporally extended preferences, Jorge combines reformulation with new, better heuristics to produce one of the strongest planners in the PDDL3 preference track of the 2006 IPC.
  • Siddharth Srivastava for his dissertation Foundations and Applications of Generalized Planning.
    Siddharth Srivastava’s thesis also addresses the problem of extending the expressive power of planning techniques, but in a different direction and using different techniques. Siddharth’s thesis provides new techniques for finding generalized plans capable of using iteration to handle goals over varying numbers of individuals, such as a plan to unload trucks with varying numbers of cargo items. Siddharth puts this problem on a firm footing by developing a theoretical basis for analyzing generalized plans, based on the model of abacus programs. He uses this analysis to find a class of generalized plans for which the problem of plan applicability is decidable. Building on this theoretical foundation, Siddharth provides algorithms for finding generalized plans exploiting solutions for single plan instances that can be generated by classical planners. His experimental results show that these techniques can be of practical, as well as theoretical interest.

Awards presented at ICAPS 2010

ICAPS Influential Paper Award 2010

• Winners
  • Patrik Haslum and Hector Geffner. Admissible Heuristics for Optimal Planning. (AIPS 2000)
• Honorable Mention
  • Minh Do and Rao Kambhampati. Solving Planning-Graph by Compiling It into CSP. (AIPS 2000)

ICAPS Best Dissertation Award 2010

• Winner
  • Hector Palacios for his dissertation Translation-based approaches to Conformant Planning.
• Honorable Mentions
  • Christian Fritz for his dissertation Monitoring the Generation and Execution of Optimal Plans.

Awards presented at ICAPS 2009

ICAPS Influential Paper Award 2009

• Winners
  • Blai Bonet and Hector Geffner. Planning as Heuristic Search: New Results. (ECP 1999)
  • Drew McDermott. A Heuristic Estimator for Means-Ends Analysis in Planning. (AIPS 1996)
• Honorable Mention
  • Kutluhan Erol, James Hendler and Dana Nau. UMCP: A Sound and Complete Procedure for Hierarchical Task-Network Planning. (AIPS 1994)

ICAPS Best Dissertation Award 2009

• Winner
  • Daniel Bryce for his dissertation Scalable Planning under Uncertainty.
• Honorable Mentions
  • Guy Shani for his dissertation Learning and Solving Partially Observable Markov Decision Processes.
  • Shahid Jabbar for his dissertation External Memory Algorithms for State Space Exploration in Model Checking and Action Planning.
  • Menkes van den Briel for his dissertation Integer Programming Approaches for Automated Planning.

Awards presented at ICAPS 2008

Awards committee: Derek Long (chair), Chris Beck, Malte Helmert, Sven Koenig, Kanna Rajan

ICAPS Influential Paper Award 2008

• Winner
  • Alessandro Cimatti, Fausto Giunchiglia, Enrico Giunchiglia and Paolo Traverso. Planning via Model Checking: A Decision Procedure for AR. (ECP 1997)
• Honorable Mention
  • Jana Koehler, Bernhard Nebel, Jörg Hoffmann and Yannis Dimopoulos. Extending Planning Graphs to an ADL Subset. (ECP 1997)

ICAPS Best Dissertation Award 2008

• Winner
  • Matthew Streeter for his dissertation Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice.
• Honorable Mention
  • Mausam for his dissertation Stochastic Planning with Concurrent, Durative Actions.

Awards presented at ICAPS 2007

Awards committee: Malik Ghallab (Chair), Susanne Biundo, Sven Koenig, Sam Steel, Dan Weld

ICAPS Influential Paper Award 2007

• Winner
  • Mark Peot and David E. Smith. Conditional Non-Linear Planning. (AIPS 1992)
• Honorable Mention
  • Fahiem Bacchus and Froduald Kabanza. Using Temporal Logic to Control Search in a Forward Chaining Planner. (ECP 1995)

ICAPS Best Dissertation Award 2007

• Winner
  • Håkan Younes for his dissertation Verification and Planning for Stochastic Processes with Asynchronous Events.
    For his creative research on formal verification of discrete event systems and planning with concurrent actions with uncertain duration, his development of an original representation based on Semi-Markov Decision Processes and of a highly innovative algorithmic approach for solving this class of planning problems.
• Honorable Mention
  • Daniel Bernstein for his dissertation Complexity Analysis and Optimal Algorithms for Decentralized Decision Making.
    For his highly innovative research on planning under uncertainty for multiple agents introducing and characterizing a new framework of decentralized MDPs.
  • Patrik Haslum for his dissertation Admissible Heuristics for Automated Planning.
    For his marked contribution to the development of a family of admissible heuristics for optimal planning in the sequential and temporal settings.
  • Malte Helmert for his dissertation Solving Planning Tasks in Theory and Practice.
    For his extensive work on the analysis and characterization of the structure of classical planning domains and his highly effective heuristics using abstraction hierarchies derived from causal graphs.