Finite-state and memoryless controllers are simple action selection mechanisms widely used in domains such as video-games and mobile robotics.  Memoryless controllers stand for functions that map observations into actions, while finite-state controllers generalize memoryless ones with a finite amount of memory.  In contrast to the policies obtained from MDPs and POMDPs, finite-state controllers have two advantages: they are often extremely compact, involving a small number of controller states or none at all, and they are general, applying to many problems and not just one. A limitation of finite-state controllers is that they must be written by hand. In this work, we address this limitation, and develop a method for deriving finite-state controllers automatically from models. These models represent a class of contingent problems where actions are deterministic and some fluents are observable.  The problem of deriving a controller from such models is converted into a conformant planning problem that is solved using classical planners, taking advantage of a complete translation introduced recently.  The controllers derived in this way are 'general' in the sense that they do not solve the original problem only, but many variations as well, including changes in the size of the problem or in the uncertainty of the initial situation and action effects.  Experiments illustrating the derivation of such controllers are presented.

Despite its ubiquitous presence, very little is known about the odds of winning the simple card game of Klondike Solitaire. The main goal of this paper is to investigate the use of probabilistic planning to shed light on this issue. Unfortunatley, most probabilistic planning techniques are not well suited for Klondike due to the difficulties of representing the domain in standard planning languages and the complexity of the required search. Klondike thus serves as an interesting addition to the complement of probabilistic planning domains. In this paper, we study Klondike using several sampling-based planning approaches including UCT, hindsight optimization, and sparse sampling, and establish lower bounds on their performance. We also introduce novel combinations of these approaches and evaluate them in Klondike. We provide a theoretical bound on the sample complexity of a method that naturally combines sparse sampling and UCT. Our results demonstrate that there is a policy that within tight confidence intervals wins over 35% of Klondike games. This result is the first reported lower bound of an optimal Klondike policy.

In this paper we realize the synthesis of continuous coordinations By envisaging standards to publish and access services over based on the conceptual framework of (Pistore, the Web, the Service-Oriented Computing (SOC) paradigm Traverso, and Bertoli 2005), which recasts the composition promises a novel degree of interoperability between distributed problem in terms of planning; namely, we act at its core applications that realize business processes. One by adopting a very simple, yet expressive requirements language, cornerstone of SOC stands in the provision of novel and and devising a novel planning algorithm. In particular, more complex business logics by the coordination of existing the requirement language expresses coordination constraints services. Due to the complexity of manually realizing that are transformed into preference-ordered maintenability such coordinations, automatedly supporting the synthesis goals, and the algorithm deals with such goals in of service orchestrations is crucial to the actual enactment the presence of exogenous events (which encode independent of SOC. This problem is extremely hard since, asynchronous evolutions of services).

The FF relaxed plan heuristic is one of the most effective techniques in domain-independent satisficing planning and is used by many state-of-the-art heuristic-search planners. However, it may sometimes provide quite inaccurate information, since its relaxation strategy, which ignores the delete effects of actions, may oversimplify a problem's structure. In this paper, we propose a novel algorithm for computing relaxed plans which — although still relaxed — aim at respecting much of the structure of the original problem. We accomplish this by generating  relaxed plans with a reduced number of conflicts. An action a will add a conflict when added to a relaxed plan if the resulting plan is provably illegal (i.e, not executable) in the un-relaxed problem. As a second contribution, we propose a new lookahead strategy, in the spirit of Vidal's YAHSP lookahead, that can better exploit the contents of relaxed plans. In our experimental analysis, we show that the resulting heuristic improves over the FF heuristic in a number of domains, most notably when lookahead is enabled. Moreover, the resulting system, which uses our new lookahead, is competitive with state-of-the-art planners, and even better in terms of the number of solved problems.

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.

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.

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.

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.