In fact, DARPA, which funded the project, ways. Elves) (Scerri, Pynadath, and Tambe 2002; Finally, we will present some lessons Pynadath and Tambe 2003) and required learned and recent research that was motivated detailed information about the calendars by our experiences in deploying the of people using the system. Thus, we decided to deploy a new application of the Electric The Travel Elves introduced two major Elves, called the Travel Elves. This application advantages over traditional approaches to appeared to be ideal for wider deployment travel planning. First, the Travel Elves provided since it could be hosted entirely outside an interactive approach to making an organization and communication travel plans in which all of the data could be performed over wireless devices, required to make informed choices is such as cellular telephones. For example, when The mission of the Travel Elves (Ambite deciding whether to park at the airport or et al. 2002, Knoblock 2004) was to facilitate take a taxi, the system compares the cost planning a trip and to ensure that the of parking and the cost of a taxi given other resulting travel plan would execute selections, such as the airport, the specific smoothly. Initial deployment of the Travel parking lot, and the starting location Elves at DARPA went smoothly.

Technically the underlying optimization development of online commerce forced problem is either NP or P-space businesses to question the week-plus supply-chain complete (depending on the details of the planning cycles that had been domain). Furthermore, the problem mixes the norm. Finally, the year 2000 (Y2K) a dozen or so classic optimization problems problem caused an across-the-board from AI and operations research (OR), replacement of enterprise software, allowing and much of the expected savings from many businesses to update their global supply-chain optimization are lost if approach to supply-chain planning. The end result of all of these factors was This article describes our experience a huge upswing in demand for supplychain from four years of solving supply-chain planning tools from i2 Technologies planning and optimization problems and other vendors. When I joined i2 in across industries, and some of the lessons 1996 as optimization architect, the company we learned.

We study the complexity of cost-optimal classical planning over propositional state variables and unary-effect actions. We discover novel problem fragments for which such optimization is tractable, and identify certain conditions that differentiate between tractable and intractable problems. These results are based on exploiting both structural and syntactic characteristics of planning problems. Specifically, following Brafman and Domshlak (2003), we relate the complexity of planning and the topology of the causal graph. The main results correspond to tractability of cost-optimal planning for propositional problems with polytree causal graphs that either have O(1)-bounded in-degree, or are induced by actions having at most one prevail condition each. Almost all our tractability results are based on a constructive proof technique that connects between certain tools from planning and tractable constraint optimization, and we believe this technique is of interest on its own due to a clear evidence for its robustness.

Scheduling problems are generally NP-hard combinatorial problems, and a lot of research has been done to solve these problems heuristically. However, most of the previous approaches are problem-specific and research into the development of a general scheduling algorithm is still in its infancy. Mimicking the natural evolutionary process of the survival of the fittest, Genetic Algorithms (GAs) have attracted much attention in solving difficult scheduling problems in recent years. Some obstacles exist when using GAs: there is no canonical mechanism to deal with constraints, which are commonly met in most real-world scheduling problems, and small changes to a solution are difficult. To overcome both difficulties, indirect approaches have been presented (in [1] and [2]) for nurse scheduling and driver scheduling, where GAs are used by mapping the solution space, and separate decoding routines then build solutions to the original problem.

Multi-robot path planning is difficult due to the combinatorial explosion of the search space with every new robot added. Complete search of the combined state-space soon becomes intractable. In this paper we present a novel form of abstraction that allows us to plan much more efficiently. The key to this abstraction is the partitioning of the map into subgraphs of known structure with entry and exit restrictions which we can represent compactly. Planning then becomes a search in the much smaller space of subgraph configurations. Once an abstract plan is found, it can be quickly resolved into a correct (but possibly sub-optimal) concrete plan without the need for further search. We prove that this technique is sound and complete and demonstrate its practical effectiveness on a real map. A contending solution, prioritised planning, is also evaluated and shown to have similar performance albeit at the cost of completeness. The two approaches are not necessarily conflicting; we demonstrate how they can be combined into a single algorithm which outperforms either approach alone.

First, we describe a polynomial-time algorithm that uses macros to generate plans for the class 3S of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may be tractable even when a planning problem has an exponentially long minimal solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.

We represent planning as a set of loosely coupled network flow problems, where each network corresponds to one of the state variables in the planning domain. The network nodes correspond to the state variable values and the network arcs correspond to the value transitions. The planning problem is to find a path (a sequence of actions) in each network such that, when merged, they constitute a feasible plan. In this paper we present a number of integer programming formulations that model these loosely coupled networks with varying degrees of flexibility. Since merging may introduce exponentially many ordering constraints we implement a so-called branch-and-cut algorithm, in which these constraints are dynamically generated and added to the formulation when needed. Our results are very promising, they improve upon previous planning as integer programming approaches and lay the foundation for integer programming approaches for cost optimal planning.

Probabilistic planning problems are typically modeled as a Markov Decision Process (MDP). MDPs, while an otherwise expressive model, allow only for sequential, non-durative actions. This poses severe restrictions in modeling and solving a real world planning problem. We extend the MDP model to incorporate -- 1) simultaneous action execution, 2) durative actions, and 3) stochastic durations. We develop several algorithms to combat the computational explosion introduced by these features. The key theoretical ideas used in building these algorithms are -- modeling a complex problem as an MDP in extended state/action space, pruning of irrelevant actions, sampling of relevant actions, using informed heuristics to guide the search, hybridizing different planners to achieve benefits of both, approximating the problem and replanning. Our empirical evaluation illuminates the different merits in using various algorithms, viz., optimality, empirical closeness to optimality, theoretical error bounds, and speed.

This article provides an overview of the nature and role of autonomy for space exploration, with a bias in focus towards describing the relevance of AI technologies. It explores the range of autonomous behavior that is relevant and useful in space exploration and illustrates the range of possible behaviors by presenting four case studies in space-exploration systems, each differing from the others in the degree of autonomy exemplified. Three core requirements are defined for autonomous space systems, and the architectures for integrating capabilities into an autonomous system are described. The article concludes with a discussion of the challenges that are faced currently in developing and deploying autonomy technologies for space.

Automated planning technology has become mature enough to be useful in applications that range from game-playing to control of space vehicles. In this article, Dana Nau discusses where automated-planning research has been, where it is likely to go, where he thinks it should go, and some major challenges in getting there. The article is an updated version of Nau's invited talk at AAAI-05 in Pittsburgh, Pennsylvania.