Main / 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 2016
ICAPS Influential Paper Award 2016
- 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
- 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
ICAPS Influential Paper Award 2015
- There is no paper award this year due to lack of nominations.
ICAPS Best Dissertation Award 2015
- 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
ICAPS Influential Paper Award 2014
- 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
- 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
ICAPS Influential Paper Award 2013
- 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
- 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
ICAPS Influential Paper Award 2012
- 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
- 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
ICAPS Influential Paper Award 2011
- 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
- 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
- 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
- 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
- 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
- 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
ICAPS Influential Paper Award 2008
- 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
- 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
ICAPS Influential Paper Award 2007
- 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
- Håkan Younes for his dissertation Verification and Planning for Stochastic Processes with Asynchronous Events.
- Honorable Mention
- Daniel Bernstein for his dissertation Complexity Analysis and Optimal Algorithms for Decentralized Decision Making.
- Patrik Haslum for his dissertation Admissible Heuristics for Automated Planning.
- Malte Helmert for his dissertation Solving Planning Tasks in Theory and Practice.