David E. Smith

HAXP Workshop 2025 Workshop Paper

How Humans Explain the Difference in the Quality of Plans -- A User Study

• Benjamin Krarup
• Amanda Jane Coles
• Dancheng Gao
• Derek Long
• David E. Smith

Recent advances in plan explanation have used abstractions to produce explanations. We consider the task of explaining why there is a difference in the quality of plans produced for a planning problem, $\Pi$, and the same problem constrained in some way, $\Pi + c$. The method involves abstracting away details of the planning problems until the difference in the quality of plans they support is minimised. It is not known whether humans use abstractions to explain these differences, and if so, what types of properties these abstractions have. We present the results of a qualitative user study investigating this. We tasked participants with explaining the difference in the quality of plans and found that users do indeed use abstractions to explain differences. We extract a set of properties that these abstractions satisfy, which can be used in automatic abstraction for explanation generation.

HAXP Workshop 2025 Workshop Paper

Plan Explanation through Recommendations

• Sarath Sreedharan
• Trisha Ghali
• David E. Smith

This paper aims to investigate an under-studied aspect of explanation, namely, its utility in helping users make better decisions. We will investigate such problems in the context of a specific explanatory setting, namely, when the user suggests the execution of an incorrect plan. Here, the system could help the user by pointing out how to update the current plan so as to avoid the failure. Such methods could be combined with existing explanatory methods to create explanations that empower users to make more effective decisions. Additionally, we will see how we could convert the problem of generating such plan recommendations into a planning problem of its own. We will ground this problem in the context of numeric planning problems and evaluate the effectiveness of the formulation in some IPC benchmark problems.

HAXP Workshop 2025 Workshop Paper

Revisiting Action Failures Through the Lens of Cooperative Games

• Sarath Sreedharan
• David E. Smith

This paper will revisit the question of explaining action or plan failures in the context of numeric planning problems. As we will see, the existing methods used in classical planning for explaining plan failures fall short in this setting, and we need a novel paradigm to handle this question. To model such explanation methods, we turn to cooperative games as a framework to capture such explanation generation problems. Then we look at two possible methods, namely, Shapley values and Banzhaf values, to identify the role played by each action in the resulting failure. While such methods have been previously used in explaining machine learning models, we see that their deployment in planning reveals novel challenges. As we will see, we will need to modify how these values are calculated for the planning setting. Finally, through a running example, we will see how explanations may be calculated using each of these methods, and how they may result in different explanations. This points to how more work needs to be done to evaluate which of these methods may be better suited for planning settings.

JAIR Journal 2021 Journal Article

Contrastive Explanations of Plans through Model Restrictions

• Benjamin Krarup
• Senka Krivic
• Daniele Magazzeni
• Derek Long
• Michael Cashmore
• David E. Smith

In automated planning, the need for explanations arises when there is a mismatch between a proposed plan and the user’s expectation. We frame Explainable AI Planning as an iterative plan exploration process, in which the user asks a succession of contrastive questions that lead to the generation and solution of hypothetical planning problems that are restrictions of the original problem. The object of the exploration is for the user to understand the constraints that govern the original plan and, ultimately, to arrive at a satisfactory plan. We present the results of a user study that demonstrates that when users ask questions about plans, those questions are usually contrastive, i.e. “why A rather than B?”. We use the data from this study to construct a taxonomy of user questions that often arise during plan exploration. Our approach to iterative plan exploration is a process of successive model restriction. Each contrastive user question imposes a set of constraints on the planning problem, leading to the construction of a new hypothetical planning problem as a restriction of the original. Solving this restricted problem results in a plan that can be compared with the original plan, admitting a contrastive explanation. We formally define model-based compilations in PDDL2.1 for each type of constraint derived from a contrastive user question in the taxonomy, and empirically evaluate the compilations in terms of computational complexity. The compilations were implemented as part of an explanation framework supporting iterative model restriction. We demonstrate its benefits in a second user study.

AIJ Journal 2018 Journal Article

Extracting mutual exclusion invariants from lifted temporal planning domains

• Sara Bernardini
• Fabio Fagnani
• David E. Smith

We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire temporal structure of the actions and the possible concurrent interactions between them. As a result, we construct a more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains but also a broader set of invariants for sequential domains. Our experimental results provide evidence that our domain analysis is effective at identifying a more extensive set of invariants, which results in the generation of fewer multi-valued state variables. We show that, in turn, this reduction in the number of variables reflects positively on the performance of the temporal planners that use a variable/value representation.

AIJ Journal 2018 Journal Article

Strong temporal planning with uncontrollable durations

• Alessandro Cimatti
• Minh Do
• Andrea Micheli
• Marco Roveri
• David E. Smith

Planning in real world domains often involves modeling and reasoning about the duration of actions. Temporal planning allows such modeling and reasoning by looking for plans that specify start and end time points for each action. In many practical cases, however, the duration of actions may be uncertain and not under the full control of the executor. For example, a navigation task may take more or less time, depending on external conditions such as terrain or weather. In this paper, we tackle the problem of strong temporal planning with uncontrollable action durations (STPUD). For actions with uncontrollable durations, the planner is only allowed to choose the start of the actions, while the end is chosen, within known bounds, by the environment. A solution plan must be robust with respect to all uncontrollable action durations, and must achieve the goal on all executions, despite the choices of the environment. We propose two complementary techniques. First, we discuss a dedicated planning method, that generalizes the state-space temporal planning framework, leveraging SMT-based techniques for temporal networks under uncertainty. Second, we present a compilation-based method, that reduces any STPUD problem to an ordinary temporal planning problem. Moreover, we investigate a set of sufficient conditions to simplify domains by removing some of the uncontrollability. We implemented both our approaches, and we experimentally evaluated our techniques on a large number of instances. Our results demonstrate the practical applicability of the two techniques, which show complementary behavior.

AAMAS Conference 2016 Conference Paper

Planning with Resource Conflicts in Human-Robot Cohabitation

• Tathagata Chakraborti
• Yu Zhang
• David E. Smith
• Subbarao Kambhampati

IJCAI Conference 2015 Conference Paper

A Fast Goal Recognition Technique Based on Interaction Estimates

• Yolanda E-Martin
• Maria D. R-Moreno
• David E. Smith

Goal Recognition is the task of inferring an actor’s goals given some or all of the actor’s observed actions. There is considerable interest in Goal Recognition for use in intelligent personal assistants, smart environments, intelligent tutoring systems, and monitoring user’s needs. In much of this work, the actor’s observed actions are compared against a generated library of plans. Recent work by Ramı́rez and Geffner makes use of AI planning to determine how closely a sequence of observed actions matches plans for each possible goal. For each goal, this is done by comparing the cost of a plan for that goal with the cost of a plan for that goal that includes the observed actions. This approach yields useful rankings, but is impractical for real-time goal recognition in large domains because of the computational expense of constructing plans for each possible goal. In this paper, we introduce an approach that propagates cost and interaction information in a plan graph, and uses this information to estimate goal probabilities. We show that this approach is much faster, but still yields high quality results.

IJCAI Conference 2015 Conference Paper

Compiling Away Uncertainty in Strong Temporal Planning with Uncontrollable Durations

• Andrea Micheli
• Minh Do
• David E. Smith

Real world temporal planning often involves dealing with uncertainty about the duration of actions. In this paper, we describe a sound-and-complete compilation technique for strong planning that reduces any planning instance with uncertainty in the duration of actions to a plain temporal planning problem without uncertainty. We evaluate our technique by comparing it with a recent technique for PDDL domains with temporal uncertainty. The experimental results demonstrate the practical applicability of our approach and show complementary behavior with respect to previous techniques. We also demonstrate the high expressiveness of the translation by applying it to a significant fragment of the ANML language.

AIJ Journal 2008 Journal Article

Sequential Monte Carlo in reachability heuristics for probabilistic planning

• Daniel Bryce
• Subbarao Kambhampati
• David E. Smith

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking. In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.

KER Journal 2000 Journal Article

Bridging the gap between planning and scheduling

• David E. Smith
• Jeremy Frank
• Ari K. Jónsson

Planning research in Artificial Intelligence (AI) has often focused on problems where there are cascading levels of action choice and complex interactions between actions. In contrast, scheduling research has focused on much larger problems where there is little action choice, but the resulting ordering problem is hard. In this paper, we give an overview of AI planning and scheduling techniques, focusing on their similarities, differences, and limitations. We also argue that many difficult practical problems lie somewhere between planning and scheduling, and that neither area has the right set of tools for solving these vexing problems.

IJCAI Conference 1999 Conference Paper

Temporal Planning with Mutual Exclusion Reasoning

• David E. Smith
• Daniel S. Weld

Many planning domains require a richer notion of time in which actions can overlap and have different durations. The key to fast performance in classical planners (e. g. , Graphplan, IPP, and Blackbox) has been the use of a disjunctive representation with powerful mutual exclusion reasoning. This paper presents T G P, a new algorithm for temporal planning. TGP operates by incrementally expanding a compact planning graph representation that handles actions of differing duration. The key to TGP performance is tight mutual exclusion reasoning which is based on an expressive language for bounding mutexes and includes mutexes between actions and propositions. Our experiments demonstrate that mutual exclusion reasoning remains valuable in a rich temporal setting.

AAAI Conference 1998 Conference Paper

Conformant Graphplan

• David E. Smith

Planning under uncertainty is a difficult task. If sensory information is available, it is possible to do contingency planning – that is, develop plans where certain branches are executed conditionally, based on the outcome of sensory actions. However, even without sensory information, it is often possible to develop useful plans that succeed no matter which of the allowed states the world is actually in. We refer to this type of planning as conformant planning. Few conformant planners have been built, partly because conformant planning requires the ability to reason about disjunction. In this paper we describe Conformant Graphplan (CGP), a Graphplan-based planner that develops sound (non-contingent) plans when faced with uncertainty in the initial conditions and in the outcome of actions. The basic idea is to develop separate plan graphs for each possible world. This requires some subtle changes to both the graph expansion and solution extraction phases of Graphplan. In particular, the solution extraction phase must consider the unexpected side effects of actions in other possible worlds, and must confront any undesirable effects. We show that CGP performs significantly better than two previous (probabilistic) conformant planners.

AIJ Journal 1989 Journal Article

Controlling backward inference

• David E. Smith

Effective control of inference is a critical problem in artificial intelligence. Expert systems make use of powerful domain-dependent control information to beat the combinatorics of inference. However, it is not always feasible or convenient to provide all of the domain-dependent control that may be needed, especially for systems that must handle a wide variety of inference problems, or must function in a changing environment. In this paper, a domain-independent means of controlling inference is developed. The basic approach is to compute expected cost and probability of success for different backward inference strategies. This information is used to select between inference steps, and to compute the best order for processing conjunctions. The necessary expected cost and probability calculations rely on simple information about the contents of the problem solver's database, such as the number of facts of a given form, and the domain sizes for the predicates and relations involved.

AIJ Journal 1988 Journal Article

Reasoning about action I

• Matthew L. Ginsberg
• David E. Smith

Reasoning about change is an important aspect of commonsense reasoning and planning. In this paper we describe an approach to reasoning about change for rich domains where it is not possible to anticipate all situations that might occur. The approach provides a solution to the frame problem, and to the related problem that it is not always reasonable to explicitly specify all of the consequences of actions. The approach involves keeping a single model of the world that is updated when actions are performed. The update procedure involves constructing the nearest world to the current one in which the consequences of the actions under consideration hold. The way we find the nearest world is to construct proofs of the negation of the explicit consequences of the expected action, and to remove a premise in each proof from the current world. Computationally, this construction procedure appears to be tractable for worlds like our own where few things tend to change with each action, or where change is regular.

AIJ Journal 1988 Journal Article

Reasoning about action II

• Matthew L. Ginsberg
• David E. Smith

We present a computationally effective approach to representing and reasoning about actions with many qualifications. The approach involves treating actions as qualified not by specific facts that may or may not hold when the action is executed, but instead as potentially qualified by general constraints describing the domain being investigated. Specifically, we suggest that the result of the action be computed without considering these qualifying domain constraints, and take the action to be qualified if and only if any of the constraints is violated after the computation is complete. Our approach is presented using the framework developed in [6], where we discussed a solution to the frame and ramification problems based on the notion of possible worlds, and compared the computational requirements of that solution to the needs of more conventional ones. In the present paper, we show that the domain constraint approach to qualification, coupled with the possible worlds approach described earlier, has the remarkable property that essentially no computational resources are required to confirm that an action is unqualified. As before, we also make a quantitative comparison between the resources needed by our approach and those required by other formulations.

AIJ Journal 1986 Journal Article

Controlling recursive inference

• David E. Smith
• Michael R. Genesereth
• Matthew L. Ginsberg

Loosely speaking, recursive inference occurs when an inference procedure generates an infinite sequence of similar subgoals. In general, the control of recursive inference involves demonstrating that recursive portions of a search space will not contribute any new answers to the problem beyond a certain level. We first review a well-known syntactic method for controlling repeating inference (inference where the conjuncts processed are instances of their ancestors), provide a proof that it is correct, and discuss the conditions under which the strategy is optimal. We also derive more powerful pruning theorems for cases involving transitivity axioms and cases involving subsumed subgoals. The treatment of repeating inference is followed by consideration of the more difficult problem of recursive inference that does not repeat. Here we show how knowledge of the properties of the relations involved and knowledge about the contents of the system's database can be used to prove that portions of a search space will not contribute any new answers.

AIJ Journal 1985 Journal Article

Ordering conjunctive queries

• David E. Smith
• Michael R. Genesereth

AAAI Conference 1983 Conference Paper

Finding All of the Solutions to a Problem

• David E. Smith

This paper describes a method of cutting off reasoning when all of the answers to a problem have been found. Briefly, the method involves keeping and maintaining information about the sizes of important sets and using this information to determine when all of the answers to a problem have been found. We show how this information can be dynamically calculated and kept accurate in a changing world. Additional complexity is encouniered when this maintenance mixed with independent meta-level reasoning for pruning search spaces.

AAAI Conference 1980 Conference Paper

A Frame-Based Production System Architecture

• David E. Smith