What should be observed for optimal reward in POMDPs?
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916319723520000 |
|---|---|
| author | Konsta, Alyzia-Maria Lafuente, Alberto Lluch Matheja, Christoph |
| author_facet | Konsta, Alyzia-Maria Lafuente, Alberto Lluch Matheja, Christoph |
| contents | Partially observable Markov Decision Processes (POMDPs) are a standard model for agents making decisions in uncertain environments. Most work on POMDPs focuses on synthesizing strategies based on the available capabilities. However, system designers can often control an agent's observation capabilities, e.g. by placing or selecting sensors. This raises the question of how one should select an agent's sensors cost-effectively such that it achieves the desired goals. In this paper, we study the novel optimal observability problem OOP: Given a POMDP M, how should one change M's observation capabilities within a fixed budget such that its (minimal) expected reward remains below a given threshold? We show that the problem is undecidable in general and decidable when considering positional strategies only. We present two algorithms for a decidable fragment of the OOP: one based on optimal strategies of M's underlying Markov decision process and one based on parameter synthesis with SMT. We report promising results for variants of typical examples from the POMDP literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10768 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | What should be observed for optimal reward in POMDPs? Konsta, Alyzia-Maria Lafuente, Alberto Lluch Matheja, Christoph Artificial Intelligence Partially observable Markov Decision Processes (POMDPs) are a standard model for agents making decisions in uncertain environments. Most work on POMDPs focuses on synthesizing strategies based on the available capabilities. However, system designers can often control an agent's observation capabilities, e.g. by placing or selecting sensors. This raises the question of how one should select an agent's sensors cost-effectively such that it achieves the desired goals. In this paper, we study the novel optimal observability problem OOP: Given a POMDP M, how should one change M's observation capabilities within a fixed budget such that its (minimal) expected reward remains below a given threshold? We show that the problem is undecidable in general and decidable when considering positional strategies only. We present two algorithms for a decidable fragment of the OOP: one based on optimal strategies of M's underlying Markov decision process and one based on parameter synthesis with SMT. We report promising results for variants of typical examples from the POMDP literature. |
| title | What should be observed for optimal reward in POMDPs? |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2405.10768 |