Robust Finite-State Controllers for Uncertain POMDPs

Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, Ufuk Topcu

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

18 Citations (Scopus)
95 Downloads (Pure)


Uncertain partially observable Markov decision processes (uPOMDPs) allow the probabilistic transition and observation functions of standard POMDPs to belong to a so-called uncertainty set. Such uncertainty, referred to as epistemic uncertainty, captures uncountable sets of probability distributions caused by, for instance, a lack of data available. We develop an algorithm to compute finite-memory policies for uPOMDPs that robustly satisfy specifications against any admissible distribution. In general, computing such policies is theoretically and practically intractable. We provide an efficient solution to this problem in four steps. (1) We state the underlying problem as a nonconvex optimization problem with infinitely many constraints. (2) A dedicated dualization scheme yields a dual problem that is still nonconvex but has finitely many constraints. (3) We linearize this dual problem and (4) solve the resulting finite linear program to obtain locally optimal solutions to the original problem. The resulting problem formulation is exponentially smaller than those resulting from existing methods. We demonstrate the applicability of our algorithm using large instances of an aircraft collision-avoidance scenario and a novel spacecraft motion planning case study.

Original languageEnglish
Title of host publicationProceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781713835974
Publication statusPublished - 2021
Event35th AAAI Conference on Artificial Intelligence, AAAI 2021 - ONLINE, Virtual, Online
Duration: 2 Feb 20219 Feb 2021


Conference35th AAAI Conference on Artificial Intelligence, AAAI 2021
CityVirtual, Online


Dive into the research topics of 'Robust Finite-State Controllers for Uncertain POMDPs'. Together they form a unique fingerprint.

Cite this