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 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.