Shirin Sohrabi

AAAI Conference 2026 System Paper

QueryGym: Step-by-Step Interaction with Relational Databases

• Haritha Ananthakrishnan
• Harsha Kokel
• Kelsey Sikes
• Debarun Bhattacharjya
• Michael Katz
• Shirin Sohrabi
• Kavitha Srinivas

We introduce QueryGym, an interactive environment for building, testing, and evaluating LLM-based query planning agents. Existing frameworks often tie agents to specific query language dialects or obscure their reasoning; QueryGym instead requires agents to construct explicit sequences of relational algebra operations, ensuring engine-agnostic evaluation and transparent step-by-step planning. The environment is implemented as a Gymnasium interface that supplies observations---including schema details, intermediate results, and execution feedback---and receives actions that represent database exploration (e.g., previewing tables, sampling column values, retrieving unique values) as well as relational algebra operations (e.g., filter, project, join).We detail the motivation and the design of the environment. In the demo, we showcase the utility of the environment by contrasting it with contemporary LLMs that query databases. QueryGym serves as a practical testbed for research in error remediation, transparency, and reinforcement learning for query generation.

AAAI Conference 2025 Conference Paper

ACPBench: Reasoning About Action, Change, and Planning

• Harsha Kokel
• Michael Katz
• Kavitha Srinivas
• Shirin Sohrabi

There is an increasing body of work using Large Language Models (LLMs) as agents for orchestrating workflows and making decisions in domains that require planning and multistep reasoning. As a result, it is imperative to evaluate LLMs on core skills required for planning. In this work, we present ACPBench, a benchmark for evaluating the reasoning tasks in the field of planning. The benchmark consists of 7 reasoning tasks over 13 planning domains. The collection is constructed from planning domains described in a formal language. This allows us to synthesize problems with provably correct solutions across many tasks and domains. Further, it allows us the luxury of scale without additional human effort, i.e., many] additional problems can be created automatically. Our extensive evaluation of 21 LLMs and OpenAI o1 reasoning models highlight the significant gap in the reasoning capability of the LLMs. Our findings with OpenAI o1, a multi-turn reasoning model, reveal significant gains in performance on multiple-choice questions, yet surprisingly, no notable progress is made on boolean questions.

AAAI Conference 2025 Short Paper

Automating Thought of Search: A Journey Towards Soundness and Completeness (Student Abstract)

• Daniel Cao
• Michael Katz
• Harsha Kokel
• Kavitha Srinivas
• Shirin Sohrabi

Large language models (LLMs) now turn their attention to search. Recently, Thought of Search (ToS) proposed defining the search space with code, having an LLM produce that code. ToS requires a human in the loop, collaboratively producing a sound successor function and goal test, achieving impressive 100% accuracy on all the tested datasets. In this work, we automate ToS (AutoToS), completely taking the human out of the loop of solving planning problems. AutoToS guides the language model step by step towards the generation of sound and complete search components, through feedback from both generic and domain specific unit tests. We achieve 100% accuracy, with minimal feedback iterations, using LLMs of various sizes on all evaluated domains.

PRL Workshop 2024 Workshop Paper

Guiding Hiearchical Reinforcement Learning in Partially Observable Environments with AI Planning

• Brandon Rozek
• Junkyu Lee
• Harsha Kokel
• Michael Katz
• Shirin Sohrabi

Partially observable Markov decision processes challenge reinforcement learning agents since observations provide an limited view of the environment. This often requires an agent to explore collecting observations to form the necessary state information to complete the task. Even assuming knowledge is monotonic, it is difficult to know when to stop exploration. We integrate AI planning within hierarchical reinforcement learning to aide in the exploration of partially observable environments. Given a set of unknown state variables, their potential valuations, along with which abstract operators may discover them, we create an abstract fully-observable nondeterministic planning problem which captures the agent’s abstract belief state. This decomposes the POMDP into a tree of semi-POMDPs based on sensing outcomes. We evaluate our agent’s performance on a MiniGrid domain and show how guided exploration may improve agent performance.

AAAI Conference 2024 System Paper

Interactive Plan Selection Using Linear Temporal Logic, Disjunctive Action Landmarks, and Natural Language Instruction

• Tathagata Chakraborti
• Jungkoo Kang
• Francesco Fuggitti
• Michael Katz
• Shirin Sohrabi

We present Lemming – a visualization tool for the interactive selection of plans for a given problem, allowing the user to efficiently whittle down the set of plans and select their plan(s) of choice. We demonstrate four different user experiences for this process, three of them based on the principle of using disjunctive action landmarks as guidance to cut down the set of choice points for the user, and one on the use of linear temporal logic (LTL) to impart additional constraints into the plan set using natural language (NL) instruction.

ICAPS Conference 2024 Conference Paper

Large Language Models as Planning Domain Generators

• James T. Oswald
• Kavitha Srinivas
• Harsha Kokel
• Junkyu Lee 0001
• Michael Katz 0001
• Shirin Sohrabi

Developing domain models is one of the few remaining places that require manual human labor in AI planning. Thus, in order to make planning more accessible, it is desirable to automate the process of domain model generation. To this end, we investigate if large language models (LLMs) can be used to generate planning domain models from simple textual descriptions. Specifically, we introduce a framework for automated evaluation of LLM-generated domains by comparing the sets of plans for domain instances. Finally, we perform an empirical analysis of 7 large language models, including coding and chat models across 9 different planning domains, and under three classes of natural language domain descriptions. Our results indicate that LLMs, particularly those with high parameter counts, exhibit a moderate level of proficiency in generating correct planning domains from natural language descriptions. Our code is available at https: //github. com/IBM/NL2PDDL.

AAAI Conference 2024 Short Paper

Large Language Models as Planning Domain Generators (Student Abstract)

• James Oswald
• Kavitha Srinivas
• Harsha Kokel
• Junkyu Lee
• Michael Katz
• Shirin Sohrabi

The creation of planning models, and in particular domain models, is among the last bastions of tasks that require exten- sive manual labor in AI planning; it is desirable to simplify this process for the sake of making planning more accessi- ble. To this end, we investigate whether large language mod- els (LLMs) can be used to generate planning domain models from textual descriptions. We propose a novel task for this as well as a means of automated evaluation for generated do- mains by comparing the sets of plans for domain instances. Finally, we perform an empirical analysis of 7 large language models, including coding and chat models across 9 different planning domains. Our results show that LLMs, particularly larger ones, exhibit some level of proficiency in generating correct planning domains from natural language descriptions

AAAI Conference 2024 Short Paper

Partially Observable Hierarchical Reinforcement Learning with AI Planning (Student Abstract)

• Brandon Rozek
• Junkyu Lee
• Harsha Kokel
• Michael Katz
• Shirin Sohrabi

Partially observable Markov decision processes (POMDPs) challenge reinforcement learning agents due to incomplete knowledge of the environment. Even assuming monotonicity in uncertainty, it is difficult for an agent to know how and when to stop exploring for a given task. In this abstract, we discuss how to use hierarchical reinforcement learning (HRL) and AI Planning (AIP) to improve exploration when the agent knows possible valuations of unknown predicates and how to discover them. By encoding the uncertainty in an abstract planning model, the agent can derive a high-level plan which is then used to decompose the overall POMDP into a tree of semi-POMDPs for training. We evaluate our agent's performance on the MiniGrid domain and show how guided exploration may improve agent performance.

PRL Workshop 2024 Workshop Paper

Planning with Language Models Through The Lens of Efficiency

• Michael Katz
• Harsha Kokel
• Kavitha Srinivas
• Shirin Sohrabi

We analyse the cost of using LLMs for planning and highlight that recent trends are profoundly uneconomical. We propose a significantly more efficient approach and argue for a responsible use of compute resources; urging research community to investigate LLM-based approaches that upholds efficiency.

SoCS Conference 2024 Conference Paper

Some Orders Are Important: Partially Preserving Orders in Top-Quality Planning

• Michael Katz 0001
• Junkyu Lee 0001
• Jungkoo Kang
• Shirin Sohrabi

The ability to generate multiple plans is central to using planning in real-life applications. Top-quality planners generate such sets of top-cost plans, allowing flexibility in determining equivalent plans. In terms of the order between actions in a plan, the literature only considers two extremes -- either all orders are important, making each plan unique, or all orders are unimportant, treating two plans differing only in the order of actions as equivalent. To allow flexibility in selecting important orders, we propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality computational problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem and present experimental evaluations demonstrating the benefits of exploiting such techniques in this setting.

NeurIPS Conference 2024 Conference Paper

Thought of Search: Planning with Language Models Through The Lens of Efficiency

• Michael Katz
• Harsha Kokel
• Kavitha Srinivas
• Shirin Sohrabi

Among the most important properties of algorithms investigated in computer science are soundness, completeness, and complexity. These properties, however, are rarely analyzed for the vast collection of recently proposed methods for planning with large language models. In this work, we alleviate this gap. We analyse these properties of using LLMs for planning and highlight that recent trends abandon both soundness and completeness for the sake of inefficiency. We propose a significantly more efficient approach that can, at the same time, maintain both soundness and completeness. We exemplify on four representative search problems, comparing to the LLM-based solutions from the literature that attempt to solve these problems. We show that by using LLMs to produce the code for the search components we can solve the entire datasets with 100% accuracy with only a few calls to the LLM. In contrast, the compared approaches require hundreds of thousands of calls and achieve significantly lower accuracy. We argue for a responsible use of compute resources; urging research community to investigate sound and complete LLM-based approaches that uphold efficiency.

ICAPS Conference 2024 Conference Paper

Unifying and Certifying Top-Quality Planning

• Michael Katz 0001
• Junkyu Lee 0001
• Shirin Sohrabi

The growing utilization of planning tools in practical scenarios has sparked an interest in generating multiple high-quality plans. Consequently, a range of computational problems under the general umbrella of top-quality planning were introduced over a short time period, each with its own definition. In this work, we show that the existing definitions can be unified into one, based on a dominance relation. The different computational problems, therefore, simply correspond to different dominance relations. Given the unified definition, we can now certify the top-quality of the solutions, leveraging existing certification of unsolvability and optimality. We show that task transformations found in the existing literature can be employed for the efficient certification of various top-quality planning problems and propose a novel transformation to efficiently certify loopless top-quality planning.

IJCAI Conference 2023 Conference Paper

Action Space Reduction for Planning Domains

• Harsha Kokel
• Junkyu Lee
• Michael Katz
• Kavitha Srinivas
• Shirin Sohrabi

Planning tasks succinctly represent labeled transition systems, with each ground action corresponding to a label. This granularity, however, is not necessary for solving planning tasks and can be harmful, especially for model-free methods. In order to apply such methods, the label sets are often manually reduced. In this work, we propose automating this manual process. We characterize a valid label reduction for classical planning tasks and propose an automated way of obtaining such valid reductions by leveraging lifted mutex groups. Our experiments show a significant reduction in the action label space size across a wide collection of planning domains. We demonstrate the benefit of our automated label reduction in two separate use cases: improved sample complexity of model-free reinforcement learning algorithms and speeding up successor generation in lifted planning. The code and supplementary material are available at https: //github. com/IBM/Parameter-Seed-Set.

SoCS Conference 2023 Conference Paper

Generating SAS+ Planning Tasks of Specified Causal Structure

• Michael Katz 0001
• Junkyu Lee 0001
• Shirin Sohrabi

Recent advances in data-driven approaches in AI planning demand more and more planning tasks. The supply, however, is somewhat limited. Past International Planning Competitions (IPCs) have introduced the de-facto standard benchmarks with the domains written by domain experts. The few existing methods for sampling random planning tasks severely limit the resulting problem structure. In this work we show a method for generating planning tasks of any requested causal graph structure, alleviating the shortage in existing planning benchmarks. We present an algorithm for constructing random SAS+ planning tasks given an arbitrary causal graph and offer random task generators for the well-explored causal graph structures in the planning literature. We further allow to generate a planning task equivalent in causal structure to an input SAS+ planning task. We generate two benchmark sets: 26 collections for select well-explored causal graph structures and 42 collections for existing IPC domains. We evaluate both benchmark sets with the state-of-the-art optimal planners, showing the adequacy for adopting them as benchmarks in cost-optimal classical planning. The benchmark sets and the task generator code are publicly available at https: //github. com/IBM/fdr-generator.

PRL Workshop 2023 Workshop Paper

Learning Parameterized Policies for Planning Annotated RL

• Harsha Kokel
• Junkyu Lee
• Michael Katz
• Shirin Sohrabi

Recently, several approaches have utilized AI planning in the context of hierarchical reinforcement learning. These methods employ planning operator descriptions to establish options for acquiring primitive or low-level skills. By employing hierarchical decomposition through operators, these approaches offer notable benefits during training, such as enhanced sample efficiency, as well as during evaluation, with improved generalization across different yet related tasks. In this study, we introduce a novel approach for defining parameterized options using operator descriptions. Our empirical evaluations conducted on the mini-grid domain demonstrate that the proposed approach not only enhances sample efficiency but also overcomes certain limitations associated with generalization capabilities.

SoCS Conference 2023 Conference Paper

On K* Search for Top-K Planning

• Junkyu Lee 0001
• Michael Katz 0001
• Shirin Sohrabi

Finding multiple high-quality plans is essential in many planning applications, and top-k planning asks for finding the k best plans, naturally extending cost-optimal classical planning. Several attempts have been made to formulate top-k classical planning as a k-shortest paths finding problem and apply K* search, which alternates between A* and Eppstein

ICAPS Conference 2023 Conference Paper

On Partial Satisfaction Planning with Total-Order HTNs

• Gregor Behnke
• David Speck 0001
• Michael Katz 0001
• Shirin Sohrabi

Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community. However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure. In this paper, we are taking the necessary steps for facilitating this research direction. First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism. Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure. We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research. Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.

AAAI Conference 2022 Conference Paper

Bounding Quality in Diverse Planning

• Michael Katz
• Shirin Sohrabi
• Octavian Udrea

Diverse planning is an important problem in automated planning with many real world applications. Recently, diverse planning has seen renewed interest, with work that defines a taxonomy of computational problems with respect to both plan quality and solution diversity. However, despite the recent advances in diverse planning, the variety of approaches and the number of available planners are still quite limited, even nonexistent for several computational problems. In this work, we aim to extend the portfolio of planners for various computational problems in diverse planning. To that end, we introduce a novel approach to finding solutions for three computational problems within diverse planning and present planners for these three problems. For one of these problems, our approach is the first one that is able to provide solutions to the problem. For another, we show that top-k and top quality planners can provide, albeit naive, solutions to the problem and we extend these planners to improve the diversity of the solution. Finally, for the third problem, we show that some existing diverse planners already provide solutions to that problem. We suggest another approach and empirically show it to compare favorably with these existing planners.

AAAI Conference 2022 Short Paper

How to Reduce Action Space for Planning Domains? (Student Abstract)

• Harsha Kokel
• Junkyu Lee
• Michael Katz
• Shirin Sohrabi
• Kavitha Srinivas

While AI planning and Reinforcement Learning (RL) solve sequential decision-making problems, they are based on different formalisms, which leads to a significant difference in their action spaces. When solving planning problems using RL algorithms, we have observed that a naive translation of the planning action space incurs severe degradation in sample complexity. In practice, those action spaces are often engineered manually in a domain-specific manner. In this abstract, we present a method that reduces the parameters of operators in AI planning domains by introducing a parameter seed set problem and casting it as a classical planning task. Our experiment shows that our proposed method significantly reduces the number of actions in the RL environments originating from AI planning domains.

ICAPS Conference 2022 Conference Paper

Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators

• Clement Gehring
• Masataro Asai
• Rohan Chitnis
• Tom Silver
• Leslie Pack Kaelbling
• Shirin Sohrabi
• Michael Katz 0001

Recent advances in reinforcement learning (RL) have led to a growing interest in applying RL to classical planning domains or applying classical planning methods to some complex RL domains. However, the long-horizon goal-based problems found in classical planning lead to sparse rewards for RL, making direct application inefficient. In this paper, we propose to leverage domain-independent heuristic functions commonly used in the classical planning literature to improve the sample efficiency of RL. These classical heuristics act as dense reward generators to alleviate the sparse-rewards issue and enable our RL agent to learn domain-specific value functions as residuals on these heuristics, making learning easier. Correct application of this technique requires consolidating the discounted metric used in RL and the non-discounted metric used in heuristics. We implement the value functions using Neural Logic Machines, a neural network architecture designed for grounded first-order logic inputs. We demonstrate on several classical planning domains that using classical heuristics for RL allows for good sample efficiency compared to sparse-reward RL. We further show that our learned value functions generalize to novel problem instances in the same domain. The source code and the appendix are available at github. com/ibm/pddlrl and arxiv. org/abs/2109. 14830.

ICAPS Conference 2022 Conference Paper

Who Needs These Operators Anyway: Top Quality Planning with Operator Subset Criteria

• Michael Katz 0001
• Shirin Sohrabi

Top-quality planning in general and quotient top-quality planning in particular deal with producing multiple high-quality plans while allowing for their efficient generation, skipping equivalent ones. Prior work has explored one equivalence relation, considering two plans to be equivalent if their operator multi-sets are equal. This allowed omitting plans that are reorderings of previously found ones. However, the resulting sets of plans were still large, in some domains even infinite. In this paper, we consider a different relation: two plans are related if one's operator multiset is a subset of the other's. We propose novel reformulations that forbid plans that are related to the given ones. While the new relation is not transitive and thus not an equivalence relation, we can define a new subset top-quality planning problem, with finite size solution sets. We formally prove that these solutions can be obtained by exploiting the proposed reformulations. Our empirical evaluation shows that solutions to the new problem can be found for more tasks than unordered top-quality planning solutions. Further, the results shows that the solution sizes significantly decrease, making the new approach more practical, particularly in domains with redundant operators.

PRL Workshop 2021 Workshop Paper

AI Planning Annotation in Reinforcement Learning: Options and Beyond

• Junkyu Lee
• Michael Katz
• Don Joven Agravante
• Miao Liu
• Tim Klinger
• Murray Campbell
• Shirin Sohrabi
• Gerald Tesauro

AI planning and reinforcement learning (RL) both solve sequential decision-making problems, taking fundamentally different approaches. In this work, we aim to bring AI planning and RL closer by investigating the relationship between abstractions in AI planning and the options framework in RL. To this end, we propose annotating RL tasks with AI planning models, allowing us to define options based purely on the planning model. Our experimental investigation shows that these options can be quickly trained offline and can improve the sample efficiency of a reinforcement learning algorithm.

AAAI Conference 2021 System Paper

IBM Scenario Planning Advisor: A Neuro-Symbolic ERM Solution

• Mark Feblowitz
• Oktie Hassanzadeh
• Michael Katz
• Shirin Sohrabi
• Kavitha Srinivas
• Octavian Udrea

Scenario Planning is a commonly used Enterprise Risk Management (ERM) technique to help decision makers with longterm plans by considering multiple alternative futures. It is typically a manual, highly labor intensive process involving dozens of experts and hundreds to thousands of person-hours. We previously introduced a Scenario Planning Advisor prototype (Sohrabi et al. 2018a, b) that focuses on generating scenarios quickly based on expert-developed models. We present the evolution of that prototype into a full-scale, clouddeployed ERM solution that: (i) can automatically (through NLP) create models from authoritative documents such as books, reports and articles, such that what typically took hundreds to thousands of person-hours can now be achieved in minutes to hours; (ii) can gather news and other feeds relevant to forces in the risk models and group them into storylines without any other user input; (iii) can generate scenarios at scale, starting with dozens of forces of interest from models with thousands of forces in seconds; (iv) provides interactive visualizations of scenario and force model graphs, including a full model editor in the browser. The SPA solution is deployed under a non-commercial use license at https: //spa-service. draco. res. ibm. com and includes a user guide to help new users get started. A video demonstration is available at https: //www. youtube. com/watch? v=Gd4CMKclkBY.

PRL Workshop 2021 Workshop Paper

Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators

• Clement Gehring
• Masataro Asai
• Rohan Chitnis
• Tom Silver
• Leslie Kaelbling
• Shirin Sohrabi
• Michael Katz

Recent advances in reinforcement learning (RL) have led to a growing interest in applying RL to classical planning domains and vise versa. However, the long-horizon goal-based problems found in classical planning lead to sparse rewards for RL, making direct application inefficient. In this paper, we propose to leverage domain-independent heuristic functions commonly used in the classical planning literature to improve the sample efficiency of RL. These classical heuristics act as dense reward generators to alleviate the sparse-rewards issue and our RL agent learns domain-specific value functions as residuals on these heuristics, making learning easier. Proper application of this technique requires consolidating the discounted metric in RL and non-discounted metric in heuristics. We implement the value functions using Neural Logic Machines, a neural network architecture designed for grounded first-order logic inputs. We demonstrate on several classical planning domains that using classical heuristics for RL allows for good sample efficiency compared to sparse-reward RL. We further show that our learned value functions generalize to novel problem instances in the same domain.

AAAI Conference 2021 Short Paper

Unsupervised Causal Knowledge Extraction from Text using Natural Language Inference (Student Abstract)

• Manik Bhandari
• Mark Feblowitz
• Oktie Hassanzadeh
• Kavitha Srinivas
• Shirin Sohrabi

In this paper, we address the problem of extracting causal knowledge from text documents in a weakly supervised manner. We target use cases in decision support and risk management, where causes and effects are general phrases without any constraints. We present a method called CaKNowLI which only takes as input the text corpus and extracts a highquality collection of cause-effect pairs in an automated way. We approach this problem using state-of-the-art natural language understanding techniques based on pre-trained neural models for Natural Language Inference (NLI). Finally, we evaluate the proposed method on existing and new benchmark data sets.

AAAI Conference 2020 System Paper

Causal Knowledge Extraction through Large-Scale Text Mining

• Oktie Hassanzadeh
• Debarun Bhattacharjya
• Mark Feblowitz
• Kavitha Srinivas
• Michael Perrone
• Shirin Sohrabi
• Michael Katz

In this demonstration, we present a system for mining causal knowledge from large corpuses of text documents, such as millions of news articles. Our system provides a collection of APIs for causal analysis and retrieval. These APIs enable searching for the effects of a given cause and the causes of a given effect, as well as the analysis of existence of causal relation given a pair of phrases. The analysis includes a score that indicates the likelihood of the existence of a causal relation. It also provides evidence from an input corpus supporting the existence of a causal relation between input phrases. Our system uses generic unsupervised and weakly supervised methods of causal relation extraction that do not impose semantic constraints on causes and effects. We show example use cases developed for a commercial application in enterprise risk management.

ICAPS Conference 2020 Conference Paper

Exploring Context-Free Languages via Planning: The Case for Automating Machine Learning

• Michael Katz 0001
• Parikshit Ram
• Shirin Sohrabi
• Octavian Udrea

While Machine Learning has achieved considerable success in recent years, this success crucially relies on human experts to select appropriate features, workflows, algorithms with their hyper-parameters, etc. Automating the role of the human expert has seen some attention from the Machine Learning community, with a dedicated workshop running since 2014 at one of the top Machine Learning conferences. % In this work, we propose to exploit multiple AI Planning tools for automating the human expert, generating Machine Learning pipelines automatically. We start from a knowledge about possible valid pipelines encoded as Context-Free Grammar, translate the problem of generating the corresponding language into Hierarchical Task Network (HTN) Planning model, further translate the HTN Planning model into a classical planning model. We use existing planners to produce multiple plans for the classical planning task, translate these plans into Machine Learning pipelines, train and evaluate these pipelines. Based on pipelines' accuracy feedback we update the classical planning model to improve the quality of pipelines obtained in next iterations. Using planning tools allows us to exploit the flexibility of model update instead of solution modification. We present an application that helps users to focus pipelines' exploration process by allowing to encode additional constraints on desired pipelines. Our experimental evaluation shows the feasibility of using planning techniques in this context.

AAAI Conference 2020 Conference Paper

Reshaping Diverse Planning

• Michael Katz
• Shirin Sohrabi

The need for multiple plans has been established by various planning applications. In some, solution quality has the predominant role, while in others diversity is the key factor. Most recent work takes both plan quality and solution diversity into account under the generic umbrella of diverse planning. There is no common agreement, however, on a collection of computational problems that fall under that generic umbrella. This in particular might lead to a comparison between planners that have different solution guarantees or optimization criteria in mind. In this work we revisit diverse planning literature in search of such a collection of computational problems, classifying the existing planners to these problems. We formally define a taxonomy of computational problems with respect to both plan quality and solution diversity, extending the existing work. We propose a novel approach to diverse planning, exploiting existing classical planners via planning task reformulation and choosing a subset of plans of required size in post-processing. Based on that, we present planners for two computational problems, that most existing planners solve. Our experiments show that the proposed approach significantly improves over the best performing existing planners in terms of coverage, the overall solution quality, and the overall diversity according to various diversity metrics.

AAAI Conference 2020 Conference Paper

Top-Quality Planning: Finding Practically Useful Sets of Best Plans

• Michael Katz
• Shirin Sohrabi
• Octavian Udrea

The need for finding a set of plans rather than one has been motivated by a variety of planning applications. The problem is studied in the context of both diverse and top-k planning: while diverse planning focuses on the difference between pairs of plans, the focus of top-k planning is on the quality of each individual plan. Recent work in diverse planning introduced additionally restrictions on solution quality. Naturally, there are application domains where diversity plays the major role and domains where quality is the predominant feature. In both cases, however, the amount of produced plans is often an artificial constraint, and therefore the actual number has little meaning. Inspired by the recent work in diverse planning, we propose a new family of computational problems called topquality planning, where solution validity is defined through plan quality bound rather than an arbitrary number of plans. Switching to bounding plan quality allows us to implicitly represent sets of plans. In particular, it makes it possible to represent sets of plans that correspond to valid plan reorderings with a single plan. We formally define the unordered top-quality planning computational problem and present the first planner for that problem. We empirically demonstrate the superior performance of our approach compared to a top-k planner-based baseline, ranging from 41% increase in coverage for finding all optimal plans to 69% increase in coverage for finding all plans of quality up to 120% of optimal plan cost. Finally, complementing the new approach by a complete procedure for generating all valid reorderings of a given plan, we derive a top-quality planner. We show the planner to be competitive with a top-k planner based baseline.

IJCAI Conference 2019 Conference Paper

AI Planning for Enterprise: Putting Theory Into Practice

• Shirin Sohrabi

In this paper, I overview a number of AI Planning applications for Enterprise and discuss a number of challenges in applying AI Planning in that setting. I will also summarize the progress made to date in addressing these challenges.

IJCAI Conference 2019 Conference Paper

Answering Binary Causal Questions Through Large-Scale Text Mining: An Evaluation Using Cause-Effect Pairs from Human Experts

• Oktie Hassanzadeh
• Debarun Bhattacharjya
• Mark Feblowitz
• Kavitha Srinivas
• Michael Perrone
• Shirin Sohrabi
• Michael Katz

In this paper, we study the problem of answering questions of type "Could X cause Y? " where X and Y are general phrases without any constraints. Answering such questions will assist with various decision analysis tasks such as verifying and extending presumed causal associations used for decision making. Our goal is to analyze the ability of an AI agent built using state-of-the-art unsupervised methods in answering causal questions derived from collections of cause-effect pairs from human experts. We focus only on unsupervised and weakly supervised methods due to the difficulty of creating a large enough training set with a reasonable quality and coverage. The methods we examine rely on a large corpus of text derived from news articles, and include methods ranging from large-scale application of classic NLP techniques and statistical analysis to the use of neural network based phrase embeddings and state-of-the-art neural language models.

AAAI Conference 2019 Conference Paper

Deep Learning for Cost-Optimal Planning: Task-Dependent Planner Selection

• Silvan Sievers
• Michael Katz
• Shirin Sohrabi
• Horst Samulowitz
• Patrick Ferber

As classical planning is known to be computationally hard, no single planner is expected to work well across many planning domains. One solution to this problem is to use online portfolio planners that select a planner for a given task. These portfolios perform a classification task, a well-known and wellresearched task in the field of machine learning. The classification is usually performed using a representation of planning tasks with a collection of hand-crafted statistical features. Recent techniques in machine learning that are based on automatic extraction of features have not been employed yet due to the lack of suitable representations of planning tasks. In this work, we alleviate this barrier. We suggest representing planning tasks by images, allowing to exploit arguably one of the most commonly used and best developed techniques in deep learning. We explore some of the questions that inevitably rise when applying such a technique, and present various ways of building practically useful online portfoliobased planners. An evidence of the usefulness of our proposed technique is a planner that won the cost-optimal track of the International Planning Competition 2018.

ICAPS Conference 2018 Conference Paper

A Novel Iterative Approach to Top-k Planning

• Michael Katz 0001
• Shirin Sohrabi
• Octavian Udrea
• Dominik Winterer

While cost-optimal planning aims at finding one best quality plan, top-k planning deals with finding a set of solutions, such that no better quality solution exists outside that set. We propose a novel iterative approach to top-k planning, exploiting any cost-optimal planner and reformulating a planning task to forbid exactly the given set of solutions. In addition, to compare to existing approaches to finding top-k solutions, we implement the K∗ algorithm in an existing PDDL planner, creating the first K∗ based solver for PDDL planning tasks. We empirically show that the iterative approach performs better for up to a large required size solution sets (thousands), while K∗ based approach excels on extremely large ones.

AAAI Conference 2018 Conference Paper

An AI Planning Solution to Scenario Generation for Enterprise Risk Management

• Shirin Sohrabi
• Anton Riabov
• Michael Katz
• Octavian Udrea

Scenario planning is a commonly used method by companies to develop their long-term plans. Scenario planning for risk management puts an added emphasis on identifying and managing emerging risk. While a variety of methods have been proposed for this purpose, we show that applying AI planning techniques to devise possible scenarios provides a unique advantage for scenario planning. Our system, the Scenario Planning Advisor (SPA), takes as input the relevant information from news and social media, representing key risk drivers, as well as the domain knowledge and generates scenarios that explain the key risk drivers and describe the alternative futures. To this end, we provide a characterization of the problem, knowledge engineering methodology, and transformation to planning. Furthermore, we describe the computation of the scenarios, lessons learned, and the feedback received from the pilot deployment of the SPA system in IBM.

IJCAI Conference 2018 Conference Paper

IBM Scenario Planning Advisor: Plan Recognition as AI Planning in Practice

• Shirin Sohrabi
• Michael Katz
• Oktie Hassanzadeh
• Octavian Udrea
• Mark D. Feblowitz

We present the IBM Research Scenario Planning Advisor (SPA), a decision support system that allows users to generate diverse alternate scenarios of the future and enhance their ability to imagine the different possible outcomes, including unlikely but potentially impactful futures. The system includes tooling for experts to intuitively encode their domain knowledge, and uses AI Planning to reason about this knowledge and the current state of the world, including news and social media, when generating scenarios.

AAAI Conference 2017 Conference Paper

State Projection via AI Planning

• Shirin Sohrabi
• Anton Riabov
• Octavian Udrea

Imagining the future helps anticipate and prepare for what is coming. This has great importance to many, if not all, human endeavors. In this paper, we develop the Planning Projector system prototype, which applies plan-recognition-asplanning technique to both explain the observations derived from analyzing relevant news and social media, and project a range of possible future state trajectories for human review. Unlike the plan recognition problem, where a set of goals, and often a plan library must be given as part of the input, the Planning Projector system takes as input the domain knowledge, a sequence of observations derived from the news, a time horizon, and the number of trajectories to produce. It then computes the set of trajectories by applying a planner capable of finding a set of high-quality plans on a transformed planning problem. The Planning Projector prototype integrates several components including: (1) knowledge engineering: the process of encoding the domain knowledge from domain experts; (2) data transformation: the problem of analyzing and transforming the raw data into a sequence of observations; (3) trajectory computation: characterizing the future state projection problem and computing a set of trajectories; (4) user interface: clustering and visualizing the trajectories. We evaluate our approach qualitatively and conclude that the Planning Projector helps users understand future possibilities so that they can make more informed decisions.

ECAI Conference 2016 Conference Paper

Finding Diverse High-Quality Plans for Hypothesis Generation

• Shirin Sohrabi
• Anton V. Riabov
• Octavian Udrea
• Oktie Hassanzadeh

In this paper, we address the problem of finding diverse high-quality plans motivated by the hypothesis generation problem. To this end, we present a planner called TK*that first efficiently solves the "top-k" cost-optimal planning problem to find k best plans, followed by clustering to produce diverse plans as cluster representatives.

IJCAI Conference 2016 Conference Paper

Interactive Planning-Based Hypothesis Generation with LTS++

• Shirin Sohrabi
• Octavian Udrea
• Anton V. Riabov
• Oktie Hassanzadeh

We present LTS++, an interactive development environment for planning-based hypothesis generation in applications with unreliable observations.

IJCAI Conference 2016 Conference Paper

Plan Recognition as Planning Revisited

• Shirin Sohrabi
• Anton V. Riabov
• Octavian Udrea

In this paper, we propose to extend previous work to (1) address observations over fluents, (2) better address unreliable observations (i. e. , noisy or missing observations), and (3) recognize plans in addition to goals. To this end, we introduce a relaxation of the plan-recognition-as-planning formulation that allows unreliable observations. That is, in addition to the original costs of the plan, we define two objectives that account for missing and noisy observations, and optimize for a linear combination of all objectives. We approximate the posterior probabilities of generated plans by taking into account the combined costs that include penalties for missing or noisy observations, and normalizing over a sample set of plans generated by finding either diverse or high-quality plans. Our experiments show that this approach improves goal recognition in most domains when observations are unreliable. In addition, we evaluate plan recognition performance and show that the high-quality plan generation approach should be preferred in most domains.

ICAPS Conference 2015 Conference Paper

Planning-Based Reasoning for Automated Large-Scale Data Analysis

• Anton V. Riabov
• Shirin Sohrabi
• Daby Sow
• Deepak S. Turaga
• Octavian Udrea
• Long H. Vu

In this paper, we apply planning-based reasoning to orchestrate the data analysis process automatically, with a focus on two applications: early detection of health complications in critical care, and detection of anomalous behaviors of network hosts in enterprise networks. Our system uses expert knowledge and AI planning to reason about possibly incomplete, noisy, or inconsistent observations, derived from data by deploying an open set of analytics, to generate plausible and consistent hypotheses about the state of the world. From these hypotheses, relevant actions are triggered leading to the deployment of additional analytics, or adaptation of existing analytics, that produce new observations for further reasoning. Planning-based reasoning is enabled by knowledge models obtained from domain experts that describe entities in the world, their states, and relationship to observations. To address the associated knowledge engineering challenges, we propose a modeling language named LTS++ and build an Integrated Development Environment. We also develop a process that provides support and guidance to domain experts, with no planning expertise, in defining and constructing models. We use this modeling process to capture knowledge for the two applications and to collect user feedback. Furthermore, we conduct empirical evaluation to demonstrate the feasibility of our approach and the benefits of using planning-based reasoning in these applications, at large real-world scales. Specifically, in the network monitoring scenario, we show that the system can dynamically deploy and manage analytics for the effective detection of anomalies and malicious behaviors with lead times of over 15 minutes, in an enterprise network with over 2 million hosts (entities).

ICAPS Conference 2013 Conference Paper

HTN Planning for the Composition of Stream Processing Applications

• Shirin Sohrabi
• Octavian Udrea
• Anand Ranganathan
• Anton V. Riabov

Goal-driven automated composition of software components is an important problem with applications in Web service composition and stream processing systems. The popular approach to address this problem is to build the composition automatically using AI planning. However, it is shown that some of these planning approaches may neither be feasible nor scalable for many large-scale flow-based applications. Recent advances have proven that the automated composition problem can take advantage of expert knowledge describing the many ways in which different reusable components can be composed. This knowledge can be represented using an extensible composition template or pattern. In prior work, a flow pattern language called Cascade and its corresponding specialized planner have shown the best performance in these domains. In this paper, we propose the use of Hierarchical Task Network (HTN) planning for the composition of stream processing applications. To this end, we propose an automated approach of creating an HTN-based problem from the Cascade representation of the flow patterns. The resulting technique not only allows us to use the HTN planning paradigm and its many advantages including added expressivity but also enables optimization and customization of composition with respect to preferences and constraints. Further, we propose and develop a lookahead heuristic and show that it significantly reduces the planning time. We have performed extensive experimentation with stream processing applications and evaluated applicability and performance of our approach.

AAAI Conference 2013 Conference Paper

Hypothesis Exploration for Malware Detection Using Planning

• Shirin Sohrabi
• Octavian Udrea
• Anton Riabov

In this paper we apply AI planning to address the hypothesis exploration problem and provide assistance to network administrators in detecting malware based on unreliable observations derived from network traffic. Building on the already established characterization and use of AI planning for similar problems, we propose a formulation of the hypothesis generation problem for malware detection as an AI planning problem with temporally extended goals and actions costs. Furthermore, we propose a notion of hypothesis “plausibility” under unreliable observations, which we model as plan quality. We then show that in the presence of unreliable observations, simply finding one most “plausible” hypothesis, although challenging, is not sufficient for effective malware detection. To that end, we propose a method for applying a stateof-the-art planner within a principled exploration process, to generate multiple distinct high-quality plans. We experimentally evaluate this approach by generating random problems of varying hardness both with respect to the number of observations, as well as the degree of unreliability. Based on these experiments, we argue that our approach presents a significant improvement over prior work that are focused on finding a single optimal plan, and that our hypothesis exploration application can motivate the development of new planners capable of generating the top high-quality plans.

AAAI Conference 2011 Conference Paper

Preferred Explanations: Theory and Generation via Planning

• Shirin Sohrabi
• Jorge Baier
• Sheila McIlraith

In this paper we examine the general problem of generating preferred explanations for observed behavior with respect to a model of the behavior of a dynamical system. This problem arises in a diversity of applications including diagnosis of dynamical systems and activity recognition. We provide a logical characterization of the notion of an explanation. To generate explanations we identify and exploit a correspondence between explanation generation and planning. The determination of good explanations requires additional domainspecific knowledge which we represent as preferences over explanations. The nature of explanations requires us to formulate preferences in a somewhat retrodictive fashion by utilizing Past Linear Temporal Logic. We propose methods for exploiting these somewhat unique preferences effectively within state-of-the-art planners and illustrate the feasibility of generating (preferred) explanations via planning.

KR Conference 2010 Conference Paper

Diagnosis as Planning Revisited

• Shirin Sohrabi
• Jorge A. Baier
• Sheila A. McIlraith

In discrete dynamical systems change results from actions. As such, given a set of observations, diagnoses often take the form of posited events that result in the observed behaviour. In this paper we revisit formal characterizations of diagnosis, and their relationship to planning. We do so from both a theoretical and a computational perspective. In particular, we extend the characterization of diagnosis to deal with the case of incomplete information, and rich preferences. We also explore the use of state-of-the-art planning technology for the automated generation of diagnoses. Examining several classes of diagnosis problems, we provide both proof of concept and benchmark experiments, the latter showing superior performance to a leading diagnosis engine. Our findings help support the hypothesis that planning technology holds great promise for efficient generation of diagnoses.

IJCAI Conference 2009 Conference Paper

• Shirin Sohrabi
• Jorge A. Baier
• Sheila A. McIlraith

In this paper we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich user preferences. To this end, we extend the popular Planning Domain Definition Language, PDDL3, to support specification of simple and temporally extended preferences over HTN constructs. To compute preferred HTN plans, we propose a branch-and-bound algorithm, together with a set of heuristics that, leveraging HTN structure, measure progress towards satisfaction of preferences. Our preference-based planner, HTNPLAN-P, is implemented as an extension of the SHOP2 planner. We compared our planner with SGPlan5 and HPLAN-P– the top performers in the 2006 International Planning Competition preference tracks. HTNPLAN-P generated plans that in all but a few cases equalled or exceeded the quality of plans returned by HPLAN-P and SGPlan5. While our implementation builds on SHOP2, the language and techniques proposed here are relevant to a broad range of HTN planners.