Counting and Reasoning with Plans

• URL: http://arxiv.org/abs/2502.00145v1
• Date: Fri, 31 Jan 2025 20:03:51 GMT
• Title: Counting and Reasoning with Plans
• Authors: David Speck, Markus Hecher, Daniel Gnad, Johannes K. Fichte, Augusto B. Corrêa,
• Abstract summary: We present the first study to quantitative and qualitative reasoning on the plan space. On the theoretical side, we study its complexity, which gives rise to rich reasoning modes. Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans.
• Score: 19.223883847258158
• License:
• Abstract: Classical planning asks for a sequence of operators reaching a given goal. While the most common case is to compute a plan, many scenarios require more than that. However, quantitative reasoning on the plan space remains mostly unexplored. A fundamental problem is to count plans, which relates to the conditional probability on the plan space. Indeed, qualitative and quantitative approaches are well-established in various other areas of automated reasoning. We present the first study to quantitative and qualitative reasoning on the plan space. In particular, we focus on polynomially bounded plans. On the theoretical side, we study its complexity, which gives rise to rich reasoning modes. Since counting is hard in general, we introduce the easier notion of facets, which enables understanding the significance of operators. On the practical side, we implement quantitative reasoning for planning. Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans. This framework scales well to large plan spaces, while enabling rich reasoning capabilities such as learning pruning functions and explainable planning.

Related papers

• Introduction to AI Planning [0.0]
  The notes begin by introducing the state model and move on to exploring classical planning. The most extensive section is dedicated to Hierarchical Task Network (HTN) planning. The lecture notes end with a bonus chapter on the Planning Domain Definition (PDDL) Language.
  arXiv  Detail & Related papers  (2024-12-16T10:38:04Z)
• Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
  We introduce CodePlan, a framework that generates and follows textcode-form plans -- pseudocode that outlines high-level, structured reasoning processes. CodePlan effectively captures the rich semantics and control flows inherent to sophisticated reasoning tasks. It achieves a 25.1% relative improvement compared with directly generating responses.
  arXiv  Detail & Related papers  (2024-09-19T04:13:58Z)
• LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning [65.86754998249224]
  We develop a novel hybrid planner that leverages a conventional rule-based planner in conjunction with an LLM-based planner. Our approach navigates complex scenarios which existing planners struggle with, produces well-reasoned outputs while also remaining grounded through working alongside the rule-based approach.
  arXiv  Detail & Related papers  (2023-12-30T02:53:45Z)
• Learning adaptive planning representations with natural language guidance [90.24449752926866]
  This paper describes Ada, a framework for automatically constructing task-specific planning representations. Ada interactively learns a library of planner-compatible high-level action abstractions and low-level controllers adapted to a particular domain of planning tasks.
  arXiv  Detail & Related papers  (2023-12-13T23:35:31Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Symbolic Search for Optimal Planning with Expressive Extensions [4.36572039512405]
  Some properties of a planning problem at hand require an expressive extension of the standard classical planning formalism to capture and model them. We study planning with axioms, planning with state-dependent action costs, oversubscription planning, and top-k planning.
  arXiv  Detail & Related papers  (2022-04-01T08:41:06Z)
• Robust Hierarchical Planning with Policy Delegation [6.1678491628787455]
  We propose a novel framework and algorithm for hierarchical planning based on the principle of delegation. We show this planning approach is experimentally very competitive to classic planning and reinforcement learning techniques on a variety of domains.
  arXiv  Detail & Related papers  (2020-10-25T04:36:20Z)
• Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks [28.488201307961624]
  Real-world planning problems often involve hundreds or even thousands of objects. We propose a graph neural network architecture for predicting object importance in a single inference pass. Our approach treats the planner and transition model as black boxes, and can be used with any off-the-shelf planner.
  arXiv  Detail & Related papers  (2020-09-11T18:55:08Z)
• Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors [124.30562402952319]
  The ability to predict and plan into the future is fundamental for agents acting in the world. Current learning approaches for visual prediction and planning fail on long-horizon tasks. We propose a framework for visual prediction and planning that is able to overcome both of these limitations.
  arXiv  Detail & Related papers  (2020-06-23T17:58:56Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)
• The Efficiency of Human Cognition Reflects Planned Information Processing [40.51474966524166]
  We make predictions about how people should plan and meta-plan as a function of the overall structure of a task. We find that people's reaction times reflect a planned use of information processing. This formulation of planning to plan provides new insight into the function of hierarchical planning, state abstraction, and cognitive control in both humans and machines.
  arXiv  Detail & Related papers  (2020-02-13T20:34:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.