Detection and Diagnosis of Deviations in Distributed Systems of Autonomous Agents

About the project :

Imagine a group of autonomous cyber-physical agents carrying out a mission such as search, surveillance, tracking, or transporting materials or data. They follow a protocol that specifies key actions/steps and ordering constraints. It may also specify intermediate results, invariants, or end points. In a perfect world, the mission will be accomplished—constraints and invariants satisfied, end points achieved.

The world is not perfect. The possibility of imperfect protocols or imperfect agents, and the unpredictable nature of the world that agents must operate in, means that things can/will go wrong, and undesirable or unexpected situations will arise. We call these unexpected/unplanned/undesired situations deviations. Some deviations are transient and the system will likely recover. Some deviations are persistent and may have serious consequences. In order to fix problems and adapt behavior, either post mortem or on-the-fly, it is important to have an explanation of what lead to the observed deviations—a diagnosis. This is a big challenge, even with perfect information. In a setting with partial information and an unpredictable environment, the challenge becomes even greater. In fact, diagnosis can at best produce a ranked set of models giving possible explanations of what went wrong.

The goal of this project is to develop a formal framework for specifying and reasoning about autonomous cyber-physical agent systems. Given the uncertain world, a binary notion of satisfaction of goals or compliance to a specification is not realistic. A protocol should specify an envelop of acceptable executions perhaps with a measure of satisfaction/acceptability.

Agents in the real world must maintain an overall situation, location, and time awareness and make safe decisions that progress towards achieving the protocol requirements in spite of uncertainty, partial knowledge and intermittent connectivity. Each agent will generally only have partial and possibly imperfect knowledge of the system state and what has happened. This is inherent in the nature of distributed cyber-physical systems. The quality of information is further degraded when operating in challenging, unpredictable environments where sensing and actions may fail and communication may be disrupted.

Our approach is based on a formal executable model framework called Soft Agents which in turn builds on a knowledge sharing communication model that is robust to network disruption. Soft refers to the use of soft constraint problems to describe an agents behavior . Soft agents are cyber-physical agents in that they can sense and affect their environment as well as carrying out computational tasks such as deciding actions or processing data.

CWI contributes to this project by developing a compositional model to formalize the behavior of SoftAgents and their environment, along with tools and techniques for analysis of and reasoning about such models. For this work, we use the notion of soft constraint automata (SCA). SCA are a generalization of constraint automata that were introduced as a formalism to describe the behavior and possible data flow in coordination models for concurrent systems. Soft constraint automata offer a well-developed framework for soft constraint problem solving based on constraint semi-rings.