Detail výsledku

Search and Explore: Symbiotic Policy Synthesis in POMDPs

ANDRIUSHCHENKO, R.; ALEXANDER, B.; ČEŠKA, M.; JUNGES, S.; KATOEN, J.; MACÁK, F. Search and Explore: Symbiotic Policy Synthesis in POMDPs. In Computer Aided Verification. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Cham: Springer Verlag, 2023. p. 113-135. ISBN: 978-3-031-37708-2.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Andriushchenko Roman, Ing., UITS (FIT)
ALEXANDER, B.
Češka Milan, doc. RNDr., Ph.D., UITS (FIT)
JUNGES, S.
KATOEN, J.
Macák Filip, Ing., UITS (FIT)
Abstrakt

This paper marries two state-of-the-art controller synthesis methods for partially observable Markov decision processes (POMDPs), a prominent model in sequential decision making under uncertainty. A central issue is to find a POMDP controller - that solely decides based on the observations seen so far - to achieve a total expected reward objective. As finding optimal controllers is undecidable, we concentrate on synthesising good finite-state controllers (FSCs). We do so by tightly integrating two modern, orthogonal methods for POMDP controller synthesis: a belief-based and an inductive approach. The former method obtains an FSC from a finite fragment of the so-called belief MDP, an MDP that keeps track of the probabilities of equally observable POMDP states. The latter is an inductive search technique over a set of FSCs, e.g., controllers with a fixed memory size. The key result of this paper is a symbiotic anytime algorithm that tightly integrates both approaches such that each profits from the controllers constructed by the other. Experimental results indicate a substantial improvement in the value of the controllers while significantly reducing the synthesis time and memory footprint.

Klíčová slova

partially observable Markov decision processes, finite-state controllers, beliefs, inductive synthesis

Rok
2023
Strany
113–135
Sborník
Computer Aided Verification
Řada
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Svazek
13966
Konference
35th International Conference on Computer Aided Verification
ISBN
978-3-031-37708-2
Vydavatel
Springer Verlag
Místo
Cham
DOI
EID Scopus
BibTeX
@inproceedings{BUT185190,
  author="ANDRIUSHCHENKO, R. and ALEXANDER, B. and ČEŠKA, M. and JUNGES, S. and KATOEN, J. and MACÁK, F.",
  title="Search and Explore: Symbiotic Policy Synthesis in POMDPs",
  booktitle="Computer Aided Verification",
  year="2023",
  series="Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
  volume="13966",
  pages="113--135",
  publisher="Springer Verlag",
  address="Cham",
  doi="10.1007/978-3-031-37709-9\{_}6",
  isbn="978-3-031-37708-2"
}
Projekty
Reliable, Secure, and Intelligent Computer Systems, VUT, Vnitřní projekty VUT, FIT-S-23-8151, zahájení: 2023-03-01, ukončení: 2026-02-28, řešení
VESCAA: Verifikovatelná a efektivní syntéza kontrolerů, GAČR, Standardní projekty, GA23-06963S, zahájení: 2023-03-01, ukončení: 2025-12-31, řešení
Výzkumné skupiny
Pracoviště
Nahoru