Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908847952625664 |
|---|---|
| author | Marwitz, Florian Andreas Braun, Tanya Möller, Ralf Gehrke, Marcel |
| author_facet | Marwitz, Florian Andreas Braun, Tanya Möller, Ralf Gehrke, Marcel |
| contents | 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 speedup of several orders of magnitude. For the approximate version of Foreplan, we also empirically show that the induced error is often negligible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22147 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions Marwitz, Florian Andreas Braun, Tanya Möller, Ralf Gehrke, Marcel Artificial Intelligence I.2.8; I.1.2; G.1.6 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 speedup of several orders of magnitude. For the approximate version of Foreplan, we also empirically show that the induced error is often negligible. |
| title | Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions |
| topic | Artificial Intelligence I.2.8; I.1.2; G.1.6 |
| url | https://arxiv.org/abs/2505.22147 |