  In a recent paper, Belle and Levesque proposed a framework for a type of
program called belief programs, a probabilistic extension of GOLOG programs
where every action and sensing result could be noisy and every test condition
refers to the agent's subjective beliefs. Inherited from GOLOG programs, the
action-centered feature makes belief programs fairly suitable for high-level
robot control under uncertainty. An important step before deploying such a
program is to verify whether it satisfies properties as desired. At least two
problems exist in doing verification: how to formally specify properties of a
program and what is the complexity of verification. In this paper, we propose a
formalism for belief programs based on a modal logic of actions and beliefs.
Among other things, this allows us to express PCTL-like temporal properties
smoothly. Besides, we investigate the decidability and undecidability for the
verification problem of belief programs.
