Recent Advances in AI Planning

Frontmatter

Planning as Model Checking

Abstract

The goal of this paper is to provide an introduction, with various elements of novelty, to the Planning as Model Checking paradigm.

Fausto Giunchiglia, Paolo Traverso

Conformant Planning via Model Checking

Abstract

Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal for any possible initial state and nondeterministic behavior of the planning domain. In this paper we present a new approach to conformant planning. We propose an algorithm that returns the set of all conformant plans of minimal length if the problem admits a solution, otherwise it returns with failure. Our work is based on the planning via model checking paradigm, and relies on symbolic techniques such as Binary Decision Diagrams to compactly represent and efficiently analyze the planning domain. The algorithm, called cmbp, has been implemented in the mbp planner. cmbp is strictly more expressive than the state of the art conformant planner sc cgp. Furthermore, an experimental evaluation suggests that cmbp is able to deal with uncertainties more efficiently than cgp.

Alessandro Cimatti, Marco Roveri

Strong Cyclic Planning Revisited

Abstract

Several realistic non-deterministic planning domains require plans that encode iterative trial-and-error strategies, e.g., “pick up a block until succeed”. In such domains, a certain effect (e.g., action success) might never be guaranteed a priori of execution and, in principle, iterative plans might loop forever. Here, the planner should generate iterative plans whose executions always have a possibility of terminating and, when they do, they are guaranteed to achieve the goal. In this paper, we define the notion of strong cyclic plan, which formalizes in temporal logic the above informal requirements for iterative plans, define a planning algorithm based on model-checking techniques, and prove that the algorithm is guaranteed to return strong cyclic plans when they exist or to terminate with failure when they do not. We show how this approach can be extended to formalize plans that are guaranteed to achieve the goal and do not involve iterations (strong plans) and plans that have a possibility (but are not guaranteed) to achieve the goal (weak plans). The results presented in this paper constitute a formal account for “planning via model checking” in non-deterministic domains, which has never been provided before.

Marco Daniele, Paolo Traverso, Moshe Y. Vardi

Scaleability in Planning

Abstract

This paper explores the performance of three planners, viz. parcPLAN, IPP and Blackbox, on a variant of the standard blocks-world problem. The variant problem has a restricted number of table positions, and the number of arms can vary (from 1 upwards). This type of problem is typical of many real world planning problems, where resources form a significant component. The empirical studies reveal that least commitment planning, as implemented in parcPLAN, is far more effective than the strategies in IPP and Blackbox. But the studies also reveal a serious limitation on the scaleability of parcPLAN’s algorithm.

Vassilis Liatsos, Barry Richards

Exploiting Competitive Planner Performance

Abstract

To date, no one planner has demonstrated clearly superior performance. Although researchers have hypothesized that this should be the case, no one has performed a large study to test its limits. In this research, we tested performance of a set of planners to determine which is best on what types of problems. The study included six planners and over 200 problems. We found that performance, as measured by number of problems solved and computation time, varied with no one planner solving all the problems or being consistently fastest. Analysis of the data also showed that most planners either fail or succeed quickly and that performance depends at least in part on some easily observable problem/domain features. Based on these results, we implemented a meta-planner that interleaves execution of six planners on a problem until one of them solves it. The control strategy for ordering the planners and allocating time is derived from the performance study data. We found that our meta-planner is able to solve more problems than any single planner, but at the expense of computation time.

Adele E. Howe, Eric Dahlman, Christopher Hansen, Michael Scheetz, Anneliese von Mayrhauser

A Parallel Algorithm for POMDP Solution

Abstract

Most exact algorithms for solving partially observable Markov decision processes (POMDPs) are based on a form of dynamic programming in which a piecewise-linear and convex representation of the value function is updated at every iteration to more accurately approximate the true value function. However, the process is computationally expensive, thus limiting the practical application of POMDPs in planning. To address this current limitation, we present a parallel distributed algorithm based on the Restricted Region method proposed by Cassandra, Littman and Zhang [1]. We compare performance of the parallel algorithm against a serial implementation Restricted Region.

Larry D. Pyeatt, Adele E. Howe

Plan Merging & Plan Reuse as Satisfiability

Abstract

Planning as satisfiability has hitherto focused only on purely generative planning. There is an evidence in traditional refinement planning that planning incrementally by reusing or merging plans can be more efficient than planning from scratch (sometimes reuse is not more efficient, but becomes necessary if the cost of abandoning the reusable plan is too high, when users are charged for the planning solution provided). We adapt the satisfiability paradigm to these scenarios by providing a framework where reusable or mergeable plans can be either contiguous or partially ordered and their actions can be removed and new actions can be added. We report the asymptotic sizes of the propositional encodings for several cases of plan reuse and plan merging. Our empirical evaluation shows that the satisfiability paradigm can scale up to handle plan reuse and plan merging.

Amol Dattatraya Mali

SAT-Based Procedures for Temporal Reasoning

Abstract

In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that—on sets of binary randomly generated disjunctive constraints—they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis’s result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables.

Alessandro Armando, Claudio Castellini, Enrico Giunchiglia

Numeric State Variables in Constraint-Based Planning

Abstract

We extend a planning algorithm to cover simple forms of arithmetics. The operator preconditions can refer to the values of numeric variables and the operator postconditions can modify the values of numeric variables. The basis planning algorithm is based on techniques from propositional satisfiability testing and does not restrict to forward or backward chaining. When several operations affect a numeric variable by increasing and decreasing its value in parallel, the effects have to be combined in a meaningful way. This problem is especially acute in planning algorithms that maintain an incomplete state description of every time point of a plan execution. The approach we take requires that for operators that are executed in parallel, all linearizations of the operations to total orders behave equivalently. We provide an efficient and general solution to the problem.

Jussi Rintanen, Hartmut Jungholt

Hierarchical Task Network Planning as Satisfiability

Abstract

The satisfiability paradigm has been hitherto applied to planning with only primitive actions. On the other hand, hierarchical task networks have been successfully used in many real world planning applications. Adapting the satisfiability paradigm to hierarchical task network planning, we show how the guidance from the task networks can be used to significantly reduce the sizes of the propositional encodings. We report promising empirical results on various encodings that demonstrate an orders of magnitude reduction in the solving times.

Amol Dattatraya Mali

Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length

Abstract

In this paper we present a general-purposed algorithm for transforming a planning problem specified in Strips into a concise state description for single state or symbolic exploration.

The process of finding a state description consists of four phases. In the first phase we symbolically analyze the domain specification to determine constant and one-way predicates, i.e. predicates that remain unchanged by all operators or toggle in only one direction, respectively.

In the second phase we symbolically merge predicates invariants which lead to a drastic reduction of state encoding size, while in the third phase we constrain the domains of the predicates to be considered by enumerating the operators of the planning problem. The fourth phase combines the result of the previous phases.

Stefan Edelkamp, Malte Helmert

Action Constraints for Planning

Abstract

Recent progress in the applications of propositional planning systems has led to an impressive speed-up of solution time and an increase in tractable problem size. In part, this improvement stems from the use of domain-dependent knowledge in form of state constraints. In this paper we introduce a different class of constraints: action constraints . They express domain-dependent knowledge about the use of actions in solution plans and can express strategies which are used by human planners. The use of action constraints results in a tendency to better plans. We explain how to calculate and apply action constraints in the framework of parallel total-order planning, which is the design of the most powerful planners at the moment. We present two classes of action constraints and demonstrate their capabilities in the planner ProbaPla.

Ulrich Scholz

Least Commitment on Variable Binding in Presence of Incomplete Knowledge

Abstract

Constraint Satisfaction techniques have been recognized to be effective tools for increasing the efficiency of least commitment planners. We focus on least commitment on variable binding. A constraint based approach for this issue has been previously proposed by Yang and Chan [21]. In this setting, the planning problem is mapped onto a Constraint Satisfaction Problem. Its variables represent domain objects and are defined on a finite domain of values; constraints remove inconsistent values from variable domains through constraint propagation. In many applications, however, it is not always convenient, if possible at all, to know in advance all objects belonging to variable domains. Thus, domain values should be retrieved during the plan construction only when needed. The interesting point is that data acquisition for each variable can be guided by the constraint (or the constraints) imposed on the variable itself, in order to retrieve only consistent values. For this purpose, we have extended a Partial Order Planner performing least commitment on variable binding. This extension can cope with incomplete knowledge. We use the Interactive Constraint Satisfaction framework defined in [12] in order to exploit the efficiency deriving from constraint propagation and the possibility of acquiring the domain knowledge during the plan construction. Experimental results and comparisons with related approaches show the effectiveness of the proposed technique.

R. Barruffi, E. Lamma, P. Mello, M. Milano

Scaling up Planning by Teasing Out Resource Scheduling

Abstract

Planning consists of an action selection phase where actions are selected and ordered to reach the desired goals, and a resource allocation phase where enough resources are assigned to ensure the successful execution of the chosen actions. In most real-world problems, these two phases are loosely coupled. Most existing planners do not exploit this loose-coupling, and perform both action selection and resource assignment employing the same algorithm. We shall show that this strategy severely curtails the scale-up potential of existing planners, including such recent ones as Graphplan and Blackbox. In response, we propose a novel planning framework in which resource allocation is teased apart from planning, and is handled in a separate “scheduling” phase. We ignore resource constraints during planning and produce an abstract plan that can correctly achieve the goals but for the resource constraints. Next, based on the actual resource availability, the abstract plan will be allocated resources to produce an executable plan. Our approach not only preserves both the correctness as well as the quality (measured in length) of the plan but also improves efficiency. We describe a prototype implementation of our approach on top of Graphplan and show impressive empirical results.

Biplav Srivastava, Subbarao Kambhampati

Real-Time Scheduling for Multi-agent Call Center Automation

Abstract

In a call center, service agents with different capabilities are available for solving incoming customer problems at any time. To supply quick response and better problem solution to customers, it is necessary to schedule customer problems to appropriate service agents efficiently. We developed SANet, a service agent network for call center, which integrates multiple service agents including both software agents and human agents, and employs a broker to schedule customer problems to service agents for better solutions according to their changing capabilities and availability. This paper describes the real-time scheduling method in SANet as well as its architecture. There are two phases in our scheduling method. One is problem-type learning. The broker is trained to learn the problem types and hence can decide the type of incoming problems automatically. The other is the scheduling algorithm based on problem types, capabilities and availability of service agents. We highlight an application in which we apply SANet to a call center problem for a cable-TV company. Finally, we support our claims via experimental results and discuss related works.

Yong Wang, Qiang Yang, Zhong Zhang

Task Decomposition Support to Reactive Scheduling

Abstract

This paper describes the development of an intelligent tasking model which has been designed to enable complex systems, human agents and software agents, to be tasked and controlled within a reactive work ow management paradigm. The task models exploit recent advances within the AI community in reactive control, scheduling and continuous execution. The Dynamic Execution Order Scheduler ( DEOS ) extends the current work ow paradigm to allow tasking in dynamic and uncertain environments by viewing the planning and scheduling tasks as being integrated and evolving entities. DEOS is being applied to the domains of Air Campaign Planning ( ACP ) and Intelligence, Surveillance and Reconnaissance ( ISR ) management. These are highly reactive domains in which new tasks and priorities are identified continuously and plans and schedules are generated and updated within a temporal and resource constrained setting.

Brian Drabble

Greedy Algorithms for the Multi-capacitated Metric Scheduling Problem

Abstract

This paper investigates the performance of a set of greedy algorithms for solving the Multi-Capacitated Metric Scheduling Problem (MCM-SP). All algorithms considered are variants of ESTA (Earliest Start Time Algorithm), previously proposed in [3]. The paper starts with an analysis of ESTA’s performance on different classes of MCM-SP problems. ESTA is shown to be effective on several of these classes, but is also seen to have difficulty solving problems with heavy resource contention. Several possibilities for improving the basic algorithm are investigated. A first crucial modification consists of substituting ESTA’s pairwise analysis of resource conflicts with a more aggregate and thus more powerful Minimal Critical Set (MCS) computation. To cope with the combinatorial task of enumerating MCSs, several approximate sampling procedures are then defined. Some systematic sampling strategies, previously shown effective on a related but different class of scheduling problem, are found to be less effective on MCM-SP. On the contrary, a randomized MCS sampling technique is introduced, forming a variant of ESTA that is shown to be quite powerful on highly constrained problems.

Amedeo Cesta, Angelo Oddi, Stephen F. Smith

Automata-Theoretic Approach to Planning for Temporally Extended Goals

Abstract

We study an automata-theoretic approach to planning for temporally extended goals. Specifically, we devise techniques based on nonemptiness of Büchi automata on infinite words, to synthesize sequential and conditional plans in a generalized setting in which we have that: goals are general temporal properties of desired execution; dynamic systems are represented by finite transition systems; incomplete information on the initial situation is allowed; and states are only partially observable. We prove that the techniques proposed are optimal wrt the worst case complexity of the problem. Thanks to the scalability of the nonemptiness algorithms, the techniques presented here promise to be applicable to fairly large systems, notwithstanding the intrinsic complexity of the problem.

Giuseppe De Giacomo, Moshe Y. Vardi

Integer Programs and Valid Inequalities for Planning Problems

Abstract

Part of the recent work in AI planning is concerned with the development of algorithms that regard planning as a combinatorial search problem. The underlying representation language is basically propositional logic. While this is adequate for many domains, it is not clear if it remains so for problems that involve numerical constraints, or optimization of complex objective functions. Moreover, the propositional representation imposes restrictions on the domain knowledge that can be utilized by these approaches. In order to address these issues, we propose moving to the more expressive language of Integer Programming (IP). We show how capacity constraints can be easily encoded into linear 0-1 inequalities and how rich forms of domain knowledge can be compactly represented and computationally exploited by IP solvers. Then we introduce a novel heuristic search method based on the linear programming relaxation. Finally, we present the results of our experiments with a classical relaxation-based IP solver and a logic-based 0-1 optimizer.

Alexander Bockmayr, Yannis Dimopoulos

Deductive Synthesis of Recursive Plans in Linear Logic

Abstract

Linear logic has previously been shown to be suitable for describing and deductively solving planning problems involving conjunction and disjunction. We introduce a recursively defined datatype and a corresponding induction rule, thereby allowing recursive plans to be synthesised. In order to make explicit the relationship between proofs and plans, we enhance the linear logic deduction rules to handle plans as a form of proof term.

Stephen Cresswell, Alan Smaill, Julian Richardson

Sensor Planning with Non-linear Utility Functions

Abstract

Sensor planning is concerned with when to sense and what to sense. We study sensor planning in the context of planning objectives that trade-off between minimizing the worst-case, expected, and best-case plan- execution costs. Sensor planning with these planning objectives is interesting because they are realistic and the frequency of sensing changes with the planning objective: more pessimistic decision makers tend to sense more frequently. We perform sensor planning by combining one of our techniques for planning with non-linear utility functions with an existing sensor-planning method. The resulting sensor-planning method is not only as easy to implement as the sensor-planning method that it extends but also (almost) as efficient. We demonstrate empirically how sensor plans change as the planning objective changes, using a common testbed for sensor planning.

Sven Koenig, Yaxin Liu

Propice-Plan: Toward a Unified Framework for Planning and Execution

Abstract

In this paper, we investigate the links between planning and plans execution. We propose a new approach (Propice-Plan) which integrates both activities. It implements supervision and execution capabilities, combined with different planning techniques:

• plan synthesis to complement existing operational plans; and
• anticipation planning to advise the execution for the best option to take when facing choices by anticipating plans execution), and to forecast problems that may arise due to unforeseen situations.

This approach relies on a common language to represent plans, actions, operational procedures and constraints. In particular, the description we propose makes transitions between planning activities and execution seamless.

This work is used in two complex real-world problems: planning and control for autonomous mobile robots, and for the transition phases of a blast furnace.

Olivier Despouys, François Félix Ingrand

What is the Expressive Power of Disjunctive Preconditions?

Abstract

While there seems to be a general consensus about the expressive power of a number of language features in planning formalisms, one can find many different statements about the expressive power of disjunctive preconditions. Using the “compilability framework,” we show that preconditions in conjunctive normal form add to the expressive power of propositional strips, which confirms a conjecture by Bäckström. Further, we show that preconditions in conjunctive normal form do not add any expressive power once we have conditional effects.

Bernhard Nebel

Some Results on the Complexity of Planning with Incomplete Information

Abstract

Planning with incomplete information may mean a number of different things; that certain facts of the initial state are not known, that operators can have random or nondeterministic effects, or that the plans created contain sensing operations and are branching. Study of the complexity of incomplete information planning has so far been concentrated on probabilistic domains, where a number of results have been found. We examine the complexity of planning in nondeterministic propositional domains. This differs from domains involving randomness, which has been well studied, in that for a nondeterministic choice, not even a probability distribution over the possible outcomes is known. The main result of this paper is that the non-branching plan existence problem in unobservable domains with an expressive operator formalism is EXPSPACE-complete. We also discuss several restrictions, which bring the complexity of the problem down to PSPACE-complete, and extensions to the fully and partially observable cases.

Patrik Haslum, Peter Jonsson

Probabilistic Planning in the Graphplan Framework

Abstract

The Graphplan planner has enjoyed considerable success as a planning algorithm for classical STRIPS domains. In this paper we explore the extent to which its representation can be used for probabilistic planning. In particular, we consider an MDP-style framework in which the state of the world is known but actions are probabilistic, and the objective is to produce a finite horizon contingent plan with highest probability of success within the horizon.

We describe two extensions of Graphplan in this direction. The first, PGraphplan, produces an optimal contingent plan. It typically suffers a performance hit compared to Graphplan but still appears to be fast compared with other approaches to probabilistic planning problems. The second, TGraphplan, runs at essentially the same speed as Graphplan, but produces potentially sub-optimal policies: TGraphplan’s policy selects the first action on the highest probability trajectory from its current state to the goal. Ideally, we would like an optimal planner for probabilistic domains with the same speed that Graphplan would have if the domain were made deterministic. By comparing the speed and quality of these two planners to each other and to other existing planners, we are able to estimate how far off we are from our ideal.

PGraphplan is based on a forward-chaining search, unlike the backward-chaining search of the standard Graphplan algorithm. Thus, one focus of this paper is exploring the extent to which Graphplan’s representation can be used to speed up forward search in addition to the backward search for which it was originally intended.

Avrim L. Blum, John C. Langford

Making Graphplan Goal-Directed

Abstract

The Graphplan algorithm exemplifies the speed-up achieveable with disjunctive representations that leverage opposing directions of refinement. It is in this spirit that we introduce Bsr-graphplan, a work in progress intended to address issues of scalability and expressiveness which are problematic for Graphplan. Specifically, we want to endow the planner with intelligent backtracking and full quantification of action schemata. Since Graphplan employs a backward chaining search, it lacks the necessary state information to efficiently support these mechanisms. We hypothesize that alternatively pointing the search in the direction of the goals provides an sufficient amelioration. Further, we demonstrate that a forward chaining search strategy can be competitive by enforcing ordering constraints on the developing plan prefix. This is accomplished by using operators of a plangraph constructed in a top-down fashion to extend the plan prefix, and by introducing an additional data structure – a constraint tree – which is constructed by regressing subgoal information through the graph operators.

Eric Parker

GRT: A Domain Independent Heuristic for STRIPS Worlds Based on Greedy Regression Tables

Abstract

This paper presents Greedy Regression Tables (GRT), a new domain independent heuristic for STRIPS worlds. The heuristic can be used to guide the search process of any state-space planner, estimating the distance between each intermediate state and the goals. At the beginning of the problem solving process a table is created, the records of which contain the ground facts of the domain, among with estimates for their distances from the goals. Additionally, the records contain information about interactions that occur while trying to achieve different ground facts simultaneously. During the search process, the heuristic, using this table, extracts quite accurate estimates for the distances between intermediate states and the goals. A simple best-first search planner that uses this heuristic has been implemented in C++ and has been tested on several “classical” problem instances taken from the bibliography and on some new taken from the AIPS-98 planning competition. Our planner has proved to be faster in all of the cases, finding also in most (but not all) of the cases shorter solutions.

Ioannis Refanidis, Ioannis Vlahavas

Planning as Heuristic Search: New Results

Abstract

In the recent AIPS98 Planning Competition, the hsp planner, based on a forward state search and a domain-independent heuristic, showed that heuristic search planners can be competitive with state of the art Graphplan and Satisfiability planners. hsp solved more problems than the other planners but it often took more time or produced longer plans. The main bottleneck in hsp is the computation of the heuristic for every new state. This computation may take up to 85% of the processing time. In this paper, we present a solution to this problem that uses a simple change in the direction of the search. The new planner, that we call hspr, is based on the same ideas and heuristic as hsp , but searches backward from the goal rather than forward from the initial state. This allows hspr to compute the heuristic estimates only once. As a result, hspr can produce better plans, often in less time. For example, hspr solves each of the 30 logistics problems from Kautz and Selman in less than 3 seconds. This is two orders of magnitude faster than blackbox. At the same time, in almost all cases, the plans are substantially smaller. hspr is also more robust than hsp as it visits a larger number of states, makes deterministic decisions, and relies on a single adjustable parameter than can be fixed for most domains. hspr, however, is not better than hsp accross all domains and in particular, in the blocks world, hspr fails on some large instances that hsp can solve. We discuss also the relation between hspr and Graphplan, and argue that Graphplan can also be understood as a heuristic search planner with a precise heuristic function and search algorithm.

Blai Bonet, Héctor Geffner

Backmatter