Adapting plans to changes in the environment by finding alternatives and taking advantage of opportunities is a common human behavior. The need for such behavior is often rooted in the uncertainty produced by our incomplete knowledge of the environment. While several existing planning approaches deal with such issues, artificial agents still lack the robustness that humans display in accomplishing their tasks. In this work, we address this brittleness by combining Hierarchical Task Network planning, Description Logics, and the notions of affordances and conceptual similarity. The approach allows a domestic service robot to find ways to get a job done by making substitutions. We show how knowledge is modeled, how the reasoning process is used to create a constrained planning problem, and how the system handles cases where plan generation fails due to missing/unavailable objects. The results of the evaluation for two tasks in a domestic service domain show the viability of the approach in finding and making the appropriate goal transformations.

List of sponsors for the Twenty-Fourth International Conference on Automated Planning and Scheduling.

While Markov Decision Processes (MDPs) have been shown to be effective models for planning under uncertainty, the objective to minimize the expected cumulative cost is inappropriate for high-stake planning problems. As such, Yu, Lin, and Yan (1998) introduced the Risk-Sensitive MDP (RS-MDP) model, where the objective is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, we revisit this problem and introduce new algorithms that are based on classical techniques, such as depth-first search and dynamic programming, and a recently introduced technique called Topological Value Iteration (TVI). We demonstrate the applicability of our approach on randomly generated MDPs as well as domains from the ICAPS 2011 International Probabilistic Planning Competition (IPPC).

Recently, universal planning has become feasible through the use of efficient symbolic methods for plan generation and representation based on reduced ordered binary decision diagrams (OBDDs). In this paper, we address adversarial universal planning for multi-agent domains in which a set of uncontrollable agents may be adversarial to us (as in e.g. robotics soccer). We present two new OBDD-based universal planning algorithms for such adversarial nondeterministic finite domains, namely optimistic adversarial planning and strong cyclic adversarial planning. We prove and show empirically that these algorithms extend the existing family of OBDD- based universal planning algorithms to the challenging domains with adversarial environments. We further relate ad- verserial planning to positive stochastic games by analyzing the properties of adversarial plans when these are considered policies for positive stochastic games. Our algorithms have been implemented within the Multi-agent OBDD-based Planner, UMOP, using the Non-deterministic Agent Domain Language, NADL.

The demonstration (ASC) will fly onboard the Air Force’s TechSat-21 constellation (an unclassified mission scheduled for launch in 2004). ASC will use onboard science analysis, replanning, robust execution, model-based estimation and control, and formation flying to radically increase science return by enabling intelligent downlink selection and autonomous retargeting. Demonstration of these capabilities in a flight environment will open up tremendous new opportunities in planetary science, space physics, and earth science that would be unreachable without this technology. We offer a demonstration of the planning, scheduling, and execution framework for this application.

Flexible support for crisis management can definitely be improved by making use of advanced planning capabilities. However, the complexity of the underlying domain often causes intractable efforts in modeling the domain as well as a huge search space to be explored by the system. A way to overcome these problems is to impose a structure not only according to tasks but also according to relationships between and properties of the objects involved, thereby using so-called decomposition axioms. We outline the prototype of a system that is capable of tackling planning for complex application domains. It is based on a well-founded combination of action and state abstractions. The paper presents the basic techniques and provides a formal semantic foundation of the approach. It introduces the planning system and illustrates its underlying principles by examples taken from the crisis management domain used in our ongoing project.

Coordination between processing entities is one of the most widely studied areas in multi-agent planning research. Recently, efforts have been made to understand the formal computational issues of this important area. In this paper, we make a step toward this direction, and analyze a certain class of coordination problems for dependent agents with independent goals acting in the same environment. We assume that a state-transition description of each agent is given, and that preconditioning an agent's transitions by the states of other agents is the only considered kind of inter-agent dependence. Off-line coordination between the agents is considered. We analyze some structural properties of these problems, and investigate the relationship between these properties and the complexity of coordination in this domain. We show that our general problem is provably intractable, but some significant subclasses are in NP and even polynomial.

This paper proposes the problem of supply restoration in faulty power distribution systems as a benchmark for planning under uncertainty. This benchmark, which is derived from a significant real-world case, is both simple to understand and easily scalable. The goal is to reconfigure the distribution network to resupply a maximum of consumers affected by the faults.  Due to sensor and actuator uncertainty, the location of the faulty areas and the current network configuration are only partially observable.  This makes the problem very challenging.

Planning under uncertainty poses a complex problem in which multiple objectives often need to be balanced. When dealing with multiple objectives, it is often assumed that the relative importance of the objectives is known a priori. However, in practice human decision makers often find it hard to specify such preferences, and would prefer a decision support system that presents a range of possible alternatives. We propose two algorithms for computing these alternatives for the case of linearly weighted objectives. First, we propose an anytime method, approximate optimistic linear support (AOLS), that incrementally builds up a complete set of ε-optimal plans, exploiting the piecewise linear and convex shape of the value function. Second, we propose an approximate anytime method, scalarised sample incremental improvement (SSII), that employs weight sampling to focus on the most interesting regions in weight space, as suggested by a prior over preferences. We show empirically that our methods are able to produce (near-)optimal alternative sets orders of magnitude faster than existing techniques.

Many real world planning problems require goals with deadlines anddurative actions that consume resources. In this paper, we present Sapa, a domain-independent heuristic forward chaining planner thatcan handle durative actions, metric resource constraints, and deadlinegoals. The main innovation of Sapa is the set of distance basedheuristics it employs to control its search. We consider bothoptimizing and satisficing search. For the former, we identifyadmissible heuristics for objective functions based on makespan andslack. For satisficing search, our heuristics are aimed at scalabilitywith reasonable plan quality. Our heuristics are derived from the``relaxed temporal planning graph'' structure, which is ageneralization of planning graphs to temporal domains. We also providetechniques for adjusting the heuristic values to account for resourceconstraints. Our experimental results indicate that Sapa returnsgood quality solutions for complex planning problems in reasonabletime.