Optional variables have for a long time been identified as a crucial component of state-of-the-art scheduling solvers. They not only offer a natural way to model many scheduling problems but also play an important role in the efficiency of such solvers by enabling a stronger inference in a constraint propagation engine. Despite this recognition, their adoption in modern solvers remains extremely scarce presumably because their native support requires pervasive changes to a solver and handling many subtleties that have not been extensively studied. In this paper, we aim to provide a good foundation in this direction by providing a formal characterization of optional variables and of their interactions with key components of a constraint programming solver including propagators, reification and lazy clause generation. In addition, we present a new lazy clause generation solver with native support for optional variables and demonstrate its efficiency on variants of the flexible jobshop problem.

Temporal planning is the problem of selecting and scheduling a set of actions in order to achieve a distant objective from an initial state. Constraint Programming (CP) has historically played an important role in many automated temporal planners based on the Plan-Space Planning (PSP) algorithm. In a nutshell, PSP would drive the search for a plan by selecting which actions to add and how to resolve conflicts, with an embedded CP engine in charge of ensuring the coherence of the plan. In this paper, we consider an existing encoding of temporal planning into constraint programming that adheres to a plan-space approach, but encodes the decision of the PSP algorithm as decision variables of the CSP, thus letting the CP engine entirely drive the search for a solution plan. Analyzing the encoding, we show that the induced search space contains many symmetries that would be absent from the original PSP algorithm. Another caveat of the encoding is that it allows for non-minimal solutions, i.e., solutions in which some actions may be removed without invalidating it. We propose to extend the encoding with additional symmetry breaking constraints to enforce canonicity of the considered plans. The encoding is further improved with additional constraints to limit the presence of non-minimal plans. We show the extended encoding to very substantially improve the performance of the original version and to be competitive with state-of-the-art state-space temporal planners on the considered benchmarks.

This paper presents the demonstrator developed in the TUPLES European Union research project for assisting human operators at Airbus to plan Beluga cargo ground logistic operations. The demonstrator features techniques providing robust, explainable, and safe decisions, which all contribute to making our decision-support system trusted by the operators. We have also worked on various planning methods to scale up to the size of the real industrial problem, including hybrid machine learning and symbolic algorithms. We demonstrate the software that was tested by Airbus operators during a user study in Finkenwerder’s production site in May 2025.

This paper deals with the problem of planning multiple agent movements through a mission area modeled as a graph. The agents undergo classic communication and temporal constraints, and the quantitative objective is the minimization of the team’s traversal makespan. Additional specificities make the problem a particularly complex routing one: on some nodes are associated durative and coordinated actions to perform, which can involve either the co-presence of several agents or time dependencies. Also, some agents are deployable and able to move on denser graphs: namely, aerial robots can take off and land on the ground vehicle at any planned position, and can fly above ground obstacles. We model the problem as a CSP and solve it with a network flow model. Results show the efficacy of the model and resolution scheme, which provides solutions with one or two orders of magnitude smaller time than a numerical temporal hierarchical planning model, with only a few percent loss of optimality.

Automated planning is a field of Artificial Intelligence interested in finding a set of actions that drives the evolution of the environment from an initial state to a desired goal state. Much of the work of the community has been on so-called domain-independent planning where a solver is expected to produce a plan from an abstract problem, specified in a common description language. This has led the community to produce a number of highly-efficient solvers that can be expected to work on a large variety of domains without any fine-tuning. Where most of the work has focused on sequential plans over purely symbolic states, we instead propose a constraint-based planner whose focus is on more expressive variants, namely numeric and temporal planning, essential in many practical applications. We extend an existing CP encoding of temporal planning with support for optimization and numeric states and leverage an existing lazy clause generation CP solver to find and optimize plans. Where the most successful automated planners rely on some form of forward-search, we show that constraint-programming can be just as effective in finding satisfiable solutions while substantially improving the quality of the produced plans.

Disjunctive scheduling problems such as the job shop and open shop are at the heart of many real world scheduling instances. In this paper, we frame such problems as disjunctive temporal networks associated with a makespan minimization objective. For those, we propose a hybrid approach between SAT/SMT and CP solvers. In particular, we keep from SMT solvers the aggregated constraint propagation in decision procedures as well as the explanations and clause learning mechanisms upon conflict. However, like all CP solvers, we maintain an explicit domain representation of integer variables, tightly integrated with clause learning. Automated search exploits explanations to derive activity-based heuristics combined with the more classical value-based heuristics of CP solvers. The resulting solver is shown to be competitive with state-of-the-art exhaustive search solvers on the classical benchmarks of job shop and open shop problems.

The formalism of Simple Temporal Networks (STNs) provides methods for evaluating the feasibility of temporal plans. The basic formalism deals with the consistency of quantitative temporal requirements on scheduled events. This implicitly assumes a single agent has full control over the timing of events. The extension of Simple Temporal Networks with Uncertainty (STNU) introduces uncertainty into the timing of some events. Two main approaches to the feasibility of STNUs involve (1) where a single schedule works irrespective of the duration outcomes, called Strong Controllability, and (2) whether a strategy exists to schedule future events based on the outcomes of past events, called Dynamic Controllability. Case (1) essentially assumes the timing of uncertain events cannot be observed by the agent while case (2) assumes full observability. The formalism of Partially Observable Simple Temporal Networks with Uncertainty (POSTNU) provides an intermediate stance between these two extremes, where a known subset of the uncertain events can be observed when they occur. A sound and complete polynomial algorithm to determining the Dynamic Controllability of POSTNUs has not previously been known; we present one in this paper. This answers an open problem that has been posed in the literature. The approach we take factors the problem into Strong Controllability micro-problems in an overall Dynamic Controllability macro-problem framework. It generalizes the notion of labeled distance graph from STNUs. The generalized labels are expressed as max/min expressions involving the observables. The paper introduces sound generalized reduction rules that act on the generalized labels. These incorporate tightenings based on observability that preserve dynamic viable strategies. It is shown that if the generalized reduction rules reach quiescence without exposing an inconsistency, then the POSTNU is Dynamically Controllable (DC). The paper also presents algorithms that apply the reduction rules in an organized way and reach quiescence in a polynomial number of steps if the POSTNU is Dynamically Controllable. Remarkably, the generalized perspective leads to a simpler and more uniform framework that applies also to the STNU special case. It helps illuminate the previous methods inasmuch as the max/min label representation is more semantically clear than the ad-hoc upper/lower case labels previously used.

Recent years have seen an important increase in the complexity of deployed robotic systems, both in terms of the number of robots involved, and scale of the tackled problems. The key challenge in this context is to allow the design of fleet control systems that, on the one hand, allow flexible and reactive operation of individual robots and, on the other hand, enable the system to optimize the global behavior of the fleet in order to increase its effectiveness and efficiency. To approach this problem, we propose to extend the Refinement Acting Engine (RAE) that has been used to program the behavior of autonomous agents through a hierarchical decomposition of high-level tasks into primitive commands, and is the subject of active research in order to guide its decisions with planning and scheduling techniques. The core of our proposal is to provide first-hand support for concurrency in the RAE procedure, allowing a natural representation for concurrent systems by reasoning on resource allocation. The resulting acting engine exploits a custom language that is designed to ease its integration with planning engines, both through its simple and orthogonal core constructs as well as in the explicit identification of decision points in the system operation. We provide an initial validation of the system in simulation on a logistic problem involving a fleet of robots.

In Human-Robot Interaction (HRI), ensuring nonambiguous communication between the robot and the human is a key point for carrying out fluently a collaborative task. With this work, we propose a method which allows the robot to generate the optimal set of assertions that are necessary in order to produce an unambiguous reference. In this paper, we present a novel approach to the Referring Expression Generation (REG) problem and its integration into a robotic system. Our method is a domain-independent approach based on an ontology as a knowledge base. We show how this generation can be performed on an ontology which is not dedicated to this task. We then validate our method through simulated situations, compare it with state of the art approach and on a real robotic system.

We present an approach to plan trajectories for a fleet of fixed-wing UAVs to observe a wildfire evolving over time. Realistic models of the terrain, of the fire propagation process, and of the UAVs are exploited, together with a model of the wind. The approach tailors a generic Variable Neighborhood Search method to these models and associated constraints. Simulation results show ability to plan observation trajectories for a small fleet of UAVs, and to update the plans when new information on the fire are incorporated in the fire model.

Reachability analysis is a crucial part of the heuristic computation for many state of the art classical and temporal planners. In this paper, we study the difficulty that arises in assessing the reachability of actions in planning problems containing sets of interdependent actions, notably including problems with required concurrency as well as hierarchical planning problems. We show the limitation of state-of-the-art techniques and propose a new method suitable for both temporal and hierarchical planning problems. Our proposal is evaluated on FAPE, a constraint-based temporal planner.A long version of this paper was presented at the HSDIP workshop [1].

This paper reports on FAPE (Flexible Acting and Planning Environment), a framework integrating acting and planning on the basis of the ANML modeling language. ANML is a recent proposal motivated by combining the expressiveness of the timeline representation with decomposition methods of Hierarchical Task Networks (HTN). Our current focus is not efficient temporal planning per se, but the tight integration of acting and planning. This integration is addressed by: (i) extending HTN methods with the refinement of planned actions with skills, expressed in PRS, to map actions into low-level commands, (ii) interleaving the planning process with acting, the former performs plan repair and replanning, while the latter implements the skill-based refinements, and (iii) executing commands with a dispatching mechanism that synchronizes observed time points of action effects and events with planned time. FAPE has been integrated to a PR2 robot and experimented in a home-like environment. The paper presents how planning is performed and integrated with acting and describes briefly the robotics experiments.

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks. We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.