A Caltech Library Service

Control Theory Meets POMDPs: A Hybrid Systems Approach

Ahmadi, Mohamadreza and Jansen, Nils and Wu, Bo and Topcu, Ufuk (2021) Control Theory Meets POMDPs: A Hybrid Systems Approach. IEEE Transactions on Automatic Control, 66 (11). pp. 5191-5204. ISSN 0018-9286. doi:10.1109/tac.2020.3035755.

PDF - Accepted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Partially observable Markov decision processes (POMDPs) provide a modeling framework for a variety of sequential decision making under uncertainty scenarios in artificial intelligence (AI). Since the states are not directly observable in a POMDP, decision making has to be performed based on the output of a Bayesian filter (continuous beliefs); hence, making POMDPs intractable to solve and analyze. To overcome the complexity challenge of POMDPs, we apply techniques from the control theory. Our contributions are fourfold. 1) We begin by casting the problem of analyzing a POMDP into analyzing the behavior of a discrete-time switched system. 2) Then, in order to estimate the reachable belief space of a POMDP, i.e., the set of all possible evolutions given an initial belief distribution over the states and a set of actions and observations, we find overapproximations in terms of sublevel sets of Lyapunov-like functions. 3) Furthermore, in order to verify safety and performance requirements of a given POMDP, we formulate a barrier certificate theorem, wherein we show that if there exists a barrier certificate satisfying a set of inequalities along the solutions to the belief update equation of the POMDP, the safety and performance properties are guaranteed to hold. In both cases 2) and 3), the calculations can be decomposed and solved in parallel. 4) Finally, we show that the conditions we formulate can be computationally implemented as a set of sum-of-squares programs. We illustrate the applicability of our method by addressing two problems in active ad scheduling and machine teaching.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Ahmadi, Mohamadreza0000-0003-1447-3012
Jansen, Nils0000-0003-1318-8973
Wu, Bo0000-0002-7199-6525
Topcu, Ufuk0000-0003-0819-9985
Additional Information:© 2020 IEEE. Manuscript received April 15, 2020; accepted October 28, 2020. Date of publication November 4, 2020; date of current version November 4, 2021. This work was supported by Grant AFOSR FA9550-19-1-0005, Grant AFRL FA9550-19-1-0169, Grant DARPA D19AP00004, Grant NSF 1646522, Grant NWO OCENW.KLEIN.187, and Grant NSF 1652113. Recommended by Associate Editor L. Palopoli. M. Ahmadi appreciates the stimulating discussions with Dr.Y. Chen at the University of Chicago, Prof. Y. Yue at Caltech, and Prof. R. M. Murray at Caltech.
Group:Center for Autonomous Systems and Technologies (CAST)
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0005
Air Force Research Laboratory (AFRL)FA9550-19-1-0169
Defense Advanced Research Projects Agency (DARPA)D19AP00004
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)OCENW.KLEIN.187
Subject Keywords:Artificial intelligence, autonomous systems, control theory, Lyapunov methods, Markov processes
Issue or Number:11
Record Number:CaltechAUTHORS:20201105-145616123
Persistent URL:
Official Citation:M. Ahmadi, N. Jansen, B. Wu and U. Topcu, "Control Theory Meets POMDPs: A Hybrid Systems Approach," in IEEE Transactions on Automatic Control, vol. 66, no. 11, pp. 5191-5204, Nov. 2021, doi: 10.1109/TAC.2020.3035755
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106456
Deposited By: George Porter
Deposited On:06 Nov 2020 15:51
Last Modified:29 Oct 2021 18:29

Repository Staff Only: item control page