# Programming and Reasoning with Partial Observability

**Authors:** Eric Atkinson, Michael Carbin  
**arXiv:** [2101.04742](https://arxiv.org/abs/2101.04742)  
**Date:** 2021-01-12  
**Summary page:** https://www.summarizepaper.com/en/paper/2101.04742v1/

## Key points

- Computer programs are increasingly being used in partially-observable environments
- Developers typically write a state estimator to deduce the hidden state of the environment from partial observations
- Verifying safety properties in such environments can be difficult
- Belief programming is a new methodology that enables developers to write an environment model that is automatically used by the program runtime for performing state estimation
- Belief programming dynamically updates and queries a belief state that captures all possible states that the environment could be in
- Epistemic Hoare Logic has been presented to enable verification of safety properties in these environments, reasoning about possible belief states of a belief program similar to how classical Hoare logic reasons about possible states of a program
- BLIMP language has been used to define semantics and program logic for belief programming, with a case study conducted on Mars Polar Lander controller written and verified using BLIMP language through belief programming methodology
- CBLIMP implementation has also been evaluated for feasibility
- Classical verification techniques have been compared with belief programming methodology
- Classical verification requires handwritten code for state estimator while belief programming uses infer statements which are more intuitive but require more effort in developing Epistemic Hoare Logic
- This work provides new foundations for soundly reasoning about software behavior executing in partially-observable environments and opens up avenues for future research in probabilistic programming.

## Summary

In today's world, computer programs are increasingly being deployed in partially-observable environments where the state of the environment is not completely visible to the program. To address this challenge, developers typically write a state estimator that attempts to deduce the hidden state of the environment from partial observations. However, verifying safety properties in such environments can be difficult. To address this issue, a new methodology called belief programming has been introduced which enables developers to write an environment model that is automatically used by the program runtime for performing state estimation. Belief programming dynamically updates and queries a belief state that captures all possible states that the environment could be in. To enable verification of safety properties in these environments, Epistemic Hoare Logic has been presented which reasons about the possible belief states of a belief program similar to how classical Hoare logic reasons about possible states of a program. The concepts have been developed using BLIMP language by defining semantics and program logic for it. A case study has also been conducted on Mars Polar Lander controller written and verified using BLIMP language through belief programming methodology. CBLIMP implementation has also been evaluated for feasibility. Furthermore, classical verification techniques have been compared with belief programming methodology where classical verification requires handwritten code for state estimator while belief programming uses infer statements which are more intuitive but require more effort in developing Epistemic Hoare Logic. Overall, this work provides new foundations for soundly reasoning about software behavior executing in partially-observable environments and opens up avenues for future research in probabilistic programming.