International Conference on Automated Planning and Scheduling, held in Toronto, Ontario, For ICAPS 2010, we received 113 submissions Canada, May 12-16, 2010. The annual ICAPS from authors of 31 countries, representing all conference series was established in 2003 continents. From these submissions, 79 were through the merger of two preexisting biennial full papers, 29 were short ones, and 5 were position conferences, the International Conference on or challenge papers. These papers were all Artificial Intelligence Planning and Scheduling reviewed by a Program Committee made up of (AIPS) and the European Conference on Planning 76 members, coordinated by 10 Senior Members, (ECP). ICAPS continues the traditional and the four PC Chairs.

We describe a timeline-based scheduling algorithm developed for mission operations of the EO-1 earth observing satellite. We first describe the range of operational constraints for operations focusing on maneuver and thermal constraints that cannot be modeled in typical planner/schedulers. We then describe a greedy heuristic scheduling algorithm and compare its performance to both the prior scheduling algorithm - documenting an over 50% increase in scenes scheduled with estimated value of millions of dollars US. We also compare to a relaxed optimal scheduler showing that the greedy scheduler produces schedules with scene count within 15% of an upper bound on optimal schedules.

Over the last few years there has been a revival of interest in the idea of least-commitment planning with a number of researchers returning to the partial-order planning approaches of UCPOP and VHPOP. In this paper we explore the potential of a forward-chaining state-based search strategy to support partial-order planning in the solution of temporal-numeric problems. Our planner, POPF, is built on the foundations of grounded forward search, in combination with linear programming to handle continuous linear numeric change. To achieve a partial ordering we delay commitment to ordering decisions, timestamps and the values of numeric parameters, managing sets of constraints as actions are started and ended. In the context of a partially ordered collection of actions, constructing the linear program is complicated and we propose an efficient method for achieving this. Our late-commitment approach achieves flexibility, while benefiting from the informative search control of forward planning, and allows temporal and metric decisions to be made - as is most efficient - by the LP solver rather than by the discrete reasoning of the planner. We compare POPF with the approach of constructing a sequenced plan and then lifting a partial order from it, showing that our approach can offer improvements in terms of makespan, and time to find a solution, in several benchmark domains.

The objective of automated planners is to synthesize sequences of actions (called policies in MDP frameworks) that will achieve a predetermined goal given a fully or partially observable formal representation of the domain. In contrast, the main characteristic of project management is the greater emphasis on plan execution under uncertainty as opposed to plan synthesis. This paper explains the need to transition from automated plan synthesis to plan management and identifies the challenges for the planning and scheduling communities using examples of construction projects.

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

On the basis of an analysis of previous research, we present a generalized approach for measuring the difference of plans with an exemplary application to machine scheduling. Our work is motivated by the need for such measures, which are used in dynamic scheduling and planning situations. In this context, quantitative approaches are needed for the assessment of the robustness and stability of schedules. Obviously, any `robustness' or `stability' of plans has to be defined w. r. t. the particular situation and the requirements of the human decision maker. Besides the proposition of an instability measure, we therefore discuss possibilities of obtaining meaningful information from the decision maker for the implementation of the introduced approach.

This paper presents an approach to integrating planning and execution in time-sensitive environments. We present a simple setting in which to consider the issue, that we call continual on-line planning. New goals arrive stochastically during execution, the agent issues actions for execution one at a time, and the environment is otherwise deterministic. We take the objective to be a form of time-dependent partial satisfaction planning reminiscent of discounted MDPs: goals offer reward that decays over time, actions incur fixed costs, and the agent attempts to maximize net utility. We argue that this setting highlights the central challenge of time-aware planning while excluding the complexity of non-deterministic actions. Our approach to this problem is based on real-time heuristic search. We view the two central issues as the decision of which partial plans to elaborate during search and the decision of when to issue an action for execution. We propose an extension of Russell and Wefald's decision-theoretic A* algorithm that can cope with our inadmissible heuristic. Our algorithm, DTOCS, handles the complexities of the on-line setting by balancing deliberative planning and real-time response.

Sensor-to-symbol conversion lies at the heart of all embedded intelligent systems. The everyday world occupied by human stakeholders is dominated by objects that have symbolic labels. For an embedded intelligent system to operate in such a world it must also be able to segment its sensory stream into objects and label those objects appropriately. It is our position that development of a consistent and flexible sensor-to-symbol reasoning system (or architecture) is a key component of embedded intelligence.

Community health worker programs provide healthcare to those living outside the financial and physical reach of the standard health infrastructure. These programs are particularly prevalent in low resource regions. Frequently such programs involve community health workers making household visits across a significant geographical area. We suggest that this problem can be posed as a formal routing and scheduling problem, and to use techniques developed from solving the travelling salesman problem with time windows. In addition, household visits can generate a series of future follow up visits, a feature not often handled in the combinatorial scheduling and routing literature. We present the basic problem and outline potential research directions.

We study the problem of allocating stocks to dark pools. We propose and analyze an optimal approach for allocations, if continuous-valued allocations are allowed. We also propose a modification for the case when only integer-valued allocations are possible. We extend the previous work on this problem to adversarial scenarios, while also improving on their results in the iid setup. The resulting algorithms are efficient, and perform well in simulations under stochastic and adversarial inputs.