Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP infinite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.

The problem of identifying the (dynamic) team structures and team behaviors from the observed activities of multiple agents is called Multi-Agent Plan Recognition (MAPR). We extend a recent formalization of this problem to accommodate a compact, partially ordered, multi-agent plan language, as well as complex plan execution models — particularly plan abandonment and activity interleaving. We adopt a branch and price approach to solve MAPR in such a challenging setting, and fully instantiate the (generic) pricing problem for MAPR. We show experimentally that this approach outperforms a recently proposed hypothesis pruning algorithm in two domains: multi-agent blocks word, and intrusion detection. The key benefit of the branch and price approach is its ability to grow the necessary component (occurrence) space from which the hypotheses are constructed, rather than begin with a fully enumerated component space that has an intractable size, and search it with pruning. Our formulation of MAPR has the broad objective of bringing mature Operations Research methodologies to bear upon MAPR, envisaged to have a similar impact as mature SAT-solvers had on planning.

We consider a new class of planning problems involving a set of non-negative real variables, and a set of non-deterministic actions that increase or decrease the values of these variables by some arbitrary amount. The formulas specifying the initial state, goal state, or action preconditions can only assert whether certain variables are equal to zero or not. Assuming that the state of the variables is fully observable, we obtain two results. First, the solution to the problem can be expressed as a policy mapping qualitative states into actions, where a qualitative state includes a Boolean variable for each original variable, indicating whether its value is zero or not. Second, testing whether any such policy, that may express nested loops of actions, is a solution to the problem, can be determined in time that is polynomial in the qualitative state space, which is much smaller than the original infinite state space. We also report experimental results using a simple generate-and-test planner to illustrate these findings.

MAPP has been previously shown as a state-of-the-art multi-agent path planning algorithm on criteria including scalability and success ratio (i.e., percentage of solved units) on realistic game maps. MAPP further provides a formal characterization of problems it can solve, and low-polynomial upper bounds on the resources required. However, until now, MAPP's solution quality had not been extensively analyzed. In this work we empirically analyze the quality of MAPP's solutions, using multiple quality criteria such as the total travel distance, the makespan and the sum of actions (including move and wait actions). We also introduce enhancements that improve MAPP's solution quality significantly. For example, the sum of actions is cut to half on average. The improved MAPP is competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature, and maintains its advantages on different performance criteria, such as scalability, success ratio, and ability to tell apriori if it will succeed in the instance at hand. As optimal algorithms have limited scalability, evaluating the quality of the solutions provided by suboptimal algorithms is another important topic. Using lower bounds of optimal values, we show that MAPP's solutions have a reasonable quality. For example, MAPP's total travel distance is on average 19% longer than a lower bound on the optimal value.

This work focuses on developing domain-independent heuristics for probabilistic planning problems characterized by full observability and non-deterministic effects of actions that are expressed by probability distributions. The approach is to first search for a high probability deterministic plan using a classical planner. A novel probabilistic plan graph heuristic is used to guide the search towards high probability plans. The resulting plans can be used in a system that handles unexpected outcomes by runtime replanning. The plans can also be incrementally augmented with contingency branches for the most critical action outcomes. This abstract will describe the steps that we have taken in completing the above work and the obtained results.

Agents in highly dynamic adversarial domains, such as RTS games, must continually make time-critical decisions to adapt their behaviour to the changing environment. In such a context, the planning agent must consider his opponent's actions as uncontrollable, or at best influenceable. In general nondeterministic domains where there is no clear turn-taking protocol, most heuristic search methods to date do not explicitly reason about the opponent's actions when guiding the state space exploration towards goal or high-reward states. In contrast, we are investigating a domain-independent heuristic planning approach which reasons about the dynamics and uncontrollability of the opponent's behaviours in order to provide better guidance to the search process of the planner. Our planner takes as input the opponent's behaviours recognized by a plan recognition module and uses them to identify opponent's actions that lead to low-utility projected states. We believe such explicit heuristic reasoning about the potential behaviours of the opponent is crucial when planning in adversarial domains, yet is missing in today's planning approaches.

Possessing a sufficient level of situation awareness is essential for effective decision making in dynamic environments. In video games, this includes being aware to some extent of the intentions of the opponents. Such high-level awareness hinges upon inferences over the lower-level situation awareness provided by the game state. Traditional plan recognizers are completely passive processes that leave all the initiative to the observed agent. In a situation where the opponent's intentions are unclear, the observer is forced to wait until further observations of the opponent's actions are made to disambiguate the pending goal hypotheses. With the plan recognizer we propose, in contrast, the observer would take the initiative and provoke the opponent, with the expectation that his reaction will give cues as to what his true intentions actually are.

One of the most ubiquitous AI applications is vehicle route planning. While state-of-the-art systems take into account current traffic conditions or historic traffic data, current planning approaches ignore the impact of their own plans on the future traffic conditions. We present a novel algorithm for self-aware route planning that uses the routes it plans for current vehicle traffic to more accurately predict future traffic conditions for subsequent cars. Our planner uses a roadmap with stochastic, time-varying traffic densities that are defined by a combination of historical data and the densities predicted by the planned routes for the cars ahead of the current traffic. We have applied our algorithm to large-scale traffic route planning, and demonstrated that our self-aware route planner can more accurately predict future traffic conditions, which results in a reduction of the travel time for those vehicles that use our algorithm.

The utility of including cyclic flows of control in plans has been long recognized by the planning community. Loops in a plan help increase both its applicability and the compactness of representation. However, progress in finding such plans has been limited largely due to lack of methods for reasoning about the correctness and safety properties of loops of actions. We present an overview of recent results for determining the class of problems that a plan with loops can solve. These methods can be used to direct the construction of a rich new form of generalized plans that solve a desired class of problems.

Logic, and declarative representation of knowledge in general, have long been a preferred framework for problem solving in AI. However, specific subareas of AI have been eager to abandon general-purpose knowledge representation in favor of methods that seem to address their computational core problems better. In planning, for example, state-space search has in the last several years been preferred to logic-based methods such as SAT. In our recent work, we have demonstrated that the observed performance differences between SAT and specialized state-space search methods largely go back to the difference between a blind (or at least planning-agnostic) and a planning-specific search method. If SAT search methods are given even simple heuristics which make the search goal-directed, the efficiency differences disappear.