Dagstuhl Seminar 18071
Planning and Operations Research
( Feb 11 – Feb 16, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18071
Organizers
- J. Christopher Beck (University of Toronto, CA)
- Daniele Magazzeni (King's College London, GB)
- Gabriele Röger (Universität Basel, CH)
- Willem-Jan Van Hoeve (Carnegie Mellon University - Pittsburgh, US)
Contact
- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Impacts
- A Multi-Label A* Algorithm for Multi-Agent Pathfinding : article : ICAPS 2019 - Grenouilleau, Florian; Hoeve, Willem Jan van; Hooker, John N. - University, 2019. - 5 pp..
- Lagrangian Decomposition for Optimal Cost Partitioning - Pommerening, Florian; Röger, Gabriele; Helmert, Malte; Cambazard, Hadrien; Rousseau, Louis-Martin; Salvagnin, Domenico - Palo Alto : AAAI.org, 2019. - 10 pp..
- Non-Traditional Objective Functions for MDPs - Koenig, Sven; Muise, Christian; Sanner, Scott - University, 2019. - 8 pp..
Schedule
The aim of operations research is to make better decisions through the application of automated analytic methods. The aim of automated planning is to find a course of actions that transforms a given world situation into a desirable setting. Both areas have in common that they deal with complex systems where a huge space of interacting options makes it almost impossible to humans to take optimal or even good decisions./
From a historical perspective, operations research stems from the application of mathematical methods to (mostly) industrial applications while planning emerged as a subfield of artificial intelligence where the emphasis was traditionally more on symbolic and logical search techniques for the intelligent selection and sequencing of actions to achieve a set of goals. Therefore operations research often focuses on the allocation of scarce resources such as transportation capacity, machine availability, production materials, or money, while planning focuses on the right choice of actions from a large space of possibilities.
A fundamental difference in the traditional problems solved by the two areas is that in operations research the problems are, with some exceptions such as column generation, modeled with a finite (and fixed) set of variables whose values must be assigned in order to satisfy a set of constraints and optimize an objective function. In contrast, in planning, it is typically unknown how many actions are required to achieve a set of goals and so a problem is defined by a state transition system with operators that can be instantiated to create a trajectory through the state space. While this difference results in problems in different complexity classes, it is often possible to cast the same problem as operation research or planning problem. For example, logistics problems are typical applications in both fields.
However, real-world artificial intelligence planning problems often require complex temporal reasoning about the efficient use and transformation of limited resources. For example, a company such as Amazon must use and consume labor, warehouse space, vehicles, and fuel to coordinate the reception, storage, order-taking, packing, and delivery of goods. Operations research deals with the orchestration of known actions rather than deciding what actions to perform and how they need to be coordinated with respect to time and resources. The latter areas are the strength of AI planning. A particular challenge, therefore, is to solve problems that exhibit both the need to develop a plan and requirements that the plan optimizes the use of limited resources over time.
In this Dagstuhl Seminar we bring together researchers in the areas of Artificial Intelligence Planning and Operations Research, and their intersection. In the seminar we want to develop a joint understanding of the problems and solution techniques that are central to these areas and move toward an understanding of how they can be hybridized to better solve existing challenges. The aim of the seminar is to extend the reach of the technologies into currently out-of-reach problems and applications.
Creative Commons BY 3.0 DE
J. Christopher Beck, Daniele Magazzeni, Gabriele Röger, and Willem-Jan Van Hoeve
This seminar brought together leading experts in the fields of AI planning, constraint programming and operations research. These areas historically come from different roots but are all concerned with supporting decision making in complex systems which a huge space of interacting options. While the approach and focus is different, some concepts have been developed in multiple areas and some solution techniques are or could be transfered. There is also a growing intersection of the areas that considers hybrid problems or uses solvers developed in one area to solve problems from a different area, for example by compiling planning problems into MIP or by using CP for subproblems in a MIP solver. Solvers of a different community are often used as black boxes and the deeper understanding of each other's area of expertise that was developed in this seminar will help to foster collaboration and transfer knowledge between the areas.
The seminar started with eleven short but intense tutorials on Monday and Tuesday morning. The tutorials on Monday conveyed the basics of AI Planning, MIP, and CP. They also already introduced the main connections between the fields by talking about compilations from planning to CP and MIP and using LPs as heuristics in planning. The tutorials on Tuesday delved deeper into areas that became the focus of discussion later in the seminar, such as non-deterministic planning, Markov decision processes, and decision diagrams. Front-loading these tutorials worked well to bring everyone up to speed and created a good basis for the rest of the seminar.
The rest of the seminar was organized into working groups that included one to three short presentations followed by a longer discussion all focused on a central topic. Three of these sessions were organized as break-out sessions where the participants split into two groups, each discussion one topic and then reconvening to present the main points discussed in each group to each other. The schedule for each day was created on the evening before which kept the topics flexible and allowed the organizers to include topics that came up during the discussion. Notes on each of the working groups and abstracts of the tutorials are included in the rest of this report.
Florian Pommerening
- Roman Bartak (Charles University - Prague, CZ) [dblp]
- J. Christopher Beck (University of Toronto, CA) [dblp]
- Adi Botea (IBM Research - Dublin, IE) [dblp]
- Christina N. Burt (Satalia - London, GB) [dblp]
- Hadrien Cambazard (Grenoble INP, FR) [dblp]
- Michael Cashmore (King's College London, GB) [dblp]
- Alessandro Cimatti (Bruno Kessler Foundation - Trento, IT) [dblp]
- Mathijs de Weerdt (TU Delft, NL) [dblp]
- Jeremy D. Frank (NASA - Moffett Field, US) [dblp]
- Patrik Haslum (Australian National University, AU) [dblp]
- Emmanuel Hebrard (LAAS - Toulouse, FR) [dblp]
- Malte Helmert (Universität Basel, CH) [dblp]
- John N. Hooker (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Serdar Kadioglu (Fidelity Investments - Boston, US) [dblp]
- Michael Katz (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Thorsten Koch (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
- Sven Koenig (USC - Los Angeles, US) [dblp]
- Michele Lombardi (University of Bologna, IT) [dblp]
- Daniele Magazzeni (King's College London, GB) [dblp]
- Andrea Micheli (Bruno Kessler Foundation - Trento, IT) [dblp]
- Christian Muise (IBM TJ Watson Research Center - Cambridge, US) [dblp]
- Eva Onaindia (Technical University of Valencia, ES) [dblp]
- Gilles Pesant (Ècole Polytechnique - Montréal, CA) [dblp]
- Chiara Piacentini (University of Toronto, CA) [dblp]
- Nicola Policella (Solenix - Darmstadt, DE) [dblp]
- Florian Pommerening (Universität Basel, CH) [dblp]
- Mark Roberts (Naval Research - Washington, US) [dblp]
- Gabriele Röger (Universität Basel, CH) [dblp]
- Louis-Martin Rousseau (Polytechnique Montreal, CA) [dblp]
- Hana Rudová (Masaryk University - Brno, CZ) [dblp]
- Domenico Salvagnin (University of Padova, IT) [dblp]
- Scott Sanner (University of Toronto, CA) [dblp]
- Pierre Schaus (UC Louvain, BE) [dblp]
- Matthijs Spaan (TU Delft, NL) [dblp]
- Charlotte Truchet (University of Nantes, FR) [dblp]
- Willem-Jan Van Hoeve (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Parisa Zehtabi (King's College London, GB)
Classification
- artificial intelligence / robotics
- modelling / simulation
- optimization / scheduling
Keywords
- Artificial Intelligence
- Operations Research
- Automated Planning and Scheduling
- Real-World Applications
