Arrow Research search

Author name cluster

Michael Katz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
1 author row

Possible papers

49

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.

PDF Details DOI

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.

PDF Details DOI

PRL Workshop 2025 Workshop Paper

AI Planning: A Primer and Survey (Preliminary Report)

  • Dillon Ze Chen
  • Pulkit Verma
  • Siddharth Srivastava
  • Michael Katz
  • Sylvie Thiebaux

Automated decision-making is a fundamental topic that spans multiple sub-disciplines in AI: reinforcement learning (RL), AI planning (AP), foundation models, and operations research, among others. Despite recent efforts to “bridge the gaps” between these communities, there remain many insights that have not yet transcended the boundaries. Our goal in this paper is to provide a brief and non-exhaustive primer on ideas well-known in AP, but less so in other subdisciplines. We do so by introducing the classical AP problem and representation, and extensions that handle uncertainty and time through the Markov Decision Process formalism. Next, we survey state-of-the-art techniques and ideas for solving AP problems, focusing on their ability to exploit problem structure. Lastly, we cover subfields within AP for learning structure from unstructured inputs and learning to generalise to unseen scenarios and situations.

PDF Details

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.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning

  • Turgay Caglar
  • Sirine Belhaj
  • Tathagata Chakraborty
  • Michael Katz
  • Sarath Sreedharan

This is the first work to look at the application of large language models (LLMs) for the purpose of model space edits in automated planning tasks. To set the stage for this union, we explore two different flavors of model space problems that have been studied in the AI planning literature and explore the effect of an LLM on those tasks. We empirically demonstrate how the performance of an LLM contrasts with combinatorial search (CS) – an approach that has been traditionally used to solve model space tasks in planning, both with the LLM in the role of a standalone model space reasoner as well as in the role of a statistical signal in concert with the CS approach as part of a two-stage process. Our experiments show promising results suggesting further forays of LLMs into the exciting world of model space reasoning for planning tasks in the future.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Generalized Planning in PDDL Domains with Pretrained Large Language Models

  • Tom Silver
  • Soham Dan
  • Kavitha Srinivas
  • Joshua B. Tenenbaum
  • Leslie Kaelbling
  • Michael Katz

Recent work has considered whether large language models (LLMs) can function as planners: given a task, generate a plan. We investigate whether LLMs can serve as generalized planners: given a domain and training tasks, generate a program that efficiently produces plans for other tasks in the domain. In particular, we consider PDDL domains and use GPT-4 to synthesize Python programs. We also consider (1) Chain-of-Thought (CoT) summarization, where the LLM is prompted to summarize the domain and propose a strategy in words before synthesizing the program; and (2) automated debugging, where the program is validated with respect to the training tasks, and in case of errors, the LLM is re-prompted with four types of feedback. We evaluate this approach in seven PDDL domains and compare it to four ablations and four baselines. Overall, we find that GPT-4 is a surprisingly powerful generalized planner. We also conclude that automated debugging is very important, that CoT summarization has non-uniform impact, that GPT-4 is far superior to GPT-3.5, and that just two training tasks are often sufficient for strong generalization.

PDF Details DOI

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.

PDF Details

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.

PDF Details DOI

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

PDF Details DOI

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.

PDF Details DOI

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.

PDF Details

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.

PDF Details DOI

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.

PDF Details DOI

PRL Workshop 2023 Workshop Paper

Generalized Planning in PDDL Domains with Pretrained Large Language Models

  • Tom Silver
  • Soham Dan
  • Kavitha Srinivas
  • Joshua B. Tenenbaum
  • Leslie Pack Kaelbling
  • Michael Katz

Recent work has considered whether large language models (LLMs) can function as planners: given a task, generate a plan. We investigate whether LLMs can serve as generalized planners: given a domain and training tasks, generate a program that efficiently produces plans for other tasks in the domain. In particular, we consider PDDL domains and use GPT-4 to synthesize Python programs. We also consider (1) Chain-of-Thought (CoT) summarization, where the LLM is prompted to summarize the domain and propose a strategy in words before synthesizing the program; and (2) automated debugging, where the program is validated with respect to the training tasks, and in case of errors, the LLM is re-prompted with four types of feedback. We evaluate this approach in seven PDDL domains and compare it to four ablations and four baselines. Overall, we find that GPT-4 is a surprisingly powerful generalized planner. We also conclude that automated debugging is very important, that CoT summarization has non-uniform impact, that GPT-4 is far superior to GPT-3.5, and that just two training tasks are often sufficient for strong generalization.

PDF Details

IJCAI Conference 2023 Conference Paper

K∗ Search over Orbit Space for Top-k Planning

  • Michael Katz
  • Junkyu Lee

Top-k planning, the task of finding k top-cost plans, is a key formalism for many planning applications and K* search is a well-established approach to top-k planning. The algorithm iteratively runs A* search and Eppstein’s algorithm until a sufficient number of plans is found. The performance of K* algorithm is therefore inherently limited by the performance of A*, and in order to improve K* performance, that of A* must be improved. In cost-optimal planning, orbit space search improves A* performance by exploiting symmetry pruning, essentially performing A* in the orbit space instead of state space. In this work, we take a similar approach to top-k planning. We show theoretical equivalence between the goal paths in the state space and in the orbit space, allowing to perform K* search in the orbit space instead, reconstructing plans from the found paths in the orbit space. We prove that our algorithm is sound and complete for top-k planning and empirically show it to achieve state-of-the-art performance, overtaking all existing to date top-k planners. The code is available at https: //github. com/IBM/kstar.

PDF Details DOI

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.

PDF Details

PRL Workshop 2023 Workshop Paper

Optimistic Exploration in Reinforcement Learning Using Symbolic Model Estimates

  • Sarath Sreedharan
  • Michael Katz

There has been an increasing interest in using symbolic models along with reinforcement learning (RL) problems, where these coarser abstract models are used as a way to provide RL agents with higher level guidance. However, most of these works are inherently limited by their assumption of having an access to a symbolic approximation of the underlying problem. To address this issue, we introduce a new method for learning optimistic symbolic approximations of the underlying world model. We will see how these representations, coupled with fast diverse planners developed by the automated planning community, provide us with a new paradigm for optimistic exploration in sparse reward settings. We investigate the possibility of speeding up the learning process by generalizing learned model dynamics across similar actions with minimal human input. Finally, we evaluate the method, by testing it on multiple benchmark domains and compare it with other RL strategies.

PDF Details

NeurIPS Conference 2023 Conference Paper

Optimistic Exploration in Reinforcement Learning Using Symbolic Model Estimates

  • Sarath Sreedharan
  • Michael Katz

There has been an increasing interest in using symbolic models along with reinforcement learning (RL) problems, where these coarser abstract models are used as a way to provide RL agents with higher level guidance. However, most of these works are inherently limited by their assumption of having an access to a symbolic approximation of the underlying problem. To address this issue, we introduce a new method for learning optimistic symbolic approximations of the underlying world model. We will see how these representations, coupled with fast diverse planners developed by the automated planning community, provide us with a new paradigm for optimistic exploration in sparse reward settings. We investigate the possibility of speeding up the learning process by generalizing learned model dynamics across similar actions with minimal human input. Finally, we evaluate the method, by testing it on multiple benchmark domains and compare it with other RL strategies.

PDF Details

PRL Workshop 2023 Workshop Paper

Towards More Likely Models for AI Planning

  • Turgay Caglar
  • Sirine Belhaj
  • Tathagata Chakraborti
  • Michael Katz
  • Sarath Sreedharan

This is the first work to look at the application of large language models (LLMs) for model space edits in automated planning tasks. We look at two quintessential model-space reasoning tasks: unsolvability and explanations. We empirically demonstrate how the performance of an LLM contrasts with combinatorial search (CS) -- an approach that has been traditionally used to solve model space tasks in planning -- with the increasing complexity of model edits and the increasing complexity of plans, both with the LLM in the role of a standalone model-space reasoner as well as in concert with the CS approach as part of a two-stage process. Our experiments show promising results suggesting further forays of LLMs into the exciting world of model space reasoning for planning tasks in the future.

PDF Details

AAAI Conference 2022 Conference Paper

A* Search and Bound-Sensitive Heuristics for Oversubscription Planning

  • Michael Katz
  • Emil Keyder

Oversubscription planning (OSP) is the problem of finding plans that maximize the utility value of their end state while staying within a specified cost bound. Recently, it has been shown that OSP problems can be reformulated as classical planning problems with multiple cost functions but no utilities. Here we take advantage of this reformulation to show that OSP problems can be solved optimally using the A∗ search algorithm, in contrast to previous approaches that have used variations on branch-and-bound search. This allows many powerful techniques developed for classical planning to be applied to OSP problems. We also introduce novel bound-sensitive heuristics, which are able to reason about the primary cost of a solution while taking into account secondary cost functions and bounds, to provide superior guidance compared to heuristics that do not take these bounds into account. We propose two such bound-sensitive variants of existing classical planning heuristics, and show experimentally that the resulting search is significantly more informed than with comparable heuristics that do not consider bounds.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

IJCAI Conference 2021 Conference Paper

Custom-Design of FDR Encodings: The Case of Red-Black Planning

  • Daniel Fišer
  • Daniel Gnad
  • Michael Katz
  • Jörg Hoffmann

Classical planning tasks are commonly described in PDDL, while most planning systems operate on a grounded finite-domain representation (FDR). The translation of PDDL into FDR is complex and has a lot of choice points---it involves identifying so called mutex groups---but most systems rely on the translator that comes with Fast Downward. Yet the translation choice points can strongly impact performance. Prior work has considered optimizing FDR encodings in terms of the number of variables produced. Here we go one step further by proposing to custom-design FDR encodings, optimizing the encoding to suit particular planning techniques. We develop such a custom design here for red-black planning, a partial delete relaxation technique. The FDR encoding affects the causal graph and the domain transition graph structures, which govern the tractable fragment of red-black planning and hence affects the respective heuristic function. We develop integer linear programming techniques optimizing the scope of that fragment in the resulting FDR encoding. We empirically show that the performance of red-black planning can be improved through such FDR custom design.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Efficient Black-Box Planning Using Macro-Actions with Focused Effects

  • Cameron Allen
  • Michael Katz
  • Tim Klinger
  • George Konidaris
  • Matthew Riemer
  • Gerald Tesauro

The difficulty of deterministic planning increases exponentially with search-tree depth. Black-box planning presents an even greater challenge, since planners must operate without an explicit model of the domain. Heuristics can make search more efficient, but goal-aware heuristics for black-box planning usually rely on goal counting, which is often quite uninformative. In this work, we show how to overcome this limitation by discovering macro-actions that make the goal-count heuristic more accurate. Our approach searches for macro-actions with focused effects (i. e. macros that modify only a small number of state variables), which align well with the assumptions made by the goal-count heuristic. Focused macros dramatically improve black-box planning efficiency across a wide range of planning domains, sometimes beating even state-of-the-art planners with access to a full domain model.

PDF Details DOI

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.

PDF Details

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.

PDF Details

AAAI Conference 2021 Conference Paper

Symbolic Search for Oversubscription Planning

  • David Speck
  • Michael Katz

The objective of optimal oversubscription planning is to find a plan that yields an end state with a maximum utility while keeping plan cost under a certain bound. In practice, the situation occurs whenever a large number of possible, often competing goals of varying value exist, or the resources are not sufficient to achieve all goals. In this paper, we investigate the use of symbolic search for optimal oversubscription planning. Specifically, we show how to apply symbolic forward search to oversubscription planning tasks and prove that our approach is sound, complete and optimal. An empirical analysis shows that our symbolic approach favorably competes with explicit state-space heuristic search, the current state of the art for oversubscription planning.

PDF Details

IJCAI Conference 2021 Conference Paper

The Fewer the Merrier: Pruning Preferred Operators with Novelty

  • Alexander Tuisov
  • Michael Katz

Heuristic search is among the best performing approaches to classical satisficing planning, with its performance heavily relying on informative and fast heuristics, as well as search-boosting and pruning techniques. While both heuristics and pruning techniques have gained much attention recently, search-boosting techniques in general, and preferred operators in particular have received less attention in the last decade. Our work aims at bringing the light back to preferred operators research, with the introduction of preferred operators pruning technique, based on the concept of novelty. Continuing the research on novelty with respect to an underlying heuristic, we present the definition of preferred operators for such novelty heuristics. For that, we extend the previously defined concepts to operators, allowing us to reason about the novelty of the preferred operators. Our experimental evaluation shows the practical benefit of our suggested approach, compared to the currently used methods.

PDF Details DOI

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.

PDF Details

AAAI Conference 2020 Conference Paper

Online Planner Selection with Graph Neural Networks and Adaptive Scheduling

  • Tengfei Ma
  • Patrick Ferber
  • Siyu Huo
  • Jie Chen
  • Michael Katz

Automated planning is one of the foundational areas of AI. Since no single planner can work well for all tasks and domains, portfolio-based techniques have become increasingly popular in recent years. In particular, deep learning emerges as a promising methodology for online planner selection. Owing to the recent development of structural graph representations of planning tasks, we propose a graph neural network (GNN) approach to selecting candidate planners. GNNs are advantageous over a straightforward alternative, the convolutional neural networks, in that they are invariant to node permutations and that they incorporate node labels for better inference. Additionally, for cost-optimal planning, we propose a twostage adaptive scheduling method to further improve the likelihood that a given task is solved in time. The scheduler may switch at halftime to a different planner, conditioned on the observed performance of the first one. Experimental results validate the effectiveness of the proposed method against strong baselines, both deep learning and non-deep learning based. The code is available at https: //github. com/matenure/GNN planner.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

AAAI Conference 2019 Conference Paper

Red-Black Heuristics for Planning Tasks with Conditional Effects

  • Michael Katz

Red-black planning is a state-of-the-art approach to satisficing classical planning. Red-black planning heuristics are at the heart of the planner Mercury, the runner-up of a satisficing track in the International Planning Competition (IPC) 2014 and a major component of four additional planners in IPC 2018, including Saarplan, the runner-up in the agile track. Mercury’s exceptional performance is amplified by the fact that conditional effects were handled by the planner in a trivial way, simply by compiling them away. Conditional effects, however, are important for classical planning, and many domains require them for efficient modeling. Consequently, we investigate the possibility of handling conditional effects directly in the red-black planning heuristic function, extending the algorithm for computing red-black plans to the conditional effects setting. We show empirically that red-black planning heuristics that handle conditional effects natively outperform the variants that compile this feature away, improving coverage on tasks where black variables exist by 19%.

PDF Details

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.

PDF Details

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.

PDF Details

AAAI Conference 2018 Conference Paper

Semi-Black Box: Rapid Development of Planning Based Solutions

  • Michael Katz
  • Dany Moshkovich
  • Erez Karpas

Software developers nowadays not infrequently face a challenge of solving problems that essentially sum up to finding a sequence of deterministic actions leading from a given initial state to a goal. This is the problem of deterministic planning, one of the most basic and well studied problems in artificial intelligence. Two of the best known approaches to deterministic planning are the black box approach, in which a programmer implements a successor generator, and the modelbased approach, in which a user describes the problem symbolically, e. g. , in PDDL. While the black box approach is usually easier for programmers who are not experts in AI to understand, it does not scale up without informative heuristics. We propose an approach that we baptize as semi-black box (SBB) that combines the strength of both. SBB is implemented as a set of Java classes, which a programmer can inherit from when implementing a successor generator. Using the known characteristics of these classes, we then automatically derive heuristics for the problem. Our empirical evaluation shows that these heuristics allow the planner to scale up significantly better than the traditional black box approach.

PDF Details

IJCAI Conference 2016 Conference Paper

In Search of Tractability for Partial Satisfaction Planning

  • Michael Katz
  • Vitaly Mirkis

The objective of partial satisfaction planning is to achieve an as valuable as possible state, tacking into account the cost of its achievement. In this work we investigate the computational complexity of restricted fragments of two variants of partial satisfaction: net-benefit and oversubscription planning. In particular, we examine restrictions on the causal graph structure and variable domain size of the planning problem, and show that even for the strictest such restrictions, optimal oversubscription planning is hard. In contrast, certain tractability results previously obtained for classical planning also apply to net-benefit planning. We then partially relax these restrictions in order to find the boundary of tractability for both variants of partial satisfaction planning. In addition, for the family of $0$-binary value functions we show a strong connection between the complexity of cost-optimal classical and optimal oversubscription planning.

PDF Details

IJCAI Conference 2016 Conference Paper

Structural Symmetries for Fully Observable Nondeterministic Planning

  • Dominik Winterer
  • Martin Wehrle
  • Michael Katz

Symmetry reduction has significantly contributed to the success of classical planning as heuristic search. However, it is an open question if symmetry reduction techniques can be lifted to fully observable nondeterministic (FOND) planning. We generalize the concepts of structural symmetries and symmetry reduction to FOND planning and specifically to the LAO* algorithm. Our base implementation of LAO* in the Fast Downward planner is competitive with the LAO*-based FOND planner myND. Our experiments further show that symmetry reduction can yield strong performance gains compared to our base implementation of LAO*.

PDF Details

AAAI Conference 2015 Conference Paper

Factored Symmetries for Merge-and-Shrink Abstractions

  • Silvan Sievers
  • Martin Wehrle
  • Malte Helmert
  • Alexander Shleyfman
  • Michael Katz

Merge-and-shrink heuristics crucially rely on effective reduction techniques, such as bisimulation-based shrinking, to avoid the combinatorial explosion of abstractions. We propose the concept of factored symmetries for merge-andshrink abstractions based on the established concept of symmetry reduction for state-space search. We investigate under which conditions factored symmetry reduction yields perfect heuristics and discuss the relationship to bisimulation. We also devise practical merging strategies based on this concept and experimentally validate their utility.

PDF Details

AAAI Conference 2015 Conference Paper

Heuristics and Symmetries in Classical Planning

  • Alexander Shleyfman
  • Michael Katz
  • Malte Helmert
  • Silvan Sievers
  • Martin Wehrle

Heuristic search is a state-of-the-art approach to classical planning. Several heuristic families were developed over the years to automatically estimate goal distance information from problem descriptions. Orthogonally to the development of better heuristics, recent years have seen an increasing interest in symmetry-based state space pruning techniques that aim at reducing the search effort. However, little work has dealt with how the heuristics behave under symmetries. We investigate the symmetry properties of existing heuristics and reveal that many of them are invariant under symmetries.

PDF Details

IJCAI Conference 2015 Conference Paper

Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning

  • Martin Wehrle
  • Malte Helmert
  • Alexander Shleyfman
  • Michael Katz

Pruning techniques based on partial order reduction and symmetry elimination have recently found increasing attention for optimal planning. Although these techniques appear to be rather different, they base their pruning decisions on similar ideas from a high level perspective. In this paper, we propose safe integrations of partial order reduction and symmetry elimination for cost-optimal classical planning. We show that previously proposed symmetrybased search algorithms can safely be applied with strong stubborn sets. In addition, we derive the notion of symmetrical strong stubborn sets as a more tightly integrated concept. Our experiments show the potential of our approaches.

PDF Details

AIJ Journal 2015 Journal Article

Red–black planning: A new systematic approach to partial delete relaxation

  • Carmel Domshlak
  • Jörg Hoffmann
  • Michael Katz

To date, delete relaxation underlies some of the most effective heuristics for deterministic planning. Despite its success, however, delete relaxation has significant pitfalls in many important classes of planning domains, and it has been a challenge from the outset to devise heuristics that take some deletes into account. We herein devise an elegant and simple method for doing just that. In the context of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red–black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. We investigate the tractability region of red–black planning, extending Chen and Giménez' characterization theorems for regular planning to the more general red–black setting. In particular, we identify significant islands of tractable red–black planning, use them to design practical heuristic functions, and experiment with a range of “painting strategies” for automatically choosing the red variables. Our experiments show that these new heuristic functions can improve significantly on the state of the art in satisficing planning. 1

Details DOI

AAAI Conference 2013 Conference Paper

Red-Black Relaxed Plan Heuristics

  • Michael Katz
  • Joerg Hoffmann
  • Carmel Domshlak

Despite its success, the delete relaxation has significant pitfalls. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Provided the red variables are chosen so that redblack plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for redblack plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate redblack plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics.

PDF Details

AIJ Journal 2012 Journal Article

Landmark-enhanced abstraction heuristics

  • Carmel Domshlak
  • Michael Katz
  • Sagi Lefler

Abstractions and landmarks are two of the key mechanisms for devising admissible heuristics for domain-independent planning. Here we aim at combining them by integrating landmark information into abstractions. We propose a concrete scheme for compiling landmarks into the problem specification. This scheme, which preserves all reachable properties of the original problem, is especially suited to implicit abstraction heuristics. Our formal and empirical analysis shows that landmark information can substantially improve the quality of heuristic estimates.

Details DOI

AAAI Conference 2012 Conference Paper

Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning

  • Michael Katz
  • Emil Keyder

Tractability analysis in terms of the causal graphs of planning problems has emerged as an important area of research in recent years, leading to new methods for the derivation of domain-independent heuristics (Katz and Domshlak 2010). Here we continue this work, extending our knowledge of the frontier between tractable and NP-complete fragments. We close some gaps left in previous work, and introduce novel causal graph fragments that we call the hourglass and semifork, for which under certain additional assumptions optimal planning is in P. We show that relaxing any one of the restrictions required for this tractability leads to NP-complete problems. Our results are of both theoretical and practical interest, as these fragments can be used in existing frameworks to derive new abstraction heuristics. Before they can be used, however, a number of practical issues must be addressed. We discuss these issues and propose some solutions.

PDF Details

AIJ Journal 2010 Journal Article

Optimal admissible composition of abstraction heuristics

  • Michael Katz
  • Carmel Domshlak

Additive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively composed in infinitely many ways and the quality of the resulting heuristic estimate depends directly on the choice of the composition. Focusing on abstraction heuristics, we describe a procedure that takes a deterministic planning problem, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all abstraction heuristics with which we are acquainted, including explicit abstractions such as pattern databases (regular or constrained) and merge-and-shrink, and implicit abstractions such as fork-decomposition and abstractions based on tractable constraint optimization over tree-shaped constraint networks.

Details DOI
v2026.09.13