Regression and Progression in Stochastic Domains Abstract   Reasoning about degrees of belief in uncertain dynamic worlds is fundamental to many applications, such as robotics and planning, where actions modify state properties and sensors provide measurements, both of which are prone to noise. With the exception of limited cases such as Gaussian processes over linear phenomena, belief state evolution can be complex and hard to reason with in a general way, especially when the agent has to deal with categorical assertions, incomplete information such as disjunctive knowledge, as well as probabilistic knowledge. Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive, allowing for such belief states to be expressed naturally as constraints. While that proposal is powerful, the task of how to plan effectively is not addressed. In fact, at a more fundamental level, the task of projection, that of reasoning about beliefs effectively after acting and sensing, is left entirely open.  To aid planning algorithms, we study the projection problem in this work. In the reasoning about actions literature, there are two main solutions to projection: regression and progression. Both of these have proven enormously useful for the design of logical agents, essentially paving the way for cognitive robotics. Roughly, regression reduces a query about the future to a query about the initial state. Progression, on the other hand, changes the initial state according to the effects of each action and then checks whether the formula holds in the updated state. In this work, we show how both of these generalize in the presence of degrees of belief, noisy acting and sensing. Our results allow for both discrete and continuous probability distributions to be used in the specification of beliefs and dynamics.

Incremental reasoning in probabilistic Signal Temporal Logic Abstract   Robot safety is of growing concern given recent developments in intelligent autonomous systems. For complex agents operating in uncertain, complex and rapidlychanging environments it is difficult to guarantee safety without imposing unrealistic assumptions and restrictions. It is therefore necessary to complement traditional formal verification with monitoring of the running system after deployment. Runtime verification can be used to monitor that an agent behaves according to a formal specification. The specification can contain safetyrelated requirements and assumptions about the environment, environmentagent interactions and agentagent interactions. A key problem is the uncertain and changing nature of the environment. This necessitates requirements on how probable a certain outcome is and on predictions of future states. We propose Probabilistic Signal Temporal Logic (ProbSTL) by extending Signal Temporal Logic with a sublanguage to allow statements over probabilities, observations and predictions. We further introduce and prove the correctness of the incremental stream reasoning technique progression over wellformed formulas in ProbSTL. Experimental evaluations demonstrate the applicability and benefits of ProbSTL for robot safety.