Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. In three cases we achieve the most desirable outcome: detection and evaluation are fpt.

Search with Subgoal Graphs (Uras, Koenig, and Hernandez 2013) was a non-dominated optimal path-planning algorithm in the Grid-Based Path Planning Competitions 2012 and 2013. During a preprocessing phase, it computes a Simple Subgoal Graph from a given grid, which is analogous to a visibility graph for continuous terrain, and then partitions the vertices into global and local subgoals to obtain a Two-Level Subgoal Graph. During the path-planning phase, it performs an A* search that ignores local subgoals that are not relevant to the search, which significantly reduces the size of the graph being searched. In this paper, we generalize this partitioning process to any undirected graph and show that it can be recursively applied to generate more than two levels, which reduces the size of the graph being searched even further. We distinguish between basic partitioning, which only partitions the vertices into different levels, and advanced partitioning, which can also add new edges.We show that the construction of Simple-Subgoal Graphs from grids and the construction of Two-Level Subgoal Graphs from Simple Subgoal Graphs are instances of generalized partitioning. We then report on experiments on Subgoal Graphs that demonstrate the effects of different types and levels of partitioning. We also report on experiments that demonstrate that our new N-Level Subgoal Graphs achieve a speed up of 1.6 compared to Two-Level Subgoal graphs from (Uras, Koenig, and Hern´andez 2013) on maps from the video games StarCraft and Dragon Age: Origins.

The main focus of our work is the use of classical planning algorithms in service of more complex problems of planning under uncertainty. In particular, we are exploring compilation techniques that allow us to reduce some probabilistic planning problems into variants of classical planning, such as metric planning,resource-bounded planning, and cost-bounded suboptimal planning. Currently, our initial work focuses on \emph{conformant probabilistic planning}. We intend toimprove our current methods by improving our compilation methods, but also by improving the ability of current planners to handle the special features ofour compiled problems. Then, we hope to extend these techniques to handle more complex probabilistic settings, such as problems with stochastic actions andpartial observability.

In real world planning problems, it might not be possible for an automated agent to satisfy all the objectives assigned to it because available resources are limited. When objectives cannot all be satisfied, classical planning returns no plan. In partial satisfaction planning, it is possible to satisfy only a subset of the objectives. To solve this kind of problems, an agent could select the objectives subset and the plan that maximizes the net benefit, i.e. the sum of satisfied objectives utilities minus the sum of the cost of actions. This approach has been experimented for deterministic planning. This paper extends partial satisfaction planning for problems with uncertainty on time. For problems under uncertainty, the best subset of objectives may not be calculated at planning time. The effective duration of actions at execution time may dynamically influence the achievable subset of objectives. Our approach introduces special actions to explicitly abort objectives. This enables control on when an objective is aborted.

Consider a family whose home is equipped with several service robots. The actions planned for the robots must adhere to Interaction Constraints (ICs) relating them to human activities and preferences. These constraints must be sufficiently expressive to model both temporal and logical dependencies among robot actions and human behavior, and must accommodate incomplete information regarding human activities. In this paper we introduce an approach for automatically generating plans that are conformant wrt. given ICs and partially specified human activities. The approach allows to separate causal reasoning about actions from reasoning about ICs, and we illustrate the computational advantage this brings with experiments on a large-scale (semi-)realistic household domain with hundreds of human activities and several robots.

Utilizing multiple queues in Greedy Best-First Search (GBFS) has been proven to be a very effective approach to satisficing planning. Successful techniques include extra queues based on Helpful Actions (or Preferred Operators), as well as using Multiple Heuristics. One weakness of all standard GBFS algorithms is their lack of exploration. All queues used in these methods work as priority queues sorted by heuristic values. Therefore, misleading heuristics, especially early in the search process, can cause the search to become ineffective. Type systems, as introduced for heuristic search by Lelis et al, are a development of ideas for exploration related to the classic stratified sampling approach. The current work introduces a search algorithm that utilizes type systems in a new way – for exploration within a GBFS multiqueue framework in satisficing planning. A careful case study shows the benefits of such exploration for overcoming deficiencies of the heuristic. The proposed new baseline algorithm Type-GBFS solves almost 200 more problems than baseline GBFS over all International Planning Competition problems. Type-LAMA, a new planner which integrates Type-GBFS into LAMA-2011, solves 36.8 more problems than LAMA-2011.

One subclass of human computation applications are those directed at tasks that involve planning (e.g. tour planning) and scheduling (e.g. conference scheduling). Interestingly, work on these systems shows that even primitive forms of automated oversight on the human contributors helps in significantly improving the effectiveness of the humans/crowd. In this paper, we argue that the automated oversight used in these systems can be viewed as a primitive automated planner, and that there are several opportunities for more sophisticated automated planning in effectively steering the crowd. Straightforward adaptation of current planning technology is however hampered by the mismatch between the capabilities of human workers and automated planners. We identify and partially address two important challenges that need to be overcome before such adaptation of planning technology can occur: (1 interpreting inputs of the human workers (and the requester) and (2) steering or critiquing plans produced by the human workers, armed only with incomplete domain and preference models. To these ends, we describe the implementation of AI-MIX, a tour plan generation system that uses automated checks and alerts to improve the quality of plans created by human workers; and present a preliminary evaluation of the effectiveness of steering provided by automated planning.

Whenever an auto manufacturer refreshes an existing car or truck model or builds a new one, the model will undergo hundreds if not thousands of tests before the factory line and tooling is finished and vehicle production beings. These tests are generally carried out on expensive, custom-made vehicles because the new factory lines for the model do not exist yet. The work presented in this paper describes how an existing intelligent scheduling software framework was modified to include domain-specific heuristics used in the vehicle test planning process. The result of this work is a prototype scheduling tool that optimizes the overall given test schedule in order to complete the work in a given time window while minimizing the total number of vehicles required for the test schedule. Initial results are presented that show a reduction in required test vehicles compared to manual scheduling of the same tasks as well as increased capability to ask “what-if” questions to further improve the schedule.

We present work toward computationally defining a model of narrative comprehension vis-à-vis memory of narrative events, via an automated planning knowledge representation, capable of being used in a narrative generation context.

Markov decision processes (MDP) offer a rich model that has been extensively used by the AI community for planning and learning under uncertainty. However, solving MDPs is often intractable, which has led to the development of many approximate algorithms. In my dissertation work I introduce a new paradigm to handle this complexity by defining a family of MDP reduced models characterized by two parameters: the maximum number of primary outcomes per action that are fully accounted for and the maximum number of occurrences of the remaining exceptional outcomes that are planned for in advance. Reduced models can be solved much faster using heuristic search algorithms, benefiting from the dramatic reduction in the number of reachable states. This framework places recent work on MDP determinization in a broader context and lays the foundation for efficient and systematic exploration of the space of MDP model reductions. Progress so far work includes a formal definition of this family of MDP reductions, a continual planning paradigm to handle the case when the number of exceptions reaches the maximum allowed, a simple greedy approach to generate good reductions for a given planning domain, and a compilation scheme that generates MDP reductions from a PPDDL description of a planning problem.