Compositional Planning for Logically Constrained Multi-Agent Markov Decision Processes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913533852123136 |
|---|---|
| author | Kalagarla, Krishna C. Low, Matthew Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi |
| author_facet | Kalagarla, Krishna C. Low, Matthew Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi |
| contents | Designing control policies for large, distributed systems is challenging, especially in the context of critical, temporal logic based specifications (e.g., safety) that must be met with high probability. Compositional methods for such problems are needed for scalability, yet relying on worst-case assumptions for decomposition tends to be overly conservative. In this work, we use the framework of Constrained Markov Decision Processes (CMDPs) to provide an assume-guarantee based decomposition for synthesizing decentralized control policies, subject to logical constraints in a multi-agent setting. The returned policies are guaranteed to satisfy the constraints with high probability and provide a lower bound on the achieved objective reward. We empirically find the returned policies to achieve near-optimal rewards while enjoying an order of magnitude reduction in problem size and execution time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04004 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Compositional Planning for Logically Constrained Multi-Agent Markov Decision Processes Kalagarla, Krishna C. Low, Matthew Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi Systems and Control Designing control policies for large, distributed systems is challenging, especially in the context of critical, temporal logic based specifications (e.g., safety) that must be met with high probability. Compositional methods for such problems are needed for scalability, yet relying on worst-case assumptions for decomposition tends to be overly conservative. In this work, we use the framework of Constrained Markov Decision Processes (CMDPs) to provide an assume-guarantee based decomposition for synthesizing decentralized control policies, subject to logical constraints in a multi-agent setting. The returned policies are guaranteed to satisfy the constraints with high probability and provide a lower bound on the achieved objective reward. We empirically find the returned policies to achieve near-optimal rewards while enjoying an order of magnitude reduction in problem size and execution time. |
| title | Compositional Planning for Logically Constrained Multi-Agent Markov Decision Processes |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2410.04004 |