The Next-Generation Transportation program coordinates the evolution and transformation of the current air-traffic management (ATM) system for the National Airspace System (NAS). Currently the NAS has a limited capacity and cannot handle the increasing future air traffic demands. However, before newly proposed ATM concepts are deployed they must be rigorously evaluated under realistic conditions. This paper presents AGENTFLY, an emerging NAS-wide highfidelity multi-agent ATM simulator with precise emulation of the human controller operation workload model and human-system interaction. The simulator is validated using a flight scenario developed by the U.S. Federal Aviation Administration that is based on real data. We present preliminary results focusing on the accuracy of the simulated controllers within AGENTFLY.

The average home computer user needs help in reducing the security risk of their home computer. We are working on an alternative approach from current home security software in which a software agent helps a user manage his/her security risk. Planning is integral to the design of this agent in several ways. First, planning can be used to make the underlying security model manageable by generating attack paths to identify vulnerabilities that are not a problem for a particular user/home computer. Second, planning can be used to identify interventions that can either avoid the vulnerability or mitigate the damage should it occur. In both cases, a central capability is that of generating alternative plans so as to find as many possible ways to trigger the vulnerability and to provide the user with options should the obvious not be acceptable. We describe our security model and our state-based approach to generating alternative plans. We show that the state-based approach can generate more diverse plans than a heuristic-based approach. However, the state-based approach sometimes generates this diversity with better quality at higher search cost.

We are working to develop plan critiquing methods where a planner is used to identify flaws in an existing plan, in order to provide assistance to human planners. In this paper, we describe how to use any classical planning algorithm for verification and counterexample generation for plans already generated by some agent (human or an automated planning system). We show how to take an original classical planning domain, problem, and plan, and a set of uncontrollable (disturbance) actions and agents, and compile those inputs into a new "counter-planning'' problem. This counter-planning problem can be given to an arbitrary PDDL planner, in order to generate counterexample traces where uncontrollable actions can upset plan execution. Our experiments with a large set of planning problems in two multi-agent, dynamic planning domains demonstrated that our approach can verify a plan or generate a counterexample quickly and reliably. We have also compared our approach with a state-of-the-art model-checking system: the results suggest that using classical planners for generating counter plans is more promising than model-checking based verification.

Much of the existing work on plan recognition assumes that actions of other agents can be observed directly. In continuous temporal domains such as traffic scenarios this assumption is typically not warranted. Instead, one is only able to observe facts about the world such as vehicle positions at different points in time, from which the agents' intentions need to be inferred. In this paper we show how this problem can be addressed in the situation calculus and a new variant of the action programming language Golog, which includes features such as continuous time and change, stochastic actions, nondeterminism, and concurrency. In our approach we match observations against a set of candidate plans in the form of Golog programs. We turn the observations into actions which are then executed concurrently with the given programs. Using decision-theoretic optimization techniques those programs are preferred which bring about the observations at the appropriate times. Besides defining this new variant of Golog we also discuss an implementation and experimental results using driving maneuvers as an example.

We describe a new sound and complete method for compiling contingentplanning problems with sensing actions into classical planning.Our method encodes conditional plans within a linear, classical plan.This allows our planner, MPSR, to reason about multiple future outcomes of sensingactions, and makes it less susceptible to dead-ends.MPRS, however, generates very large classical planningproblems. To overcome this, we use an incomplete variantof the method, based on state sampling, within an online replanner. On most current domains, MPSR finds plans faster, although its plans are often longer. But on a new challenging variant of Wumpus with dead-ends,it finds smaller plans, faster, and scales better.

We discuss preliminary work focusing on the problem of combining social interaction with task-based action in a dynamic, multiagent bartending domain, using an embodied robot. We show how the users' spoken input is interpreted, discuss how social states are inferred from the parsed speech together with low-level information from the vision system, and present a planning approach that models task, dialogue, and social actions in a simple bartending scenario. This approach allows us to build interesting plans, which have been evaluated in a real-world study, using a general purpose, off-the-shelf planner, as an alternative to more mainstream methods of interaction management.

The most critical moves that determine the success of a manipulation task are performed within the close vicinities of the object prior to grasping, and the goal prior to the final placement. Memorizing these state-action sequences and reusing them can dramatically improve the task efficiency, whereas even the state-of-the-art planning algorithms may require significant amount of time and computational resources to generate a solution from scratch depending on the complexity and the constraints of the task. In this paper, we propose a hybrid approach that combines the reliability of the past experiences gained through demonstration and the flexibility of a generative motion planning algorithm, namely RRT*, to improve task execution efficiency. As a side benefit of reusing these final moves, we can dramatically reduce the number of nodes used by the generative planner, hence the planning time, by either early-terminating the planner when the generated plan reaches a "recalled state", or deliberately biasing it towards the memorized state-action sequences that are feasible at the moment. This complementary combination of the already available partial plans and the generated ones yield to fast, reliable, and repeatable solutions.

Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, simplifying the planning problem. In many practical settings, such plans can be of higher quality than conformant plans. We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

Planning with action concurrency under time and resources constraints and uncertainty is a challenging problem. Current approaches which rely on Markov Decision Processes and a discrete model for time and resources are limited by a blow-up of the search state-space. This paper presents a planner which is based on a classical forward search for solving this kind a problems. A continuous model is used for time and resources. The uncertainty on time is represented by continuous random variables which are organized in a dynamically generated Bayesian network. Two versions of the ActuPlan planner are presented. As a first step, ActuPlan_nc performs a forward-search in an augmented state-space to generate epsilon-optimal nonconditional plans which are robust to uncertainty (threshold on the probability of success). ActuPlan_nc is then adapted to generate a set of nonconditional plans which are characterized by different trade-offs between their probability of success and their expected cost. ActuPlan, the second version, builds a conditional plan with a lower expected cost by merging previously generated nonconditional plans. The branches are built by conditioning on the time. Empirical experimentation on standard benchmarks demonstrates the effectiveness of the approach.

Refining a network topology is an important network management technique. Nevertheless, determining the appropriate steps to transform a network from one topology to another, in a way that minimizes service disruptions, has received little attention. This is a critical problem since service disruptions can be particularly harmful and costly for networks hosting mission-critical services. In this paper, we introduce the incremental network transformation (INT) problem and explore this problem in the context of automated planning. We define two metrics to measure the quality of generated transformation plans, one of which is amenable to classical propositional planning. We find that while state-of-the-art domain-independent planning techniques are effective at finding high-quality solutions for small problem instances, they cannot scale to solve realistically sized INT instances. To address the shortcomings of existing approaches, we developed a number of domain-dependent planners that use novel domain-specific heuristics. We empirically evaluated our planners on a wide range of synthetic network topologies. Our results illustrate that our automated planning inspired techniques are effective on realistically sized INT problems. We envision that our approach could eventually provide a compelling addition to the arsenal of techniques employed by network practitioners to support network refinement with minimal disruption to running services.