The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work (Hoffmann 2005), it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) — the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains — we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish ``easy'' domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.

We address a scheduling problem in the context of military aircraft maintenance where the goal is to meet the aircraft requirements for a number of missions in the presence of breakdowns. The assignment of aircraft to a mission must consider the requirements for the mission, the probability of aircraft failure, and capacity of the repair shop that maintains the aircraft. Therefore, a solution both assigns aircraft to missions and schedules the repair shop to meet the assignments. We propose a dispatching heuristic algorithm; three complete approaches based on mixed integer programming, constraint programming, and logic-based Benders decomposition; and a hybrid heuristic-complete approach. Experiments demonstrate that the logic-based Benders variation combining mixed integer programming and constraint programming outperforms the other approaches, that the dispatching heuristic can feasibly schedule the repair shop in a very short time, and that using the dispatching solution as a bound marginally improves the complete approaches.

Learners may develop expertise by experiencing numerous different but relevant situations. Computer games and virtual simulations can facilitate these training opportunities, however, because of the relative difficulty in authoring new scenarios, the increasing need for new and different scenarios becomes a bottleneck in the learning process. Furthermore, a one-size-fits-all scenario may not address all of the abilities, needs, or goals of a particular learner. To address these issues we present a novel technique, Automated Scenario Adaptation, to automatically “rewrite” narrative scenario content to suit individual learners’ needs and abilities and to incorporate recent changes from real world learning needs. Scenario adaptation acts as problem generation for intelligent tutoring systems, producing greater learning opportunities that facilitate engagement and continued learner involvement.

Partial-order schedules are valued because they are flexible, and therefore more robust to unexpected delays. Previous work has indicated that constructing partial-order schedules by a two-stage method, in which a fixed-time schedule is first found and a partial order then lifted from it, is far more efficient than constructing them directly by a least-commitment partial-order scheduling algorithm. However, the two-stage method is limited to exploring only a fraction of the space of partial-order schedules, namely those that can be obtained from the given fixed-time schedule. We introduce a novel constraint formulation of partial-order scheduling, which establishes explicit resource-providing "links" between activities instead of detecting and eliminating potential resource conflicts. We show that this yields an algorithm that is much faster than previous (precedence constraint posting) partial-order scheduling methods, and comparable to the two-stage method in terms of the quality and robustness of the schedules it finds. This algorithm is also complete, and because it searches the entire space of partial-order schedules, can be adapted to optimising different robustness criteria.

State-of-the-art abstraction heuristics are those constructed by the merge-and-shrink approach in which an abstraction consists of a labeled transition system, and the composition of abstractions correspond to the synchronized product of transition systems. Merge-and-shrink heuristics build a composite abstraction from atomic abstractions that are directly associated with the variables of the planning problem. In this paper, we show that the framework of labeled transition systems is more general, and propose a new type of abstraction called the counting abstraction. Counting abstractions can be transparently combined with other type of abstractions to get more informative heuristics. We show how to effectively construct the counting abstractions and presents preliminary experiments over benchmark problems.

Engineering complete planning domain descriptions is often very costly because of human error or lack of domain knowl- edge. Learning complete domain descriptions is also very challenging because many features are irrelevant to achieving the goals and data may be scarce. We present a planner and agent that respectively plan and act in incomplete domains by i) synthesizing plans to avoid execution failure due to ignorance of the domain model, and ii) passively learning about the domain model during execution to improve later re-planning attempts. Our planner DeFault is the first to reason about a domain’s incompleteness to avoid potential plan failure. DeFault computes failure explanations for each action and state in the plan and counts the number of interpretations of the incomplete domain where failure will occur. We show that DeFault performs best by counting prime implicants (failure diagnoses) rather than propositional models. Our agent Goalie learns about the preconditions and effects of incompletely-specified actions while monitoring its state and, in conjunction with DeFault plan failure explanations, can diagnose past and future action failures. We show that by reasoning about incompleteness (as opposed to ignoring it) Goalie fails and re-plans less and executes fewer actions.

Consider the task of a mobile robot autonomously navigating through an environment while detecting and mapping objects of interest using a noisy object detector. The robot must reach its destination in a timely manner, but is rewarded for correctly detecting recognizable objects to be added to the map, and penalized for false alarms. However, detector performance typically varies with vantage point, so the robot benefits from planning trajectories which maximize the efficacy of the recognition system. This work describes an online, any-time planning framework enabling the active exploration of possible detections provided by an off-the-shelf object detector. We present a probabilistic approach where vantage points are identified which provide a more informative view of a potential object. The agent then weighs the benefit of increasing its confidence against the cost of taking a detour to reach each identified vantage point. The system is demonstrated to significantly improve detection and trajectory length in both simulated and real robot experiments.

In this paper we present a planner, LPRPG-P, capable of reasoning with the non-temporal subset of PDDL 3 preferences. Our focus is on computation of relaxed plan based heuristics that effectively guide a planner towards good solutions satisfying preferences. We build on the planner LPRPG, a hybrid relaxed planning graph (RPG)--linear programming (LP) approach. We make extensions to the RPG to reason with propositional preferences, and to the LP to reason with numeric preferences. LPRPG-P is the first planner with direct guidance for numeric preference satisfaction, exploiting the strong numeric reasoning of the LP. We introduce an anytime search approach for use with our new heuristic, and present results showing that LPRPG-P extends the state of the art in domain-independent planning with preferences.

This volume contains the papers accepted for presentation at ICAPS 2011, the Twenty-First International Conferenceon Automated Planning and Scheduling, held in Freiburg, Germany, on June 11–16, 2011. The annual ICAPS conference series was established in 2003 through the merger of two pre-existing biennial conferences, the International Conference on Artificial Intelligence Planning and Scheduling (AIPS) and the European Conference on Planning (ECP). ICAPS continues the traditional high standards of AIPS and ECP as an archival forum for new research in the rapidly developing field of automated planning andscheduling. This volume contains the papers accepted at the conference.

Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem. We describe the approach we have adopted to modelling and solving this problem, seen as a Markov Decision Problem, building effective policies for battery switching in the face of stochastic load profiles. Our solution exploits and adapts several existing techniques from the planning literature and leads to the construction of policies that significantly outperform those that are currently in use and the best published solutions to the battery management problem. We achieve solutions that achieve more than 99\% efficiency compared with the theoretical limit and do so with far fewer battery switches than existing policies. We describe the approach in detail and provide empirical evaluation demonstrating its effectiveness.