Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions

• URL: http://arxiv.org/abs/2505.22147v1
• Date: Wed, 28 May 2025 09:08:27 GMT
• Title: Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions
• Authors: Florian Andreas Marwitz, Tanya Braun, Ralf Möller, Marcel Gehrke,
• Abstract summary: We present a first-order representation to store the spaces in instead of exponential size in the number of objects.<n>We also introduce Foreplan, a relational forward planner, which uses this representation to efficiently compute policies for numerous indistinguishable objects and actions.
• Score: 3.8034305806296747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision making is a central problem in AI that can be formalized using a Markov Decision Process. A problem is that, with increasing numbers of (indistinguishable) objects, the state space grows exponentially. To compute policies, the state space has to be enumerated. Even more possibilities have to be enumerated if the size of the action space depends on the size of the state space, especially if we allow concurrent actions. To tackle the exponential blow-up in the action and state space, we present a first-order representation to store the spaces in polynomial instead of exponential size in the number of objects and introduce Foreplan, a relational forward planner, which uses this representation to efficiently compute policies for numerous indistinguishable objects and actions. Additionally, we introduce an even faster approximate version of Foreplan. Moreover, Foreplan identifies how many objects an agent should act on to achieve a certain task given restrictions. Further, we provide a theoretical analysis and an empirical evaluation of Foreplan, demonstrating a speedup of at least four orders of magnitude.

Related papers

• Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game [26.665033202052257]
  We propose a procedure for creating a planning benchmark centered around the game called Countdown.<n>We discuss how this problem meets many of the desiderata associated with an ideal benchmark for planning capabilities evaluation.<n>Our results show that, unlike other domains like 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches.
  arXiv  Detail & Related papers  (2025-08-04T21:01:03Z)
• Counting and Reasoning with Plans [19.223883847258158]
  We present the first study to quantitative and qualitative reasoning on the plan space.<n>On the theoretical side, we study its complexity, which gives rise to rich reasoning modes.<n>Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans.
  arXiv  Detail & Related papers  (2025-01-31T20:03:51Z)
• 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)
• 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)
• Skip-Plan: Procedure Planning in Instructional Videos via Condensed Action Space Learning [85.84504287685884]
  Skip-Plan is a condensed action space learning method for procedure planning in instructional videos. By skipping uncertain nodes and edges in action chains, we transfer long and complex sequence functions into short but reliable ones. Our model explores all sorts of reliable sub-relations within an action sequence in the condensed action space.
  arXiv  Detail & Related papers  (2023-10-01T08:02:33Z)
• 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)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic [11.878820609988693]
  We examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency.
  arXiv  Detail & Related papers  (2021-12-29T07:30:47Z)
• Learning to Search in Task and Motion Planning with Streams [20.003445874753233]
  Task and motion planning problems in robotics combine symbolic planning over discrete task variables with motion optimization over continuous state and action variables. We propose a geometrically informed symbolic planner that expands the set of objects and facts in a best-first manner. We apply our algorithm on a 7DOF robotic arm in block-stacking manipulation tasks.
  arXiv  Detail & Related papers  (2021-11-25T15:58:31Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.