Despite the extensive development of first-principles planning in recent years, planning applications are still primarily developed using knowledge-based planners which can exploit domain-specific heuristics and weaker domain models.  Hierarchical Task Network (HTN) planners capture domain-specific heuristics for more efficient search, accommodate incomplete causal models, and can be used to enforce standard operating procedures.  Unfortunately, we do not have semantics for the methods or tasks that make up HTN models, that help evaluate the correctness of methods, or to build a reliable executive for HTN plans.  This paper fills the gap by providing a well-defined semantics for the methods and plans of SHOP2, a state-of-the-art HTN planner.  The semantics are defined in terms of concurrent golog (ConGolog) and the situation calculus.  We provide a proof of equivalence between the plans generated by SHOP2 and the action sequences of the ConGolog semantics.  We show how the semantics reflects the distinction between plan-time and execution-time, and provide some simple examples showing how the semantics can support method verification.  The semantics provide an implementation-neutral specification for an executive, showing how an executive must treat the plans SHOP2 generates in order to enforce the expected behaviors.  Future directions include automated verification of method specifications, automatically generating plan monitors, and plan revision and repair.

This paper proposes an iterative improvement approach for solving the Resource Constraint Project Scheduling Problem with Time-Windows (RCPSP/max), a well-known and challenging NP-hard scheduling problem. The algorithm is based on Iterative Flattening Search (IFS), an effective heuristic strategy for solving multi-capacity optimization scheduling problems. Given an initial solution, IFS iteratively performs two-steps: a relaxation-step , that randomly removes a subset of solution constraints and a solving-step , that incrementally recomputes a new solution. At the end, the best solution found is returned. The main contribution of this paper is the extension to RCPSP/max of the IFS optimization procedures developed for solving scheduling problems without time-windows. An experimental evaluation performed on medium-large size and web-available benchmark sets confirms the effectiveness of the proposed procedures. In particular, we have improved the average quality w.r.t. the current bests, while discovering three new optimal solutions, thus demonstrating the general efficacy of IFS.

This paper presents a generic solution to apply a mission described by a sequence of tasks on a robot while accounting for its physical constraints, without computing explicitly a reference trajectory. A naive solution to this problem would be to schedule the execution of the tasks sequentially, avoiding concurrency. This solution does not exploit fully the robot capabilities such as redundancy and have poor performance in terms of execution time or energy. Our contribution is to determine the time-optimal realization of the mission taking into account robotic constraints that may be as complex as collision avoidance. Our approach achieves more than a simple scheduling; its originality lies in maintaining the task approach in the formulated optimization of the task sequencing problem. This theory is exemplified through a complete experiment on the real HRP-2 robot.

The ability to automatically compose Web Services is critical for realising  more complex functionalities.  Several proposals to use automated planning to deal with the problem of service composition have been recently made. We present an approach, based on modelling the problem as a CSP (Constraint  Satisfaction Problem), that accommodates for the use of numeric variables, sensing and incomplete knowledge. We introduce a language for expressing extended goals, equipped with temporal constructs, maintainability properties, and an explicit distinction between sensing and achievement goals, in order to avoid undesirable situations.

Adaptive A* is an incremental version of A* that updates the h-values of the previous A* search to make them more informed and thus future A* searches more focused. In this paper, we show how the A* searches performed by Adaptive A* can reuse part of the path of the previous search and terminate before they expand a goal state, resulting in Path-Adaptive A*. We demonstrate experimentally that Path-Adaptive A* expands fewer states per search and runs faster than Adaptive A* when solving path-planning problems in initially unknown terrain.

The h m ( m = 1 ... ) family of admissible heuristics for STRIPS planning with additive costs generalise the h max heuristic, which results when m = 1. We show that the step from h 1 to h m can be made by changing the planning problem instead of the heuristic function. This furthers our understanding of the h m heuristic, and may inspire application of the same generalisation to admissible heuristics stronger than h max . As an example, we show how it applies to the additive variant of h m obtained via cost splitting.

The field of automated plan generation has recently significantly advanced. However, while several powerful domainindependent PbP has two variants: PbP.s focusing on speed, and planners have been developed, no one of these PbP.q focusing on plan quality. PbP.s entered the learning clearly outperforms all the others in every known benchmark track of the sixth international planning competition (IPC6), domain. It would then be useful to have a multi-planner system and was the overall winner of this competition track (Fern, that automatically selects and combines the most efficient Khardon and Tadepalli 2008). The paper includes some experimental planner(s) for each given domain.

The problem of formulating knowledge bases containing action schema is a central concern in knowledge engineering for AI Planning. This paper describes LOCM, a system which carries out the automated induction of action schema from sets of example plans.  Each plan is assumed to be a sound sequence of actions; each action in a plan is stated as a name and a list of objects that the action refers to. LOCM exploits the assumption that actions change the state of objects, and require objects to be in a certain state before they can be executed.  The novelty of LOCM is that it can induce action schema without being provided with any information about predicates or initial, goal or intermediate state descriptions for the example action sequences.  In this paper we describe the implemented LOCM algorithm, and analyse its performance by its application to the induction of domain models for several domains. To evaluate the algorithm, we used random action sequences from existing models of domains, as well as solutions to past IPC problems.

In this paper a planning framework based on Ant Colony Optimization techniques is presented. It is well known that finding optimal solutions to planning problems is a very hard computational problem. Stochastic methods do not guarantee either optimality or completeness, but it has been proved that in many applications they are able to find very good, often optimal, solutions. We propose several approaches based both on backward and forward search over the state space, using several heuristics and testing different pheromone models in order to solve sequential optimization planning problems.

Nowadays many urban areas have been equipped with networks of surveillance cameras, which can be used for automatic localization and tracking of people. However, given the large resource demands of imaging sensors in terms of bandwidth and computing power, processing the image streams of all cameras simultaneously might not be feasible. In this paper, we consider the problem of dynamical sensor selection based on user-defined objectives, such as maximizing coverage or improved localization uncertainty.  We propose a decision-theoretic approach modeled as a POMDP, which selects k sensors to consider in the next time frame, incorporating all observations made in the past. We show how, by changing the POMDP's reward function, we can change the system's behavior in a straightforward manner, fulfilling the user's chosen objective. We successfully apply our techniques to a network of 10 cameras.