The areas of Artificial Intelligence planning and scheduling have seen important advances thanks to the application of constraint satisfaction models and techniques. Especially, solutions to many real-world problems need to integrate plan synthesis capabilities with resource allocation, which can be efficiently managed by using constraint satisfaction techniques. Constraint satisfaction plays an important role in solving such real life problems, and integrated techniques that manage planning and scheduling with constraint satisfaction are particularly useful.

Most of the current top-performing planners are sequential planners that only handle total-order plans. Although this is a computationally efficient approach, the management of total-order plans restrict the choices of reasoning and thus the generation of flexible plans. In this paper, we present FLAP2, a forward-chaining planner that follows the principles of the classical POCL (Partial-Order Causal-Link Planning) paradigm. Working with partial-order plans allows FLAP2 to easily manage the parallelism of the plans, which brings several advantages: more flexible executions, shorter plan durations (makespan) and an easy adaptation to support new features like temporal or multi-agent planning. However, one of the limitations of POCL planners is that they require far more computational effort to deal with the interactions that arise among actions. FLAP2 minimizes this overhead by applying several techniques that improve its performance: the combination of different state-based heuristics and the use of parallel processes to diversify the search in different directions when a plateau is found. To evaluate the performance of FLAP2, we have made a comparison with four state-of-the-art planners: SGPlan, YAHSP2, Temporal Fast Downward and OPTIC. Experimental results show that FLAP2 presents a very acceptable trade-off between time and quality and a high coverage on the current planning benchmarks.

As planning problems become more complex, it is increasingly useful to integrate complex constraints on time and resources into planning models, and use constraint reasoning approaches to help solve the resulting problems. Dynamic constraint satisfaction is a key enabler of automated planning in the presence of such constraints. In this paper, we identify some limitations with the previously developed theories of dynamic constraint satisfaction. We identify a minimum set of elementary transformations from which all other transformations can be constructed. We propose a new classification of dynamic constraint satisfaction transformations based on a formal criteria, namely the change in the fraction of solutions. This criteria can be used to evaluate elementary transformations of a constraint satisfaction problem as well as sequences of transformations. We extend the notion of transformations to include constrained optimization problems. We discuss how this new framework can inform the evolution of planning models, automated planning algorithms, and mixed-initiative planning.

Logic-based Benders decomposition (LBBD) has improved the state of the art for solving a variety of planning and scheduling problems, in part by combining the complementary strengths of constraint programming and mixed integer programming (MIP). We undertake a computational analysis of specific factors that contribute to the success of LBBD, to provide guidance for future implementations. We study a problem class that assign tasks to multiple resources and poses a cumulative scheduling problem on each resource. We find that LBBD is at least 1000 times faster than state-of-the-art MIP on larger instances, despite recent advances in the latter. Further, we conclude that LBBD is most effective when the planning and scheduling aspects of the problem are roughly balanced in difficulty. The most effective device for improving LBBD is the inclusion of a subproblem relaxation in the master problem. The strengthening of Benders cuts also plays an important role when the master and subproblem complexity are properly balanced. These findings suggest future research directions.

RANTANPLAN is a numeric planning solver that takes advantage of recent advances in satisfiability modulo theories. It extends reduction to SAT approaches with an easy and efficient handling of numeric fluents using background theories. In this paper, we describe the design choices and features of RANTANPLAN, especially, how numeric reasoning is integrated in the system. We also provide experimental results showing that RANTANPLAN is competitive with existing exact numeric planners.

One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.

Many real life problems can be modeled as a scheduling problem. The main objective of these problems is to obtain optimal solutions in terms of processing time, cost and quality. Nowadays, energy-efficiency is also taken into consideration. However, these problems are NP-hard, so many search techniques are not able to obtain a solution in a reasonable time. In this paper, a genetic algorithm is developed to solve an extended version of the classical job-shop scheduling problem. In the extended version, each operation has to be executed by one machine and this machine can work at different speed rates. The machines consume different amounts of energy to process tasks at different rates. The evaluation section shows that a powerful commercial tools for solving scheduling problems was not able to solve large instances in a reasonable time, meanwhile our genetic algorithm was able to solve all instances with a good solution quality.

Unmanned Aerial Vehicles (UAV) represent a major advantage in defense, disaster relief and first responder applications. UAV may provide valuable information on the environment if their Command and Control (C2) is shared by different operators. In a C2 networking system, any operator may request and use the UAV to perform a remote sensing operation. These requests have to be scheduled in time and a consistent navigation plan must be defined for the UAV. Moreover, maximizing UAV utilization is a key challenge for user acceptance and operational efficiency. The global planning problem is constrained by the environment, targets to observe, user availability, mission duration and on-board resources. This problem follows previous research works on automatic mission Planning & Scheduling for defense applications. The paper presents a full constraint-based approach to simultaneously satisfy observation requests, and resolve navigation plans.

With the growing demand of freight transport by means of container vessels as well as the important competition among terminals, managers and stakeholders seek to improve the exploitation of the container terminal resources efficiently. In this context, arises the Berth Allocation Problem, which aims to allocate and schedule incoming vessels along the quay. Its appropriate solution plays a relevant role in enhancing the terminal productivity. Thus, for addressing this problem, we propose a cooperative search, where the individuals are organized into groups and each member shares information with its group partners. This grouping strategy allows to diversify as well as intensify the search in some regions by means of information shared among the individuals of each group. The computational experiments for this problem reveal that our approach reports high-quality solutions and identifies promising regions within the search space in short computational times.