We study a daily mine planning problem where, given a set of blocks we wishto mine, our task is to generate a mining sequence for the excavators suchthat blending resource constraints are met at various stages of thesequence. Such time-oriented resource constraintsare not traditionally handled well by automated planners. On the other hand,the remaining problem involves finding node-disjoint sequences withstate-dependent travel times on the arcs, which are highly challenging for a Mixed-Integer Program (MIP).In this paper, we address the problem of finding feasible sequences using a combined MIP and planning based decomposition approach. The MIP takes care of the resource constraints, and the planner solves the remaining sequence problem. We extend the notion of finding feasible sequences to finding good feasible sequences, by devising a heuristic objective function in the MIP, which improves the resulting search space for the planner.We empirically analyse the scalability of our approach on a benchmark data set, before demonstrating its effectiveness on a real world case study provided by our industry partner. These results demonstrate that by using a heuristic MIP, it is possible to obtain better makespan results with a suboptimal planner than by using an optimal planner with an uninformed MIP.

Uncertainty is commonly encountered in temporal scheduling and planning problems, and can often lead to over-constrained situations. Previous relaxation algorithms for over-constrained temporal problems only work with requirement constraints, whose outcomes can be controlled by the agents. When applied to uncontrollable durations, these algorithms may only satisfy a subset of the random outcomes and hence their relaxations may fail during execution. In this paper, we present a new relaxation algorithm, Conflict-Directed Relaxation with Uncertainty (CDRU), which generates relaxations that restore the controllability of conditional temporal problems with uncontrollable durations. CDRU extends the Best-first Conflict-Directed Relaxation (BCDR) algorithm to uncontrollable temporal problems. It generalizes the conflict-learning process to extract conflicts from strong and dynamic controllability checking algorithms, and resolves the conflicts by both relaxing constraints and tightening uncontrollable durations. Empirical test results on a range of trip scheduling problems show that CDRU is efficient in resolving large scale uncontrollable problems: computing strongly controllable relaxations takes the same order of magnitude in time compared to consistent relaxations that do not account for uncontrollable durations. While computing dynamically controllable relaxations takes two orders of magnitude more time, it provides significant improvements in solution quality when compared to strongly controllable relaxations.

Multiagent path planning is important in a variety of fields, ranging from games to robotics and warehouse management. Although centralized control in the joint action space can provide optimal plans, this often is computationally infeasi- ble. Decoupled planning is much more scalable. Traditional decoupled approaches perform a unit-centric decomposition, replacing a multi-agent search with a series of single-agent searches, one for each mobile unit. We introduce an orthogonal, significantly different approach, following a spatial distribution that partitions a map into high- contention, bottleneck areas and low-contention areas. Lo- cal agents called controllers are in charge with one local area each, routing mobile units in their corresponding area. Dis- tributing the knowledge across the map, each controller can observe only the state of its own area. Adjacent controllers can communicate to negotiate the transfer of mobile units. We evaluate our implemented algorithm, SDP, on real game maps with a mixture of larger areas and narrow, bottleneck gateways. The results demonstrate that spatially distributed planning can have substantial benefits in terms of makespan quality and computation speed.

Estimating the distance from a current partial-order plan to the goal state of the plan task is a challenging problem, with past research achieving only limited success. In an effort to understand the reasons for this situation, we investigate the computational complexity of the partial-order plan viability problem. We define several boundaries between the tractable and intractable subclasses of the problem, from which we identify several constraints that contribute to the computational intractability of the problem. These results bring new insights into the design and the development of future  partial-order planning heuristics.

In previous work we have shown that grounding, while used by most (if not all) modern state-of-the-art planners, is not necessary and is sometimes even undesirable. In this paper we extend this work and present a novel forward-chaining planner that does not require grounding and can solve problem instances that are too large for current planners to handle. We achieve this by exploiting equivalence relationships between objects whist constructing a lifted version of the relaxed planning graph (RPG) and extracting a relaxed plan. We compare our planner to FF and show that our approach consumes far less memory whist still being competitive. In addition we show that by not having to ground the domain we can solve much larger problem instances.

We present a novel approach to fully-observable nondeterministic planning (FOND) that attempts to bridge the gap between symbolic fix-point computation and recent approaches based on forward heuristic search. Concretely, we formalize the relationship between symbolic and dynamic programming nondeterministic planners, and then exploit such connection to propose a novel familyof planning algorithms that reasons over symbolic policies in a directed manner. By doing so, our proposal reasons over sets of states and executions in a succinct way (as done by symbolic planners) while biasing the reasoning with respect to the initial and goal states of the specific planning problem at hand (as done by heuristic planners). We show empirical results that prove this approach promising in settings where there is an intrinsic tension between plan efficiency and plan "robustness," a feature to be expected in nondeterministic domains.

We propose a new problem we refer to as goal recognitiondesign ( grd) , in which we take a domain theory and a set ofgoals and ask the following questions: to what extent do theactions performed by an agent within the model reveal its objective, and what is the best way to modify a model so thatany agent acting in the model reveals its objective as early aspossible. Our contribution is the introduction of a new measure we call worst case distinctiveness ( wcd ) with which weassess a  grd model. The  wcd represents the maximal lengthof a prefix of an optimal path an agent may take within a system before it becomes clear at which goal it is aiming. Tomodel and solve the  grd problem we choose to use the models and tools from the closely related field of automated planning. We present two methods for calculating the  wcd of a grd model, one of which is based on a novel compilation to aclassical planning problem. We then propose a way to reducethe  wcd of a model by limiting the set of available actions anagent can perform and provide a method for calculating theoptimal set of actions to be removed from the model. Our empirical evaluation shows the proposed solution to be effectivein computing and minimizing  wcd .

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete STRIPS domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We introduce two approximations, lower and upper bound, for plan robustness, and then utilize them to derive heuristics for synthesizing robust plans. Our planning system, PISA, incorporating stochastic local search with these novel techniques outperforms a state-of-the-art planner handling incomplete domains in most of the tested domains, both in terms of plan quality and planning time.

Linking online planning for MDPs with their special case of stochastic multi-armed bandit problems, we analyze three state-of-the-art Monte-Carlo tree search al-gorithms: UCT, BRUE, and MaxUCT. Using the outcome, we (i) introduce two new MCTS algorithms,MaxBRUE, which combines uniform sampling with Bellman backups, and MpaUCT, which combines UCB1with a novel backup procedure, (ii) analyze them formally and empirically, and (iii) show how MCTS algorithms can be further stratified by an exploration control mechanism that improves their empirical performance without harming the formal guarantees.

The Resource Constrained Project Scheduling Problem consists of finding start times for precedence-constrained activities which compete over renewable resources, with the goal to produce the shortest schedule. The method of Justification is a very popular post-processing schedule optimization technique which, although it is not clear exactly why, has been shown to work very well, even improving randomly generated schedules over those produced by advanced heuristics. In this paper, we set out to investigate why Justification works so well, and, with this understanding, to bypass the need for Justification by computing a priori the priorities Justification implicitly employs. We perform an exploratory study to investigate the effectiveness of Justification on a novel test set which varies the RCPSP phase-transition parameters across a larger range than existing test sets. We propose several hypotheses to explain the behavior of Justification, which we test by deriving from them several predictions, and a new priority rule. We show that this rule matches the priorities used by Justification more closely than existing rules, making it outperform the most successful priority rule heuristic.