From this excellent collection of papers, three for presentation at ICAPS 2012, the were selected for special recognition. ICAPS continues Nguyen, Vien Tran, Tran Cao Son and Enrico the traditional high standards of AIPS and ECP Pontelli were selected for Best Student Paper as an archival forum for new research in the Award. In addition to the oral presentation of these e 45 papers included in this volume, consisting papers, the technical program of this year's of 37 long papers and 8 short papers, are ICAPS conference includes invited talks by those selected for plenary presentation at three distinguished speakers: Robert O. Ambrose ICAPS 2012 from a total of 132 submissions. Topics under various constraints and assumptions, included real-time planning, planning in mixed to empirical evaluation of planning and discrete-continuous domains, planning for systems scheduling techniques in practical applications. Papers in the subareas of optimal planning, probabilistic were encouraged from a range of neighboring and non-deterministic planning, planning disciplines, including model-based and scheduling for transportation, robot path reasoning, hybrid systems, run-time verification, planning, and new developments in heuristics control and robotics.

The control of dynamic systems, which aims to minimize the deviation of state variables from reference values in a continuous state space, is a central domain of cybernetics and control theory. The objective of action planning is to find feasible state trajectories in a discrete state space from an initial state to a state satisfying the goal conditions, which in principle addresses the same issue on a more abstract level. We combine these approaches to switch between dynamic system characteristics on the fly, and to generate control input sequences that affect both discrete and continuous state variables. Our approach (called Domain Predictive Control) is applicable to hybrid systems with linear dynamics and discretizable inputs.

This paper aims at incorporating tactical aspects of oil pipeline networks to the supply chain planning model. The strategic design of supply chains is covered in literature by well understood and recurring patterns such as multi-commodity networks, dynamic parameters over time, capacity on facilities, transportation capacity or facilities with demand, production and inventory. We consider the following characteristics: capacity for in-transit inventory, transit time and flow reversal. Our objective is a better estimate for resources required by the network and therewith allow a more precise optimization of their use. All aspects are modeled to be efficiently solved by linear programming algorithms.

Portfolio planners and parameter tuning are two ideas that have recently attracted significant attention in the domain-independent planning community. We combine these two ideas and present a portfolio planner that runs automatically configured planners. We let the automatic parameter tuning framework ParamILS find fast configurations of the Fast Downward planning system for a number of planning domains. Afterwards we learn a portfolio of those planner configurations. Evaluation of our portfolio planner on the IPC 2011 domains shows that it has a significantly higher IPC score than the winner of the sequential satisficing track.

We consider the problem of on-line continual planning, in whichadditional goals may arrive while plans for previous goals are stillexecuting and plan quality depends on how quickly goals are achieved.This is a challenging problem even in domains with deterministicactions. One common and straightforward approach is reactive planning,in which plans are synthesized when a new goal arrives. In this paper,we adapt the technique of hindsight optimization from on-line schedulingand probabilistic planning to create an anticipatory on-line planningalgorithm. Using an estimate of the goal arrival distribution, wesample possible futures and use a deterministic planner to estimate thevalue of taking possible actions at each time step. Results in twobenchmark domains based on unmanned aerial vehicle planning andmanufacturing suggest that an anticipatory approach yields a superiorplanner that is sensitive not only to which action should be executed,but when.

Real-time optimization of the dynamic flow of vehicle traffic through a network of signalized intersections is an important practical problem. In this paper, we take a decentralized, schedule-driven coordination approach to address the challenge of achieving scalable network-wide optimization. To be locally effective, each intersection is controlled independently by an on-line scheduling agent. At each decision point, an agent constructs a schedule that optimizes movement of the observable traffic through the intersection, and uses this schedule to determine the best control action to take over the current look-ahead horizon. Decentralized coordination mechanisms, limited to interaction among direct neighbors to ensure scalability, are then layered on top of these asynchronously operating scheduling agents to promote overall performance. As a basic protocol, each agent queries for newly planned output flows from its upstream neighbors to obtain an optimistic projection of future demand. This projection may incorporate non-local influence from indirect neighbors depending on horizon length. Two additional mechanisms are then introduced to dampen ``nervousness'' and dynamic instability in the network, by adjusting locally determined schedules to better align with those of neighbors. We present simulation results on two traffic networks of tightly-coupled intersections that demonstrate the ability of our approach to establish traffic flows with lower average vehicle wait times than both a simple isolated control strategy and other contemporary coordinated control strategies that use moving average forecast or traditional offset calculation.

The Liner Shipping Fleet Repositioning Problem (LSFRP) poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between services in a liner shipping network. The LSFRP is characterized by chains of interacting activities, many of which have costs that are a function of their duration; for example, sailing slowly between two ports is cheaper than sailing quickly. Despite its great industrial importance, the LSFRP has received little attention in the literature. We show how the LSFRP can be solved sub-optimally using the planner POPF and optimally with a mixed-integer program (MIP) and a novel method called Temporal Optimization Planning (TOP). We evaluate the performance of each of these techniques on a dataset of real-world instances from our industrial collaborator, and show that automated planning scales to the size of problems faced by industry.

Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for moving-target search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.

This paper provides an analysis of the efficacy of a known iterative improvement meta-heuristic approach from the AI area in solving the Blocking Job Shop Scheduling Problem (BJSSP) class of problems. The BJSSP is known to have significant fallouts on practical domains, and differs from the classical Job Shop Scheduling Problem (JSSP) in that it assumes that there are no intermediate buffers for storing a job as it moves from one machine to another; according to the BJSSP definition, each job has to wait on a machine until it can be processed on the next machine. In our analysis, two specific variants of the iterative improvement meta-heuristic are evaluated: (1) an adaptation of an existing scheduling algorithm based on the Iterative Flattening Search and (2) an off-the-shelf optimization tool, the IBM ILOG CP Optimizer, which implements Self-Adapting Large Neighborhood Search. Both are applied to a reference benchmark problem set and comparative performance results are presented. The results confirm the effectiveness of the iterative improvement approach in solving the BJSSP; both variants perform well individually and together succeed in improving the entire set of benchmark instances.

There has been much interest recently in problems that com-bine high-level task planning with low-level motion planning.In this paper, we present a problem of this kind that arises inmulti-vehicle mission planning. It tightly integrates task al-location and scheduling, who will do what when, with pathplanning, how each task will actually be performed. It ex-tends classical vehicle routing in that the cost of executing aset of high-level tasks can vary significantly in time and costaccording to the low-level paths selected. It extends classi-cal motion planning in that each path must minimize costwhile also respecting temporal constraints, including thoseimposed by the agent’s other tasks and the tasks assigned toother agents. Furthermore, the problem is a subtask withinan interactive system and therefore must operate within se-vere time constraints. We present an approach to the problembased on a combination of tabu search, linear programming,and heuristic search. We evaluate our planner on represen-tative problem instances and find that its performance meetsthe demanding requirements of our application. These resultsdemonstrate how integrating multiple diverse techniques cansuccessfully solve challenging real-world planning problemsthat are beyond the reach of any single method.