6th Italian Workshop on Planning and Scheduling (IPS 2015)

In the last fifteen years, AI planning and scheduling techniques have been characterized by an impressive increase of their performances in terms of size of problems solved and complexity of the solutions produced. These improvements are related to the definition of new data structures which can efficiently encode and make explicit constraints that are only implicitly defined in problem formulation, and to the definition of heuristics that allow one to visit only the most promising parts of the search space. Interestingly, an increasing number of systems started to adopt planning and scheduling techniques in order to afford complex application contexts, and obtaining solutions that better fit the problem constraints and the users’ needs. This volume contains selected papers presented at IPS 2015, the 6th Italian Workshop on Planning and Scheduling held in Ferrara, Italy, September 22nd, 2015.¹ IPS 2015 was held within the 14th Conference of the Italian Association for Artificial Intelligence (AI*IA 2015), and gathered together researchers interested in different aspects of planning and scheduling, and introduced new researchers to the community. For this edition of IPS, the call for papers solicited submissions of two different types: full papers and short papers. Full technical papers reported work in progress or completed work, while short papers reported views or ambitions of the field, or described open problems. Twelve papers in various areas of Automated Planning & Scheduling were presented at the workshop: Algorithms, Applications, Architectures, Case-based Planning, Constraint-based Planning/Scheduling and Control Techniques, Evolution Algorithms, Formal Models, Heuristics, Knowledge engineering for planning, Landmarks, Learning, Memory Based Approaches, Monte Carlo Simulations, Multi-objective Functions, Social Continual Planning, Strategic Vehicle Routing, Web Services.

The best papers presented at the workshop were invited to submit a revised and extended version. After a further round review process, the following five papers were selected for this special issue.

A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling by Marco Baioletti, Alfredo Milani and Valentino Santucci, presents an evolutionary algorithm for solving a multi-objective permutation flow-shop scheduling problem (PFSP). In particular, the authors propose an extension of the algebraic discrete differential evolution scheme for the single-objective PFSP to multi-objective case, such that three objective functions (makespan, total flow time and total tardiness) are considered by analysing the three possible bi-objective combinations of them.

On the Use of Landmarks in Planner LPG by Francesco Benzi, Alfonso Gerevini, Alessandro Saetti and Ivan Serina, presents some new techniques for planning with landmarks that have been implemented in the LPG planning system. Landmarks are logical expressions consisting of facts that become true or actions that are executed in any solution plan. The experimental results show significant improvements in terms of both number of problems solved and CPU time. Moreover, the authors introduce and experimentally evaluate the concept of quasi-landmarks; these are facts that are likely to become true in every solution plan, or facts that must become true in a subset of the solution plans.

Automated Planning for Urban Traffic Control: Strategic Vehicle Routing to Respect Air Quality Limitations by Lukas Chrpa, Daniele Magazzeni, Keith Mccabe, Lee Mccluskey and Mauro Vallati, presents a planning-based approach to vehicle routing in urban areas, to control both traffic and air quality. In particular, the authors show the feasibility of using automated planning to perform vehicle routing where the goals are to minimise overall vehicle delay while utilising network capacity fully, and respecting air quality limits, taking into account a knowledge of vehicle types, vehicle emissions, route maps, and air quality zones. The approach has been evaluated on micro-simulation models that use real-world data supplied by an industrial partner. Results show the feasibility of using AI planning technology to deliver efficient routes for vehicles that avoid the breaking of air quality limits, and that balance traffic flow through the network.

Investigating Domain Independent Heuristics in a Timeline-Based Planner by Riccardo De Benedictis and Amedeo Cesta, presents the iLoC domain-independent planning system which is a timeline-based planner that allows to model both planning and scheduling problems according to a uniform schema. An experimental evaluation demonstrates the iLoC strength in solving temporally expressive problems and its improved ability to address the causal reasoning capability which is a dominant feature of classical planning. The authors show that iLoC has comparable (or even better) performance of other planners in those domains in which temporal reasoning constitutes the main reasoning requirements (i.e., temporally expressive domains).

Leveraging Constraint-based approaches for Multi-objective Flexible Flow-Shop Scheduling with Energy Costs by Angelo Oddi and Riccardo Rasconi, presents two approaches to solve the Energy-Flexible Flow Shop Scheduling (EnFFS) problem which is a multi-objective optimisation problem focused on the minimisation of both the overall completion time and the global energy consumption of the solutions. One approach is based on Constraint Programming and the other one is a meta-heuristic algorithm. The authors analyzed experimentally the techniques proposed considering an EnFFS benchmark recently proposed in the literature and a set of new challenging instances of increasing size.

We thank all members of the IPS Program Committee members and the additional reviewers recruited for the special issue reviews. The effort of all reviewers was fundamental for maintaining the high scientific level of the workshop. We thank the AI*IA council, who trusted us to organize IPS 2015, and all the researchers of the planning and scheduling community who supported this event by submitting their work and actively participating in it. Finally, we would like to express our gratitude to Fabrizio Riguzzi, Editor in Chief of Intelligenza Artificiale, for hosting this special issue.