Non-player character diversity enriches game environments increasing their replay value. We propose a method for obtaining character behavior diversity based on the diversity of plans enacted by characters, and demonstrate this method in a scenario in which characters have multiple choices. Using case-based planning techniques, we reuse plans for varied character behavior, which simulate different personality traits.

Existing theoretical universal algorithmic intelligence models are not practically realizable. More pragmatic approach to artificial general intelligence is based on cognitive architectures, which are, however, non-universal in sense that they can construct and use models of the environment only from Turing-incomplete model spaces. We believe that the way to the real AGI consists in bridging the gap between these two approaches. This is possible if one considers cognitive functions as a "cognitive bias" (priors and search heuristics) that should be incorporated into the models of universal algorithmic intelligence without violating their universality. Earlier reported results suiting this approach and its overall feasibility are discussed on the example of perception, planning, knowledge representation, attention, theory of mind, language, and some others.

Domain-independent planning is one of the foundational areas in the field of Artificial Intelligence. A description of a planning task consists of an initial world state, a goal, and a set of actions for modifying the world state. The objective is to find a sequence of actions, that is, a plan, that transforms the initial world state into a goal state. In optimal planning, we are interested in finding not just a plan, but one of the cheapest plans. A prominent approach to optimal planning these days is heuristic state-space search, guided by admissible heuristic functions. Numerous admissible heuristics have been developed, each with its own strengths and weaknesses, and it is well known that there is no single "best'' heuristic for optimal planning in general. Thus, which heuristic to choose for a given planning task is a difficult question. This difficulty can be avoided by combining several heuristics, but that requires computing numerous heuristic estimates at each state, and the tradeoff between the time spent doing so and the time saved by the combined advantages of the different heuristics might be high. We present a novel method that reduces the cost of combining admissible heuristics for optimal planning, while maintaining its benefits. Using an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for learning a classifier with that decision rule as the target concept, and employ the learned classifier to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms the standard method for combining several heuristics via their pointwise maximum.

The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (Baeckstroem and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning have seemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partial-order planner exploit this fact.

Planning is concerned with the automated solution of action sequencing problems described in declarative languages giving the action preconditions and effects. One important application area for such technology is the creation of new processes in Business Process Management (BPM), which is essential in an ever more dynamic business environment. A major obstacle for the application of Planning in this area lies in the modeling. Obtaining a suitable model to plan with -- ideally a description in PDDL, the most commonly used planning language -- is often prohibitively complicated and/or costly. Our core observation in this work is that this problem can be ameliorated by leveraging synergies with model-based software development. Our application at SAP, one of the leading vendors of enterprise software, demonstrates that even one-to-one model re-use is possible. The model in question is called Status and Action Management (SAM). It describes the behavior of Business Objects (BO), i.e., large-scale data structures, at a level of abstraction corresponding to the language of business experts. SAM covers more than 400 kinds of BOs, each of which is described in terms of a set of status variables and how their values are required for, and affected by, processing steps (actions) that are atomic from a business perspective. SAM was developed by SAP as part of a major model-based software engineering effort. We show herein that one can use this same model for planning, thus obtaining a BPM planning application that incurs no modeling overhead at all. We compile SAM into a variant of PDDL, and adapt an off-the-shelf planner to solve this kind of problem. Thanks to the resulting technology, business experts may create new processes simply by specifying the desired behavior in terms of status variable value changes: effectively, by describing the process in their own language.

This paper documents extending the ELEXIR (Engine for LEXicalized Intent Recognition) system (Geib 2009; Geib 2011) with a world model. This is a significant increase in the expressiveness of the plan recognition system and allows a number of additions to the algorithm, most significantly conditioning probabilities for recognized plans on the state of the world during execution. Since, ELEXIR falls in the family of gramatical methods for plan recognition in viewing the problem of plan recognition as that of parsing, this paper will also briefly discuss how this extension relates to state of the art proposals in the natural language community regarding probabilistic parsing.

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.

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.

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.

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.