Abstraction of Nondeterministic Situation Calculus Action Theories -- Extended Version

• URL: http://arxiv.org/abs/2305.14222v1
• Date: Sat, 20 May 2023 05:42:38 GMT
• Title: Abstraction of Nondeterministic Situation Calculus Action Theories -- Extended Version
• Authors: Bita Banihashemi, Giuseppe De Giacomo, Yves Lesp\'erance
• Abstract summary: We develop a general framework for abstracting the behavior of an agent that operates in a nondeterministic domain. We assume that we have both an abstract and a concrete nondeterministic basic action theory. We show that if the agent has a (strong FOND) plan/strategy to achieve a goal/complete a task at the abstract level, and it can always execute the nondeterministic abstract actions to completion at the concrete level.
• Score: 23.24285208243607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a general framework for abstracting the behavior of an agent that operates in a nondeterministic domain, i.e., where the agent does not control the outcome of the nondeterministic actions, based on the nondeterministic situation calculus and the ConGolog programming language. We assume that we have both an abstract and a concrete nondeterministic basic action theory, and a refinement mapping which specifies how abstract actions, decomposed into agent actions and environment reactions, are implemented by concrete ConGolog programs. This new setting supports strategic reasoning and strategy synthesis, by allowing us to quantify separately on agent actions and environment reactions. We show that if the agent has a (strong FOND) plan/strategy to achieve a goal/complete a task at the abstract level, and it can always execute the nondeterministic abstract actions to completion at the concrete level, then there exists a refinement of it that is a (strong FOND) plan/strategy to achieve the refinement of the goal/task at the concrete level.

Related papers

• DynaSaur: Large Language Agents Beyond Predefined Actions [108.75187263724838]
  Existing LLM agent systems typically select actions from a fixed and predefined set at every step. We propose an LLM agent framework that enables the dynamic creation and composition of actions in an online manner. Our experiments on the GAIA benchmark demonstrate that this framework offers significantly greater flexibility and outperforms previous methods.
  arXiv  Detail & Related papers  (2024-11-04T02:08:59Z)
• Abstracting Situation Calculus Action Theories [24.181367387692944]
  We assume that we have a high-level specification and a low-level specification of the agent, both represented as basic action theories. A refinement mapping specifies how each high-level action is implemented by a low-level ConGolog program. We identify a set of basic action theory constraints that ensure that for any low-level action sequence, there is a unique high-level action sequence.
  arXiv  Detail & Related papers  (2024-10-09T16:34:28Z)
• Learning Abstract World Model for Value-preserving Planning with Options [11.254212901595523]
  We leverage the structure of a given set of temporally-extended actions to learn abstract Markov decision processes (MDPs) We characterize state abstractions necessary to ensure that planning with these skills, by simulating trajectories in the abstract MDP, results in policies with bounded value loss in the original MDP. We evaluate our approach in goal-based navigation environments that require continuous abstract states to plan successfully and show that abstract model learning improves the sample efficiency of planning and learning.
  arXiv  Detail & Related papers  (2024-06-22T13:41:02Z)
• Unified Task and Motion Planning using Object-centric Abstractions of Motion Constraints [56.283944756315066]
  We propose an alternative TAMP approach that unifies task and motion planning into a single search. Our approach is based on an object-centric abstraction of motion constraints that permits leveraging the computational efficiency of off-the-shelf AI search to yield physically feasible plans.
  arXiv  Detail & Related papers  (2023-12-29T14:00:20Z)
• 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)
• Code Models are Zero-shot Precondition Reasoners [83.8561159080672]
  We use code representations to reason about action preconditions for sequential decision making tasks. We propose a precondition-aware action sampling strategy that ensures actions predicted by a policy are consistent with preconditions.
  arXiv  Detail & Related papers  (2023-11-16T06:19:27Z)
• Consciousness-Inspired Spatio-Temporal Abstractions for Better Generalization in Reinforcement Learning [83.41487567765871]
  Skipper is a model-based reinforcement learning framework. It automatically generalizes the task given into smaller, more manageable subtasks. It enables sparse decision-making and focused abstractions on the relevant parts of the environment.
  arXiv  Detail & Related papers  (2023-09-30T02:25:18Z)
• LTLf Best-Effort Synthesis in Nondeterministic Planning Domains [27.106071554421664]
  We study best-effort strategies (aka plans) in fully observable nondeterministic domains (FOND) We present a game-theoretic synthesis technique for synthesizing best-effort strategies that exploit the specificity of nondeterministic planning domains.
  arXiv  Detail & Related papers  (2023-08-29T10:10:41Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• Exploration Policies for On-the-Fly Controller Synthesis: A Reinforcement Learning Approach [0.0]
  We propose a new method for obtaining unboundeds based on Reinforcement Learning (RL) Our agents learn from scratch in a highly observable partially RL task and outperform existing overall, in instances unseen during training.
  arXiv  Detail & Related papers  (2022-10-07T20:28:25Z)
• Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning [26.715198108255162]
  We develop a novel framework for learning state and action abstractions. We learn relational, neuro-symbolic abstractions that generalize over object identities and numbers. We show that our learned abstractions are able to quickly solve held-out tasks of longer horizons.
  arXiv  Detail & Related papers  (2022-03-17T22:13:09Z)
• Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization [30.456180468318305]
  In the sequential decision making setting, an agent aims to achieve systematic generalization over a large, possibly infinite, set of environments. In this paper, we provide a tractable formulation of systematic generalization by employing a causal viewpoint. Under specific structural assumptions, we provide a simple learning algorithm that guarantees any desired planning error up to an unavoidable sub-optimality term.
  arXiv  Detail & Related papers  (2022-02-14T08:34:51Z)
• Generalized Inverse Planning: Learning Lifted non-Markovian Utility for Generalizable Task Representation [83.55414555337154]
  In this work, we study learning such utility from human demonstrations. We propose a new quest, Generalized Inverse Planning, for utility learning in this domain. We outline a computational framework, Maximum Entropy Inverse Planning (MEIP), that learns non-Markovian utility and associated concepts in a generative manner.
  arXiv  Detail & Related papers  (2020-11-12T21:06:26Z)

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.