Probabilistic Constraint Nets

By Robert St. Aubin

Computer-controlled systems are becoming ubiquitous. Most of these systems exhibit uncertainty, rendering their behaviour somewhat unpredictable. For some systems, this unpredictability can be overlooked. However, for many systems, such as safety critical systems, the uncertainty arising can have dramatic effects. In order to handle such systems, we need a formal modeling framework and a methodology for analyzing them. In systems responding to users requests, for instance, an analysis could be performed to show that a time of service property is satisfied on average. We have developed Probabilistic Constraint Nets (PCN), a framework that can handle a wide range of uncertainty, whether it be probabilistic, stochastic or non-deterministic. In PCN, we view probabilistic dynamical systems as online constraint-solvers for dynamic probabilistic constraints and requirements specification as global behavioural constraints on the systems. We present verification rules, which have been fully implemented, to perform automatic behavioural constraint verification. Finally, we demonstrate the utility of our framework by applying it to a simple robotic surveillance system.

Back to the LCI Forum page