In this talk, I will introduce computer-aided algorithm design and discuss its main ingredients: design patterns, which provide ways of structuring potentially large spaces of candidate algorithms, and meta-algorithmic optimisation procedures, which are used for finding good designs within these spaces. After explaining how this algorithm design approach differs from and complements related approaches in program synthesis, genetic programming and so-called hyperheuristics, I will illustrate its success using examples from our own work in SAT-based software verification (Hutter et al. 2007), timetabling (Chiarandini, Fawcett, and Hoos 2008) and mixed integer programming (Hutter, Hoos, and Leyton-Brown 2010). Furthermore, I will argue why this approach can be expected to be particularly useful and effective for building better solvers for rich and diverse classes of combinatorial problems, such as planning and scheduling. Finally, I will outline out how programming by optimisation — a design paradigm that emphasises the automated construction of performance-optimised algorithm by means of searching large spaces of alternative designs — has the potential to transform the design of high-performance algorithm from a craft that is based primarily on experience and intuition into a principled and highly effective engineering effort.

Recently, "determinization in hindsight" has enjoyed surprising success in on-line probabilistic planning. This technique evaluates the actions available in the current state by using non-probabilistic planning in deterministic approximations of the original domain. Although the approach has proven itself effective in many challenging domains, it is computationally very expensive. In this paper, we present three significant improvements to help mitigate this expense. First, we use a method for detecting potentially useful actions, allowing us to avoid estimating the values of unnecessary ones. Second, we exploit determinism in the domain by reusing relevant plans rather than computing new ones. Third, we improve action evaluation by increasing the chance that at least one determin- istic plan reaches a goal. Taken together, these improvements allow determinization in hindsight to scale significantly better on large or mostly-deterministic problems.

The objective of automated planners is to synthesize sequences of actions (called policies in MDP frameworks) that will achieve a predetermined goal given a fully or partially observable formal representation of the domain. In contrast, the main characteristic of project management is the greater emphasis on plan execution under uncertainty as opposed to plan synthesis. This paper explains the need to transition from automated plan synthesis to plan management and identifies the challenges for the planning and scheduling communities using examples of construction projects.

We present a hierarchical planning system and its application to robotic manipulation.  The novel features of the system are: 1) it finds high-quality kinematic solutions to task-level problems; 2) it takes advantage of subtask-specific irrelevance information, reusing optimal solutions to state-abstracted subproblems across the search space.  We briefly describe how the system handles uncertainty during plan execution, and present results on discrete problems as well as pick-and-place tasks for a mobile robot.

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

We empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality, speed, and search guidance. Our results indicate that using multiple heuristics for satisficing search is indeed useful. Among the combination methods we consider, the best results are obtained by the alternation method of the "Fast Diagonally Downward" planner.

We present a planning domain that encodes the problem of generating natural language sentences. This domain has a number of features that provoke fairly unusual behavior in planners. In particular, hitherto no existing automated planner was sufficiently effective to be of practical value in this application. We analyze in detail the reasons for ineffectiveness in FF, resulting in a few minor implementation fixes in FF's preprocessor, and in a basic reconfiguration of its search options. The performance of the modified FF is up to several orders of magnitude better than that of the original FF, and for the first time makes automated planners a practical possibility for this application. Beside thus highlighting the importance of preprocessing and automated configuration techniques, we show that the domain still poses several interesting challenges to the development of search heuristics.

We introduce the Scanalyzer planning domain, a domain for classical planning which models the problem of automatic greenhouse logistic management. At its mathematical core, the Scanalyzer domain is a permutation problem with striking similarities to common search benchmarks such as Rubik's Cube or TopSpin. At the same time, it is also a real application domain, and efficient algorithms for the problem are of considerable practical interest. The Scanalyzer domain was used as a benchmark for sequential planners at the last International Planning Competition. The competition results show that domain-independent automated planners can find solutions of comparable quality to those generated by specialized algorithms developed by domain experts, while being considerably more flexible.

We present Shopper, a plan execution engine that facilitates experimental evaluation of plans and makes it easier for planning researchers to incorporate replanning. Shopper interprets the LTML plan language, which extends PDDL in two major ways: with more expressive control structures, and with support for semantic web services modeled on OWL-S. LTML's command structures include not only conventional ones such as branching, iteration, and procedure calls, but also features needed to handle HTN plans, such as precondition-filtered method choice. Unlike conventional programming languages, LTML supports interaction with the agent's belief store, so that its execution semantics line up with those assumed by planners. LTML actions extend PDDL actions in having outputs as well as effects, which means that they can support actions that sense the world; an important special case of this is semantic web services, which reveal information about a state hidden from the agent. To support experimentation as well as action in the real world, Shopper accommodates multiple, swappable implementations of its primitive action API. For example, one may interact with real web services through SOAP and WSDL, or with simulated web services through local procedure calls. We describe novel features of LTML, the interpretation strategy, swappable back-ends, and the implementation.

The PDDL+ language has been mainly devised to allow modelling of real-world systems, with continuous, time-dependant dynamics. Several interesting case studies with these characteristics have been also proposed, to test the language expressiveness and the capabilities of the support tools. However, most of these case studies have not been completely developed so far. In this paper we focus on the batch chemical plant case study, a very complex hybrid system with nonlinear dynamics that could represent a challenging benchmark problem for planning techniques and tools. We present a complete PDDL+ model for such system, and show an example application where the UPMurphi universal planner is used to generate a set of production policies for the plant.