GenAI4ELab/papercli-papers huggingface dataset:
Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis
Authors: Pascal Bachor; Gregor Behnke
Venue: AAAI 2024 (main)

Abstract: Domain learning is the task of finding an action model that can explain given observed plan executions, so-called traces.                                                                                   
It allows us to automate the identification of actions' preconditions and effects instead of relying on hand-modeled expert knowledge.                                                                      
While previous research has put forth various techniques and covers multiple planning formalisms, the theoretical foundations of domain learning are still in their infancy.
                                                                                                                                                                                                          
We investigate the most basic setting, that is grounded classical planning without negative preconditions or conditional effects with full observability of the state variables.                            
The given traces are assumed to be justified in the sense that either no single action or no set of actions can be removed without violating correctness of the plan.                                       
Furthermore, we might be given additional constraints in the form of a propositional logical formula.                                                                                                       
We show the consequences of these assumptions for the computational complexity of identifying a satisfactory planning domain.
Dealing with Numeric and Metric Time Constraints in PDDL3 via Compilation to Numeric Planning
Authors: Luigi Bonassi; Alfonso Emilio Gerevini; Enrico Scala
Venue: AAAI 2024 (main)

Abstract: This paper studies an approach to planning with PDDL3 constraints involving mixed propositional and numeric conditions, as well as metric time constraints.  
We show how the whole PDDL3 with instantaneous actions can be compiled away into a numeric planning problem without PDDL3 constraints, enabling the use of any state-of-the-art numeric planner that is agnostic to the existence of PDDL3. Our solution exploits the concept of regression. In addition to a basic compilation, we present an optimized variant based on the observation that it is possible to make the compilation sensitive to the structure of the problem to solve; this can be done by reasoning on the interactions between the problem actions and the constraints. The resulting optimization substantially reduces the size of the planning task. We experimentally observe that our approach significantly outperforms existing state-of-the-art planners supporting the same class of constraints over known benchmark domains, settling a new state-of-the-art planning system for PDDL3.
The Complexity of Optimizing Atomic Congestion
Authors: Cornelius Brand; Robert Ganian; Subrahmanyam Kalyanasundaram; Fionn Mc Inerney
Venue: AAAI 2024 (main)

Abstract: Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies - that is, a centrally planned routing that minimizes the average cost of agents - is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
Stop! Planner Time: Metareasoning for Probabilistic Planning Using Learned Performance Profiles
Authors: Matthew Budd; Bruno Lacerda; Nick Hawes
Venue: AAAI 2024 (main)

Abstract: The metareasoning framework aims to enable autonomous agents to factor in planning costs when making decisions. In this work, we develop the first non-myopic metareasoning algorithm for planning with Markov decision processes. Our method learns the behaviour of anytime probabilistic planning algorithms from performance data. Specifically, we propose a novel model for metareasoning, based on contextual performance profiles that predict the value of the planner's current solution given the time spent planning, the state of the planning algorithm's internal parameters, and the difficulty of the planning problem being solved. This model removes the need to assume that the current solution quality is always known, broadening the class of metareasoning problems that can be addressed. We then employ deep reinforcement learning to learn a policy that decides, at each timestep, whether to continue planning or start executing the current plan, and how to set hyperparameters of the planner to enhance its performance. We demonstrate our algorithm's ability to perform effective metareasoning in two domains.
Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning
Authors: Turgay Caglar; Sirine Belhaj; Tathagata Chakraborty; Michael Katz; Sarath Sreedharan
Venue: AAAI 2024 (main)

Abstract: 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.
Symbolic Numeric Planning with Patterns
Authors: Matteo Cardellini; Enrico Giunchiglia; Marco Maratea
Venue: AAAI 2024 (main)

Abstract: In this paper, we propose a novel  approach for solving linear numeric planning problems, called Symbolic Pattern Planning. Given a planning problem Pi, a bound n and a pattern --defined as an arbitrary sequence of actions-- we encode the problem of finding a plan for Pi with bound n as a formula with fewer variables and/or clauses than the state-of-the-art rolled-up and relaxed-relaxed-exists encodings. More importantly, we prove that for any given bound, it is never the case that the latter two encodings allow finding a valid plan while ours does not. On the experimental side, we consider 6 other planning systems  --including the ones which participated in this year's International Planning Competition (IPC)-- and we show that our planner Patty has remarkably good comparative performances on this year's IPC problems.
Learning Domain-Independent Heuristics for Grounded and Lifted Planning
Authors: Dillon Z. Chen; Sylvie Thiébaux; Felipe Trevizan
Venue: AAAI 2024 (main)

Abstract: We present three novel graph representations of planning tasks suitable for learning domain-independent heuristics using Graph Neural Networks (GNNs) to guide search. In particular, to mitigate the issues caused by large grounded GNNs we present the first method for learning domain-independent heuristics with only the lifted representation of a planning task. We also provide a theoretical analysis of the expressiveness of our models, showing that some are more powerful than STRIPS-HGN, the only other existing model for learning domain-independent heuristics. Our experiments show that our heuristics generalise to much larger problems than those in the training set, vastly surpassing STRIPS-HGN heuristics.
Approximate Distance Oracle for Fault-Tolerant Geometric Spanners
Authors: Kyungjin Cho; Jihun Shin; Eunjin Oh
Venue: AAAI 2024 (main)

Abstract: In this paper, we present approximate distance and shortest-path oracles for fault-tolerant Euclidean spanners motivated by the routing problem in real-world road networks.
A fault-tolerant Euclidean spanner for a set of points in Euclidean space is a graph
in which, despite the deletion of small number of any points, the distance between any two points in the damaged graph is an approximation of their Euclidean distance. 
Given a fault-tolerant Euclidean spanner and a small approximation factor, 
our data structure allows us to compute an approximate distance between two points in the damaged spanner in constant time when a query involves any two points and a small set of failed points. 
Additionally, by incorporating additional data structures, we can return a path itself in time almost linear in the length of the returned path. 
Both data structures require near-linear space.
Optimizing the Optimization of Planning Domains by Automatic Action Schema Splitting
Authors: Mojtaba Elahi; Jussi Rintanen
Venue: AAAI 2024 (main)

Abstract: Most planners are based on grounding, that is, generating all instances of a parameterized action during a preprocessing phase.
For some problems the number of ground actions is too high, causing a performance bottleneck.
Building upon an existing approach, we present an enhanced method to split action schemas automatically during the grounding phase, to reduce the number of ground actions.
First, we propose to exploit the structural knowledge of the problems to have a more informative dependency graph.
Then, we suggest a better objective function to define and choose the best split.
Finally, we present a more effective search to find it.
We experimentally measure the impact of each of these improvements, and show that our approach significantly outperforms the state of the art.
An Effective Polynomial Technique for Compiling Conditional Effects Away
Authors: Alfonso Emilio Gerevini; Francesco Percassi; Enrico Scala
Venue: AAAI 2024 (main)

Abstract: The paper introduces a novel polynomial compilation technique for the sound and complete removal of conditional effects in classical planning problems. Similar to Nebel's polynomial compilation of conditional effects, our solution also decomposes each action with conditional effects into several simpler actions. However, it does so more effectively by exploiting the actual structure of the given conditional effects. We characterise such a structure using a directed graph and leverage it to significantly reduce the number of additional atoms required, thereby shortening the size of valid plans. Our experimental analysis indicates that this approach enables the effective use of polynomial compilations, offering benefits in terms of modularity and reusability of existing planners. It also demonstrates that a compilation-based approach can be more efficient, either independently or in synergy with state-of-the-art optimal planners that directly support conditional effects.
GOALNET: Interleaving Neural Goal Predicate Inference with Classical Planning for Generalization in Robot Instruction Following
Authors: Jigyasa Gupta; Shreya Sharma; Shreshth Tuli; Rohan Paul; Mausam
Venue: AAAI 2024 (main)

Abstract: Our goal is to enable a robot to learn how to sequence its actions to perform high-level tasks specified as natural language instructions, given successful demonstrations from a human partner. Our novel neuro-symbolic solution GOALNET builds an iterative two-step approach that interleaves (i) inferring next subgoal predicate implied by the language instruction, for a given world state, and (ii) synthesizing a feasible subgoal-reaching plan from that state. The agent executes the plan, and the two steps are repeated. GOALNET combines (i) learning, where dense representations are acquired for language instruction and the world state via a neural network prediction model, enabling generalization to novel settings and (ii) planning, where the cause-effect modeling by a classical planner eschews irrelevant predicates, facilitating multi-stage decision making in large domains. GOALNET obtains 78% improvement in the goal reaching rate in comparison to several state-of-the-art approaches on benchmark data with multi-stage instructions. Further, GOALNET can generalize to novel instructions for scenes with unseen objects. Source code available at https://github. com/reail-iitd/goalnet.
SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge
Authors: Rishi Hazra; Pedro Zuidberg Dos Martires; Luc De Raedt
Venue: AAAI 2024 (main)

Abstract: Large Language Models (LLMs) have demonstrated impressive planning abilities due to their vast "world knowledge". Yet, obtaining plans that are both feasible (grounded in affordances) and cost-effective (in plan length), remains a challenge, despite recent progress. This contrasts with heuristic planning methods that employ domain knowledge (formalized in action models such as PDDL) and heuristic search to generate feasible, optimal plans. Inspired by this, we propose to combine the power of LLMs and heuristic planning by leveraging the world knowledge of LLMs and the principles of heuristic search. Our approach, SayCanPay, employs LLMs to generate actions (Say) guided by learnable domain knowledge, that evaluates actions' feasibility (Can) and long-term reward/payoff (Pay), and heuristic search to select the best sequence of actions. Our contributions are (1) a novel framing of the LLM planning problem in the context of heuristic planning, (2) integrating grounding and cost-effective elements into the generated plans, and (3) using heuristic search over actions. Our extensive evaluations show that our model surpasses other LLM planning approaches.
A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees
Authors: Marcus Hoerger; Hanna Kurniawati; Dirk Kroese; Nan Ye
Venue: AAAI 2024 (main)

Abstract: The Partially Observable Markov Decision Process (POMDP) provides a principled framework for decision making in stochastic partially observable environments. However, computing good solutions for problems with continuous action spaces remains challenging. To ease this challenge, we propose a simple online POMDP solver, called Lazy Cross-Entropy Search Over Policy Trees (LCEOPT). At each planning step, our method uses a novel lazy Cross-Entropy method to search the space of policy trees, which provide a simple policy representation. Specifically, we maintain a distribution on promising finite-horizon policy trees. The distribution is iteratively updated by sampling policies, evaluating them via Monte Carlo simulation, and refitting them to the top-performing ones. Our method is lazy in the sense that it exploits the policy tree representation to avoid redundant computations in policy sampling, evaluation, and distribution update. This leads to computational savings of up to two orders of magnitude. Our LCEOPT is surprisingly simple as compared to existing state-of-the-art methods, yet empirically outperforms them on several continuous-action POMDP problems, particularly for problems with higher-dimensional action spaces.
Optimizing Local Satisfaction of Long-Run Average Objectives in Markov Decision Processes
Authors: David Klaška; Antonín Kučera; Vojtěch Kůr; Vít Musil; Vojtěch Řehák
Venue: AAAI 2024 (main)

Abstract: Long-run average optimization problems for Markov decision processes (MDPs) require constructing policies with optimal steady-state behavior, i.e., optimal limit frequency of visits to the states. However, such policies may suffer from local instability in the sense that the frequency of states visited in a bounded time horizon along a run differs significantly from the limit frequency. In this work, we propose an efficient algorithmic solution to this problem.
Monte Carlo Tree Search in the Presence of Transition Uncertainty
Authors: Farnaz Kohankhaki; Kiarash Aghakasiri; Hongming Zhang; Ting-Han Wei; Chao Gao; Martin Müller
Venue: AAAI 2024 (main)

Abstract: Monte Carlo Tree Search (MCTS) is an immensely popular search-based framework used for decision making. It is traditionally applied to domains where a perfect simulation model of the environment is available. We study and improve MCTS in the context where the environment model is given but imperfect. We show that the discrepancy between the model and the actual environment can lead to significant performance degradation with standard MCTS. We therefore develop Uncertainty Adapted MCTS (UA-MCTS), a more robust algorithm within the MCTS framework. We estimate the transition uncertainty in the given model, and direct the search towards more certain transitions in the state space. We modify all four MCTS phases to improve the search behavior by considering these estimates. We prove, in the corrupted bandit case, that adding uncertainty information to adapt UCB leads to tighter regret bound than standard UCB. Empirically, we evaluate UA-MCTS and its individual components on the deterministic domains from the MinAtar test suite. Our results demonstrate that UA-MCTS strongly improves MCTS in the presence of model transition errors.
Learning Safe Action Models with Partial Observability
Authors: Hai S. Le; Brendan Juba; Roni Stern
Venue: AAAI 2024 (main)

Abstract: A common approach for solving planning problems is to model them in a formal language such as the Planning Domain Definition Language (PDDL), and then use an appropriate PDDL planner. 
Several algorithms for learning PDDL models from observations have been proposed but plans created with these learned models may not be sound. 
We propose two algorithms for learning PDDL models that are guaranteed to be safe to use even when given observations that include partially observable states. 
We analyze these algorithms theoretically, characterizing the sample complexity each algorithm requires to guarantee probabilistic completeness. 
We also show experimentally that our algorithms are often better than FAMA, a state-of-the-art PDDL learning algorithm.
Generalized Planning for the Abstraction and Reasoning Corpus
Authors: Chao Lei; Nir Lipovetzky; Krista A. Ehinger
Venue: AAAI 2024 (main)

Abstract: The Abstraction and Reasoning Corpus (ARC) is a general artificial intelligence benchmark that poses difficulties for pure machine learning methods due to its requirement for fluid intelligence with a focus on reasoning and abstraction. In this work, we introduce an ARC solver, Generalized Planning for Abstract Reasoning (GPAR). It casts an ARC problem as a generalized planning (GP) problem, where a solution is formalized as a planning program with pointers. We express each ARC problem using the standard Planning Domain Definition Language (PDDL) coupled with external functions representing object-centric abstractions. We show how to scale up GP solvers via domain knowledge specific to ARC in the form of restrictions over the actions model, predicates, arguments and valid structure of planning programs. Our experiments demonstrate that  GPAR outperforms the state-of-the-art solvers on the object-centric tasks of the ARC, showing the effectiveness of GP and the expressiveness of PDDL to model ARC problems. The challenges provided by the ARC benchmark motivate research to advance existing GP solvers and understand new relations with other planning computational models. Code is available at github.com/you68681/GPAR.
Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice
Authors: Idan Lev-Yehudi; Moran Barenboim; Vadim Indelman
Venue: AAAI 2024 (main)

Abstract: Solving partially observable Markov decision processes (POMDPs) with high dimensional and continuous observations, such as camera images, is required for many real life robotics and planning problems. Recent researches suggested machine learned probabilistic models as observation models, but their use is currently too computationally expensive for online deployment. We deal with the question of what would be the implication of using simplified observation models for planning, while retaining formal guarantees on the quality of the solution. Our main contribution is a novel probabilistic bound based on a statistical total variation distance of the simplified model. We show that it bounds the theoretical POMDP value w.r.t. original model, from the empirical planned value with the simplified model, by generalizing recent results of particle-belief MDP concentration bounds. Our calculations can be separated into offline and online parts, and we arrive at formal guarantees without having to access the costly model at all during planning, which is also a novel result. Finally, we demonstrate in simulation how to integrate the bound into the routine of an existing continuous online POMDP solver.
Learning to Optimize Permutation Flow Shop Scheduling via Graph-Based Imitation Learning
Authors: Longkang Li; Siyuan Liang; Zihao Zhu; Chris Ding; Hongyuan Zha; Baoyuan Wu
Venue: AAAI 2024 (main)

Abstract: The permutation flow shop scheduling (PFSS), aiming at finding the optimal permutation of jobs, is widely used in manufacturing systems. When solving large-scale PFSS problems, traditional optimization algorithms such as heuristics could hardly meet the demands of both solution accuracy and computational efficiency, thus learning-based methods have recently garnered more attention. Some work attempts to solve the problems by reinforcement learning methods, which suffer from slow convergence issues during training and are still not accurate enough regarding the solutions. To that end, we propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Moreover, in order to extract better feature representations of input jobs, we incorporate the graph structure as the encoder. The extensive experiments reveal that our proposed model obtains significant promotion and presents excellent generalizability in large-scale problems with up to 1000 jobs. Compared to the state-of-the-art reinforcement learning method, our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average. The code is available at: https://github.com/longkangli/PFSS-IL.
NaRuto: Automatically Acquiring Planning Models from Narrative Texts
Authors: Ruiqi Li; Leyang Cui; Songtuan Lin; Patrik Haslum
Venue: AAAI 2024 (main)

Abstract: Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.