Classically, scheduling research in artificial intelligence has concentrated on the combinatorial challenges arising in a large, static domain where the set of jobs, resource capacities, and other problem parameters are known with certainty and do not change. In contrast, queueing theory has focused primarily on the stochastic arrival and resource requirements of new jobs, de-emphasizing the combinatorics. We study a dynamic parallel scheduling problem with sequence-dependent setup times: arriving jobs must be assigned (online) to one of a set of resources. The jobs have different service times on different resources and there exist setup times that are required to elapse between jobs, depending on both the resource used and the job sequence. We investigate four models that hybridize a scheduling model with techniques from queueing theory to address the dynamic problem. We demonstrate that one of the hybrid models can significantly reduce observed mean flow time performance when compared to the pure scheduling and queueing theory methods. More specifically, at high system loads, our hybrid model achieves a 15% to 60% decrease in mean flow time compared to the pure methodologies. This paper illustrates the advantages of integrating techniques from queueing theory and scheduling to improve performance in dynamic problems with complex combinatorics.

In CPP, we are given a set of actions (assumed deterministic in this paper), a distribution over initial states, a goal condition, and a real value 0 < θ ≤1. We seek a plan π such that following its execution, the goal probability is at least θ. Motivated by the success of the translation-based approach for conformant planning, introduced by Palacios and Geffner, we suggest a new compilation scheme from CPP to classical planning. Our compilation scheme maps CPP into cost-bounded classical planning, where the cost-bound represents the maximum allowed probability of failure. Empirically, this technique shows mixed, but promising results, performing very well on some domains, and less so on others when compared to the state of the art PFF planner. It is also very flexible due to its generic nature, allowing us to experiment with diverse search strategies developed for classical planning. Our results show that compilation-based technique offer a new viable approach to CPP and, possibly, more general probabilistic planning problems.

Finding optimal schedules for the most commonly considered classes of scheduling problems is NP-complete. Best algorithms scale up to very large scheduling problems when optimality is not required and good solution quality suffices. These problems have perfect information in the sense that the resource availability, set of tasks, task duration, and other important facts, are fully known at the time of constructing a schedule. However, the assumption of perfect information is rarely satisfied, and real-world scheduling faces several forms of uncertainty, most notably with respect to durations and availability of resources. The effective handling of uncertainty is a major issue in applying scheduling in new areas. In this work, we investigate the properties of a number of classes of problems of contingent scheduling, in which assignments of resources to tasks depend on resource availability and other facts that are only known fully during execution, and hence the off-line construction of one fixed schedule is insufficient. We show that contingent scheduling in most general cases is most likely outside the complexity class NP, and resides, depending on the assumptions, in PSPACE, Sigma-p-2 or Pi-p-2. The results prove that standard constraint-satisfaction and SAT frameworks are in general not straightforwardly applicable to contingent scheduling.

The behavior composition problem involves the automatic synthesis of a controller able to “realize” (i.e., implement) a target behavior module by suitably coordinating a collection of partially controllable available behaviors. In this paper, we show that the existence of a composition solution amounts to finding a strong cyclic plan for a special non-deterministic planning problem, thus establishing the formal link between the two synthesis tasks. Importantly, our results support the use of non-deterministic planing systemsfor solving composition problems in an off-the-shelf manner. We then empirically evaluate three state-of-the-art synthesis systems (a domain-independent automated planner and two game solvers based on model checking techniques) on various non-trivial composition instances. Our experiments show that while behavior composition is EXPTIME-complete, the current technology is already able to handle instances of significant complexity. Our work is, as far as we know, the first serious experimental work on behavior composition.

Sequential decision-making under uncertainty often uses an approach in which a plan is built over a given horizon ahead using a deterministic model, the first decisions in this plan are applied, new information is acquired, the plan is adapted or rebuilt from scratch over a sliding horizon, and so on. This paper introduces a generic local search library that can be used in this context to quickly build and rebuild good quality plans. This library is built upon the notion of invariant used in constraint-based local search. Invariants allow temporal constraints, resource constraints, and criteria to be very quickly evaluated from a variable assignment and re-evaluated from a small change in this assignment. The paper also shows how the library can be used to reason on dynamic problem instances using a unique static problem model, without dynamic memory allocation. The approach is illustrated on a problem of data download under uncertainty about the volume of data, coming from the space domain.

In heuristic search and especially in optimal classical planning the computation of accurate heuristic values can take up the majority of runtime. In many cases, the heuristic computations for a search node and its successors are very similar, leading to significant duplication of effort. For example most landmarks of a node that are computed by the LM-cut algorithm are also landmarks for the node's successors. We propose to reuse these landmarks and incrementally compute new ones to speed up the LM-cut calculation. The speed advantage obtained by incremental computation is offset by higher memory usage. We investigate different search algorithms that reduce memory usage without sacrificing the faster computation, leading to a substantial increase in coverage for benchmark domains from the International Planning Competitions.

Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree. The Heuristic Search algorithm AO∗ finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs. We introduce a common framework, Trial-based Heuristic Tree Search, that subsumes these approaches and distinguishes them based on five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. Using this framework, we describe three new algorithms which mix these ingredients in novel ways in an attempt to combine their different strengths. Our evaluation shows that two of our algorithms not only provide superior theoretical properties to UCT, but also outperform state-of-the-art approaches experimentally.

Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

When planning problems have many kinds of resources or high concurrency, each optimal state has exponentially many minor variants, some of which are "better" than others. Standard methods like \Astar cannot effectively exploit these minor relative differences, and therefore must explore many redundant, clearly suboptimal plans. We describe a new optimal search algorithm for planning that leverages a partial order relation between states. Under suitable conditions, states that are dominated by other states with respect to this order can be pruned while provably maintaining optimality. We also describe a simple method for automatically discovering compatible partial orders in both serial and concurrent domains. In our experiments we find that more than 98% of search states can be pruned in some domains.

This paper addresses the flexible job shop scheduling problem with sequence-dependent setup times (SDSTFJSP). This is an extension of the classical job shop scheduling problem with many applications in real production environments. We propose an effective neighborhood structure for the problem, including feasibility and non improving conditions, as well as procedures for fast neighbor estimation. This neighborhood is embedded into a genetic algorithm hybridized with tabu search. We conducted an experimental study to compare the proposed algorithm with the state-of-the-art in the SDST-FJSP and also in the standard FJSP. In this study, our algorithm has obtained better results than those from other methods. Moreover, it has established new upper bounds for a number of instances.