![[2505.22147] Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2505.22147] Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions
Summary
The paper presents Foreplan, a novel relational forward planner for Markov Decision Processes (MDPs) that efficiently handles concurrent actions, significantly reducing computational complexity.
Why It Matters
As MDPs become increasingly complex with concurrent actions, traditional methods struggle with efficiency. Foreplan offers a polynomial-time solution, enabling the resolution of more planning problems accurately and quickly, which is crucial for advancements in AI applications.
Key Takeaways
- Foreplan utilizes a first-order representation to manage state and action space growth in MDPs.
- The planner operates in polynomial time, enhancing the feasibility of solving complex planning problems.
- An approximate version of Foreplan is introduced, providing speed improvements with manageable error rates.
- Empirical evaluations demonstrate significant speedups, making Foreplan a practical tool for AI applications.
- The research contributes to the field of AI by addressing scalability issues in planning under uncertainty.
Computer Science > Artificial Intelligence arXiv:2505.22147 (cs) [Submitted on 28 May 2025 (v1), last revised 23 Feb 2026 (this version, v3)] Title:Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions Authors:Florian Andreas Marwitz, Tanya Braun, Ralf Möller, Marcel Gehrke View a PDF of the paper titled Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions, by Florian Andreas Marwitz and 3 other authors View PDF HTML (experimental) Abstract:When allowing concurrent actions in Markov Decision Processes, whose state and action spaces grow exponentially in the number of objects, computing a policy becomes highly inefficient, as it requires enumerating the joint of the two spaces. For the case of indistinguishable objects, we present a first-order representation to tackle the exponential blow-up in the action and state spaces. We propose Foreplan, an efficient relational forward planner, which uses the first-order representation allowing to compute policies in space and time polynomially in the number of objects. Thus, Foreplan significantly increases the number of planning problems solvable in an exact manner in reasonable time, which we underscore with a theoretical analysis. To speed up computations even further, we also introduce an approximate version of Foreplan, including guarantees on the error. Further, we provide an empirical evaluation of both Foreplan versions, demonstrating a sp...