PlanSOpt

The field of AI planning shares many parallels with a diverse range of optimization areas, such as mathematical programming, constraint programming, and stochastic optimization. However, the potential integration of concepts and techniques used in these fields remains largely unexplored. For instance, one of the most popular strategies for solving planning problems is A* search, which is similar in many ways to a branch-and-bound strategy that is predominantly used to solve mixed-integer linear programming (MILP) problems. This opens the possibility of adapting several auxiliary methods to speed up search (including, e.g., merging, landmarks, and cutting planes algorithms) from one area to the other.

Invited Talk

J. Christopher Beck (University of Toronto)

The Phase Transition in Heuristic Search

Abstract:In the mid-1990s, it was observed, over many problem classes such as SAT and CSP, that the likelihood that a randomly generated problem instance has a solution transitions quickly from almost definitely one to almost definitely zero over a narrow range of a problem generation parameter. Furthermore, the observed computational difficulty peaks during this transition at a point where approximately half of the generated problems have a solution. This phenomenon has come to be known as the phase transition with the most popular example being seen in parameter of the clause-to-variable ratio of random SAT problems. Much empirical and theoretical work ensued with one result in the constraint programming community being an acknowledgement that numeric experiments should take into account the phase transition when generating suites of test problems for algorithm comparison.

While recent work in heuristic search has addressed problem difficulty for algorithms such as greedy best first search (GBFS), there has been very little work on whether the phase transition can be observed in heuristic search problems. In this work, we develop two problem generation models that admit a parameter that empirically leads to both the rapid transition between soluble and insoluble instances and the accompanying peak in search effort for GBFS. We show that the phase transition phenomenon has implications for work on problem difficulty in heuristic search including the comparison of heuristics, the impact of operator cost ratio, and the decision of whether to re-open nodes.

This is joint work with Eldan Cohen at the University of Toronto.

Bio: J. Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. Chris' MSc and PhD degrees both come from the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. His research interests include scheduling, constraint programming, hybrid optimization techniques, mixed integer programming, AI planning, reasoning under uncertainty, and queueing theory. He has published over 100 papers in international journals and conferences in these areas.

Chris has served as the the President of the Executive Council for the International Conference on Automated Planning and Scheduling and held editorial responsibilities at the Journal of Artificial Intelligence Research, Constraints, the Journal of Scheduling, and the Knowledge Engineering Review. He has been the program chair or co-chair of the International Conference on Automated Planning and Scheduling, the International Conference on the Integration of AI and OR Technology in Constraint Programming, and, in 2017, the International Conference on the Principles and Practice of Constraint Programming.

Topics and Objectives

In this workshop, we aim to explore the similarities and differences of AI and optimization, and ways that we can leverage the methodologies from one field to the other. An important part of this workshop is extending our knowledge of closely related fields, and positioning ourselves as a community to introduce researchers of these fields to AI planning concepts.

There have been some pioneering efforts at using optimization techniques for planning; notably in compilation approaches to MILP and/or constraint programming. We welcome submissions on these topics and more, including (but not limited to):

• formulating the heuristic generation and selection as an optimization problem;
• using MILP algorithms and techniques for efficient computation of heuristics in classical planning;
• hybridization of optimization techniques (e.g,. linear, mixed integer linear, constraint, nonlinear programming, and satisfiability modulo theory) to handle planning problems involving a combination of both logical and numeric constraints;
• integration of existing optimization techniques with planning to improve search performance.

The goal of this workshop is to provide a forum for researchers in AI planning, search, and optimization to investigate novel problems and solution approaches, as well as to discuss opportunities and challenges arising when applying optimization to planning and vice-versa. We encourage applications of optimization technology to planning/search problems, applications of traditional planning/search technology (e.g., variations of A* search) to optimization problems, and hybrid approaches that combine planning and optimization. This workshop is complementary to HSDIP, since the topic of heuristic search is highly relevant for the optimization community. However, PlanSOpt will focus more deeply on the language, ideas and methods from optimization fields. The workshop will therefore be more accessible to conference attendees from the general optimization community, and will provide an excellent entry into AI planning topics.

Tentative Schedule

Monday (June 19, 2017)

Deadlines and Dates

• Submission deadline: March 17th, 2017
• Notification: April 14th, 2017
• Camera-ready version: May 15th, 2017
• Workshop: June 19th, 2017

Workshop Organizers

• Andre A. Cire, University of Toronto, Canada
• Christina Burt, Zuse Institute Berlin, Germany
• Florian Pommerening, University of Basel, Switzerland
• Christian Muise, Massachusetts Institute of Technology, USA