Robert St.-Aubin
The development of autonomous agents, such as mobile robots or software agents has generated considerable research in recent years. Robotic systems, which are usually built from a mixture of continuous (analog) and discrete (digital) components, are often referred to as hybrid dynamical systems.
The modeling and analysis of hybrid dynamical systems is becoming more and more important as such systems are now widely used to reason about complex physical systems. Ying Zhang and Alan Mackworth developed a semantic model for dynamic systems, called Constraint Nets (CN) [1]. CN introduces an abstraction and unitary framework to model hybrid systems. Furthermore, specification and verification methods were introduced for deterministic system.
Traditional approaches to real-time hybrid systems usually define behaviors purely in terms of determinism or sometimes non-determinism. The CN framework was develop to model and verify deterministic systems, with the capability to model non-determinism. However, real-time dynamical systems very often behave probabilistically and thus exhibit (structured) uncertainty. It is therefore important to be able to model and analyze real-time probabilistic systems. Hence, a formal framework to model systems with unpredictable behaviors is essential.
We extend the work previously done on Constraint Nets by developing a new framework that we call "Probabilistic Constraint Nets" (PCN). The PCN framework allows for the modeling and simulation of any dynamical system, whether it is deterministic, non-deterministic or probabilistic. We introduce formal syntax and semantics for the framework that ensure the correctness of the models. We also provide a graphical representation that simplifies the task of modeling complex systems. Moreover, we show that our framework is a generalization of many commonly used frameworks like Bayesian Networks and Markov Decision Processes (MDP) which allows the user to take advantage of a unified framework encompassing most popular modeling paradigms. Furthermore, we provide, for a subclass of PCN models called synchfin-PCN, algorithms for control synthesis. With such algorithms, a designer can automatically construct an optimal controller for his system, hence greatly facilitating his task.
Current work include the formulation of a specification language and verification algorithms for PCN models while upcoming work will tackle the task of coupling the PCN framework with learning techniques that would allow a designer to build a controller capable of adjusting its systems parameters as it interacts with the environment in a real time fashion.