Subbarao Kambhampati

AAMAS Conference 2026 Conference Paper

Nested Training for Mutual Adaptation in Human-AI Teaming

• Upasana Biswas
• Durgesh Kalwar
• Subbarao Kambhampati
• Sarath Sreedharan

Mutual adaptation is essential in human–robot teaming, as humans adjust their behavior in response to the robot. Prior work trains against diverse but static partners, missing adaptive human responses, while simultaneous multi-agent learning often yields brittle coordination conventions that fail to generalize. We model human–robot teaming as a finite-Level Interactive Partially Observable Markov Decision Process (I-POMDP), explicitly representing human adaptation within the state. To approximately solve this formulation, we introduce a nested training regime in which agents at a level are trained against adaptive agents at a level below. This exposes agents to adaptation while preventing emergence of opaque coordination strategies. In the Overcooked domain with required-cooperation, our method outperforms standard baselines with unseen adaptive partners and demonstrates stronger adaptability during interaction.

AAAI Conference 2026 Conference Paper

Who Is Helping Whom? Analyzing Inter-Dependencies to Evaluate Cooperation in Human-AI Teaming

• Upasana Biswas
• Vardhan Palod
• Siddhant Bhambri
• Subbarao Kambhampati

State-of-the-art methods for Human-AI Teaming and Zero-shot Cooperation focus on task completion i.e. task rewards, as the sole evaluation metric while being agnostic to `how' the two agents work with each other. Furthermore, subjective user studies only offer limited insight into the quality of cooperation existing within the team. Specifically, we are interested in understanding the cooperative behaviors arising within the team when trained agents are paired with humans - a problem that has been overlooked by the existing literature. To formally address this problem, we propose the concept of constructive interdependence - measuring how much agents rely on each other’s actions to achieve the shared goal - as a key metric for evaluating cooperation in human-agent teams. We measure interdependence in terms of action interactions in a STRIPS formalism, and define metrics that allow us to assess the degree of reliance between the agents' actions. We pair state-of-the-art agents with learned human models as well as human participants in a user study for the popular Overcooked domain, and evaluate the task reward and teaming performance for these human-agent teams. While prior work has claimed that state-of-the-art agents exhibit cooperative behavior based on their high task rewards, our results reveal that these agents often fail to induce cooperation, as evidenced by consistently low interdependence across teams. Furthermore, our analysis reveals that teaming performance is not necessarily correlated with task reward, highlighting that task reward alone cannot reliably measure cooperation arising in a human-agent team.

TMLR Journal 2025 Journal Article

A Systematic Evaluation of the Planning and Scheduling Abilities of the Reasoning Model o1

• Karthik Valmeekam
• Kaya Stechly
• Atharva Gundawar
• Subbarao Kambhampati

OpenAI claims that their recent o1 (Strawberry) model has been specifically constructed and trained to escape the normal limitations of autoregressive Large Language Models (LLMs)–making it a new kind of model: a Large Reasoning Model (LRM)–and be generally capable of tackling procedural reasoning tasks. We present the first comprehensive evaluation of these models on the fundamental tasks of planning and scheduling. Previous research attempted to use LLMs’ expressive generation capabilities to solve these problems, but met with only limited success. We fill in the gaps in this literature by testing a larger suite of state-of-the-art LLMs on a set of large benchmarks, and then use this as a baseline to evaluate o1-preview and o1-mini. We see that while they can offer significant accuracy improvements over LLMs, this single metric is misleading and incomplete, as LRM queries demand large and unpredictable costs and take significant amounts of time to complete. We provide a case study demonstrating that, at those same price points, other methods of inference time scaling can do just as well. We also show that, contrary to OpenAI’s injunctions, o1’s performance can be improved further by embedding it in compound systems that separately, but complementarily, scale inference time further. Finally, while the paper is focused on o1, we provide similar evaluations of a more recent (and open-weight) LRM -- DeepSeek R1.

TMLR Journal 2025 Journal Article

Do Think Tags Really Help LLMs Plan? A Critical Evaluation of ReAct-Style Prompting

• Siddhant Bhambri
• Mudit Verma
• Subbarao Kambhampati

The reasoning abilities of Large Language Models (LLMs) remain a topic of considerable interest and debate. Among the original papers arguing for emergent reasoning abilities of LLMs, ReAct became particularly popular by claiming to tease out LLM reasoning abilities with special prompting involving “interleaving reasoning trace with action execution". In this paper, we critically examine the claims of ReAct style prompting for planning and sequential decision-making problems. By introducing systematic variations to the input prompt, we perform a sensitivity analysis along the original claims of ReAct. Our experiments in AlfWorld and WebShop, domains that were used in the original ReAct work, show that the performance is minimally influenced by the interleaved reasoning trace or by the content of these generated reasoning traces. Instead, the performance of LLMs is primarily driven by the unreasonably high degree of similarity between input example tasks and queries, with shockingly little ability to generalize. In addition to raising questions on claims about reasoning abilities, this lack of generalization also implicitly forces the prompt designer to provide instance-specific examples, significantly increasing the cognitive burden on the human. Our empirical results show that the perceived reasoning abilities of LLMs stem from the exemplar-query similarity and approximate retrieval rather than any inherent reasoning abilities, thereby leading to severe lack of generalization beyond the few-shot examples given in the prompts. Our code and prompt settings can be found here on GitHub.

AIJ Journal 2025 Journal Article

Explain it as simple as possible, but no simpler – Explanation via model simplification for addressing inferential gap

• Sarath Sreedharan
• Siddharth Srivastava
• Subbarao Kambhampati

One of the core challenges of explaining decisions made by modern AI systems is the need to address the potential gap in the inferential capabilities of the system generating the decision and the user trying to make sense of it. This inferential capability gap becomes even more critical when it comes to explaining sequential decisions. While there have been some isolated efforts at developing explanation methods suited for complex decision-making settings, most of these current efforts are limited in scope. In this paper, we introduce a general framework for generating explanations in the presence of inferential capability gaps. A framework that is grounded in the generation of simplified representations of the agent model through the application of a sequence of model simplifying transformations. This framework not only allows us to develop an extremely general explanation generation algorithm, but we see that many of the existing works in this direction could be seen as specific instantiations of our more general method. While the ideas presented in this paper are general enough to be applied to any decision-making framework, we will focus on instantiating the framework in the context of stochastic planning problems. As a part of this instantiation, we will also provide an exhaustive characterization of explanatory queries and an analysis of various classes of applicable transformations. We will evaluate the effectiveness of transformation-based explanations through both synthetic experiments and user studies.

IJCAI Conference 2025 Conference Paper

Explain It as Simple as Possible, but No Simpler – Explanation via Model Simplification for Addressing Inferential Gap (Abstract Reprint)

• Sarath Sreedharan
• Siddharth Srivastava
• Subbarao Kambhampati

One of the core challenges of explaining decisions made by modern AI systems is the need to address the potential gap in the inferential capabilities of the system generating the decision and the user trying to make sense of it. This inferential capability gap becomes even more critical when it comes to explaining sequential decisions. While there have been some isolated efforts at developing explanation methods suited for complex decision-making settings, most of these current efforts are limited in scope. In this paper, we introduce a general framework for generating explanations in the presence of inferential capability gaps. A framework that is grounded in the generation of simplified representations of the agent model through the application of a sequence of model simplifying transformations. This framework not only allows us to develop an extremely general explanation generation algorithm, but we see that many of the existing works in this direction could be seen as specific instantiations of our more general method. While the ideas presented in this paper are general enough to be applied to any decision-making framework, we will focus on instantiating the framework in the context of stochastic planning problems. As a part of this instantiation, we will also provide an exhaustive characterization of explanatory queries and an analysis of various classes of applicable transformations. We will evaluate the effectiveness of transformation-based explanations through both synthetic experiments and user studies.

ICLR Conference 2025 Conference Paper

On the self-verification limitations of large language models on reasoning and planning tasks

• Kaya Stechly
• Karthik Valmeekam
• Subbarao Kambhampati

There has been considerable divergence of opinion on the reasoning abilities of Large Language Models (LLMs). While the initial optimism that reasoning might emerge automatically with scale has been tempered thanks to a slew of counterexamples--ranging from multiplication to simple planning--there persists a wide spread belief that LLMs can self-critique and improve their own solutions in an iterative fashion. This belief seemingly rests on the assumption that verification of correctness should be easier than generation--a rather classical argument from computational complexity--which should be irrelevant to LLMs to the extent that what they are doing is approximate retrieval. In this paper, we set out to systematically investigate the effectiveness of iterative prompting in the context of reasoning and planning. We present a principled empirical study of the performance of GPT-4 in three domains: Game of 24, Graph Coloring, and STRIPS planning. We experiment both with the model critiquing its own answers and with an external correct reasoner verifying proposed solutions. In each case, we analyze whether the content of criticisms actually affects bottom line performance, and whether we can ablate elements of the augmented system without losing performance. We observe significant performance collapse with self-critique and significant performance gains with sound external verification. We also note that merely re-prompting with a sound verifier maintains most of the benefits of more involved setups.

NeurIPS Conference 2024 Conference Paper

Chain of Thoughtlessness? An Analysis of CoT in Planning

• Kaya Stechly
• Karthik Valmeekam
• Subbarao Kambhampati

Large language model (LLM) performance on reasoning problems typically does not generalize out of distribution. Previous work has claimed that this can be mitigated with chain of thought prompting--a method of demonstrating solution procedures--with the intuition that it is possible to in-context teach an LLM an algorithm for solving the problem. This paper presents a case study of chain of thought on problems from Blocksworld, a classical planning domain, and examines the performance of two state-of-the-art LLMs across two axes: generality of examples given in prompt, and complexity of problems queried with each prompt. While our problems are very simple, we only find meaningful performance improvements from chain of thought prompts when those prompts are exceedingly specific to their problem class, and that those improvements quickly deteriorate as the size n of the query-specified stack grows past the size of stacks shown in the examples. We also create scalable variants of three domains commonly studied in previous CoT papers and demonstrate the existence of similar failure modes. Our results hint that, contrary to previous claims in the literature, CoT's performance improvements do not stem from the model learning general algorithmic procedures via demonstrations but depend on carefully engineering highly problem specific prompts. This spotlights drawbacks of chain of thought, especially the sharp tradeoff between possible performance gains and the amount of human labor necessary to generate examples with correct reasoning traces.

AAAI Conference 2024 Conference Paper

Learning from Ambiguous Demonstrations with Self-Explanation Guided Reinforcement Learning

• Yantian Zha
• Lin Guan
• Subbarao Kambhampati

Our work aims at efficiently leveraging ambiguous demonstrations for the training of a reinforcement learning (RL) agent. An ambiguous demonstration can usually be interpreted in multiple ways, which severely hinders the RL agent from learning stably and efficiently. Since an optimal demonstration may also suffer from being ambiguous, previous works that combine RL and learning from demonstration (RLfD works) may not work well. Inspired by how humans handle such situations, we propose to use self-explanation (an agent generates explanations for itself) to recognize valuable high-level relational features as an interpretation of why a successful trajectory is successful. This way, the agent can leverage the explained important relations as guidance for its RL learning. Our main contribution is to propose the Self-Explanation for RL from Demonstrations (SERLfD) framework, which can overcome the limitations of existing RLfD works. Our experimental results show that an RLfD model can be improved by using our SERLfD framework in terms of training stability and performance. To foster further research in self-explanation-guided robot learning, we have made our demonstrations and code publicly accessible at https://github.com/YantianZha/SERLfD. For a deeper understanding of our work, interested readers can refer to our arXiv version at https://arxiv.org/pdf/2110.05286.pdf, including an accompanying appendix.

AIJ Journal 2024 Journal Article

Planning with mental models – Balancing explanations and explicability

• Sarath Sreedharan
• Tathagata Chakraborti
• Christian Muise
• Subbarao Kambhampati

Human-aware planning involves generating plans that are explicable, i. e. conform to user expectations, as well as providing explanations when such plans cannot be found. In this paper, we bring these two concepts together and show how an agent can achieve a trade-off between these two competing characteristics of a plan. To achieve this, we conceive a first-of-its-kind planner MEGA that can reason about the possibility of explaining a plan in the plan generation process itself. We will also explore how solutions to such problems can be expressed as “self-explaining plans” – and show how this representation allows us to leverage classical planning compilations of epistemic planning to reason about this trade-off at plan generation time without having to incur the computational burden of having to search in the space of differences between the agent model and the mental model of the human in the loop in order to come up with the optimal trade-off. We will illustrate these concepts in two well-known planning domains, as well as with a robot in a typical search and reconnaissance task. Human factor studies in the latter highlight the usefulness of the proposed approach.

ICML Conference 2024 Conference Paper

Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks

• Subbarao Kambhampati
• Karthik Valmeekam
• Lin Guan 0003
• Mudit Verma
• Kaya Stechly
• Siddhant Bhambri
• Lucas Saldyt
• Anil Murthy

We argue that auto-regressive LLMs cannot, by themselves, do planning or self-verification (which is after all a form of reasoning), and shed some light on the reasons for misunderstandings in the literature. We will also argue that LLMs should be viewed as universal approximate knowledge sources that have much more meaningful roles to play in planning/reasoning tasks beyond simple front-end/back-end format translators. We present a vision of LLM-Modulo Frameworks that combine the strengths of LLMs with external model-based verifiers in a tighter bi-directional interaction regime. We will show how the models driving the external verifiers themselves can be acquired with the help of LLMs. We will also argue that rather than simply pipelining LLMs and symbolic components, this LLM-Modulo Framework provides a better neuro-symbolic approach that offers tighter integration between LLMs and symbolic components, and allows extending the scope of model-based planning/reasoning regimes towards more flexible knowledge, problem and preference specifications.

AAAI Conference 2024 Conference Paper

‘Why Didn’t You Allocate This Task to Them?’ Negotiation-Aware Task Allocation and Contrastive Explanation Generation

• Zahra Zahedi
• Sailik Sengupta
• Subbarao Kambhampati

In this work, we design an Artificially Intelligent Task Allocator (AITA) that proposes a task allocation for a team of humans. A key property of this allocation is that when an agent with imperfect knowledge (about their teammate's costs and/or the team's performance metric) contests the allocation with a counterfactual, a contrastive explanation can always be provided to showcase why the proposed allocation is better than the proposed counterfactual. For this, we consider a negotiation process that produces a negotiation-aware task allocation and, when contested, leverages a negotiation tree to provide a contrastive explanation. With human subject studies, we show that the proposed allocation indeed appears fair to a majority of participants and, when not, the explanations generated are judged as convincing and easy to comprehend.

AAMAS Conference 2023 Conference Paper

'Why didn't you allocate this task to them? ' Negotiation-Aware Explicable Task Allocation and Contrastive Explanation Generation

• Zahra Zahedi
• Sailik Sengupta
• Subbarao Kambhampati

In this work, we design an Artificially Intelligent Task Allocator (AITA) that proposes a task allocation for multi-agent systems especially with humans. A key property of this allocation is that when an agent with imperfect knowledge (about their teammate’s costs and/or the team’s performance metric) questions the allocation by contesting with a counterfactual, a contrastive explanation is provided to answer their challenge. For this, we consider a negotiation process that produces a negotiation-aware task allocation and, in turn, leverages a negotiation tree to provide a contrastive explanation. With human subject studies, we show that the proposed allocation indeed appears fair to a majority of participants, and the explanations generated are easy to comprehend and convincing.

ICAPS Conference 2023 Conference Paper

Generalizing Action Justification and Causal Links to Policies

• Sarath Sreedharan
• Christian J. Muise
• Subbarao Kambhampati

We revisit two concepts popularly used within the context of classical planning, namely action justification and causal links. While these concepts have come to underpin some of the most popular notions of explanations in classical planning, these notions are restricted to sequential plans. To address this shortcoming, we propose a generalization of these concepts that is applicable to state-action policies. We introduce algorithms that can identify justified actions and causal links contributed by such actions for policies generated for Fully Observable Non-Deterministic (FOND) planning problems. We also present an empirical evaluation that demonstrates the computational characteristics of these algorithms on standard FOND benchmarks.

IJCAI Conference 2023 Conference Paper

Gradient-Based Mixed Planning with Symbolic and Numeric Action Parameters (Extended Abstract)

• Kebing Jin
• Hankz Hankui Zhuo
• Zhanhao Xiao
• Hai Wan
• Subbarao Kambhampati

Dealing with planning problems with both logical relations and numeric changes in real-world dynamic environments is challenging. Existing numeric planning systems for the problem often discretize numeric variables or impose convex constraints on numeric variables, which harms the performance when solving problems, especially when the problems contain obstacles and non-linear numeric effects. In this work, we propose a novel algorithm framework to solve numeric planning problems mixed with logical relations and numeric changes based on gradient descent. We cast the numeric planning with logical relations and numeric changes as an optimization problem. Specifically, we extend the syntax to allow parameters of action models to be either objects or real-valued numbers, which enhances the ability to model real-world numeric effects. Based on the extended modeling language, we propose a gradient-based framework to simultaneously optimize numeric parameters and compute appropriate actions to form candidate plans. The gradient-based framework is composed of an algorithmic heuristic module based on propositional operations to select actions and generate constraints for gradient descent, an algorithmic transition module to update states to the next ones, and a loss module to compute loss. We repeatedly minimize loss by updating numeric parameters and compute candidate plans until it converges into a valid plan for the planning problem.

NeurIPS Conference 2023 Conference Paper

Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning

• Lin Guan
• Karthik Valmeekam
• Sarath Sreedharan
• Subbarao Kambhampati

There is a growing interest in applying pre-trained large language models (LLMs) to planning problems. However, methods that use LLMs directly as planners are currently impractical due to several factors, including limited correctness of plans, strong reliance on feedback from interactions with simulators or even the actual environment, and the inefficiency in utilizing human feedback. In this work, we introduce a novel alternative paradigm that constructs an explicit world (domain) model in planning domain definition language (PDDL) and then uses it to plan with sound domain-independent planners. To address the fact that LLMs may not generate a fully functional PDDL model initially, we employ LLMs as an interface between PDDL and sources of corrective feedback, such as PDDL validators and humans. For users who lack a background in PDDL, we show that LLMs can translate PDDL into natural language and effectively encode corrective feedback back to the underlying domain model. Our framework not only enjoys the correctness guarantee offered by the external planners but also reduces human involvement by allowing users to correct domain models at the beginning, rather than inspecting and correcting (through interactive prompting) every generated plan as in previous work. On two IPC domains and a Household domain that is more complicated than commonly used benchmarks such as ALFWorld, we demonstrate that GPT-4 can be leveraged to produce high-quality PDDL models for over 40 actions, and the corrected PDDL models are then used to successfully solve 48 challenging planning tasks. Resources, including the source code, are released at: https: //guansuns. github. io/pages/llm-dm.

AAMAS Conference 2023 Conference Paper

Methods and Mechanisms for Interactive Novelty Handling in Adversarial Environments

• Tung Thai
• Mudit Verma
• Utkarsh Soni
• Sriram Gopalakrishnan
• Ming Shen
• Mayank Garg
• Ayush Kalani
• Nakul Vaidya

Learning to detect, characterize and accommodate novelties is a challenge that agents operating in open-world domains need to address to achieve satisfactory task performance. We sketch general methods for detecting and characterizing different types of novelties, and for building an appropriate adaptive model to accommodate them utilizing logical representations and reasoning methods in stochastic partially observable multi-agent environments. We also briefly report results from evaluations of our algorithms in the game domain of Monopoly. The results show high novelty detection and accommodation rates.

NeurIPS Conference 2023 Conference Paper

On the Planning Abilities of Large Language Models - A Critical Investigation

• Karthik Valmeekam
• Matthew Marquez
• Sarath Sreedharan
• Subbarao Kambhampati

Intrigued by the claims of emergent reasoning capabilities in LLMs trained on general web corpora, in this paper, we set out to investigate their planning capabilities. We aim to evaluate (1) the effectiveness of LLMs in generating plans autonomously in commonsense planning tasks and (2) the potential of LLMs as a source of heuristic guidance for other agents (AI planners) in their planning tasks. We conduct a systematic study by generating a suite of instances on domains similar to the ones employed in the International Planning Competition and evaluate LLMs in two distinct modes: autonomous and heuristic. Our findings reveal that LLMs’ ability to generate executable plans autonomously is rather limited, with the best model (GPT-4) having an average success rate of ~12% across the domains. However, the results in the heuristic mode show more promise. In the heuristic mode, we demonstrate that LLM-generated plans can improve the search process for underlying sound planners and additionally show that external verifiers can help provide feedback on the generated plans and back-prompt the LLM for better plan generation.

NeurIPS Conference 2023 Conference Paper

PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change

• Karthik Valmeekam
• Matthew Marquez
• Alberto Olmo
• Sarath Sreedharan
• Subbarao Kambhampati

Generating plans of action, and reasoning about change have long been considered a core competence of intelligent agents. It is thus no surprise that evaluating the planning and reasoning capabilities of large language models (LLMs) has become a hot topic of research. Most claims about LLM planning capabilities are however based on common sense tasks–where it becomes hard to tell whether LLMs are planning or merely retrieving from their vast world knowledge. There is a strong need for systematic and extensible planning benchmarks with sufficient diversity to evaluate whether LLMs have innate planning capabilities. Motivated by this, we propose PlanBench, an extensible benchmark suite based on the kinds of domains used in the automated planning community, especially in the International Planning Competition, to test the capabilities of LLMs in planning or reasoning about actions and change. PlanBench provides sufficient diversity in both the task domains and the specific planning capabilities. Our studies also show that on many critical capabilities–including plan generation–LLM performance falls quite short, even with the SOTA models. PlanBench can thus function as a useful marker of progress of LLMs in planning and reasoning.

ICLR Conference 2023 Conference Paper

Relative Behavioral Attributes: Filling the Gap between Symbolic Goal Specification and Reward Learning from Human Preferences

• Lin Guan 0003
• Karthik Valmeekam
• Subbarao Kambhampati

Generating complex behaviors that satisfy the preferences of non-expert users is a crucial requirement for AI agents. Interactive reward learning from trajectory comparisons (a.k.a. RLHF) is one way to allow non-expert users to convey complex objectives by expressing preferences over short clips of agent behaviors. Even though this parametric method can encode complex tacit knowledge present in the underlying tasks, it implicitly assumes that the human is unable to provide richer feedback than binary preference labels, leading to intolerably high feedback complexity and poor user experience. While providing a detailed symbolic closed-form specification of the objectives might be tempting, it is not always feasible even for an expert user. However, in most cases, humans are aware of how the agent should change its behavior along meaningful axes to fulfill their underlying purpose, even if they are not able to fully specify task objectives symbolically. Using this as motivation, we introduce the notion of Relative Behavioral Attributes, which allows the users to tweak the agent behavior through symbolic concepts (e.g., increasing the softness or speed of agents' movement). We propose two practical methods that can learn to model any kind of behavioral attributes from ordered behavior clips. We demonstrate the effectiveness of our methods on four tasks with nine different behavioral attributes, showing that once the attributes are learned, end users can produce desirable agent behaviors relatively effortlessly, by providing feedback just around ten times. This is over an order of magnitude less than that required by the popular learning-from-human-preferences baselines. The supplementary video and source code are available at: https://guansuns.github.io/pages/rba.

ICLR Conference 2022 Conference Paper

Bridging the Gap: Providing Post-Hoc Symbolic Explanations for Sequential Decision-Making Problems with Inscrutable Representations

• Sarath Sreedharan
• Utkarsh Soni
• Mudit Verma
• Siddharth Srivastava 0001
• Subbarao Kambhampati

As increasingly complex AI systems are introduced into our daily lives, it becomes important for such systems to be capable of explaining the rationale for their decisions and allowing users to contest these decisions. A significant hurdle to allowing for such explanatory dialogue could be the {\em vocabulary mismatch} between the user and the AI system. This paper introduces methods for providing contrastive explanations in terms of user-specified concepts for sequential decision-making settings where the system's model of the task may be best represented as an inscrutable model. We do this by building partial symbolic models of a local approximation of the task that can be leveraged to answer the user queries. We test these methods on a popular Atari game (Montezuma's Revenge) and variants of Sokoban (a well-known planning benchmark) and report the results of user studies to evaluate whether people find explanations generated in this form useful.

AIJ Journal 2022 Journal Article

Gradient-based mixed planning with symbolic and numeric action parameters

• Kebing Jin
• Hankz Hankui Zhuo
• Zhanhao Xiao
• Hai Wan
• Subbarao Kambhampati

Dealing with planning problems with both logical relations and numeric changes in real-world dynamic environments is challenging. Existing numeric planning systems for the problem often discretize numeric variables or impose convex constraints on numeric variables, which harms the performance when solving problems. In this paper, we propose a novel algorithm framework to solve numeric planning problems mixed with logical relations and numeric changes based on gradient descent. We cast the numeric planning with logical relations and numeric changes as an optimization problem. Specifically, we extend syntax to allow parameters of action models to be either objects or real-valued numbers, which enhances the ability to model real-world numeric effects. Based on the extended modeling language, we propose a gradient-based framework to simultaneously optimize numeric parameters and compute appropriate actions to form candidate plans. The gradient-based framework is composed of an algorithmic heuristic module based on propositional operations to select actions and generate constraints for gradient descent, an algorithmic transition module to update states to next ones, and a loss module to compute loss. We repeatedly minimize loss by updating numeric parameters and compute candidate plans until it converges into a valid plan for the planning problem. In the empirical study, we exhibit that our algorithm framework is both effective and efficient in solving planning problems mixed with logical relations and numeric changes, especially when the problems contain obstacles and non-linear numeric effects.

AIJ Journal 2022 Journal Article

Imperfect ImaGANation: Implications of GANs exacerbating biases on facial data augmentation and snapchat face lenses

• Niharika Jain
• Alberto Olmo
• Sailik Sengupta
• Lydia Manikonda
• Subbarao Kambhampati

In this paper, we show that popular Generative Adversarial Network (GAN) variants exacerbate biases along the axes of gender and skin tone in the generated data. The use of synthetic data generated by GANs is widely used for a variety of tasks ranging from data augmentation to stylizing images. While practitioners celebrate this method as an economical way to obtain synthetic data to train data-hungry machine learning models or provide new features to users of mobile applications, it is unclear whether they recognize the perils of such techniques when applied to real world datasets biased along latent dimensions. Although one expects GANs to replicate the distribution of the original data, in real-world settings with limited data and finite network capacity, GANs suffer from mode collapse. First, we show readily-accessible GAN variants such as DCGANs ‘imagine’ faces of synthetic engineering professors that have masculine facial features and fair skin tones. When using popular GAN architectures that attempt to address mode-collapse, we observe that these variants either provide a false sense of security or suffer from other inherent limitations due to their design choice. Second, we show that a conditional GAN variant transforms input images of female and nonwhite faces to have more masculine features and lighter skin when asked to generate faces of engineering professors. Worse yet, prevalent filters on Snapchat end up consistently lightening the skin tones in people of color when trying to make face images appear more feminine. Thus, our study is meant to serve as a cautionary tale for practitioners and educate them about the side-effect of bias amplification when applying GAN-based techniques.

ICML Conference 2022 Conference Paper

Leveraging Approximate Symbolic Models for Reinforcement Learning via Skill Diversity

• Lin Guan 0003
• Sarath Sreedharan
• Subbarao Kambhampati

Creating reinforcement learning (RL) agents that are capable of accepting and leveraging task-specific knowledge from humans has been long identified as a possible strategy for developing scalable approaches for solving long-horizon problems. While previous works have looked at the possibility of using symbolic models along with RL approaches, they tend to assume that the high-level action models are executable at low level and the fluents can exclusively characterize all desirable MDP states. Symbolic models of real world tasks are however often incomplete. To this end, we introduce Approximate Symbolic-Model Guided Reinforcement Learning, wherein we will formalize the relationship between the symbolic model and the underlying MDP that will allow us to characterize the incompleteness of the symbolic model. We will use these models to extract high-level landmarks that will be used to decompose the task. At the low level, we learn a set of diverse policies for each possible task subgoal identified by the landmark, which are then stitched together. We evaluate our system by testing on three different benchmark domains and show how even with incomplete symbolic model information, our approach is able to discover the task structure and efficiently guide the RL agent towards the goal.

AAMAS Conference 2022 Conference Paper

Minimizing Robot Navigation Graph for Position-Based Predictability by Humans

• Sriram Gopalakrishnan
• Subbarao Kambhampati

When multiple humans and robots are moving in spaces like restaurants, hospitals, or banks, making the robot’s movements easy to predict can help the humans co-navigate the space with the robots. Since people would be busy with their own goals, they are not paying close attention to the prior movements, or goals of multiple robots. So predictability from the robot’s current position alone would help. With this in mind, we propose using an algorithm to lay out fixed paths for the different tasks the robots would do, such that predictability from only the current position alone is optimized, and motion costs are kept within acceptable bounds.

IJCAI Conference 2022 Conference Paper

On the Computational Complexity of Model Reconciliations

• Sarath Sreedharan
• Pascal Bercher
• Subbarao Kambhampati

Model-reconciliation explanation is a popular framework for generating explanations for planning problems. While the framework has been extended to multiple settings since its introduction for classical planning problems, there is little agreement on the computational complexity of generating minimal model reconciliation explanations in the basic setting. In this paper, we address this lacuna by introducing a decision-version of the model-reconciliation explanation generation problem and we show that it is Sigma-2-P Complete.

ICAPS Conference 2022 Conference Paper

RADAR-X: An Interactive Mixed Initiative Planning Interface Pairing Contrastive Explanations and Revised Plan Suggestions

• Karthik Valmeekam
• Sarath Sreedharan
• Sailik Sengupta
• Subbarao Kambhampati

Decision support systems seek to enable informed decision-making. In the recent years, automated planning techniques have been leveraged to empower such systems to better aid the human-in-the-loop. The central idea for such decision support systems is to augment the capabilities of the human-in-the-loop with automated planning techniques and enhance the quality of decision-making. In addition to providing planning support, effective decision support systems must be able to provide intuitive explanations based on specific user queries for proposed decisions to its end users. Using this as motivation, we present our decision support system RADAR-X that showcases the ability to engage the user in an interactive explanatory dialogue by first enabling them to specify an alternative to a proposed decision (which we refer to as foils), and then providing contrastive explanations to these user-specified foils which helps the user understand why a specific plan was chosen over the alternative (or foil). Furthermore, the system uses this dialogue to elicit the user's latent preferences and provides revised plan suggestions through three different interaction strategies.

AAAI Conference 2022 Conference Paper

Symbols as a Lingua Franca for Bridging Human-AI Chasm for Explainable and Advisable AI Systems

• Subbarao Kambhampati
• Sarath Sreedharan
• Mudit Verma
• Yantian Zha
• Lin Guan

Despite the surprising power of many modern AI systems that often learn their own representations, there is significant discontent about their inscrutability and the attendant problems in their ability to interact with humans. While alternatives such as neuro-symbolic approaches have been proposed, there is a lack of consensus on what they are about. There are often two independent motivations (i) symbols as a lingua franca for human-AI interaction and (ii) symbols as systemproduced abstractions used by the AI system in its internal reasoning. The jury is still out on whether AI systems will need to use symbols in their internal reasoning to achieve general intelligence capabilities. Whatever the answer there is, the need for (human-understandable) symbols in human-AI interaction seems quite compelling. Symbols, like emotions, may well not be sine qua non for intelligence per se, but they will be crucial for AI systems to interact with us humans – as we can neither turn off our emotions nor get by without our symbols. In particular, in many human-designed domains, humans would be interested in providing explicit (symbolic) knowledge and advice – and expect machine explanations in kind. This alone requires AI systems to to maintain a symbolic interface for interaction with humans. In this blue sky paper, we argue this point of view, and discuss research directions that need to be pursued to allow for this type of human-AI interaction.

IJCAI Conference 2021 Conference Paper

A Unifying Bayesian Formulation of Measures of Interpretability in Human-AI Interaction

• Sarath Sreedharan
• Anagha Kulkarni
• David Smith
• Subbarao Kambhampati

Existing approaches for generating human-aware agent behaviors have considered different measures of interpretability in isolation. Further, these measures have been studied under differing assumptions, thus precluding the possibility of designing a single framework that captures these measures under the same assumptions. In this paper, we present a unifying Bayesian framework that models a human observer's evolving beliefs about an agent and thereby define the problem of Generalized Human-Aware Planning. We will show that the definitions of interpretability measures like explicability, legibility and predictability from the prior literature fall out as special cases of our general framework. Through this framework, we also bring a previously ignored fact to light that the human-robot interactions are in effect open-world problems, particularly as a result of modeling the human's beliefs over the agent. Since the human may not only hold beliefs unknown to the agent but may also form new hypotheses about the agent when presented with novel or unexpected behaviors.

AIJ Journal 2021 Journal Article

Foundations of explanations as model reconciliation

• Sarath Sreedharan
• Tathagata Chakraborti
• Subbarao Kambhampati

Past work on plan explanations primarily involved the AI system explaining the correctness of its plan and the rationale for its decision in terms of its own model. Such soliloquy is wholly inadequate in most realistic scenarios where users have domain and task models that differ from that used by the AI system. We posit that the explanations are best studied in light of these differing models. In particular, we show how explanation can be seen as a “model reconciliation problem” (MRP), where the AI system in effect suggests changes to the user's mental model so as to make its plan be optimal with respect to that changed user model. We will study the properties of such explanations, present algorithms for automatically computing them, discuss relevant extensions to the basic framework, and evaluate the performance of the proposed algorithms both empirically and through controlled user studies.

IROS Conference 2021 Conference Paper

Not all users are the same: Providing personalized explanations for sequential decision making problems

• Utkarsh Soni
• Sarath Sreedharan
• Subbarao Kambhampati

There is a growing interest in designing robots that can work alongside humans. Such robots will undoubtedly be expected to explain their behavior and decisions. While generating explanations is an actively researched topic, most works tend to focus on methods that generate explanations that are one size fits all. As in the specifics of the user-model are completely ignored. The handful of works that look at tailoring their explanation to the user’s background rely on having specific models of the users (either analytic models or learned labeling models). The goal of this work is thus to propose an end-to-end adaptive explanation generation system that begins by learning the different types of users that the robot could interact with. Then during the interaction with the target user, it is tasked with identifying the type on the fly and adjust its explanations accordingly. The former is achieved by a data-driven clustering approach while for the latter, we compile our explanation generation problem into a POMDP. We demonstrate the usefulness of our system on two domains using state-of-the-art POMDP solvers. We also report the results of a user study that investigates the benefits of providing personalized explanations in a human-robot interaction setting.

AAAI Conference 2021 System Paper

RADAR-X: An Interactive Interface Pairing Contrastive Explanations with Revised Plan Suggestions

• Valmeekam Karthik
• Sarath Sreedharan
• Sailik Sengupta
• Subbarao Kambhampati

Automated Planning techniques can be leveraged to build effective decision support systems that assist and cooperate with the human-in-the-loop. Such systems must provide intuitive explanations when the suggestions made by these systems seem inexplicable to the human. In this regard, we consider scenarios where the user questions the system’s suggestion by providing alternatives (referred to as foils). In response, we empower existing decision support technologies to engage in an interactive explanatory dialogue with the user and provide contrastive explanations based on user-specified foils to reach a consensus on proposed decisions. To provide contrastive explanations, we adapt existing techniques in Explainable AI Planning (XAIP). Furthermore, we use this dialog to elicit the user’s latent preferences and propose three modes of interaction that use these preferences to provide revised plan suggestions. Finally, we showcase a decision support system that provides all these capabilities.

AIJ Journal 2021 Journal Article

Using state abstractions to compute personalized contrastive explanations for AI agent behavior

• Sarath Sreedharan
• Siddharth Srivastava
• Subbarao Kambhampati

There is a growing interest within the AI research community in developing autonomous systems capable of explaining their behavior to users. However, the problem of computing explanations for users of different levels of expertise has received little research attention. We propose an approach for addressing this problem by representing the user's understanding of the task as an abstraction of the domain model that the planner uses. We present algorithms for generating minimal explanations in cases where this abstract human model is not known. We reduce the problem of generating an explanation to a search over the space of abstract models and show that while the complete problem is NP-hard, a greedy algorithm can provide good approximations of the optimal solution. We empirically show that our approach can efficiently compute explanations for a variety of problems and also perform user studies to test the utility of state abstractions in explanations.

NeurIPS Conference 2021 Conference Paper

Widening the Pipeline in Human-Guided Reinforcement Learning with Explanation and Context-Aware Data Augmentation

• Lin Guan
• Mudit Verma
• Suna (Sihang) Guo
• Ruohan Zhang
• Subbarao Kambhampati

Human explanation (e. g. , in terms of feature importance) has been recently used to extend the communication channel between human and agent in interactive machine learning. Under this setting, human trainers provide not only the ground truth but also some form of explanation. However, this kind of human guidance was only investigated in supervised learning tasks, and it remains unclear how to best incorporate this type of human knowledge into deep reinforcement learning. In this paper, we present the first study of using human visual explanations in human-in-the-loop reinforcement learning (HIRL). We focus on the task of learning from feedback, in which the human trainer not only gives binary evaluative "good" or "bad" feedback for queried state-action pairs, but also provides a visual explanation by annotating relevant features in images. We propose EXPAND (EXPlanation AugmeNted feeDback) to encourage the model to encode task-relevant features through a context-aware data augmentation that only perturbs irrelevant features in human salient information. We choose five tasks, namely Pixel-Taxi and four Atari games, to evaluate the performance and sample efficiency of this approach. We show that our method significantly outperforms methods leveraging human explanation that are adapted from supervised learning, and Human-in-the-loop RL baselines that only utilize evaluative feedback.

ICAPS Conference 2020 Conference Paper

- D3WA+ - A Case Study of XAIP in a Model Acquisition Task for Dialogue Planning

• Sarath Sreedharan
• Tathagata Chakraborti
• Christian J. Muise
• Yasaman Khazaeni
• Subbarao Kambhampati

Recently, the D3WA system was proposed as a paradigm shift in how complex goal-oriented dialogue agents can be specified by taking a declarative view of design. However, it turns out actual users of the system have a hard time evolving their mental model and grasping the imperative consequences of declarative design. In this paper, we adopt ideas from existing works in the field of Explainable AI Planning (XAIP) to provide guidance to the dialogue designer during the model acquisition process. We will highlight in the course of this discussion how the setting presents unique challenges to the XAIP setting, including having to deal with the user persona of a domain modeler rather than the end-user of the system, and consequently having to deal with the unsolvability of models in addition to explaining generated plans. Quickview http: //ibm. biz/d3wa-xaip

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.

TIST Journal 2020 Journal Article

Discovering Underlying Plans Based on Shallow Models

• Hankz Hankui Zhuo
• Yantian Zha
• Subbarao Kambhampati
• Xin Tian

Plan recognition aims to discover target plans (i.e., sequences of actions) behind observed actions, with history plan libraries or action models in hand. Previous approaches either discover plans by maximally “matching” observed actions to plan libraries, assuming target plans are from plan libraries, or infer plans by executing action models to best explain the observed actions, assuming that complete action models are available. In real-world applications, however, target plans are often not from plan libraries, and complete action models are often not available, since building complete sets of plans and complete action models are often difficult or expensive. In this article, we view plan libraries as corpora and learn vector representations of actions using the corpora; we then discover target plans based on the vector representations. Specifically, we propose two approaches, DUP and RNNPlanner, to discover target plans based on vector representations of actions. DUP explores the EM-style (Expectation Maximization) framework to capture local contexts of actions and discover target plans by optimizing the probability of target plans, while RNNPlanner aims to leverage long-short term contexts of actions based on RNNs (Recurrent Neural Networks) framework to help recognize target plans. In the experiments, we empirically show that our approaches are capable of discovering underlying plans that are not from plan libraries without requiring action models provided. We demonstrate the effectiveness of our approaches by comparing its performance to traditional plan recognition approaches in three planning domains. We also compare DUP and RNNPlanner to see their advantages and disadvantages.

AAAI Conference 2020 Conference Paper

Expectation-Aware Planning: A Unifying Framework for Synthesizing and Executing Self-Explaining Plans for Human-Aware Planning

• Sarath Sreedharan
• Tathagata Chakraborti
• Christian Muise
• Subbarao Kambhampati

In this work, we present a new planning formalism called Expectation-Aware planning for decision making with humans in the loop where the human’s expectations about an agent may differ from the agent’s own model. We show how this formulation allows agents to not only leverage existing strategies for handling model differences like explanations (Chakraborti et al. 2017) and explicability (Kulkarni et al. 2019), but can also exhibit novel behaviors that are generated through the combination of these different strategies. Our formulation also reveals a deep connection to existing approaches in epistemic planning. Specifically, we show how we can leverage classical planning compilations for epistemic planning to solve Expectation-Aware planning problems. To the best of our knowledge, the proposed formulation is the first complete solution to planning with diverging user expectations that is amenable to a classical planning compilation while successfully combining previous works on explanation and explicability. We empirically show how our approach provides a computational advantage over our earlier approaches that rely on search in the space of models.

IJCAI Conference 2020 Conference Paper

The Emerging Landscape of Explainable Automated Planning & Decision Making

• Tathagata Chakraborti
• Sarath Sreedharan
• Subbarao Kambhampati

In this paper, we provide a comprehensive outline of the different threads of work in Explainable AI Planning (XAIP) that has emerged as a focus area in the last couple of years and contrast that with earlier efforts in the field in terms of techniques, target users, and delivery mechanisms. We hope that the survey will provide guidance to new researchers in automated planning towards the role of explanations in the effective design of human-in-the-loop systems, as well as provide the established researcher with some perspective on the evolution of the exciting world of explainable planning.

ICAPS Conference 2020 Conference Paper

TLdR: Policy Summarization for Factored SSP Problems Using Temporal Abstractions

• Sarath Sreedharan
• Siddharth Srivastava 0001
• Subbarao Kambhampati

As more and more people are expected to work with complex AI-systems, it becomes more important than ever that such systems provide intuitive explanations for their decisions. A prerequisite for holding such explanatory dialogue is the ability of the systems to present their proposed decisions to the user in an easy-to-understand form. Unfortunately, such dialogues could become hard to facilitate in real-world problems where the system may be planning for multiple eventualities in stochastic environments. This means for the system to be effective, it needs to be able to present the policy at a high-level of abstraction and delve into details as required. Towards this end, we investigate the utility of temporal abstractions derived through analytically computed landmarks and their relative ordering to build a summarization of policies for Stochastic Shortest Path Problems. We formalize the concept of policy landmarks and show how it can be used to provide a high level overview of a given policy. Additionally, we establish the connections between the type of hierarchy we generate and previous works in temporal abstractions, specifically MaxQ hierarchies. Our approach is evaluated through user studies as well as empirical metrics that establish that people tend to choose landmarks facts as subgoals to summarize policies and demonstrates the performance of our approach on standard benchmarks.

AAAI Conference 2019 Conference Paper

A Unified Framework for Planning in Adversarial and Cooperative Environments

• Anagha Kulkarni
• Siddharth Srivastava
• Subbarao Kambhampati

Users of AI systems may rely upon them to produce plans for achieving desired objectives. Such AI systems should be able to compute obfuscated plans whose execution in adversarial situations protects privacy, as well as legible plans which are easy for team members to understand in cooperative situations. We develop a unified framework that addresses these dual problems by computing plans with a desired level of comprehensibility from the point of view of a partially informed observer. For adversarial settings, our approach produces obfuscated plans with observations that are consistent with at least k goals from a set of decoy goals. By slightly varying our framework, we present an approach for producing legible plans in cooperative settings such that the observation sequence projected by the plan is consistent with at most j goals from a set of confounding goals. In addition, we show how the observability of the observer can be controlled to either obfuscate or convey the actions in a plan when the goal is known to the observer. We present theoretical results on the complexity analysis of our approach. We also present an empirical evaluation to show the feasibility and usefulness of our approaches using IPC domains.

IJCAI Conference 2019 Conference Paper

Balancing Explicability and Explanations in Human-Aware Planning

• Tathagata Chakraborti
• Sarath Sreedharan
• Subbarao Kambhampati

Human-aware planning involves generating plans that are explicable as well as providing explanations when such plans cannot be found. In this paper, we bring these two concepts together and show how an agent can achieve a trade-off between these two competing characteristics of a plan. In order to achieve this, we conceive a first of its kind planner MEGA that can augment the possibility of explaining a plan in the plan generation process itself. We situate our discussion in the context of recent work on explicable planning and explanation generation and illustrate these concepts in two well-known planning domains, as well as in a demonstration of a robot in a typical search and reconnaissance task. Human factor studies in the latter highlight the usefulness of the proposed approach.

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.

AAMAS Conference 2019 Conference Paper

Explicable Planning as Minimizing Distance from Expected Behavior

• Anagha Kulkarni
• Yantian Zha
• Tathagata Chakraborti
• Satya Gautam Vadlamudi
• Yu Zhang
• Subbarao Kambhampati

In order to achieve effective human-AI collaboration, it is necessary for an AI agent to align its behavior with the human’s expectations. When the agent generates a task plan without such considerations, it may often result in inexplicable behavior from the human’s point of view. This may have serious implications for the human, from increased cognitive load to more serious concerns of safety around the physical agent. In this work, we present an approach to generate explicable behavior by minimizing the distance between the agent’s plan and the plan expected by the human. To this end, we learn a mapping between plan distances (distances between expected and agent plans) and human’s plan scoring scheme. The plan generation process uses this learned model as a heuristic. We demonstrate the effectiveness of our approach in a delivery robot domain.

IJCAI Conference 2019 Conference Paper

Model-Free Model Reconciliation

• Sarath Sreedharan
• Alberto Olmo Hernandez
• Aditya Prasad Mishra
• Subbarao Kambhampati

Designing agents capable of explaining complex sequential decisions remains a significant open problem in human-AI interaction. Recently, there has been a lot of interest in developing approaches for generating such explanations for various decision-making paradigms. One such approach has been the idea of explanation as model-reconciliation. The framework hypothesizes that one of the common reasons for a user's confusion could be the mismatch between the user's model of the agent's task model and the model used by the agent to generate the decisions. While this is a general framework, most works that have been explicitly built on this explanatory philosophy have focused on classical planning settings where the model of user's knowledge is available in a declarative form. Our goal in this paper is to adapt the model reconciliation approach to a more general planning paradigm and discuss how such methods could be used when user models are no longer explicitly available. Specifically, we present a simple and easy to learn labeling model that can help an explainer decide what information could help achieve model reconciliation between the user and the agent with in the context of planning with MDPs.

AAMAS Conference 2019 Conference Paper

Synthesizing Explainable Behavior for Human-AI Collaboration

• Subbarao Kambhampati

As AI technologies enter our everyday lives at an ever increasing pace, there is a greater need for AI systems to work synergistically with humans. This requires AI systems to exhibit behavior that is explainable to humans. Synthesizing such behavior requires AI systems to reason not only with their own models of the task at hand, but also about the mental models of the human collaborators. Using several case-studies from our ongoing research, I will discuss how such multi-model planning forms the basis for explainable behavior.

IJCAI Conference 2019 Conference Paper

Why Can’t You Do That HAL? Explaining Unsolvability of Planning Tasks

• Sarath Sreedharan
• Siddharth Srivastava
• David Smith
• Subbarao Kambhampati

Explainable planning is widely accepted as a prerequisite for autonomous agents to successfully work with humans. While there has been a lot of research on generating explanations of solutions to planning problems, explaining the absence of solutions remains an open and under-studied problem, even though such situations can be the hardest to understand or debug. In this paper, we show that hierarchical abstractions can be used to efficiently generate reasons for unsolvability of planning problems. In contrast to related work on computing certificates of unsolvability, we show that these methods can generate compact, human-understandable reasons for unsolvability. Empirical analysis and user studies show the validity of our methods as well as their computational efficacy on a number of benchmark planning domains.

AAMAS Conference 2018 Conference Paper

Explicability versus Explanations in Human-Aware Planning

• Tathagata Chakraborti
• Sarath Sreedharan
• Subbarao Kambhampati

Human aware planning requires an agent to be aware of the mental model of the human in the loop during its decision process. This can involve generating plans that are explicable to the human as well as the ability to provide explanations when such plans cannot be generated. In this paper, we bring these two concepts together and show how an agent can account for both these needs and achieve a trade-off during the plan generation process itself by means of a model-space search method MEGA∗. This provides a revised perspective of what it means for an AI agent to be “human-aware” by bringing together recent works on explicable planning and plans explanations under the umbrella of a single plan generation process. We illustrate these concepts using a robot involved in a typical search and reconnaissance task with an external supervisor.

IJCAI Conference 2018 Conference Paper

Extracting Action Sequences from Texts Based on Deep Reinforcement Learning

• Wenfeng Feng
• Hankz Hankui Zhuo
• Subbarao Kambhampati

Extracting action sequences from texts is challenging, as it requires commonsense inferences based on world knowledge. Although there has been work on extracting action scripts, instructions, navigation actions, etc. , they require either the set of candidate actions be provided in advance, or action descriptions are restricted to a specific form, e. g. , description templates. In this paper we aim to extract action sequences from texts in \emph{free} natural language, i. e. , without any restricted templates, provided the set of actions is unknown. We propose to extract action sequences from texts based on the deep reinforcement learning framework. Specifically, we view ``selecting'' or ``eliminating'' words from texts as ``actions'', and texts associated with actions as ``states''. We build Q-networks to learn policies of extracting actions and extract plans from the labeled texts. We demonstrate the effectiveness of our approach on several datasets with comparison to state-of-the-art approaches.

ICAPS Conference 2018 Conference Paper

Handling Model Uncertainty and Multiplicity in Explanations via Model Reconciliation

• Sarath Sreedharan
• Tathagata Chakraborti
• Subbarao Kambhampati

Model reconciliation has been proposed as a way for an agent to explain its decisions to a human who may have a different understanding of the same planning problem by explaining its decisions in terms of these model differences. However, often the human's mental model (and hence the difference) is not known precisely and such explanations cannot be readily computed. In this paper, we show how the explanation generation process evolves in the presence of such model uncertainty or incompleteness by generating {\em conformant explanations} that are applicable to a set of possible models. We also show how such explanations can contain superfluous informationand how such redundancies can be reduced using conditional explanations to iterate with the human to attain common ground. Finally, we will introduce an anytime version of this approach and empirically demonstrate the trade-offs involved in the different forms of explanations in terms of the computational overhead for the agent and the communication overhead for the human. We illustrate these concepts in three well-known planning domains as well as in a demonstration on a robot involved in a typical search and reconnaissance scenario with an external human supervisor.

IJCAI Conference 2018 Conference Paper

Hierarchical Expertise Level Modeling for User Specific Contrastive Explanations

• Sarath Sreedharan
• Siddharth Srivastava
• Subbarao Kambhampati

There is a growing interest within the AI research community in developing autonomous systems capable of explaining their behavior to users. However, the problem of computing explanations for users of different levels of expertise has received little research attention. We propose an approach for addressing this problem by representing the user's understanding of the task as an abstraction of the domain model that the planner uses. We present algorithms for generating minimal explanations in cases where this abstract human model is not known. We reduce the problem of generating an explanation to a search over the space of abstract models and show that while the complete problem is NP-hard, a greedy algorithm can provide good approximations of the optimal solution. We also empirically show that our approach can efficiently compute explanations for a variety of problems.

IROS Conference 2018 Conference Paper

Projection-Aware Task Planning and Execution for Human-in-the-Loop Operation of Robots in a Mixed-Reality Workspace

• Tathagata Chakraborti
• Sarath Sreedharan
• Anagha Kulkarni 0002
• Subbarao Kambhampati

Recent advances in mixed-reality technologies have renewed interest in alternative modes of communication for human-robot interaction. However, most of the work in this direction has been confined to tasks such as teleoperation, simulation or explication of individual actions of a robot. In this paper, we will discuss how the capability to project intentions affect the task planning capabilities of a robot. Specifically, we will start with a discussion on how projection actions can be used to reveal information regarding the future intentions of the robot at the time of task execution. We will then pose a new planning paradigm - projection-aware planning - whereby a robot can trade off its plan cost with its ability to reveal its intentions using its projection actions. We will demonstrate each of these scenarios with the help of a joint human-robot activity using the HoloLens.

AAMAS Conference 2018 Conference Paper

Recognizing Plans by Learning Embeddings from Observed Action Distributions

• Yantian Zha
• Yikang Li
• Sriram Gopalakrishnan
• Baoxin Li
• Subbarao Kambhampati

Automated video surveillance requires the recognition of agent plans from videos. One promising direction for plan recognition involves learning shallow action affinity models from plan traces. Extracting such traces from raw video involves uncertainty about the actions. One solution is to represent traces as sequences of action distributions. To use such a representation in approximate plan recognition, we need embeddings of these action distributions. To address this problem, we propose a distribution to vector (Distr2Vec) model, which learns embeddings of action distributions using KL-divergence as the loss function.

AAMAS Conference 2017 Conference Paper

A Game Theoretic Approach to Strategy Generation for Moving Target Defense in Web Applications

• Sailik Sengupta
• Satya Gautam Vadlamudi
• Subbarao Kambhampati
• Adam Doupé
• Ziming Zhao
• Marthony Taguinod
• Gail-Joon Ahn

AIJ Journal 2017 Journal Article

Model-lite planning: Case-based vs. model-based approaches

• Hankz Hankui Zhuo
• Subbarao Kambhampati

There is increasing awareness in the planning community that depending on complete models impedes the applicability of planning technology in many real world domains where the burden of specifying complete domain models is too high. In this paper, we consider the problem of generating robust and accurate plans, when the agent only has access to incomplete domain models, supplanted by a set of successful plan cases. We will develop two classes of approaches – one case-based and the other model-based. ML-CBP is a case-based approach that leverages the incomplete model and the plan cases to solve a new problem directly by affecting case-level transfer. RIM is a model-based approach that uses the incomplete model and the plan cases to first learn a more complete model. This model contains both primitive actions as well as macro-operators that are derived from the plan cases. The learned model is then used in conjunction with an off-the-shelf planner to solve new problems. We present a comprehensive evaluation of the two approaches, both to characterize their relative tradeoffs, and to quantify their advances over existing approaches.

IJCAI Conference 2017 Conference Paper

Plan Explanations as Model Reconciliation: Moving Beyond Explanation as Soliloquy

• Tathagata Chakraborti
• Sarath Sreedharan
• Yu Zhang
• Subbarao Kambhampati

When AI systems interact with humans in the loop, they are often called on to provide explanations for their plans and behavior. Past work on plan explanations primarily involved the AI system explaining the correctness of its plan and the rationale for its decision in terms of its own model. Such soliloquy is wholly inadequate in most realistic scenarios where the humans have domain and task models that differ significantly from that used by the AI system. We posit that the explanations are best studied in light of these differing models. In particular, we show how explanation can be seen as a "model reconciliation problem" (MRP), where the AI system in effect suggests changes to the human's model, so as to make its plan be optimal with respect to that changed human model. We will study the properties of such explanations, present algorithms for automatically computing them, and evaluate the performance of the algorithms.

ICRA Conference 2017 Conference Paper

Plan explicability and predictability for robot task planning

• Yu Zhang 0055
• Sarath Sreedharan
• Anagha Kulkarni 0002
• Tathagata Chakraborti
• Hankz Hankui Zhuo
• Subbarao Kambhampati

Intelligent robots and machines are becoming pervasive in human populated environments. A desirable capability of these agents is to respond to goal-oriented commands by autonomously constructing task plans. However, such autonomy can add significant cognitive load and potentially introduce safety risks to humans when agents behave in unexpected ways. Hence, for such agents to be helpful, one important requirement is for them to synthesize plans that can be easily understood by humans. While there exists previous work that studied socially acceptable robots that interact with humans in “natural ways”, and work that investigated legible motion planning, there is no general solution for high level task planning. To address this issue, we introduce the notions of plan explicability and predictability. To compute these measures, first, we postulate that humans understand agent plans by associating abstract tasks with agent actions, which can be considered as a labeling process. We learn the labeling scheme of humans for agent plans from training examples using conditional random fields (CRFs). Then, we use the learned model to label a new plan to compute its explicability and predictability. These measures can be used by agents to proactively choose or directly synthesize plans that are more explicable and predictable to humans. We provide evaluations on a synthetic domain and with a physical robot to demonstrate the effectiveness of our approach.

AIJ Journal 2017 Journal Article

Robust planning with incomplete domain models

• Tuan Nguyen
• Sarath Sreedharan
• Subbarao Kambhampati

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We present two approaches to synthesizing robust plans. While the method based on the compilation to conformant probabilistic planning is much intuitive, its performance appears to be limited to only small problem instances. Our second approach based on stochastic heuristic search works well for much larger problems. It aims to use the robustness measure directly for estimating heuristic distance, which is then used to guide the search. Our planning system, PISA, outperforms a state-of-the-art planner handling incomplete domain models in most of the tested domains, both in terms of plan quality and planning time. Finally, we also present an extension of PISA called C PISA that is able to exploit the available of past successful plan traces to both improve the robustness of the synthesized plans and reduce the domain modeling burden.

AAAI Conference 2016 Conference Paper

A Combinatorial Search Perspective on Diverse Solution Generation

• Satya Gautam Vadlamudi
• Subbarao Kambhampati

ICAPS Conference 2016 Conference Paper

A Formal Analysis of Required Cooperation in Multi-Agent Planning

• Yu Zhang 0055
• Sarath Sreedharan
• Subbarao Kambhampati

It is well understood that, through cooperation, multiple agents can achieve tasks that are unachievable by a single agent. However, there are no formal characterizations of situations where cooperation is required to achieve a goal, thus warranting the application of multiple agents. In this paper, we provide such a formal characterization for multi-agent planning problems with sequential action execution. We first show that determining whether there is required cooperation (RC) is in general intractable even in this limited setting. As a result, we start our analysis with a subset of more restrictive problems where agents are homogeneous. For such problems, we identify two conditions that can cause RC. We establish that when none of these conditions hold, the problem is single-agent solvable; otherwise, we provide upper bounds on the minimum number of agents required. For the remaining problems with heterogeneous agents, we further divide them into two subsets. For one of the subsets, we propose the concept of {\em transformer agent} to reduce the number of agents to be considered which is used to improve planning performance. We implemented a planner using our theoretical results and compared it with one of the best IPC CoDMAP planners in the centralized track. Results show that our planner provides significantly improved performance on IPC CoDMAP domains.

SoCS Conference 2016 Conference Paper

Compliant Conditions for Polynomial Time Approximation of Operator Counts

• Tathagata Chakraborti
• Sarath Sreedharan
• Sailik Sengupta
• T. K. Satish Kumar
• Subbarao Kambhampati

In this brief abstract, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is thus threefold, we (1) propose an efficient closed form approximation to the operator count heuristic; (2) leverage compressed sensing techniques to obtain an integer approximation in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches are useful.

AAMAS Conference 2016 Conference Paper

Discovering Underlying Plans Based on Distributed Representations of Actions

• Xin Tian
• Hankz Hankui Zhuo
• Subbarao Kambhampati

AAMAS Conference 2016 Conference Paper

Moving Target Defense for Web Applications Using Bayesian Stackelberg Games (Extended Abstract)

• Satya Gautam Vadlamudi
• Sailik Sengupta
• Marthony Taguinod
• Ziming Zhao
• Adam Doupé
• Gail-Joon Ahn
• Subbarao Kambhampati

Vulnerabilities in web applications allow hackers to access and/or modify restricted data. Here the hackers have the opportunity to perform reconnaissance so as to gain knowledge about the web application layout before launching an attack, whereas the defender (administrator of the web application) must secure the application even with its potential vulnerabilities. In order to mask such vulnerabilities which are primarily associated with different individual configurations, Moving Target Defense systems were proposed wherein the defender switches between various configurations thereby making it difficult to attack with success, while maintaining a seamless experience for the genuine users. In this paper, we present a way to find effective switching strategies by modeling this ecosystem as a Bayesian Stackelberg game with the administrator as the leader and the hackers as the followers, which as we show succinctly captures various aspects of the Moving Target Defense systems. Furthermore, we propose ways to find the most critical vulnerabilities and the most sensitive attacker types, which are key issues in such scenarios.

AAMAS Conference 2016 Conference Paper

Planning with Resource Conflicts in Human-Robot Cohabitation

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

IJCAI Conference 2016 Conference Paper

Preface

• Subbarao Kambhampati
• Gerhard Brewka

IJCAI-2016 is different from earlier conferences in the IJCAI series in various respects. It is the first conference of its kind taking place one year after the last IJCAI (and the first-ever leap year one! ). In our view one of the major roles of the flagship AI conference is to provide a forum for reintegrating diverse subfields of AI. For this reason we decided not to have vertical special tracks this year: that is, special tracks divided along specific subtopics such as knowledge representation, machine learning, planning and the like. We did introduce a horizontal special track, though, namely the AI and Web track. This track was chaired by Evgeniy Gabrilovich and Mausam and represents one of the most exciting current application areas for a broad range of AI techniques.

IROS Conference 2015 Conference Paper

A human factors analysis of proactive support in human-robot teaming

• Yu Zhang 0055
• Vignesh Narayanan
• Tathagata Chakraborti
• Subbarao Kambhampati

It has long been assumed that for effective human-robot teaming, it is desirable for assistive robots to infer the goals and intents of the humans, and take proactive actions to help them achieve their goals. However, there has not been any systematic evaluation of the accuracy of this claim. On the face of it, there are several ways a proactive robot assistant can in fact reduce the effectiveness of teaming. For example, it can increase the cognitive load of the human teammate by performing actions that are unanticipated by the human. In such cases, even though the teaming performance could be improved, it is unclear whether humans are willing to adapt to robot actions or are able to adapt in a timely manner. Furthermore, misinterpretations and delays in goal and intent recognition due to partial observations and limited communication can also reduce the performance. In this paper, our aim is to perform an analysis of human factors on the effectiveness of such proactive support in human-robot teaming. We perform our evaluation in a simulated Urban Search and Rescue (USAR) task, in which the efficacy of teaming is not only dependent on individual performance but also on teammates' interactions with each other. In this task, the human teammate is remotely controlling a robot while working with an intelligent robot teammate `Mary'. Our main result shows that the subjects generally preferred Mary with the ability to provide proactive support (compared to Mary without this ability). Our results also show that human cognitive load was increased with a proactive assistant (albeit not significantly) even though the subjects appeared to interact with it less.

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 2014 Conference Paper

A Heuristic Approach to Planning with Incomplete STRIPS Action Models

• Tuan A. Nguyen
• Subbarao Kambhampati

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete STRIPS domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We introduce two approximations, lower and upper bound, for plan robustness, and then utilize them to derive heuristics for synthesizing robust plans. Our planning system, PISA, incorporating stochastic local search with these novel techniques outperforms a state-of-the-art planner handling incomplete domains in most of the tested domains, both in terms of plan quality and planning time.

ICRA Conference 2014 Conference Paper

Coalition coordination for tightly coupled multirobot tasks with sensor constraints

• Yu Zhang 0055
• Lynne E. Parker
• Subbarao Kambhampati

Although many approaches have been developed to form robot coalitions that can achieve a multirobot task, no general methods exist to execute these coalitions, especially when the coordination among the robots is tightly coupled. In this paper, we propose a coordination mechanism as the first step to address coalition execution; it provides a flexible method to reason about synergies with overlapping coalitions (thus enabling multi-tasking robots in multi-robot tasks), which not only improves efficiency, but also reduces resource requirements in task execution. This means that our approach enables tasks that cannot be easily handled before, especially when critical resources are rare but commonly required. Our approach is based on the concept of sensor constraint, which is introduced by the tight coupling (e. g. , information sharing) between the robots. We show that our algorithm is sound and complete in finding a coordination solution given a few assumptions, and discuss a distributed implementation. Simulation results are provided to demonstrate the capabilities of this new approach.

IROS Conference 2014 Conference Paper

Coordination in human-robot teams using mental modeling and plan recognition

• Kartik Talamadupula
• Gordon Briggs
• Tathagata Chakraborti
• Matthias Scheutz
• Subbarao Kambhampati

Beliefs play an important role in human-robot teaming scenarios, where the robots must reason about other agents' intentions and beliefs in order to inform their own plan generation process, and to successfully coordinate plans with the other agents. In this paper, we cast the evolving and complex structure of beliefs, and inference over them, as a planning and plan recognition problem. We use agent beliefs and intentions modeled in terms of predicates in order to create an automated planning problem instance, which is then used along with a known and complete domain model in order to predict the plan of the agent whose beliefs are being modeled. Information extracted from this predicted plan is used to inform the planning process of the modeling agent, to enable coordination. We also look at an extension of this problem to a plan recognition problem. We conclude by presenting an evaluation of our technique through a case study implemented on a real robot.

TIST Journal 2014 Journal Article

Learning Probabilistic Hierarchical Task Networks as Probabilistic Context-Free Grammars to Capture User Preferences

• Nan Li
• William Cushing
• Subbarao Kambhampati
• Sungwook Yoon

We introduce an algorithm to automatically learn probabilistic hierarchical task networks (pHTNs) that capture a user's preferences on plans by observing only the user's behavior. HTNs are a common choice of representation for a variety of purposes in planning, including work on learning in planning. Our contributions are twofold. First, in contrast with prior work, which employs HTNs to represent domain physics or search control knowledge, we use HTNs to model user preferences. Second, while most prior work on HTN learning requires additional information (e.g., annotated traces or tasks) to assist the learning process, our system only takes plan traces as input. Initially, we will assume that users carry out preferred plans more frequently, and thus the observed distribution of plans is an accurate representation of user preference. We then generalize to the situation where feasibility constraints frequently prevent the execution of preferred plans. Taking the prevalent perspective of viewing HTNs as grammars over primitive actions, we adapt an expectation-maximization (EM) technique from the discipline of probabilistic grammar induction to acquire probabilistic context-free grammars (pCFG) that capture the distribution on plans. To account for the difference between the distributions of possible and preferred plans, we subsequently modify this core EM technique by rescaling its input. We empirically demonstrate that the proposed approaches are able to learn HTNs representing user preferences better than the inside-outside algorithm. Furthermore, when feasibility constraints are obfuscated, the algorithm with rescaled input performs better than the algorithm with the original input.

IJCAI Conference 2013 Conference Paper

Action-Model Acquisition from Noisy Plan Traces

• Hankz Hankui Zhuo
• Subbarao Kambhampati

There is increasing awareness in the planning community that the burden of specifying complete domain models is too high, which impedes the applicability of planning technology in many real-world domains. Although there have been many learning approaches that help automatically creating domain models, they all assume plan traces (training data) are correct. In this paper, we aim to remove this assumption, allowing plan traces to be with noise. Compared to collecting large amount of correct plan traces, it is much easier to collect noisy plan traces, e. g. , we can directly exploit sensors to help collect noisy plan traces. We consider a novel solution for this challenge that can learn action models from noisy plan traces. We create a set of random variables to capture the possible correct plan traces behind the observed noisy ones, and build a graphical model to describe the physics of the domain. We then learn the parameters of the graphical model and acquire the domain model based on the learnt parameters. In the experiment, we empirically show that our approach is effective in several planning domains.

IJCAI Conference 2013 Conference Paper

Listening to the Crowd: Automated Analysis of Events via Aggregated Twitter Sentiment

• Yuheng Hu
• Fei Wang
• Subbarao Kambhampati

Individuals often express their opinions on social media platforms like Twitter and Facebook during public events such as the U. S. Presidential debate and the Oscar awards ceremony. Gleaning insights from these posts is of importance to analyzing the impact of the event. In this work, we consider the problem of identifying the segments and topics of an event that garnered praise or criticism, according to aggregated Twitter responses. We propose a flexible factorization framework, SOCSENT, to learn factors about segments, topics, and sentiments. To regulate the learning process, several constraints based on prior knowledge on sentiment lexicon, sentiment orientations (on a few tweets) as well as tweets alignments to the event are enforced. We implement our approach using simple update rules to get the optimal solution. We evaluate the proposed method both quantitatively and qualitatively on two large-scale tweet datasets associated with two events from different domains to show that it improves significantly over baseline models.

AAAI Conference 2013 Conference Paper

Model-Lite Case-Based Planning

• Hankz Hankui Zhuo
• Tuan Nguyen
• Subbarao Kambhampati

There is increasing awareness in the planning community that depending on complete models impedes the applicability of planning technology in many real world domains where the burden of specifying complete domain models is too high. In this paper, we consider a novel solution for this challenge that combines generative planning on incomplete domain models with a library of plan cases that are known to be correct. While this was arguably the original motivation for case-based planning, most existing case-based planners assume (and depend on) from-scratch planners that work on complete domain models. In contrast, our approach views the plan generated with respect to the incomplete model as a “skeletal plan” and augments it with directed mining of plan fragments from library cases. We will present the details of our approach and present an empirical evaluation of our method in comparison to a state-of-the-art case-based planner that depends on complete domain models.

IJCAI Conference 2013 Conference Paper

Refining Incomplete Planning Domain Models through Plan Traces

• Hankz Hankui Zhuo
• Tuan Nguyen
• Subbarao Kambhampati

Most existing work on learning planning models assumes that the entire model needs to be learned from scratch. A more realistic situation is that the planning agent has an incomplete model which it needs to refine through learning. In this paper we propose and evaluate a method for doing this. Our method takes as input an incomplete model (with missing preconditions and effects in the actions), as well as a set of plan traces that are known to be correct. It outputs a “refined” model that not only captures additional precondition/effect knowledge about the given actions, but also “macro actions”. We use a MAX-SAT framework for learning, where the constraints are derived from the executability of the given plan traces, as well as the preconditions/effects of the given incomplete model. Unlike traditional macro-action learners which use macros to increase the efficiency of planning (in the context of a complete model), our motivation for learning macros is to increase the accuracy (robustness) of the plans generated with the refined model. We demonstrate the effectiveness of our approach through a systematic empirical evaluation.

NeurIPS Conference 2013 Conference Paper

Synthesizing Robust Plans under Incomplete Domain Models

• Tuan Nguyen
• Subbarao Kambhampati
• Minh Do

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to synthesize plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness and formalize the notion of plan robustness with respect to an incomplete domain model. We then show an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem, and present experimental results with Probabilistic-FF planner.

NeurIPS Conference 2012 Conference Paper

Action-Model Based Multi-agent Plan Recognition

• Hankz Zhuo
• Qiang Yang
• Subbarao Kambhampati

Multi-Agent Plan Recognition (MAPR) aims to recognize dynamic team structures and team behaviors from the observed team traces (activity sequences) of a set of intelligent agents. Previous MAPR approaches required a library of team activity sequences (team plans) be given as input. However, collecting a library of team plans to ensure adequate coverage is often difficult and costly. In this paper, we relax this constraint, so that team plans are not required to be provided beforehand. We assume instead that a set of action models are available. Such models are often already created to describe domain physics; i. e. , the preconditions and effects of effects actions. We propose a novel approach for recognizing multi-agent team plans based on such action models rather than libraries of team plans. We encode the resulting MAPR problem as a \emph{satisfiability problem} and solve the problem using a state-of-the-art weighted MAX-SAT solver. Our approach also allows for incompleteness in the observed plan traces. Our empirical studies demonstrate that our algorithm is both effective and efficient in comparison to state-of-the-art MAPR methods based on plan libraries.

TIST Journal 2012 Journal Article

An Ensemble Architecture for Learning Complex Problem-Solving Techniques from Demonstration

• Xiaoqin Shelley Zhang
• Bhavesh Shrestha
• Sungwook Yoon
• Subbarao Kambhampati
• Phillip DiBona
• Jinhong K. Guo
• Daniel McFarlane
• Martin O. Hofmann

We present a novel ensemble architecture for learning problem-solving techniques from a very small number of expert solutions and demonstrate its effectiveness in a complex real-world domain. The key feature of our “Generalized Integrated Learning Architecture” (GILA) is a set of heterogeneous independent learning and reasoning (ILR) components, coordinated by a central meta-reasoning executive (MRE). The ILRs are weakly coupled in the sense that all coordination during learning and performance happens through the MRE. Each ILR learns independently from a small number of expert demonstrations of a complex task. During performance, each ILR proposes partial solutions to subproblems posed by the MRE, which are then selected from and pieced together by the MRE to produce a complete solution. The heterogeneity of the learner-reasoners allows both learning and problem solving to be more effective because their abilities and biases are complementary and synergistic. We describe the application of this novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspaces need to be deconflicted, reconciled, and managed automatically. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Furthermore, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

AAAI Conference 2012 Conference Paper

ET-LDA: Joint Topic Modeling for Aligning Events and their Twitter Feedback

• Yuheng Hu
• Ajita John
• Fei Wang
• Subbarao Kambhampati

During broadcast events such as the Superbowl, the U. S. Presidential and Primary debates, etc. , Twitter has become the de facto platform for crowds to share perspectives and commentaries about them. Given an event and an associated large-scale collection of tweets, there are two fundamental research problems that have been receiving increasing attention in recent years. One is to extract the topics covered by the event and the tweets; the other is to segment the event. So far these problems have been viewed separately and studied in isolation. In this work, we argue that these problems are in fact inter-dependent and should be addressed together. We develop a joint Bayesian model that performs topic modeling and event segmentation in one unified framework. We evaluate the proposed model both quantitatively and qualitatively on two large-scale tweet datasets associated with two events from different domains to show that it improves significantly over baseline models.

AIJ Journal 2012 Journal Article

Generating diverse plans to handle unknown and partially known user preferences

• Tuan Anh Nguyen
• Minh Do
• Alfonso Emilio Gerevini
• Ivan Serina
• Biplav Srivastava
• Subbarao Kambhampati

Current work in planning with preferences assumes that user preferences are completely specified, and aims to search for a single solution plan to satisfy these. In many real world planning scenarios, however, the user may provide no knowledge or at best partial knowledge of her preferences with respect to a desired plan. In such situations, rather than presenting a single plan as the solution, the planner must instead provide a set of plans containing one or more plans that are similar to the one that the user really prefers. In this paper, we first propose the usage of different measures to capture the quality of such plan sets. These are domain-independent distance measures based on plan elements (such as actions, states, or causal links) if no knowledge of the user preferences is given, or the Integrated Convex Preference (ICP) measure in case incomplete knowledge of such preferences is provided. We then investigate various heuristic approaches to generate sets of plans in accordance with these measures, and present empirical results that demonstrate the promise of our methods.

AIJ Journal 2011 Journal Article

State agnostic planning graphs: deterministic, non-deterministic, and probabilistic planning

• Daniel Bryce
• William Cushing
• Subbarao Kambhampati

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source. We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i. e. , search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.

SoCS Conference 2010 Conference Paper

Cost Based Search Considered Harmful

• William Cushing
• J. Benton 0001
• Subbarao Kambhampati

Planning research has returned to the issue of optimizing costs (rather than sizes) of plans. A prevalent perception, at least among non-experts in search, is that graph search for optimizing the size of paths generalizes more or less trivially to optimizing the cost of paths. While this kind of generalization is usually straightforward for graph theorems, graph algorithms are a different story. In particular, implementing a search evaluation function by substituting cost for size is a Bad Idea. Though experts have stated as much, cutting-edge practitioners are still learning of the consequences the hard way; here we mount a forceful indictment on the inherent dangers of cost-based search.

ICAPS Conference 2010 Conference Paper

G-Value Plateaus: A Challenge for Planning

• J. Benton 0001
• Kartik Talamadupula
• Patrick Eyerich
• Robert Mattmüller
• Subbarao Kambhampati

While the string of successes found in using heuristic, best-first search methods have provided positive reinforcement for continuing work along these lines, fundamental problems arise when handling objectives whose value does not change with search operations. An extreme case of this occurs when handling the objective of generating a temporal plan with short makespan. Typically used heuristic search methods assume strictly positive edge costs for their guarantees on completeness and optimality, while the usual ``fattening'' and ``advance time'' steps of heuristic search for temporal planning have the potential of resulting in ``g-value plateaus''. In this paper we point out some underlying difficulties with using modern heuristic search methods when operating over g-value plateaus and discuss how the presence of these problems contributes to the poor performance of heuristic search planners. To further illustrate this, we show empirical results on recent benchmarks using a planner made with makespan optimization in mind.

AAAI Conference 2010 Conference Paper

Integrating a Closed World Planner with an Open World Robot: A Case Study

• Kartik Talamadupula
• J. Benton
• Paul Schermerhorn
• Subbarao Kambhampati
• Matthias Scheutz

In this paper, we present an integrated planning and robotic architecture that actively directs an agent engaged in an urban search and rescue (USAR) scenario. We describe three salient features that comprise the planning component of this system, namely (1) the ability to plan in a world open with respect to objects, (2) execution monitoring and replanning abilities, and (3) handling soft goals, and detail the interaction of these parts in representing and solving the USAR scenario at hand. We show that though insufficient in an individual capacity, the integration of this trio of features is sufficient to solve the scenario that we present. We test our system with an example problem that involves soft and hard goals, as well as goal deadlines and action costs, and show that the planner is capable of incorporating sensing actions and execution monitoring in order to produce goal-fulfilling plans that maximize the net benefit accrued.

TIST Journal 2010 Journal Article

Planning for human-robot teaming in open worlds

• Kartik Talamadupula
• J. Benton
• Subbarao Kambhampati
• Paul Schermerhorn
• Matthias Scheutz

As the number of applications for human-robot teaming continue to rise, there is an increasing need for planning technologies that can guide robots in such teaming scenarios. In this article, we focus on adapting planning technology to Urban Search And Rescue (USAR) with a human-robot team. We start by showing that several aspects of state-of-the-art planning technology, including temporal planning, partial satisfaction planning, and replanning, can be gainfully adapted to this scenario. We then note that human-robot teaming also throws up an additional critical challenge, namely, enabling existing planners, which work under closed-world assumptions, to cope with the open worlds that are characteristic of teaming problems such as USAR. In response, we discuss the notion of conditional goals, and describe how we represent and handle a specific class of them called open world quantified goals. Finally, we describe how the planner, and its open world extensions, are integrated into a robot control architecture, and provide an empirical evaluation over USAR experimental runs to establish the effectiveness of the planning components.

IJCAI Conference 2009 Conference Paper

• Nan Li
• Subbarao Kambhampati
• Sungwook Yoon

While much work on learning in planning focused on learning domain physics (i. e. , action models), and search control knowledge, little attention has been paid towards learning user preferences on desirable plans. Hierarchical task networks (HTN) are known to provide an effective way to encode user prescriptions about what constitute good plans. However, manual construction of these methods is complex and error prone. In this paper, we propose a novel approach to learning probabilistic hierarchical task networks that capture user preferences by examining user-produced plans given no prior information about the methods (in contrast, most prior work on learning within the HTN framework focused on learning “method preconditions”—i. e. , domain physics—assuming that the structure of the methods is given as input). We will show that this problem has close parallels to the problem of probabilistic grammar induction, and describe how grammar induction methods can be adapted to learn task networks. We will empirically demonstrate the effectiveness of our approach by showing that task networks we learn are able to generate plans with a distribution close to the distribution of the userpreferred plans.

IJCAI Conference 2009 Conference Paper

• Tuan A. Nguyen
• Minh B. Do
• Subbarao Kambhampati
• Biplav Srivastava

In many real-world planning scenarios, the users are interested in optimizing multiple objectives (such as makespan and execution cost), but are unable to express their exact tradeoff between those objectives. When a planner encounters such partial preference models, rather than look for a single optimal plan, it needs to present the pareto set of plans and let the user choose from them. This idea of presenting the full pareto set is fraught with both computational and user-interface challenges. To make it practical, we propose the approach of finding a representative subset of the pareto set. We measure the quality of this representative set using the Integrated Convex Preference (ICP) model, originally developed in the OR community. We implement several heuristic approaches based on the Metric- LPG planner to find a good solution set according to this measure. We present empirical results demonstrating the promise of our approach.

AIJ Journal 2009 Journal Article

Anytime heuristic search for partial satisfaction planning

• J. Benton
• Minh Do
• Subbarao Kambhampati

We present a heuristic search approach to solve partial satisfaction planning (PSP) problems. In these problems, goals are modeled as soft constraints with utility values, and actions have costs. Goal utility represents the value of each goal to the user and action cost represents the total resource cost (e. g. , time, fuel cost) needed to execute each action. The objective is to find the plan that maximizes the trade-off between the total achieved utility and the total incurred cost; we call this problem PSP Net Benefit. Previous approaches to solving this problem heuristically convert PSP Net Benefit into STRIPS planning with action cost by pre-selecting a subset of goals. In contrast, we provide a novel anytime search algorithm that handles soft goals directly. Our new search algorithm has an anytime property that keeps returning better quality solutions until the termination criteria are met. We have implemented this search algorithm, along with relaxed plan heuristics adapted to PSP Net Benefit problems, in a forward state-space planner called Sapa PS. An adaptation of Sapa PS, called Yochan PS, received a “distinguished performance” award in the “simple preferences” track of the 5th International Planning Competition.

IROS Conference 2009 Conference Paper

Finding and exploiting goal opportunities in real-time during plan execution

• Paul W. Schermerhorn
• J. Benton 0001
• Matthias Scheutz
• Kartik Talamadupula
• Subbarao Kambhampati

Autonomous robots that operate in real-world domains face multiple challenges that make planning and goal selection difficult. Not only must planning and execution occur in real time, newly acquired knowledge can invalidate previous plans, and goals and their utilities can change during plan execution. However, these events can also provide opportunities, if the architecture is designed to react appropriately. We present here an architecture that integrates the SapaReplan planner with the DIARC robot architecture, allowing the architecture to react dynamically to changes in the robot's goal structures.

ICAPS Conference 2009 Conference Paper

Learning User Plan Preferences Obfuscated by Feasibility Constraints

• Nan Li
• William Cushing
• Subbarao Kambhampati
• Sung Wook Yoon

It has long been recognized that users can have complex preferences on plans. Non-intrusive learning of such preferences by observing the plans executed by the user is an attractive idea. Unfortunately, the executed plans are often not a true representation of user preferences, as they result from the interaction between user preferences and feasibility constraints. In the travel planning scenario, a user whose true preference is to travel by a plane may well be frequently observed traveling by car because of feasibility constraints (perhaps the user is a poor graduate student). In this work, we describe a novel method for learning true user preferences obfuscated by such feasibility constraints. Our base learner induces probabilistic hierarchical task networks (pHTNs) from sets of training plans. Our approach is to rescale the input so that it represents the user's preference distribution on plans rather than the observed distribution on plans.

ICAPS Conference 2008 Conference Paper

An Online Learning Method for Improving Over-Subscription Planning

• Sung Wook Yoon
• J. Benton 0001
• Subbarao Kambhampati

Despite the recent resurgence of interest in learning methods for planning, most such efforts are still focused exclusively on classical planning problems. In this work, we investigate the effectiveness of learning approaches for improving over-subscription planning, a problem that has received significant recent interest. Viewing over-subscription planning as a domain-independent optimization problem, we adapt the STAGE (Boyan and Moore 2000) approach to learn and improve the plan search. The key challenge in our study is how to automate the feature generation process. In our case, we developed and experimented with a relational feature set, based on Taxonomic syntax as well as a propositional feature set, based on ground-facts. The feature generation process and training data generation process are all automatic, making it a completely domain-independent optimization process that takes advantage of online learning. In empirical studies, our proposed approach improved upon the baseline planner for over-subscription planning on many of the benchmark problems.

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.

IJCAI Conference 2007 Conference Paper

• Biplav Srivastava
• Subbarao Kambhampati
• Tuan A. Nguyen
• Minh Binh Do
• Alfonso Gerevini
• Ivan Serina

In many planning situations, a planner is required to return a diverse set of plans satisfying the same goals which will be used by the external systems collectively. We take a domain-independent approach to solving this problem. We propose different domain independent distance functions among plans that can provide meaningful insights about the diversity in the plan set. We then describe how two representative state-of-the-art domain independent planning approaches -- one based on compilation to CSP, and the other based on heuristic local search -- can be adapted to produce diverse plans. We present empirical evidence demonstrating the effectiveness of our approaches.

IJCAI Conference 2007 Conference Paper

• William Cushing
• Mausam
• Subbarao Kambhampati
• Daniel Weld

While even STRIPS planners must search for plans of unbounded length, temporal planners must also cope with the fact that actions may start at any point in time. Most temporal planners cope with this challenge by restricting action start times to a small set of decision epochs, because this enables search to be carried out in state-space and leverages powerful state-based reachability heuristics, originally developed for classical planning. Indeed, decision-epoch planners won the International Planning Competition's Temporal Planning Track in 2002, 2004 and 2006. However, decision-epoch planners have a largely unrecognized weakness: they are incomplete. In order to characterize the cause of incompleteness, we identify the notion of required concurrency, which separates expressive temporal action languages from simple ones. We show that decision-epoch planners are only complete for languages in the simpler class, and we prove that the simple class is `equivalent' to STRIPS! Surprisingly, no problems with required concurrency have been included in the planning competitions. We conclude by designing a complete state-space temporal planning algorithm, which we hope will be able to achieve high performance by leveraging the heuristics that power decision epoch planners.

IJCAI Conference 2007 Conference Paper

• Minh Do
• J. Benton
• Menkes van den Briel
• Subbarao Kambhampati

Work in partial satisfaction planning (PSP) has hitherto assumed that goals are independent thus implying that they have additive utility values. In many real-world problems, we cannot make this assumption. In this paper, we motivate the need for handling various types of goal utility dependence in PSP. We provide a framework for representing them using the General Additive Independence model and investigate two different approaches to handle this problem: (1) compiling PSP with utility dependencies to Integer Programming; (2) extending forward heuristic search planning to handle PSP goal dependencies. To guide the forward planning search, we introduce a novel heuristic framework that combines cost-propagation and Integer Programming to select beneficial goals to find an informative heuristic estimate. The two implemented planners, iPUD and SPUDS, using the approaches discussed above, are compared empirically on several benchmark domains. While iPUD is more readily amendable to handle goal utility dependencies and can provide bounded optimality guarantees, SPUDS scales much better.

ICAPS Conference 2007 Conference Paper

A Hybrid Linear Programming and Relaxed Plan Heuristic for Partial Satisfaction Planning Problems

• J. Benton 0001
• Menkes van den Briel
• Subbarao Kambhampati

The availability of informed (but inadmissible) planning heuristics has enabled the development of highly scalable planning systems. Due to this success, a body of work has grown around modifying these heuristics to handle extensions to classical planning. Most recently, there has been an interest in addressing partial satisfaction planning problems, but existing heuristics fail to address the complex interactions that occur in these problems between action and goal selection. In this paper we provide a unique admissible heuristic based on linear programming that we use to solve a relaxed version of the partial satisfaction planning problem. We incorporate this heuristic in conjunction with a lookahead strategy in a branch and bound algorithm to solve a class of over-subscribed planning problems.

ICAPS Conference 2007 Conference Paper

Evaluating Temporal Planning Domains

• William Cushing
• Daniel S. Weld
• Subbarao Kambhampati
• Mausam
• Kartik Talamadupula

The last eight years have seen dramatic progress in temporal planning as highlighted by the temporal track in the last three International Planning Competitions (IPC). However, our recent work, (Cushing et al. 2007), showed that most of the competition winning planners are only complete for very restricted forms of temporal planning languages that are in a sense indistinguishable from STRIPS. In this paper we consider the impact of those results on the design of benchmark temporal planning domains, and by extension, the temporal planning competition. We start by setting out to verify our speculation that the competition domains are temporally simple. This turns out to be tricky, and we develop a set of increasingly powerful analytic methods for domain analysis. Our analysis establishes that the benchmark domains are indeed inherently sequential (i. e., do not require concurrency). We suggest some real-world domains with required concurrency, and use a compilation argument to show that these are harder in the sense that they correspond to longer sequential plans. We conclude with the argument that temporal planners should be evaluated on both inherently sequential domains as well as those requiring concurrency.

AAAI Conference 2007 Conference Paper

Model-lite Planning for the Web Age Masses: The Challenges of Planning with Incomplete and Evolving Domain Models

• Subbarao Kambhampati

The automated planning community has traditionally focused on the efficient synthesis of plans given a complete domain theory. In the past several years, this line of work met with significant successes, and the future course of the community seems to be set on efficient planning with even richer models. While this line of research has its applications, there are also many domains and scenarios where the first bottleneck is getting the domain model at any level of completeness. In these scenarios, the modeling burden automatically renders the planning technology unusable. To counter this, I will motivate model-lite planning technology aimed at reducing the domain-modeling burden (possibly at the expense of reduced functionality), and outline the research challenges that need to be addressed to realize it.

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.

UAI Conference 2005 Conference Paper

Cost Sensitive Reachability Heuristics for Handling State Uncertainty

• Daniel Bryce
• Subbarao Kambhampati

ICAPS Conference 2005 Conference Paper

Planning Graph Heuristics for Selecting Objectives in Over-subscription Planning Problems

• Romeo Sanchez Nigenda
• Subbarao Kambhampati

Partial Satisfaction or Over-subscription Planning problems arise in many real world applications. Applications in which the planning agent does not have enough resources to accomplish all of their given goals, requiring plans that satisfy only a subset of them. Solving such partial satisfaction planning (PSP) problems poses several challenges, from new models for handling plan quality to efficient heuristics for selecting the most beneficial goals. In this paper, we extend planning graph-based reachability heuristics with mutex analysis to overcome complex goal interactions in PSP problems. We start by describing one of the most general PSP problems, the PSP Net Benefit problem, where actions have execution costs and goals have utilities. Then, we present AltWlt, our heuristic approach augmented with a multiple goal set selection process and mutex analysis. Our empirical studies show that AltWlt is able to generate the most beneficial solutions, while incurring only a small fraction of the cost of other PSP approaches.

ICAPS Conference 2005 Conference Paper

Reviving Integer Programming Approaches for AI Planning: A Branch-and-Cut Framework

• Menkes van den Briel
• Thomas Vossen
• Subbarao Kambhampati

The conventional wisdom in the planning community is that planners based on integer programming (IP) techniques cannot compete with satisfiability and constraint satisfaction based planners. In this paper we challenge this perception of IP techniques by presenting novel formulations that outperform the most efficient SAT-based planner that currently exists. We will present a series of IP formulations that (1) use multi-valued state variables that are represented by networks, and that (2) control the encoding length by progressively generalizing the notion of parallelism. The resulting IP encodings are solved within a branch-and-cut framework and yield impressive results.

ICAPS Conference 2004 Conference Paper

Heuristic Guidance Measures for Conformant Planning

• Daniel Bryce
• Subbarao Kambhampati

Scaling conformant planning is a problem that has received much attention of late. Many planners solve the problem as a search in the space of belief states, and some heuristic guidance techniques have been developed to estimate the distance between belief states. We claim that heuristic techniques in the past involved an ad hoc combination of classical planning heuristics and cardinality measures. We discuss how to derive heuristics systematically, with the help of planning graphs, such that the measures reflect the reachability of relevant states within belief states. To demonstrate these ideas we show how distances between belief states can be estimated by a set of reachability heuristics. We empirically evaluate their effectiveness within a conformant regression planner named CAltAlt.

ICAPS Conference 2003 Conference Paper

Improving Temporal Flexibility of Position Constrained Metric Temporal Plans

• Minh Binh Do
• Subbarao Kambhampati

In this paper we address the problem of post-processing position constrained plans, output by many of the recent efficient metric temporal planners, to improve their execution flexibility. Specifically, given a position constrained plan, we consider the problem of generating a partially ordered (aka "order constrained") plan that uses the same actions. Although variations of this "partialization" problem have been addressed in classical planning, the metric and temporal considerations bring in significant complications. We develop a general CSP encoding for partializing position-constrained temporal plans, that can be optimized under an objective function dealing with a variety of temporal flexibility criteria, such as makespan. We then propose several approaches (e. g. coupled CSP, MILP) of solving this encoding. We also present a greedy value ordering strategy that is designed to efficiently generate solutions with good makespan values for these encodings. We demonstrate the effectiveness of our greedy partialization approach in the context of a recent metric temporal planner that produces p. c. plans. We also compare the effects of greedy and optimal partialization using MILP encodings on the set of metric temporal problems used at the Third International Planning Competition.

IJCAI Conference 2003 Conference Paper

Parallelizing State Space Plans Online

• Romeo Sanchez Nigenda
• Subbarao Kambhampati

Searching for parallel solutions in state space planners is a challenging problem, because it would require the planners to branch on all possible subsets of parallel actions, exponentially increasing their branching factor. We introduce a variant of our heuristic state search planner AltAlt, which generates parallel plans by using greedy online parallelization of partial plans. Empirical results show that our online approach outperforms postprocessing (offline) techniques in terms of the quality of the solutions returned. 2 AltAlt Background The AltAlt planning system is based on a combination of Graphplan [Blum and Furst, 1997] and heuristic state space search [Haslum and Geffner, 2000] technology. The problem specification and the action template description arc first fed to a Graphplan-style planner, which constructs a planning graph for that problem in polynomial time. This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective heuristics [Nguyen et al. , 2000]. These heuristics, along with the problem specification, and the set of ground actions in the final action level of the planning graph are then fed to a regression state-search planner.

IJCAI Conference 2003 Conference Paper

Using Available Memory to Transform Graphplans Search

• Terry Zimmerman
• Subbarao Kambhampati

AIJ Journal 2002 Journal Article

Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search

• XuanLong Nguyen
• Subbarao Kambhampati
• Romeo S. Nigenda

Most recent strides in scaling up planning have centered around two competing themes—disjunctive planners, exemplified by Graphplan, and heuristic state search planners, exemplified by UNPOP, HSP and HSP-r. In this paper, we present a novel approach for successfully harnessing the advantages of the two competing paradigms to develop planners that are significantly more powerful than either of the approaches. Specifically, we show that the polynomial-time planning graph structure that the Graphplan builds provides a rich substrate for deriving a family of highly effective heuristics for guiding state space search as well as CSP style search. The main leverage provided by the planning graph structure is a systematic and graded way to take subgoal interactions into account in designing state space heuristics. For state space search, we develop several families of heuristics, some aimed at search speed and others at optimality of solutions, and analyze many approaches for improving the cost-quality tradeoffs offered by these heuristics. Our normalized empirical comparisons show that our heuristics handily outperform the existing state space heuristics. For CSP style search, we describe a novel way of using the planning graph structure to derive highly effective variable and value ordering heuristics. We show that these heuristics can be used to improve Graphplan's own backward search significantly. To demonstrate the effectiveness of our approach vis a vis the state-of-the-art in plan synthesis, we present AltAlt, a planner literally cobbled together from the implementations of Graphplan and state search style planners using our theory. We evaluate AltAlt on the suite of problems used in the recent AIPS-2000 planning competition. The results place AltAlt in the top tier of the competition planners—outperforming both Graphplan based and heuristic search based planners.

ICAPS Conference 2002 Conference Paper

Planning Graph-based Heuristics for Cost-sensitive Temporal Planning

• Minh Binh Do
• Subbarao Kambhampati

Abstract Real world planners need to be sensitive to the quality of the plans they generate. Unlike classical planning where quality is often synonymous with plans having least number of actions, in temporal planning plan quality is multidimensional. It involves both temporal aspects of the plan (such as makespan, slack, tardiness) and execution cost aspects (such as cumulative action cost, resource consumption). Until now, most domain-independent temporal planners have concentrated solely on the former, ignoring the latter. In this paper, we consider the problem of developing heuristics that are sensitive to both makespan and cost, and develop a planning graph-based approach for this purpose. Our approach involves augmenting a (temporal) planning graph data structure with a mechanism to track the execution cost of the goals and subgoals. Since the cost of achieving a goal is dependent on the amount of available time, we need to track the cost of a literal as a function of time. We present a methodology for efficiently tracking the cost functions, and discuss how they can be used as the basis for deriving heuristics to support any objective function based on makespan and execution cost. We demonstrate the effectiveness of this general method for deriving cost- and makespan-sensitive heuristics in the context of Sapa a forward chaining planner for metric temporal domains that we have been developing. A version of Sapausing a subset of the techniques discussed in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02.

AIJ Journal 2001 Journal Article

Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP

• Minh Binh Do
• Subbarao Kambhampati

The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to satisfiability (SAT) theories and integer linear programming (ILP). In this paper we will show that CSP is a better substrate for the compilation approach, compared to both SAT and ILP. We describe GP-CSP, a system that does planning by automatically converting Graphplan's planning graph into a CSP encoding and solving it using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is superior to both the Blackbox system, which compiles planning graphs into SAT encodings, and an ILP-based planner in a wide range of planning domains. Our results show that CSP encodings outperform SAT encodings in terms of both space and time requirements in various problems. The space reduction is particularly important as it makes GP-CSP less susceptible to the memory blow-up associated with SAT compilation methods. The paper also discusses various techniques in setting up the CSP encodings, planning specific improvements to CSP solvers, and strategies for variable and value selection heuristics for solving the CSP encodings of different types of planning problems.

AIJ Journal 2001 Journal Article

Planning the project management way: Efficient planning by effective integration of causal and resource reasoning in RealPlan

• Biplav Srivastava
• Subbarao Kambhampati
• Minh B. Do

In most real-world reasoning problems, planning and scheduling phases are loosely coupled. For example, in project planning, the user comes up with a task list and schedules it with a scheduling tool like Microsoft Project. One can view automated planning in a similar way in which there is an action selection phase where actions are selected and ordered to reach the desired goals, and a resource allocation phase where enough resources are assigned to ensure the successful execution of the chosen actions. On the other hand, most existing automated planners studied in Artificial Intelligence do not exploit this loose-coupling and perform both action selection and resource assignment employing the same algorithm. The current work shows that the above strategy severely curtails the scale-up potential of existing state of the art planners which can be overcome by leveraging the loose coupling. Specifically, a novel planning framework called RealPlan is developed in which resource allocation is de-coupled from planning and is handled in a separate scheduling phase. The scheduling problem with discrete resources is represented as a Constraint Satisfaction Problem (CSP) problem, and the planner and scheduler interact either in a master-slave manner or in a peer-peer relationship. In the former, the scheduler simply tries to assign resources to the abstract causal plan passed to it by the planner and returns success. In the latter, a more sophisticated “multi-module dependency directed backtracking” approach is used where the failure explanation in the scheduler is translated back to the planner and serves as a nogood to direct planner search. RealPlan not only preserves both the correctness as well as the quality (measured in length) of the plan but also improves efficiency. Moreover, the failure-driven learning of constraints can serve as an elegant and effective approach for integrating planning and scheduling systems. Beyond the context of planner efficiency, the current work can be viewed as an important step towards merging planning with real-world problem solving where plan failure during execution can be resolved by undertaking only necessary resource re-allocation and not complete re-planning.

ICAPS Conference 2000 Conference Paper

Distance-Based Goal-Ordering Heuristics for Graphplan

• Subbarao Kambhampati
• Romeo Sanchez Nigenda

We will discuss the shortcomings of known variable and value ordering strategies for Graphplan’s backward search phase, and propose a novel strategy that is based on a notion of the difficulty of achieving the corresponding subgoal. The difficulty of achievement is quantified in terms of the structure of the planning graph itself–specifically, the earliest level of the planning-graph at which that subgoal appears. We will present empirical results showing the surprising effectiveness of this simple heuristic on benchmark problems. We will end by contrasting the way distance-based heuristics are used in Graphplan and state-search planners like UNPOP, HSP and HSP-R.

ICAPS Conference 2000 Conference Paper

Investigating the Effect of Relevance and Reachability Constraints on SAT Encodings of Planning

• Minh Binh Do
• Biplav Srivastava
• Subbarao Kambhampati

Currently, Graphplan and Blackbox, which converts Graphplan’s plan graph into the satisfaction (SAT) problem, are two of the most successful planners. Since Graphplan gains its efficiency from the forward propagation of reachability based mutual exclusion constraints (mutex) and their backward use, it has been believed that SAT encoding will also benefit from mutexes. In this paper, we will try to answer two important questions: (1) Are mutual exclusions actually useful for solution extraction in SAT encoding? (2) Are there other useful constraints that can be propagated on the planning graph which may help SAT solvers? Our experiments with systematic solvers Relsat and Satz shows that though forward mutexes are useful in general, there are domains in which mutex constraints can slow down search. Moreover, we introduce the notion of backward mutex and their propagation which is based on relevance analysis and implement it in Blackbox. We find that the addition of relevance based backward mutual exclusions helps speedup the Relsat solver in solving the SAT encoding of many standard planning problems.

ICAPS Conference 2000 Conference Paper

Solving Planning-Graph by Compiling It into CSP

• Minh Binh Do
• Subbarao Kambhampati

Although the deep affinity between Graphplan’s backward search, and the process of solving constraint satisfaction problems has been noted earlier, these relations have hither-to been primarily used to adapt CSP search techniques into the backward search phase of Graphplan. This paper describes GP-CSP, a system that does planning by automatically converting Graphplan’s planning graph into a CSP encoding, and solving the CSP encoding using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is quite competitive with both standard Graphplan and Blackbox system, which compiles planning graphs into SAT encodings. We discuss the many advantages offered by focusing on CSP encodings rather than SAT encodings, including the fact that by exploiting implicit constraint representations, GP-CSP tends to be less susceptible to memory blow-up associated with methods that compile planning problems into SAT encodings. Our work is inspired by the success of van Beek & Chen’s CPLAN system. However, in contrast to CPLAN, which expects handcoded CSP encodings for individual domains and problems, GP-CSP is able to take domain descriptions in STRIPS (PDDL) representation, and automatically generate the CSP encodings. learning and dependency directed backtracking strategies from CSP to backward search phase of Graphplan. More recently, researchers from CSP have started taking interest in applying constraint programming to classical planning. van Beek & Chen [30] describe a system called CPLAN that achieves impressive performance by posing planning as a CSP problem. However, an important characteristic (and limitation) of CPLAN is that it expects a hand-coded encoding–humans have to setup a domain and problem encoding independently for each problem and domain. In this paper, we propose a different route to exploiting the similarities between the planning graph and CSP problems. We describe an implemented planner called GP-CSP that solves the planning graphs by automatically converting them into CSP encodings. GP-CSP generates implicitly specified constraints wherever possible, to keep the encoding size small. The encoding is then passed onto the standard CSP solvers in the CSP library created by van Beek[29]. Our empirical studies show that GP-CSP is significantly superior to Graphplan as well as Blackbox which compiles planning problems into SAT encodings. While GP-CSP’s dominance over standard Graphplan is in terms of runtime, its advantages over Blackbox’s SAT encodings include improvements in both runtime and memory consumption. The relative advantages of GP-CSP can be easily explained:  Unlike the backward search in standard Graphplan, GP- CSP is not constrained by any directional search, and is able to to exploit all standard CSP search techniques straight out of the box. This involves nondirectional search [24] as well as speedup techniques such as arc-consistency, dependency directed backtracking, explanation-based learning and a variety of variable ordering techniques. In practice, GP-CSP is found to be orders of magnitude faster than standard Graphplan on many benchmark problems.

AAAI Conference 1999 Conference Paper

Exploiting Symmetry in the Planning-Graph via Explanation-Guided Search

• Terry Zimmerman
• Subbarao Kambhampati
• Arizona State University

We present a method for exploiting the symmetry in the planning graph structure and certain redundancies inherent in the Graphplan algorithm, so as to improve its backward search. The main insight underlying our method is that due to these features the backward search conducted at level k + 1 of the graph is essentially a replay of the search conducted at the previous level k with certain welldefined extensions. Our method consists of maintaining a pilot explanation structure capturing the failures encountered at previous levels of the search, and using it in an intelligent way to guide the search at the newer levels. The standard EBL and DDB techniques can be employed to control the size of the pilot explanation. The technique has been implemented in the EGBG system, and we present a preliminary empirical study.

AAAI Conference 1999 Conference Paper

On the Utility of Plan-Space (Causal) Encodings

• Amol D. Mali
• Subbarao Kambhampati
• Arizona State University

Recently, casting planning as propositional satisfiability has been shown to be a very promising technique for plan synthesis. Although encodings based both on statespace planning and on plan-space (causal) planning have been proposed, most implementations and trade-off evaluations primarily use state-based encodings. This is surprising given both the prominence of plan-space planners in traditional planning, as well as the recent claim that lifted versions of causal encodings provide the smallest encodings. In this paper we attempt a systematic analytical and empirical comparison of plan-space (causal) encodings and state-space encodings. We start by pointing out the connection between the different ways of proving the correctness of a plan, and the spectrum of possible SAT encodings. We then characterize the dimensions along which causal proofs, and consequently, plan-space encodings, can vary. We provide two encodings that are much smaller than those previously proposed. We then show that the smallest causal encodings cannot be smaller in size than the smallest state-based encodings. We shall show that the “lifting” transformation does not affect this relation. Finally, we will present some empirical results that demonstrate that the relative encoding sizes are indeed correlated with the hardness of solving them. We end with a discussion on when the primacy of traditional plan-space planners over state-space planners might carry over to their respective SAT encodings.

ICAPS Conference 1998 Conference Paper

Encoding HTN Planning in Propositional Logic

• Amol Dattatraya Mali
• Subbarao Kambhampati

Casting planning problemsas propositional satlsfiability problems has recently been shownto be an effective wayof scaling up plan synthesis. Until now, the benefits of this approach have only been utUized in primitive action-based planning models. Motivated by the conventional wisdomin the planning community about the effectiveness of hierarchical task network (HTN)planning models, in this paper we adapt the "planningas satlsfiability" approachto HT_X planning models. HTNplanning models can be thought of as an augmentationof primitive action based planning models with a grammarof legal solutions, provided in the form of non-primitive tasks and task reduction schemas. Accordingly, we argue that any action-based encoding scheme can be generalized to handle HTN planning models. Informally, this generalization involves adding constraints to the encoding to ensure that the solutions produced by solving the encoding will conform to the grammar provided by the HTN planning model. The constraints can be added in either a ’~op-down"or "bottom-up" fashion, resulting in two HTNencoding schemesfor each primitive action-based encoding scheme. Weillustrate this process by providing three different HTNencodings. We discuss the asymptoticsizes of these encodings, as well as the complexityof finding modelsfor them.

AAAI Conference 1998 Conference Paper

Hybrid Planning for Partially Hierarchical Domains

• Subbarao Kambhampati

Hierarchical task network and action-based planning approaches have traditionally been studied separately. In many domains, human expertise in the form of hierarchical reduction schemas exists, but is incomplete. In such domains, hybrid approaches that use both HTN and action-based planning techniques are needed. In this paper, we extend our previous work on refinement planning to include hierarchical planning. Specifically, we provide a generalized plan-space refinement that is capable of handling non-primitiveactions. The generalization provides a principled way of handling partially hierarchical domains, while preserving systematicity, and respecting the user-intent inherent in the reduction schemas. Our general account also puts into perspective the many surface differences between the HTN and action-based planners, and could support the transfer of progress between HTN and action-based planning approaches.

AIJ Journal 1998 Journal Article

On the relations between intelligent backtracking and failure-driven explanation-based learning in constraint satisfaction and planning

• Subbarao Kambhampati

The ideas of intelligent backtracking (IB) and explanation-based learning (EBL) have developed independently in the constraint satisfaction, planning, machine learning and problem solving communities. The variety of approaches developed for IB and EBL in the various communities have hither-to been incomparable. In this paper, I formalize and unify these ideas under the task-independent framework of refinement search, which can model the search strategies used in both planning and constraint satisfaction problems (CSPs). I show that both IB and EBL depend upon the common theory of explanation analysis—which involves explaining search failures, and regressing them to higher levels of the search tree. My comprehensive analysis shows that most of the differences between the CSP and planning approaches to EBL and IB revolve around different solutions to: (a) how the failure explanations are computed; (b) how they are contextualized (contextualization involves deciding whether or not to keep the flaw description and the description of the violated problem constraints); and (c) how the storage of explanations is managed. The differences themselves can be understood in terms of the differences between planning and CSP problems as instantiations of refinement search. This unified understanding is expected to support a greater cross-fertilization of ideas among CSP, planning and EBL communities.

IJCAI Conference 1997 Conference Paper

Challenges in bridging plan synthesis paradigms

• Subbarao Kambhampati

ICAPS Conference 1996 Conference Paper

A Candidate Set Based Analysis of Subgoal Interactions in Conjunctive Goal Planning

• Subbarao Kambhampati
• Laurie H. Ihrig
• Biplav Srivastava

Subgoal interactions have received considerable attention in AI Planning. Earlier analyses by Korf and Joslin and Roach [6] were done in terms of the topology of the space of world states. More recent analyses by Barrett and Weld and Veloso and Blythe were done in terms of the nature of the planner. In this paper, we will argue that subgoal interactions are best understood in terms of the candidate sets of the plans for the individual subgoals. We will describe a generalized representation for partial plans that applies to a large class of refinement planners, and discuss the notion of mergeability and serial extensibility of these partial plans. The concepts of independence and serializability of subgoals are derived by generalizing mergeability and serial extensibility over classes of partial plans. Unlike previous work, our analysis also applies to multi-method refinement planners such as UCP. We will show that all existing characterizations of serializability differ only in terms of the specific class of partial plans that they implicitly address. Finally, we will use our interaction analysis to explore factors affecting the selection of a refinement planner for a given domain.

AIJ Journal 1996 Journal Article

Failure driven dynamic search control for partial order planners: an explanation based approach

• Subbarao Kambhampati
• Suresh Katukam
• Yong Qu

Given the intractability of domain independent planning, the ability to control the search of a planner is vitally important. One way of doing this involves learning from search failures. This paper describes SNLP + EBL, the first implementation of an explanation based search control rule learning framework for a partial order (plan-space) planner. We will start by describing the basic learning framework of SNLP + EBL. We will then concentrate on SNLP + EBL's ability to learn from failures, and describe the results of empirical studies which demonstrate the effectiveness of the search control rules SNLP + EBL learns using our method. We then demonstrate the generality of our learning methodology by extending it to UCPOP (Penberthy and Weld, 1992), a descendant of SNLP that allows for more expressive domain theories. The resulting system, UCPOP + EBL, is used to analyze and understand the factors influencing the effectiveness of EBL. Specifically, we analyze the effect of (i) expressive action representations, (ii) domain specific failure theories and (iii) sophisticated backtracking strategies on the utility of EBL. Through empirical studies, we demonstrate that expressive action representations allow for more explicit domain representations which in turn increase the ability of EBL to learn from analytical failures, and obviate the need for domain specific failure theories. We also explore the strong affinity between dependency directed backtracking and EBL in planning.

AAAI Conference 1996 Conference Paper

Formalizing Dependency Directed Backtracking and Explanation Based Learning in Refinement Search

• Subbarao Kambhampati

The ideas of dependency directed backtracking (DDB) and explanation based learning (EBL) have developed independently in constraint satisfaction, planning and problem solving communities. In this paper, I formalize and unify these ideas under the task-independent framework of refinement search, which can model the search strategies used in both planning and constraint satisfaction. I show that both DDB and EBL depend upon the common theory ofexplaining search failuresand regressing them to higher levels of the search tree. The relevant issues of importance include (a) how the failures are explained and (b) how many failure explanations are remembered. This task-independent understanding of DDB and EBL helps support cross-fertilization of ideas among Constraint Satisfaction, Planning and Explanation-Based Learning communities.

AIJ Journal 1996 Journal Article

On the nature and role of modal truth criteria in planning

• Subbarao Kambhampati
• Dana S. Nau

Chapman's paper, “Planning for conjunctive goals”, has been widely acknowledged for its contribution toward understanding the nature of partial-order planning, and it has been one of the bases of later work by others—but it is not free of problems. This paper addresses some problems involving modal truth and the modal truth criterion (MTC). Our results are as follows: (i) Even though modal duality is a fundamental property of classical modal logics, it does not hold for modal truth in Chapman's plans; i. e. , “necessarily p” is not equivalent to “not possibly -p”. (ii) Although the MTC for necessary truth is correct, the MTC for possible truth is incorrect: it provides necessary but insufficient conditions for ensuring possible truth. Furthermore, even though necessary truth can be determined in polynomial time, possible truth is NP-hard. (iii) If we rewrite the MTC to talk about modal conditional truth (i. e. , modal truth conditional on executability) rather than modal truth, then both the MTC for necessary conditional truth and the MTC for possible conditional truth are correct; and both can be computed in polynomial time. (iv) The MTC plays a different role in plan generation than it does in checking the correctness of plans, and this has led to several misconceptions about the MTC. Several researchers have mistakenly attempted to simplify the MTC by eliminating the white-knight declobbering clause from it; and others have used Chapman's results to conjecture that partial-order planning will not scale up to more expressive action representations. We point out that these ideas are misconceptions, and explain why.

AAAI Conference 1996 Conference Paper

Refinement Planning: Status and Prospectus

• Subbarao Kambhampati

Most current-day AI planning systems operate by iteratively refining a partial plan until it meets the goal requirements. In the past five years, significant progress has been made in our understanding of the spectrum and capabilities of such refinement planners. In this talk, I will summarize this understanding in terms of a unified framework for refinement planning and discuss several current research directions.

AIJ Journal 1995 Journal Article

Planning as refinement search: a unified framework for evaluating design tradeoffs in partial-order planning

• Subbarao Kambhampati
• Craig A. Knoblock
• Qiang Yang

Despite the long history of classical planning, there has been very little comparative analysis of the performance tradeoffs offered by the multitude of existing planning algorithms. This is partly due to the many different vocabularies within which planning algorithms are usually expressed. In this paper we show that refinement search provides a unifying framework within which various planning algorithms can be cast and compared. Specifically, we will develop refinement search semantics for planning, provide a generalized algorithm for refinement planning, and show that planners that search in the space of (partial) plans are specific instantiations of this algorithm. The different design choices in partial-order planning correspond to the different ways of instantiating the generalized algorithm. We will analyze how these choices affect the search space size and refinement cost of the resultant planner, and show that in most cases they trade one for the other. Finally, we will concentrate on two specific design choices, viz. , protection strategies and tractability refinements, and develop some hypotheses regarding the effect of these choices on the performance on practical problems. We will support these hypotheses with a series of focused empirical studies.

AIJ Journal 1994 Journal Article

A unified framework for explanation-based generalization of partially ordered and partially instantiated plans

• Subbarao Kambhampati
• Smadar Kedar

Most previous work in explanation-based generalization (EBG) of plans dealt with totally ordered plans. These methods cannot be directly applied to generalizing partially ordered partially instantiated plans, a class of plans that have received significant attention in planning. In this paper we present a natural way of extending the explanation-based generalization methods to partially ordered partially instantiated (POPI) plans. Our development is based on modal truth criteria for POPI plans [3]. We develop explanation structures from these truth criteria, and use them as a common basis to derive a variety of generalization algorithms. Specifically we present algorithms for precondition generalization, order generalization, and possible correctness generalization of POPI plans. The systematic derivation of the generalization algorithms from the modal truth criterion obviates the need for carrying out a separate formal proof of correctness of the EBG algorithms. Our development also systematically explicates the tradeoffs among the spectrum of possible generalizations for POPI plans, and provides an empirical demonstration of the relative utility of EBG in partial ordering, as opposed to total ordering, planning frameworks.

ICAPS Conference 1994 Conference Paper

Design Tradeoffs in Partial Order (Plan space) Planning

• Subbarao Kambhampati

the generalizedre~tementplanningalgorithmanddescribesthe difDespitethe IonBhistoryof classicalplmming, therehas beenverylit compsrative analysisof the performance tradeoffsofferedbythe multit of existin8 planningalSodthms. Thisis partly dueto the many di vocabularies withinwhichplanningalgorithmsare usuallyexpressed. In this paperI providea generalized algorithmfor refinemant plannin dhow that plannersthat searchin the spaceof (partial) plansare speci instantisfiom of this al$orithm. Thedifferontdesignchoicesin partial o plannin 8 correspond to the differantwaysof instantistin8 the Beneral alsorithm. I will analyzehowthese choicesaffect the search-space andrefmemant cosl of the resultant planner. Finally, I wW conce oft twospecificdemsn choices, viz,, protection strate$iesandtractab refinements, anddevelopsomehypotheses regardingthe effect of t choicesonthe perfocnn~nce onpractical problems. I will support hypotheses witha focussedempiricalstudy.

AIJ Journal 1994 Journal Article

Multi-contributor causal structures for planning: a formalization and evaluation

• Subbarao Kambhampati

Explicit causal structure representations have been widely used in classical planning systems to guide a variety of aspects of planning, including plan generation, modification and generalization. For the most part, these representations were limited to single-contributor causal structures. Although widely used, single-contributor causal structures have several limitations in handling partially ordered and partially instantiated plans. Specifically they are (i) incapable of exploiting redundancy in the plan causal structure and (ii) force premature commitment to individual contributors thereby causing unnecessary backtracking. In this paper, we study multi-contributor causal structures as a way of overcoming these limitations. We will provide a general formulation for multi-contributor causal links, and explore the properties of several special classes of this formulation. We will then describe two planning algorithms—MP and MP-I—that use multi-contributor causal links to organize their search for plans. We will describe empirical studies demonstrating the advantages of MP and MP-I over planners that use single contributor causal structures, and argue that they strike a more favorable balance in the tradeoff between search space redundancy and premature commitment to contributors. Finally, we will present a framework for justifying plans with respect to multi-contributor causal structures and describe its applications in plan modification and generalization.

AAAI Conference 1994 Conference Paper

On the Nature of Modal Truth Criteria in Planning

• Subbarao Kambhampati

Chapman’s paper, "Planning for Conjunctive Goals," has been widely acknowledged for its contribution toward understanding the nature of nonlinear (partial-order) planning, and it has been one of the bases of later work by others---but it is not free of problems. This paper addresses some problems involving modal truth and the Modal Truth Criterion (MTC). Our results are as follows: Even though modal duality is a fundamental axiom of classical modal logics, it does not hold for modal truth in Chapman’s plans; i.e., "necessarily p" is not equivalent to "not possibly lp." Although the MTC for necessary truth is correct, the MTC for possible truth is incorrect: it provides necessary but insufficient conditions for ensuring possible truth. Furthermore, even though necessary truth can be determined in polynomial time, possible truth is NP-hard. If we rewrite the MTC to talk about modal conditional truth (i.e., modal truth conditional on executability) rather than modal truth, then both the MTC for necessary conditional truth and the MTC for possible conditional truth are correct; and both can be computed in polynomial time.

AAAI Conference 1993 Conference Paper

Relative Utility of EBG based Plan Reuse in Partial Ordering vs. Total Ordering Planning

• Subbarao Kambhampati

AIJ Journal 1992 Journal Article

A validation-structure-based theory of plan modification and reuse

• Subbarao Kambhampati
• James A. Hendler

The ability to modify existing plans to accommodate a variety of externally imposed constraints (such as changes in the problem specification, the expected world state, or the structure of the plan) is a valuable tool for improving efficiency of planning by avoiding repetition of planning effort. In this paper, we present a theory of incremental plan modification suitable for hierarchical nonlinear planning, and describe its implementation in a system called PRIAR. In this theory, the causal and teleological structure of the plans generated by a planner are represented in the form of an explanation of correctness called the “validation structure”. Individual planning decisions are justified in terms of their relation to the validation structure. Plan modification is formalized as a process of removing inconsistencies in the validation structure of a plan when it is being reused in a new or changed planning situation. The repair of these inconsistencies involves removing unnecessary parts of the plan and adding new nonprimitive tasks to the plan to establish missing or failing validations. The result is a partially reduced plan with a consistent validation structure, which is then sent to the planner for complete reduction. We discuss this theory, present an empirical evaluation of the resulting plan modification system, and characterize the coverage, efficiency and limitations of the approach.

AAAI Conference 1991 Conference Paper

Combining Specialized Reasoners and General Purpose Planners: A Case Study

• Subbarao Kambhampati
• Marty Tenenbaum

Many real-world planning problems involve substantial amounts of domain-specific reasoning that is either awkward or inefficient to encode in a general purpose planner. Previous approaches for planning in such domains have either been largely domain specific or have employed shallow models of the domain-specific considerations. In this paper we investigate a hybrid planning model that utilizes a set of specialists to complement both the overall expressiveness and the reasoning power of a traditional hierarchical planner. Such a model retains the flexibility and generality of classical planning framework while allowing deeper and more efficient domain-specific reasoning through specialists. We describe a preliminary implementation of a planning architecture based on this model in a manufacturing planning domain, and use it to explore issues regarding the effect of the specialists on the planning, and the interactions and interfaces between them and the planner.

AAAI Conference 1991 Conference Paper

Explanation-Based Generalization of Partially Ordered Plans

• Subbarao Kambhampati

AAAI Conference 1990 Conference Paper

A Theory of Plan Modification

• Subbarao Kambhampati

We present a theory of plan modificationapplicableto hierarchical no&ear planning. Ourtheoryutilizesthe validationstructureof the stored plans to yield a flexible and conservativeplan modification framework The validationstructure, whichconstitutesa hierarchical explanationof correctnessof the plan with respectto the planner’ s own knowledge of the domain, is annotated on the plan as a byproductof i&al planning. Plan modificationis ch&cteri& as a brocess of remov&ginconsistenciesin the validationstructureof a &an whenit is being reusedin a new (changed)planningsituation. The reuair of these-inconsistenciesinvolves removingunnecessary pans of the plan and addingnew non-primitive tasksto the plan to establish mi&g or failing validations. The resultantpartiallyreduced plan (with a consistent validation structure)is sent to the plannerfor completereduction. We discussthe development of this theory in PMARsystem, and characterizeits completeness, coverage, efficiencyandlimitations.

AAAI Conference 1990 Conference Paper

Mapping and Retrieval During Plan Reuse: A Validation Structure Based Approach

• Subbarao Kambhampati

Effective mapping and retrieval are important issues in successful deployment of plan reuse strategies. In this paper we present a domain independent strategy for ranking a set of plausible reuse candidates in the order of cost of modifying them to solve a new planning problem. The cost of modification is estimated by measuring the amount of disturbance caused to the validation structure of a reuse candidate if it were to be reused in the new problem situation. This strategy is more informed than the typical feature based retrieval strategies, and is more efficient than the methods which require partial knowledge of the nature of the plan for the new problem situation to guide the retrieval process. We discuss the implementation of this retrieval strategy in PRIAR, a framework for flexible reuse and modification in hierarchical planning.

IJCAI Conference 1989 Conference Paper

Control of Refitting during Plan Reuse

• Subbarao Kambhampati
• James A. Hendler

ICRA Conference 1985 Conference Paper

Visual algorithms for autonomous navigation

• Fred P. Andresen
• Larry S. Davis
• Roger D. Eastman
• Subbarao Kambhampati

The Computer Vision Laboratory at the University of Maryland is designing and developing a vision system for autonomous ground navigation. Our approach to visual navigation segments the task into three levels called long range, intermediate range and short range navigation. At the long range, one would first generate a plan for the day's outing, identifying the starting location, the goal, and a low resolution path for moving from the start to the goal. From time to time, during the course of the outing, one may want to establish his position with respect to the long range plan. This could be accomplished by visually identifying landmarks of known location, and then triangulating to determine current position. We describe a vision system for position determination that we have developed as part of this project. At the intermediate range, one would look ahead to determine generally safe directions of travel called corridors of free space. Short range navigation is the process that, based on a detailed topographic analysis of one's immediate environment, enables us to safely navigate around obstacles in the current corridor of free space along a track of safe passage. We describe a quadtree based path planning algorithm which could serve as the basis for identifying such tracks of safe passage.