PlanSOpt

Planning, Search and Optimization

An ICAPS 2018 Workshop
Delft, The Netherlands
June 25, 2018

AI planning problems are traditionally formulated using state-transition systems and solved using heuristic search. In optimization, problems consist of finding the values for variables that maximize an objective subject to mathematical constraints, and traditionally rely on sophisticated enumerative procedures such as branch and bound for mixed-integer linear programming. While similarities between AI planning and optimization are numerous, the two fields advanced almost independently and their interconnection remains largely unexplored. Renewed interest in the integration of optimization techniques into AI planning has recently emerged with the use of mathematical programming to automatically derive heuristics, but several other auxiliary methods from one area to the other can still be exploited to speed up search.

Invited Talk

Felipe Trevizan

Autonomous systems, such as driverless cars, unmanned explorer vehicles and smart appliances, need to handle unsafe environments, uncertain action outcomes and uncertain resource consumption while still being required to act within acceptable risk bounds. These planning under uncertainty problems are an integral part of AI planning; however, the collaboration between AI planning and OR has been limited mostly to deterministic unconstrained planning problems. This limited collaboration is due to the uncertain action outcomes and the resource constraints. The uncertainty in the outcomes of actions is a challenge for the current OR-based planning approaches because they can only reason about one single outcome of each action. Therefore, the other outcomes, including catastrophic failures, are ignored or underestimated. Constraints on resources with uncertain consumption pose another challenge: the solution for such constrained problems lies in the space of stationary stochastic policies which the current heuristic search methods are unable to handle.

In this talk, we present how to address both of these challenges by representing the planning problems as LPs over the occupation measure space. Formally, an occupation measure represents the expected number of times a given action is executed in a given state and the occupation measure space encodes the space of stationary stochastic policies. Occupation measures allow us to develop the first admissible heuristics for Stochastic Shortest Path Problems (SSPs) and Cost-Constrained SSPs that are able to account for the uncertainty in the outcomes of the actions and the resource constraints. Moreover, we show how to combine the occupation measure representation with column generation to obtain heuristic search algorithms capable of solving problems over the space of stationary stochastic policies.

Bio: Dr. Felipe Trevizan is an Assistant Professor in the Research School of Computer Science at the Australian National University (ANU). Previously, Felipe was a Senior Research Scientist at NICTA (now Data61/CSIRO). Felipe earned his Ph.D. (2013) and M.Sc. (2010) in Machine Learning from Carnegie Mellon University and his M.Sc. (2006) and B.Sc. (2004) in Computer Science from University of São Paulo.

Felipe's research interests lie at the intersection of Artificial Intelligence, Operations Research and Machine Learning including automated planning and scheduling, reasoning under uncertainty, heuristic search, and reinforcement learning. Along with colleagues and students, Felipe is the co-recipient of the 2016 Kikuchi-Karlaftis Best Paper Award of the Transport Research Board and the Best Paper Award in at the International Conference on Automated Planning and Scheduling (ICAPS) in 2016 and 2017.

Slides

Topics and Objectives

The aim of this workshop is to foster communication and collaboration between researchers in the fields of AI planning/scheduling, search, and optimization. Comparing complementary approaches to common problems and their solution, we aim to promote the exchange of methodologies among these disciplines. Submissions on the following topics are strongly encouraged (although others are considered):

• understanding and comparing AI and optimization modeling approaches and algorithms on problems to which both are applicable;
• reasoning with time and/or resources under complex objective functions (e.g., requiring multi-objective, bi-level, robust, or adversarial optimization or search) in the context of real-world application;
• applications of heuristic search to optimization problems, and conversely applications of optimization techniques to planning problems;
• hybridization of planning and optimization;
• novel mathematical programming formulations for efficient computation of heuristics in AI planning;
• exploitation of symmetries, inference and decomposition in heuristic search in particular comparisons of such approaches in constraint programming and mathematical programming.

Submissions

Submissions must be in AAAI format (see instructions in the Author Kit at http://www.aaai.org/Publications/Templates/AuthorKit18.zip) and no longer than 8 pages excluding references. Authors who would like to resubmit workshop papers rejected by the main conference should ensure that the comments from ICAPS reviewers have been properly addressed. Please do not submit papers that have been already accepted for the main conference track.

Submissions should be made through EasyChair at the following URL: https://easychair.org/conferences/?conf=plansopt18

Deadlines and Dates

• Submission deadline: March 23rd, 2018
• Notification: April 20th, 2018
• Camera-ready version: May 25th, 2018
• Workshop: June 25, 2018

Every submission will be reviewed by three members of the program committee according to the usual criteria such as relevance to the workshop, significance of the contribution, and technical quality. The review process will be single-blind: the authors' identity will be known to the reviewers, but not vice versa.

Papers submitted to other conferences are allowed as long as this does not interfere with both the workshop and the original conference rules. Submissions under double-blind review in another conference must be anonymous.

The workshop is meant to be an open and inclusive forum, and we encourage papers that report on work in progress or that do not fit the mold of a typical conference paper.

At least one author of each accepted paper must attend the workshop in order to present the paper. Authors must register for the ICAPS main conference in order to attend the workshop, since there will be no separate workshop-only registration.

Schedule