This paper is concerned with local search methods to solve job shop scheduling problems with uncertain durations modelled as fuzzy numbers. Based on a neighbourhood structure from the literature, a reduced set of moves and the consequent structure are defined. Theoretical results show that the proposed neighbourhood contains all the improving solutions from the original neighbourhood and provide a sufficient condition for optimality. Additionally, a makespan lower bound is proposed which can be used to discard neighbours. Experimental results illustrate the good performance of both proposals, which considerably reduce the computational load of the local search, as well as a synergy effect when they are simultaneously used.

In order to scale with modern processors, planning algorithms must become multi-threaded. In this paper, we present parallel shared-memory algorithms for two problems that underlie many planning systems: suboptimal and anytime heuristic search. We extend a recently-proposed approach for parallel optimal search to the suboptimal case, providing two new pruning rules for bounded suboptimal search. We also show how this new approach can be used for parallel anytime search. Using temporal logic, we prove the correctness of our framework, and in an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that it yields faster search performance than previous proposals.

Model-based planning often presumes a static system model, while in a practice physical system may evolve or drift over time. This paper proposes the idea of pervasive model adaptation in a production system, where the model is dynamically updated using observation of production output. The core idea is the interplay between model adaptation and production planning. We seek plans which simultaneously serve the goals of achieving high productivity for production, and information gathering for model adaptation. We use a modular printing example to illustrate issues such as formulation of the information criterion and search strategy for informative plans. The idea of pervasive adaptation can be further extended to improve long term productivity in production systems.

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.

In this paper we extend dynamic controllability of temporally-flexible plans to temporally-flexible reactive programs.  We consider three reactive programming language constructs whose behavior depends on runtime observations; conditional execution, iteration, and exception handling. Temporally-flexible reactive programs are distinguished from temporally-flexible plans in that program execution is conditioned on the runtime state of the world.  In addition, exceptions are thrown and caught at runtime in response to violated timing constraints, and handled exceptions are considered successful program executions.  Dynamic controllability corresponds to a guarantee that a program will execute to completion, despite runtime constraint violations and uncertainty in runtime state.  An algorithm is developed which frames the dynamic controllability problem as an AND/OR search tree over possible program executions.  A key advantage of this approach is the ability to enumerate only a subset of possible program executions that guarantees dynamic controllability, framed as an AND/OR solution subtree.

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.

We consider real-time planning problems in which some states are unsolvable, i.e., have no path to a goal. Such problems are difficult for real-time planning algorithms such as RTA* in which all states must be solvable. We identify a property called k-safeness, in which the consequences of a bad choice become apparent within k moves after the choice is made. When k is not too large, this makes it possible to identify unsolvable states in real time. We provide a modified version of RTA* that is provably complete on all k -safe problems. We derive k -safeness conditions for real-time deterministic versions of the well-known Tireworld and Racetrack domains, and provide experimental results showing that our modified version of RTA* works quite well in these domains.

PDDL 2.1 supports modelling of complex temporal planning domains in which solutions must exploit concurrency. Few existing temporal planners can solve problems that require concurrency and those that do typically pay a performance price to deploy reasoning machinery that is not always required. In this paper we show how to improve the performance of forward-search planners that attempt to solve the full temporal planning problem, both by narrowing the use of the concurrency machinery to situations that demand it and also by improving the power of inference to prune redundant branches of the search space for common patterns of interaction in temporal domains that do require concurrency. Results illustrate the effectiveness of our ideas in improving the efficiency of a temporal planner that can solve problems with required concurrency, both in domains that exploit this ability and in those that do not.

This paper presents a generic anytime forward-search constraint-based algorithm for solving planning problems expressed in the CNT framework (Constraint Network on Timelines). It is generic because it allows many kinds of search to be covered, from complete tree search to greedy search. It is anytime because some parameter settings, together with domain-specific knowledge, allow high quality plans to be produced very quickly and to be further improved. It is forward because it systematically considers the decisions to be made in a chronological order. It is finally constraint-based because it is built on top of the CNT framework which is an extension of the CSP framework able to model discrete event dynamic systems and because it is implemented on top of the Choco constraint programming tool from which it inherits all the constraint handling machinery. Experimental comparisons are made in terms of quality profile with other domain-dependent and domain-independent planners.

Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems.  We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters.  In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state.  We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner.  The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners.  We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales  well for a single, shared-memory multicore machine.