This special issue on Planning and Scheduling (P&S) contains a selection of papers from the Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS’08) and the Workshop on Knowledge Engineering for Planning and Scheduling (KEPS’08), both organized during the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008), held in Sydney, Australia, during September 14–18, 2008. The selection results from the submission of extended versions of papers after the workshops and two reviewing cycles on such longer versions. The selected papers present novel advances in planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and knowledge engineering applications. On the whole, this issue focuses on managing complex problems for which 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. Furthermore, this issue includes a survey on constraint satisfaction, planning, scheduling and integration among these areas.
The different papers not only present recent progress in planning, scheduling, constraint satisfaction and search strategies and algorithms, but also describe particular applications of these techniques to real-life problems. While some authors extend ideas from traditional constraint programming to push forward the state of the art on planning, scheduling and temporal reasoning from a constraint satisfaction perspective, others mainly focus on the formulation of real-world problems as CSPs and present novel ways of facing 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, four research papers are presented preceded by a general survey.
1. The survey ‘New Trends on Constraint Satisfaction, Planning, and Scheduling: A Survey’ by R. Barták, M.A. Salido and F. Rossi introduces the audience to the area of constraint satisfaction, P&S from the artificial intelligence (AI) point of view. This survey helps the reader to better understand the rest of the papers of this special issue by introducing the main concepts involved in the technical papers. It gives the definitions of CSPs, models and techniques. It also defines the concepts of P&S from the AI point of view, as well as the inclusion of constraint satisfaction in planning and scheduling. Finally, the survey includes some open research issues.
2. The paper ‘Generation of Macro-operators via Investigation of Action Dependencies in Plans’ by L. Chrpa investigates a method for gathering macro-operators by analyzing training plans. This sort of analysis is based on the investigation of action dependencies in training plans. The knowledge gained by the proposed method can be passed directly to planning algorithms to improve their efficiency.
3. The paper ‘Validation and Verification Issues in a Timeline-Based Planning System’ by A. Cesta, A. Finzi, S. Fratini, A. Orlandini and E. Tronci aims to integrate validation and verification (V&V), and automated P&S techniques in a knowledge engineering environment. The paper analyzes the use of state-of-the-art V&V technology to support knowledge engineering in a timeline-based planning system called MrSPOCK. The paper presents the application domain for which the automated solver has been developed, introduces the timeline-based planning ideas and then describes the different possibilities to apply V&V to planning. Hence, it continues by describing the step of adding V&V functionalities around the specialized planner, MrSPOCK. New functionalities have been added to perform both model validation and plan verification. Lastly, a specific section describes the benefits as well as the performance of such functionalities.
4. The timeline-based approach is also the main topic of the paper ‘How to model planning and scheduling problems using constraint networks on timelines’ by G. Verfaillie, C. Pralet and M. Lemaître. The authors present the modelling power of Constraint Network on Timelines (CNT) and its ability to support various modelling styles, coming from the planning, scheduling and constraint programming communities. This is carried out by producing and comparing various models of two mission management problems in the aerospace domain: management of a team of unmanned air vehicles and of an Earth-observing satellite.
5. The paper ‘Efficient Variable Elimination for Semi-Structured Simple Temporal Networks with Continuous Domains’ by N. Yorke-Smith and H.H. Bui shows that for a Simple Temporal Network (STN), the pass of messages can be represented compactly as sub-STNs. The paper presents an efficient message-passing scheme for computing the minimal constraints of an STN. The analysis of this algorithm, Prop-STP, brings formal explanation of the performance of the existing STN solvers ΔSTP and SR-PC. Empirical results validate the efficiency of Prop-STP, demonstrating performance comparable to ΔSTP, in cases in which the constraint graph is known to have a small tree width, such as those that arise during Hierarchical Task Network (HTN) planning.
The editors of this special issue would like to thank all the authors for their interesting contributions and to the reviewers of the papers for their effort when providing valuable feedback to authors. Our special thanks go to Peter McBurney, co-editor of The Knowledge Engineering Review, for his support and help to make this special issue a reality.
