David E. Smith 0001

ICAPS Conference 2024 Conference Paper

Explaining Plan Quality Differences

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

We describe a method for explaining the differences between the quality of plans produced for similar planning problems. The method exploits a process of abstracting away details of the planning problems until the difference in solution quality they support has been minimised. We give a general definition of a valid abstraction of a planning problem. We then give the details of the implementation of a number of useful abstractions. Finally, we present a breadth-first search algorithm for finding suitable abstractions for explanations; and detail the results of an evaluation of the approach.

IROS Conference 2020 Conference Paper

Designing Environments Conducive to Interpretable Robot Behavior

• Anagha Kulkarni 0002
• Sarath Sreedharan
• Sarah Keren
• Tathagata Chakraborti
• David E. Smith 0001
• Subbarao Kambhampati

Designing robots capable of generating interpretable behavior is essential for effective human-robot collaboration. This requires robots to be able to generate behavior that aligns with human expectations but exhibiting such behavior in arbitrary environments could be quite expensive for robots, and in some cases, the robot may not even be able to exhibit expected behavior. However, in structured environments (like warehouses, restaurants, etc.), it may be possible to design the environment so as to boost the interpretability of a robot's behavior or to shape the human's expectations of the robot's behavior. In this paper, we investigate the opportunities and limitations of environment design as a tool to promote a particular type of interpretable behavior - known in the literature as explicable behavior. We formulate a novel environment design framework that considers design over multiple tasks and over a time horizon. In addition, we explore the longitudinal effect of explicable behavior and the trade-off that arises between the cost of design and the cost of generating explicable behavior over an extended time horizon.

ICAPS Conference 2019 Conference Paper

Explicability? Legibility? Predictability? Transparency? Privacy? Security? The Emerging Landscape of Interpretable Agent Behavior

• Tathagata Chakraborti
• Anagha Kulkarni 0002
• Sarath Sreedharan
• David E. Smith 0001
• Subbarao Kambhampati

There has been significant interest of late in generating behavior of agents that is interpretable to the human (observer) in the loop. However, the work in this area has typically lacked coherence on the topic, with proposed solutions for “explicable”, “legible”, “predictable” and “transparent” planning with overlapping, and sometimes conflicting, semantics all aimed at some notion of understanding what intentions the observer will ascribe to an agent by observing its behavior. This is also true for the recent works on “security” and “privacy” of plans which are also trying to answer the same question, but from the opposite point of view – i. e. when the agent is trying to hide instead of reveal its intentions. This paper attempts to provide a workable taxonomy of relevant concepts in this exciting and emerging field of inquiry.

ICAPS Conference 2018 Conference Paper

CHAP-E: A Plan Execution Assistant for Pilots

• J. Benton 0001
• David E. Smith 0001
• John Kaneshige
• Leslie Keely
• Thomas Stucky

Pilots have benefited from ever-increasing and evolving automation techniques for many decades. This automation has allowed pilots to handle increasingly complex aircraft with greater safety, precision, and reduced workload. Unfortunately, it can also lead to misunderstandings and loss of situational awareness. In the face of malfunctions or unexpected events, pilots sometimes have an unclear picture of the situation and what to do next or must find and follow written procedures that do not take into account all the details of the particular situation. Pilots may also incorrectly assume the mode or state of an automated system and fail to perform certain necessary actions that they assumed the automated system would handle. To help alleviate these issues, we introduce the Cockpit Hierarchical Activity Planning and Execution CHAP-E system. CHAP-E provides pilots with intuitive graphical guidance on what actions need to be performed and when they need to be performed based on the aircraft and automation state, and projection of this state into the future. This assists pilots in both nominal and off-nominal flight situations.

ECAI Conference 2016 Conference Paper

Delete-Free Reachability Analysis for Temporal and Hierarchical Planning

• Arthur Bit-Monnot
• David E. Smith 0001
• Minh Do

Reachability analysis is a crucial part of the heuristic computation for many state of the art classical and temporal planners. In this paper, we study the difficulty that arises in assessing the reachability of actions in planning problems containing sets of interdependent actions, notably including problems with required concurrency as well as hierarchical planning problems. We show the limitation of state-of-the-art techniques and propose a new method suitable for both temporal and hierarchical planning problems. Our proposal is evaluated on FAPE, a constraint-based temporal planner. A long version of this paper was presented at the HSDIP workshop [1].

IROS Conference 2015 Conference Paper

Planning for serendipity

• Tathagata Chakraborti
• Gordon Briggs
• Kartik Talamadupula
• Yu Zhang 0055
• Matthias Scheutz
• David E. Smith 0001
• Subbarao Kambhampati

Recently there has been a lot of focus on human robot co-habitation issues that are often orthogonal to many aspects of human-robot teaming; e. g. on producing socially acceptable behaviors of robots and de-conflicting plans of robots and humans in shared environments. However, an interesting offshoot of these settings that has largely been overlooked is the problem of planning for serendipity - i. e. planning for stigmergic collaboration without explicit commitments on agents in co-habitation. In this paper we formalize this notion of planning for serendipity for the first time, and provide an Integer Programming based solution for this problem. Further, we illustrate the different modes of this planning technique on a typical Urban Search and Rescue scenario and show a real-life implementation of the ideas on the Nao Robot interacting with a human colleague.

ICAPS Conference 2006 Conference Paper

Sequential Monte Carlo in Probabilistic Planning Reachability Heuristics

• Daniel Bryce
• Subbarao Kambhampati
• David E. Smith 0001

The current best conformant probabilistic planners encode the problem as a bounded length CSP or SAT problem. While these approaches can find optimal solutions for given plan lengths, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms CSP/SAT techniques (especially when a 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 the distribution over reachable relaxed planning graph layers. Computing these distributions is costly, so we apply Sequential Monte Carlo to approximate them. We demonstrate on several domains how our approach enables our planner to far out-scale existing (optimal) probabilistic planners and still find reasonable quality solutions.

ICAPS Conference 2004 Conference Paper

Choosing Objectives in Over-Subscription Planning

• David E. Smith 0001

Many NASA planning problems are over-subscription problems — that is, there are a large number of possible goals of differing value, and the planning system must choose a subset that can be accomplished within the limited time and resources available. Examples include planning for telescopes like Hubble, SIRTF, and SOFIA; scheduling for the Deep Space Network; and planning science experiments for a Mars rover. Unfortunately, existing planning systems are not designed to deal with problems like this — they expect a well-defined conjunctive goal and terminate in failure unless the entire goal can be achieved. In this paper we develop techniques for over-subscription problems that assist a classical planner in choosing which goals to achieve, and the order in which to achieve them. These techniques use plan graph cost-estimation techniques to construct an orienteering problem, which is then used to provide heuristic advice on the goals and goal order that should be considered by a planner.

UAI Conference 2003 Conference Paper

Optimal Limited Contingency Planning

• Nicolas Meuleau
• David E. Smith 0001

ICAPS Conference 2002 Conference Paper

Fragment-based Conformant Planning

• James Kurien
• P. Pandurang Nayak
• David E. Smith 0001

With complex systems such as spacecraft, we often need to achieve goals even though failures prevent the exact state of the system from being determined. Conformant planning is the problem of generating a plan that moves a system from any of a number of possible initial states to a goal state, given that actions may have uncertain outcomes and sensing is unavailable. Two existing approaches to conformant planning are to consider the effects of actions in all worlds simultaneously, or to generate a plan in one world and test it in the remaining worlds. In contrast, in this work we attempt to find a plan for one world and extend it to work in all worlds. This approach is motivated by the desire to find conformant plans when one exists and partially conformant plans when one does not. It can be implemented with many underlying planning approaches and search strategies, and can be used in an anytime manner. We show that on a familiar conformant planning domain this approach is competitive with all but the fastest planners on serial problems and dominant on problems where a parallel plan is required.

UAI Conference 2002 Conference Paper

Planning under Continuous Time and Resource Uncertainty: A Challenge for AI

• John L. Bresina
• Richard Dearden
• Nicolas Meuleau
• Sailesh Ramakrishnan
• David E. Smith 0001
• Richard Washington

We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world problems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.

ICAPS Conference 2002 Conference Paper

The Logic of Reachability

• David E. Smith 0001
• Ari K. Jónsson

In recent years, Graphplan style reachability analysis and mutual exclusion reasoning have been used in many high performance planning systems. While numerous refinements and extensions have been developed, the basic plan graph structure and reasoning mechanisms used in these systems are tied to the very simple STRIPS model of action. In 1999, Smith and Weld generalized the Graphplan methods for reachability and mutex reasoning to allow actions to have differing durations. However, the representation of actions still has some severe limitations that prevent the use of these techniques for many real-world planning systems. In this paper, we 1) develop a logical notion of reachability that is independent of the particular representation and inference methods used in Graphplan, and 2) extend the notions of reachability and mutual exclusion to more general notions of time and action. As it turns out, the general rules for mutual exclusion reasoning take on a remarkably clean and simple form. However, practical instantiations of them turn out to be messy, and require that we make representation and reasoning choices.

ICAPS Conference 1998 Conference Paper

Conditional Effects in Graphplan

• Corin R. Anderson
• David E. Smith 0001
• Daniel S. Weld

Graphplanhas attracted considerable interest because of its extremelyhigh performance, but the algorithm’s inability to handle action representations moreexpressive than STRIPSis a major limitation. In particular, extending Graphplanto handle conditional effects is a surprisingly subtle enterprise. In this paper, we describe the space of possible alternatives, and then concentrate on one particular approach we call factored expansion. Factored expansion splits an action with conditional effects into several newactions called components, one for each conditional effect. Because these action components are not independent, factored expansion complicates both the mutual exclusion and backwardchaining phases of Graphplan. As compensation, factored expansion often produces dramatically smaller domainmodels than does the more obvious full-expansion into exclusive STRIPSactions. Wepresent experimental results showingthat factored expansion dominatesfull expansion on large problems.

ICAPS Conference 1996 Conference Paper

Suspending Recursion in Causal-Link Planning

• David E. Smith 0001
• Mark A. Peot

We present a strategy tbr suspending recursive open conditions during planning. We also show conditions under which plans with suspended open conditions can be pruned. To make this suspension and pruning strategy efficient, we use an operator graph to analyze potential recursion before the planning process begins. This approach covers a broader range of recursive problems than the approaches of Morris and Kambhampati, and is much more tractable than Kambhampati’s approach. We give experimental results that indicate I) significant improvement on recursive problems and 2) negligible overhead when applied to recursive and non-recursive problems alike.