1 Introduction

This special issue on Constraint Satisfaction for Planning and Scheduling contains a selection of papers from two Workshops on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS’14 and COPLAS’15), organized during the International Conferences on Automated Planning and Scheduling (ICAPS 2014–2015), held in Portsmouth, USA and Jerusalem, Israel, respectively. The selection results from submission of revised versions of the best papers from both workshop editions. The selected papers present novel advances in planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and applications to real life problems. On the whole, this issue focusses on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, and shows the enormous potential of such techniques for both practical applications and future research.

The different papers represent recent progress in planning, scheduling, constraint satisfaction and heuristic and metaheuristic search strategies, and also describe particular applications of these techniques to real life problems. While some authors extend ideas from constraint programming to push forward the state of the art on planning and scheduling from a constraint satisfaction perspective, others mainly focus on the formulation of real-world problems as CSPs and present novel ways to face them. In both cases, they combine ideas from various disciplines of computer science and address several appealing lines of research within the constraint satisfaction field. In total, seven research papers are presented.

1. 1. The paper ‘Parallel heuristic search in forward partial-order planning’ by O. Sapena, E. Onainda, A. Torreo investigates a forward-chaining planner (FLAP2) that follows the principles of the classical POCL (Partial-Order Causal-Link Planning) paradigm. It easily manages the parallelism of plans to take several advantages: more flexible executions, shorter plan durations (makespan), and an easy adaptation to support new features like temporal and multi-agent planning.

2. 2. The paper ‘Revisiting dynamic constraint satisfaction for model-based planning’ by J. Frank aims to identify a new classification of dynamic constraint satisfaction transformations based on formal criteria, namely the change in the fraction of solutions. These criteria can be used to evaluate elementary transformations of a CSP as well as sequences of transformations. He extends the notion of transformations to include constrained optimization problems.

3. 3. The paper ‘Logic-based benders decomposition for planning and scheduling: a computational analysis’ by A. A. Ciré, E. Çoban and J. N. Hooker undertakes a computational analysis of specific factors that contribute to the success of Logic-Based Benders Decomposition (LBBD), to provide guidance for future implementations. The results show that LBBD is most effective when the planning and scheduling aspects of the problem are roughly balanced in difficulty. Furthermore, new interesting properties have also been identified.

4. 4. The paper ‘The Rantanplan planner: system description’ by M. Bofill, J. Espasa and M. Villaret describes the design choices and features of Rantanplan, a numeric planning solver that takes advantage of recent advances in SMT. The paper also provides experimental results showing that Rantanplan is competitive with existing exact numeric planners.

5. 5. The paper ‘Comparing planning problem compilation approaches for quantum annealing’ by B. O’Gorman, E. G. Rieffel, M. Do, D. Venturelli and J. Frank introduces the planning community to the key steps in compiling planning problems to quantum annealing hardware. To this end, two approaches are described to mapping general planning problems to Quadratic Unconstrained Binary Optimization (QUBO) and preliminary results are described from running an early quantum annealer on a parametrized family of hard planning problems.

6. 6. The paper ‘A metaheuristic technique for energy-efficiency in job-shop scheduling’ by J. Escamilla, M. A. Salido, A. Giret and F. Barber proposes a genetic algorithm to solve an extended version of the Job-shop Scheduling Problem in which machines can consume different amounts of energy to process tasks at different rates.

7. 7. The paper ‘A Constraint-based Approach for Planning UAV Activities’ by C. Guettier, F. Lucas presents a full constraint-based approach to simultaneously satisfy observation requests, and resolve navigation plans of Unmanned Aerial Vehicles which can communicate with the network to transmit remote videos to manned vehicles on the ground.

8. 8. The paper ‘Cooperative Search for Berth Scheduling’ by E. Lalla-Ruiz, B. Melián-Batista and J. M. Moreno-Vega proposes a cooperative search termed as Decentralized Cooperative Metaheuristic (DCM) to solve the Dynamic Berth Allocation Problem (DBAP), 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.