ICAPS 2013 Best Paper
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core
Martin Wehrle, Malte Helmert, Yusra Alkhazraji and Robert Mattmüller
In the last years, pruning techniques based on partial order reduction have found increasing attention in the planning community. One recent result is that the expansion core method is a special case of the strong stubborn sets method proposed in model checking. However, it is still an open question if there exist efficiently computable strong stubborn sets with strictly higher pruning power than expansion core. In this paper, we prove that the pruning power of strong stubborn sets is strictly higher than the pruning power of expansion core even for a straight-forward instantiation of strong stubborn sets. This instantiation is as efficiently computable as expansion core. Hence, our theoretical results suggest that strong stubborn sets should be preferred to expansion core. Our empirical evaluation on all optimal benchmarks from the international planning competitions up to 2011 supports the theoretical results.
ICAPS 2013 Best Student Paper
Trial-based Heuristic Tree Search for Finite Horizon MDPs
Thomas Keller and Malte Helmert
Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree. The Heuristic Search algorithm AO∗ finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs. We introduce a common framework, Trial-based Heuristic Tree Search, that subsumes these approaches and distinguishes them based on five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. Using this framework, we describe three new algorithms which mix these ingredients in novel ways in an attempt to combine their different strengths. Our evaluation shows that two of our algorithms not only provide superior theoretical properties to UCT, but also outperform state-of-the-art approaches experimentally.
ICAPS 2013 Special Track on Novel Applications
Planning for Social Interaction in a Robot Bartender Domain
Ronald P. A. Petrick and Mary E. Foster
A robot coexisting with humans must not only be able to perform physical tasks, but must also be able to interact with humans in a socially appropriate manner. In many social settings, this involves the use of social signals like gaze, facial expression, and language. In this paper, we describe an application of planning to task-based social interaction using a robot that must interact with multiple human agents in a simple bartending domain. We show how social states are inferred from low-level sensors, using vision and speech as input modalities, and how we use the knowledge-level PKS planner to construct plans with task, dialogue, and social actions, as an alternative to current mainstream methods of interaction management. The resulting system has been evaluated in a real-world study with human subjects.
ICAPS 2013 Special Track on Novel Applications
Best Student Paper
Combining a Temporal Planner with an External Solver for the Power Balancing Problem in an Electricity Network
Chiara Piacentini, Varvara Alimisis, Maria Fox and Derek Long
The electricity network balancing problem consists of ensuring that the electricity demands of the consumers are met by the committed supply. Constraints are imposed on the different elements of the network, so that damage to the equipment is prevented when transformers are stepped up or down, or generation is increased. We consider this problem within zones, which are sub-networks constructed using carefully chosen decomposition principles. The automation of decision making in electricity networks is a step forward in their management which is necessary for coping with the increase in power system complexity that we expect in the near term. In this paper we explore the deployment of planning techniques to solve the zone-balancing problem. Embedding electricity networks in a domain description presents new challenges for planning. The key point is that the propagation of information requires complex updates to the state when an action is applied. We have developed a method in which the computation of the critical numeric quantities is performed calling an external power flow equation solver, demonstrating a clean interface between the planner and this domain-specific computation. This solver allows us to move the power flow computations outside of the planning process and update the values efficiently. We also examine a second important feature of this problem, which is the interaction between exogenous events and constraints over the entire plan trajectory within a zone.
ICAPS 2013 Influential Paper Award
On the Extraction, Ordering, and Usage of Landmarks in Planning
Julie Porteous, Laura Sebastia and Jörg Hoffmann
in Proceedings of ECP-01, Sixth European Conference on Planning, Toledo, Spain, 2001
Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and use them for guiding search, in the hope to speed up the planning process. We go beyond the previous approaches by defining ordering constraints not only over the (top level) goals, but also over the sub-goals that will arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We show how such landmarks can be found, how their inherent ordering constraints can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner independent. The implementation demonstrates that the approach can yield significant performance improvements in both heuristic forward search and GRAPHPLAN-style planning.
ICAPS 2013 Best Dissertation Award
The Australian National University & NICTA
Scalable Cooperative Multi-Agent Pathfinding with Tractability and Completeness Guarantees
ICAPS 2013 Best Dissertation Award
Universitat Pompeu Fabra
Structure and Inference In Classical Planning
Classical planning is the problem of finding a sequence of actions for achieving a goal from an initial state assuming that actions have deterministic effects. The most effective approach for finding such plans is based on heuristic search guided by heuristics extracted automatically from the problem representation. In this thesis, we introduce alternative approaches for performing inference over the structure of planning problems that do not appeal to heuristic functions, nor to reductions to other formalisms such as SAT or CSP. We show that many of the standard benchmark domains can be solved with almost no search or a polynomially bounded amount of search, once the structure of planning problems is taken into account. In certain cases we can characterize this structure in terms of a novel width parameter for classical planning.
ICAPS 2013 Best Application Showcase Award
Authoring Plan-based Narratives via a Social Network
Julie Porteous, Fred Charles and Marc Cavazza
One way of interacting with an Interactive Storytelling system is via an authoring system prior to plan-based narrative generation. In the search for a user-friendly authoring method for plan-based storytelling domains we have developed a method that captures important narrative aspects such as characters’ relationships as a way of defining a story. This represents a novel form of high-level authoring for plan-based storytelling which fits specific narrative genres: namely, serial dramas (or soap operas) where social relationships between characters act as a determinant for the narrative events that make up different episodes. The approach is implemented in a demonstration system which makes the dependency explicit: using a visual interface users can set social relationships between virtual characters and generate an episode based on that network. Stories are generated at run-time using a plan-based approach that exercises meta-level control over narrative trajectory via the use of pseudo-landmarks. Thus the system provides authors with a visual mechanism for the specification of key story determinants and observation of their impact on generated narratives. The demonstration system is set in the medical drama genre (in the style of serials such as House, ER and Scrubs). During the demo participants are able to interact freely with the system: setting relationships between virtual characters to “author” an episode of the drama in which the relationships they have set lead to peripeteia in the context of medical story lines; and then watching this episode as it is visualised as a 3D animation.
The Award for the Best Application was chosen by the ICAPS 2013 participants through a ballot.
The Award was sponsored by IBM Research.
Call for Nominations: ICAPS Influential Paper Award and ICAPS Best Dissertation Award here.