Considering directed graphs on n vertices and m edges with real (possibly negative) weights, we present two new, efficient algorithms for computing all-pairs shortest paths (APSP). These algorithms make use of directed path consistency (DPC) along a vertex ordering d. The algorithms run in O(n 2 w d ) time, where w d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n 2 ) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. We show empirically that also in many general cases, both constructed and from realistic benchmarks, the algorithms often outperform Johnson's algorithm, which represents the current state of the art with a run time of O(nm + n 2 log n). These algorithms can be used for temporal and spatial reasoning, e.g. for the Simple Temporal Problem (STP), which underlines its relevance to the planning and scheduling community.

This paper brings together work in stochastic modelling, using the process algebra PEPA, and work in automated planning. Stochastic modelling has been concerned with verification of system performance metrics for some time: given a model of a system, determining whether it will meet a service-level agreement (SLA). For example, whether a given sequence of transitions on a network will complete within 5 seconds 80% of the time. The problem of deciding how to reconfigure the system most cost-effectively when the SLA cannot be met has not been widely explored: it is currently solved manually. Inspired by this, we consider how planning can be used to automate the configuration of service-oriented systems. Configuring these stochastic systems presents new challenges to planning: building plans that meet SLAs, but also have low cost. To this end, we present a domain-independent planner for planning problems with action costs and stochastic durations, and show how this can be used to solve both traditional planning domains, and within the framework of configuring a larger process algebra model.

Most predominant approaches in probabilistic planning utilize techniques from the more thoroughly investigated field of classical planning by determinizing the problem at hand. In this paper, we present a method to map probabilistic operators to an equivalent set of probabilistic operators in a novel normal form, requiring polynomial time and space. From this, we directly derive a determinization which can be used for, e.g., replanning strategies incorporating a classical planning system. Unlike previously described all outcome determinizations, the number of deterministic operators is not exponentially but polynomially bounded in the number of parallel probabilistic effects, enabling the use of more sophisticated determinization-based techniques in the future.

In this paper optimal state space planning is parallelized by exploiting the processing power of a graphics card. The two exploration steps, namely selecting the actions to be applied and generating the successors, are performed on a graphics processing unit. Duplicate detection, however, is delayed to be executed on the central processing unit. Multiple cores are employed to bypass main memory latency. To increase processing speed for exact duplicate detection, the hash tables are lock-free. Moreover, a bucket-based representation enhances the concurrent distribution of frontier states. The planner supports cost-first exploration and is able to deal with a considerable fraction of current PDDL, including numerical state variables, complex objective functions, and goal preferences. It can maximize the net-benefit. Experimental findings show visible performance gains especially for larger benchmark problems.

This paper presents a generalization of the coupled-task scheduling problem introduced by Shapiro, where considered tasks are subject to incompatibility constraint depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the border between P and NP-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of the complexity of scheduling problems with coupled-task given by Orman and Potts to our problem, determine new complexity results, and thus propose a new visualization including incompatibility constraint. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.

Applying learning techniques to acquire action models is an area of intense research interest. Most previous works in this area have assumed that there is a significant amount of training data available in a planning domain of interest, which we call target domain, where action models are to be learned. However, it is often difficult to acquire sufficient training data to ensure that the learned action models are of high quality. In this paper, we develop a novel approach to learning action models with limited training data in the target domain by transferring knowledge from related auxiliary or source domains. We assume that the action models in the source domains have already been created before, and seek to transfer as much of the the available information from the source domains as possible to help our learning task. We first exploit a Web searching method to bridge the target and source domains, such that transferrable knowledge from source domains is identified. We then encode the transferred knowledge together with the available data from the target domain as constraints in a maximum satisfiability problem, and solve these constraints using a weighted MAX-SAT solver. We finally transform the solutions thus obtained into high-quality target-domain action models. We empirically show that our transfer-learning based framework is effective in several domains, including the International Planning Competition (IPC) domains and some synthetic domains.

We consider an application of scheduling to hardware-accelerated functional verification, a massively-parallel computational paradigm used in the simulation of complex integrated circuits. Our domain requires the compilation of logical primitives into a set of instruction memories that optimize the concurrency and communication between tightly synchronized processing units. The scheduling process is burdened by a complex model in which all logical dependencies must be resolved by a dynamic network of routes that compete for sparsely distributed resources. We describe a series of optimization steps that cooperate to minimize simulation depth while scaling to problem sizes on the order of a billion gates. Our approach targets an industrial acceleration architecture containing 262,144 parallel processors.

The paper proposes a method that uses topological information to guide path planning in any 2D workspace. Our method builds a topological environment based on the workspace to compute homotopy classes, which topologically describe how paths go through the obstacles in the workspace. Then, the homotopy classes are sorted according to an heuristic estimation of their lower bound. Only those with smaller lower bound are used to guide a planner based on the Rapidly-exploring Random Tree (RRT), called Homotopic RRT (HRRT), to compute the path in the workspace. Simulated and real results with an Autonomous Underwater V ehicle (AUV) are presented showing the feasibility of the proposal. Comparison with well-known path planning algorithms has also been included.

The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work (Hoffmann 2005), it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) — the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains — we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish ``easy'' domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.

We address a scheduling problem in the context of military aircraft maintenance where the goal is to meet the aircraft requirements for a number of missions in the presence of breakdowns. The assignment of aircraft to a mission must consider the requirements for the mission, the probability of aircraft failure, and capacity of the repair shop that maintains the aircraft. Therefore, a solution both assigns aircraft to missions and schedules the repair shop to meet the assignments. We propose a dispatching heuristic algorithm; three complete approaches based on mixed integer programming, constraint programming, and logic-based Benders decomposition; and a hybrid heuristic-complete approach. Experiments demonstrate that the logic-based Benders variation combining mixed integer programming and constraint programming outperforms the other approaches, that the dispatching heuristic can feasibly schedule the repair shop in a very short time, and that using the dispatching solution as a bound marginally improves the complete approaches.