Awards

ICAPS 2013 Best Paper

The Relative Pruning Power of Strong Stubborn Sets and Expansion Core

by
Martin Wehrle, Malte Helmert, Yusra Alkhazraji and Robert Mattmüller

Friday, June 14 2013, 10.30 am, Auditorium

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

by
Thomas Keller and Malte Helmert

Wednesday, June 12 2013, 2.35 pm, Auditorium

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
Best Paper

Planning for Social Interaction in a Robot Bartender Domain

by
Ronald P. A. Petrick and Mary E. Foster

Thursday, June 13 2013, 10.55 am, Auditorium

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

by
Chiara Piacentini, Varvara Alimisis, Maria Fox and Derek Long

Thursday, June 13 2013, 3.35 pm, Auditorium

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

by
Julie Porteous, Laura Sebastia and Jörg Hoffmann

in Proceedings of ECP-01, Sixth European Conference on Planning, Toledo, Spain, 2001

Thursday, June 13 2013, 5.05 pm, Auditorium

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

Cindy Wang
The Australian National University & NICTA

Scalable Cooperative Multi-Agent Pathfinding with Tractability and Completeness Guarantees

Thursday, June 13 2013, 5.05 pm, Auditorium

Multi-agent pathfinding is a challenging problem with many applications, including robotics, logistics, and computer games. Running a systematic centralised A* search in the combined state space of all units is complete and cost-optimal, but scales poorly in the number of mobile units. Decoupled approaches such as the successful WHCA* algorithm, decompose the initial problem into a series of smaller searches, significantly improving speed and scalability at the expense of completeness. This thesis addresses these important issues in multi-agent pathfinding in concert, including tractability, completeness, scalability, and solution quality.

We first present FAR, which is empirically shown to run significantly faster than WHCA* on grid maps, using much less memory, and scaling up to larger problems. Like WHCA*, FAR is incomplete, and does not tell in advance whether it would succeed in finding a solution to a given instance, nor does it provide guarantees with respect to the total running time or solution quality. To overcome such limitations, we introduce MAPP, a tractable algorithm on undirected graphs. We present a basic version and several extensions. All versions have low-polynomial worst-case upper bounds on the running time, memory, and solution length. Even though all versions are incomplete in the general case, each provides efficiently computable formal guarantees on problems it can solve. For each version, we discuss the algorithm’s completeness with respect to clearly defined subclasses of instances.

Experiments were run on grid maps extracted from a popular commercial computer game called Baldur’s Gate with 100–2000 mobile units. Out of the three algorithms, FAR is the fastest running, and also gives the shortest solutions. Nonetheless, MAPP has the advantages of providing partial completeness guarantees and low-polynomial upper bounds on resources required, as well as being the clear winner in scalability and success ratio, balancing well the tradeoff between its partial completeness and its practical performance.

ICAPS 2013 Best Dissertation Award

Nir Lipovetzky
Universitat Pompeu Fabra

Structure and Inference In Classical Planning

Thursday, June 13 2013, 5.05 pm, Auditorium

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

by
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.