=Paper=
{{Paper
|id=Vol-1504/uai2015aci_abstract1
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1504/uai2015aci_abstract1.pdf
|volume=Vol-1504
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-1504/uai2015aci_abstract1.pdf</pdf>
<pre>
            Exploiting Causality for Efficient Monitoring in POMDPs



                  Stefano V. Albrecht                                    Subramanian Ramamoorthy
                 School of Informatics                                       School of Informatics
                University of Edinburgh                                     University of Edinburgh
               Edinburgh EH8 9AB, UK                                       Edinburgh EH8 9AB, UK
           s.v.albrecht@sms.ed.ac.uk                                    s.ramamoorthy@ed.ac.uk


                                                       Abstract

Partially observable Markov decision processes (POMDPs) are a useful model for decision making in systems
with uncertain states. One of the core tasks in a POMDP is the monitoring task, in which the belief state (i.e. the
probability distribution over system states) is updated based on incomplete and noisy observations. This can be a
hard problem in complex real-world systems due to the often very large state space. In this article, we explore the
idea of accelerating the monitoring task by automatically exploiting causality in the system. We consider a specific
type of causal relation, called passivity, which pertains to how system variables cause changes in other variables.
Specifically, a system variable is called passive if it changes its value only if it is directly acted upon, or if at least
one of the variables that directly affect it (i.e. parent variables) change their values. This property can be readily
determined from the conditional probability table of the system variable. We present a novel monitoring method,
called Passivity-based Monitoring (PM), which maintains a factored belief state representation and exploits
passivity to perform selective updates over the factored beliefs. PM produces exact belief states under certain
assumptions and approximate belief states otherwise, where the approximation error is bounded by the degree of
uncertainty in the process. We show empirically, in synthetic processes with varying sizes and degrees of passivity,
that PM is faster than two standard monitoring methods while achieving competitive accuracy. Furthermore, we
demonstrate how passivity occurs naturally in a real-world system such as a multi-robot warehouse, and how PM
can exploit this to accelerate the monitoring task.

The full article can be found at: http://arxiv.org/abs/1401.7941

</pre>