The Resource-Constrained Project Scheduling Problem (RCPSP) is a classical scheduling problem that has received significant attention due to of its numerous applications in industry. However, in practice, task durations are subject to uncertainty that must be considered in order to propose resilient scheduling. In this paper, we address the RCPSP variant with uncertain tasks duration (modeled using known probabilities) and aim to minimize the overall expected project duration. Our objective is to produce a baseline schedule that can be reused multiple times in an industrial setting regardless of the actual duration scenario. We leverage Graph Neural Networks in conjunction with Deep Reinforcement Learning (DRL) to develop an effective policy for task scheduling. This policy operates similarly to a priority dispatch rule and is paired with a Serial Schedule Generation Scheme to produce a schedule. Our empirical evaluation on standard benchmarks demonstrates the approach's superiority in terms of performance and its ability to generalize. The developed framework, Wheatley, is made publicly available online to facilitate further research and reproducibility.

In the context of tree-search stochastic planning algorithms where a generative model is available, we consider on-line planning algorithms building trees in order to recommend an action. We investigate the question of avoiding re-planning in subsequent decision steps by directly using sub-trees as action recommender. Firstly, we propose a method for open loop control via a new algorithm taking the decision of re-planning or not at each time step based on an analysis of the statistics of the sub-tree. Secondly, we show that the probability of selecting a suboptimal action at any depth of the tree can be upper bounded and converges towards zero. Moreover, this upper bound decays in a logarithmic way between subsequent depths. This leads to a distinction between node-wise optimality and state-wise optimality. Finally, we empirically demonstrate that our method achieves a compromise between loss of performance and computational gain.

Recent domain-determinization techniques have been very successful in many probabilistic planning problems. We claim that traditional heuristic MDP algorithms have been unsuccessful due mostly to the lack of efficient heuristics in structured domains. Previous attempts like mGPT used classical planning heuristics to an all-outcome determinization of MDPs without discount factor; yet, discounted optimization is required to solve problems with potential dead-ends. We propose a general extension of classical planning heuristics to goal-oriented discounted MDPs, in order to overcome this flaw. We apply our theoretical analysis to the well-known classical planning heuristics Hmax and Hadd, and prove that the extended Hmax is admissible. We plugged our extended heuristics to popular graph-based (Improved-LAO*, LRTDP, LDFS) and ADD-based (sLAO*, sRTDP) MDP algorithms: experimental evaluations highlight competitive results compared with the winners of previous competitions (FF-Replan, FPG, RFF), and show that our discounted heuristics solve more problems than non-discounted ones, with better criteria values. As for classical planning, the extended Hadd outperforms the extended Hmax on most problems.

Robotic missions require to implement various functionalities in order to link reactive functions at actuators and sensors level to deliberative functions like vision, supervision and planning at decisional level. All these functionalities must be versatile and generic enough to interact differently according to the missions while minimizing recoding effort. Moreover, deliberative functions like automated planning consume lots of memory and CPU time and usually complete in time incompatible with robotic missions' durations. Thus, we present a new generic and anytime planning concept for modular robotic architectures, which manages multiple planning requests at a time, solved in background, while allowing for reactive execution of planned actions at the same time. Different planners based on various formalisms and data structures can be plugged to the planning component without changing its behavior nor its code, facilitating reusability and validation of the component. We highlight the versatility of our concept on different use cases; then we demonstrate the efficiency of our approach in terms of mission duration and success, compared with traditional plan-then-execute approaches; we finally present a search and rescue mission by an autonomous rotorcraft solved with our paradigm, that cannot be tackled by traditional approaches.

Controller synthesis consists in automatically building controllers taking as inputs observation data and returning outputs guaranteeing that the controlled system satisfies some desired properties. In system specification, these properties may be safety properties specifying that some conditions must always hold. In planning, they express that the evolution of the controlled system must terminate in a goal state. In this paper, we propose a generic approach able to synthesize memoryless or finite-memory controllers for both safety-oriented and goal-oriented control problems. This approach relaxes some restrictive assumptions made by existing work on controller synthesis with non-determinism and partial observability and is shown to induce potentially significant gains. The proposed “Simulate and Branch” algorithm consists in exploring the possible evolutions of the controlled system and in adding new control elements when uncovered states are discovered. The approach developed is constraint-based in the sense that control problems are formulated using the flexibility of constraint programming languages and that our implementation uses the Gecode constraint programming library.

Spatial probabilistic temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L,U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database-we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.

Rackham is an interactive robot-guide that has been used in several places and exhibitions. This paper presents its design and reports on results that have been obtained after its deployment in a permanent exhibition. The project is conducted so as to incrementally enhance the robot functional and decisional capabilities based on the observation of the interaction between the public and the robot. Besides robustness and efficiency in the robot navigation abilities in a dynamic environment, our focus was to develop and test a methodology to integrate human-robot interaction abilities in a systematic way. We first present the robot and some of its key design issues. Then, we discuss a number of lessons that we have drawn from its use in interaction with the public and how that will serve to refine our design choices and to enhance robot efficiency and acceptability