Inductive synthesis of finite-state controllers for POMDPs

Roman Andriushchenko, Milan Češka, Sebastian Junges, Joost-Pieter Katoen
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:85-95, 2022.

Abstract

We present a novel learning framework to obtain finite-state controllers (FSCs) for partially observable Markov decision processes and illustrate its applicability for indefinite-horizon specifications. Our framework builds on oracle-guided inductive synthesis to explore a design space compactly representing available FSCs. The inductive synthesis approach consists of two stages: The outer stage determines the design space, i.e., the set of FSC candidates, while the inner stage efficiently explores the design space. This framework is easily generalisable and shows promising results when compared to existing approaches. Experiments indicate that our technique is (i) competitive to state-of-the-art belief-based approaches for indefinite-horizon properties, (ii) yields smaller FSCs than existing methods for several POMDP models, and (iii) naturally treats multi-objective specifications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-andriushchenko22a, title = {Inductive synthesis of finite-state controllers for POMDPs}, author = {Andriushchenko, Roman and \v{C}e\v{s}ka, Milan and Junges, Sebastian and Katoen, Joost-Pieter}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {85--95}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/andriushchenko22a/andriushchenko22a.pdf}, url = {https://proceedings.mlr.press/v180/andriushchenko22a.html}, abstract = {We present a novel learning framework to obtain finite-state controllers (FSCs) for partially observable Markov decision processes and illustrate its applicability for indefinite-horizon specifications. Our framework builds on oracle-guided inductive synthesis to explore a design space compactly representing available FSCs. The inductive synthesis approach consists of two stages: The outer stage determines the design space, i.e., the set of FSC candidates, while the inner stage efficiently explores the design space. This framework is easily generalisable and shows promising results when compared to existing approaches. Experiments indicate that our technique is (i) competitive to state-of-the-art belief-based approaches for indefinite-horizon properties, (ii) yields smaller FSCs than existing methods for several POMDP models, and (iii) naturally treats multi-objective specifications.} }
Endnote
%0 Conference Paper %T Inductive synthesis of finite-state controllers for POMDPs %A Roman Andriushchenko %A Milan Češka %A Sebastian Junges %A Joost-Pieter Katoen %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-andriushchenko22a %I PMLR %P 85--95 %U https://proceedings.mlr.press/v180/andriushchenko22a.html %V 180 %X We present a novel learning framework to obtain finite-state controllers (FSCs) for partially observable Markov decision processes and illustrate its applicability for indefinite-horizon specifications. Our framework builds on oracle-guided inductive synthesis to explore a design space compactly representing available FSCs. The inductive synthesis approach consists of two stages: The outer stage determines the design space, i.e., the set of FSC candidates, while the inner stage efficiently explores the design space. This framework is easily generalisable and shows promising results when compared to existing approaches. Experiments indicate that our technique is (i) competitive to state-of-the-art belief-based approaches for indefinite-horizon properties, (ii) yields smaller FSCs than existing methods for several POMDP models, and (iii) naturally treats multi-objective specifications.
APA
Andriushchenko, R., Češka, M., Junges, S. & Katoen, J.. (2022). Inductive synthesis of finite-state controllers for POMDPs. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:85-95 Available from https://proceedings.mlr.press/v180/andriushchenko22a.html.

Related Material