In this paper, we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich qualitative user preferences. The outcome of our work is a language for specifyin user preferences, tailored to HTN planning, together with a provably optimal preference-based planner, HTNPLAN, that is implemented as an extension of SHOP2. To compute preferred plans, we propose an approach based on forward-chaining heuristic search. Our heuristic uses an admissible evaluation function measuring the satisfaction of preferences over partial plans. Our empirical evaluation demonstrates the effectiveness of our HTNPLAN heuristics. We prove our approach sound and optimal with respect to the plans it generates by appealing to a situation calculus semantics of our preference language and of HTN planning. While our implementation builds on SHOP2, the language and techniques proposed here are relevant to a broad range of HTN planners.

Constraint Programming is an attractive approach for solving AI planning problems by modelling them as Constraint Satisfaction Problems (CSPs). However, formulating effective constraint models of complex planning problems is challenging,  and CSPs resulting from standard approaches often require further enhancement to perform well. Common subexpression elimination is a computationally cheap and  general technique for improving CSPs, which can lead to a great reduction in instance size, solving time and search space. In this work we identify general causes of common subexpressions from three modelling techniques often used to encode planning problems into   constraints. We present four case studies of constraint  models of AI planning problems. In each, we describe the constraint model, highlight the sources of common subexpressions, and present an empirical analysis of the effects of eliminating common subexpressions.

State abstraction has been widely used for state aggregation in approaches to AI search and planning. In this paper we use a powerful abstraction technique from software model checking for representing collections of states with different object quantities and properties. We exploit this method to develop precise abstractions and action operators for use in AI. This enables us to find scalable, algorithm-like plans with branches and loops which can solve problems of unbounded sizes. We describe how this method of abstraction can be effectively used in AI, with compelling results from implementations of two planning algorithms.

Despite a big progress in solving planning problems, more complex problems still remain hard and challenging for existing planners. One of the most promising research directions is exploiting knowledge engineering techniques such as (re)formulating the planning problem to be easier to solve for existing planners. In particular, it is possible to automatically gather knowledge from toy planning problems and exploit this knowledge when solving more complex planning problems. In this paper we propose a method for eliminating some actions from the problem specification that are often useless or may mislead the planners. The method detects if actions are somehow connected with the initial or goal predicates and by using this information we suggest that some actions are not necessary when solving the planning problem. To eliminate these actions we modify the planning domain and hence the method remains independent of used planning system.

Classical planning deals with finding a (shortest) sequence of actions transferring the world from its initial state to a state satisfying the goal condition. Traditional planning systems explore either paths in the state space (state-space planning) or partial plans (plan-space planning). In this paper we show how the ideas from plan-space (partial order) planning can be integrated into state-space (sequential) planning by combining constraint models describing both types of planning. In particular, we extend our existing constraint model for sequential planning by constraints describing satisfaction of open goals. We demonstrate experimentally that this extension pays-off especially when the planning problems become harder.

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.

This paper describes an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. A class of oversubscribed scheduling problems is considered where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities, and activities are subject to deadlines. To ensure scalability, the approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. Experimental results obtained in a multi-agent simulation environment demonstrate that coupling probabilistic and deterministic reasoning in this way results in significantly higher rewards than are achieved by relying on deterministic reasoning alone. In the future, the approach will be extended to include probability-driven meta-level management of execution.

We present an implementation of a plan adaptation system, BioPlanner, built for biological pathway prediction across species. BioPlanner formulates a pathway discovery problem as a Hierarchical Task Network (HTN) planning problem and solves it by adapting a plan solution of another well-studied pathway. BioPlanner provides the following functionalities: It automatically builds HTN planning models for a biological pathway domain from the semantic web biological knowledge bases (KBs). It retrieves plan cases from the biological KBs. It generates hypothetical pathways using plan adaptation strategies with the aid of biological domain knowledge. It evaluates the hypothetical plan candidates, ranks them, and recommends the most likely hypotheses to users. It employs an information gathering multi-agent system to capture knowledge from heterogeneous sources to help the hypothetical plan generation process. We utilize BioPlanner to predict Signaling Transduction pathways for Mus musculus, Gallus gallus, and Drosophila melanogaster from Homo sapiens.

This paper presents a project awarded by MGB HK to handle their inspection scheduling problem. MGB HK is the buying office of one of the largest retailers in the world, Metro Group. MGB HK handles all product procurement of Metro Group out of Europe. The inspection process is one of their critical processes along their entire procurement exercise. The objective of this project is to provide an effective scheduling engine so that in-house inspectors can handle as many inspections as possible using the least amount of time and costs. Meanwhile, we also help the company overcome their difficulties of data collection and maintenance as a result of the system we developed. Our engine will be deployed and integrated into the company’s IMS. The engine recorded an improvement in the scheduling of their inspections and initial prognosis indicates that delayed inspections have been greatly reduced by compared with previous schedule. The system can effectively schedule inspections by urgency, shipment value, and supplier’s historical performance. Other than the schedule, the AI engine can also generate solutions based on different strategies and criteria, which facilitate the decision-making process for the scheduling team and management at MGB HK.

Considerable progress has been made over the last 15 years on building adaptive control systems to assist pilots in flying damaged aircraft. Once a pilot has regained control of a damaged aircraft, the next problem is to determine the best site for an emergency landing.  In general, the decision depends on many factors including the actual control envelope of the aircraft, distance to the site, weather en route, characteristics of the approach path, characteristics of the runway or landing site, and emergency facilities at the site.  All of these influence the risk to the aircraft, to the passengers and crew, and to people and property on the ground.  We describe an emergency landing planner that takes these various factors into consideration and proposes possible routes and landing sites to the pilot, ordering them according to estimated risk.   We give an overview of the system architecture and input data, describe our modeling of risk, describe how we search the space of landing sites and routes, and give a preliminary performance assessment for characteristic emergency scenarios using the current research prototype.