Detecting and repairing anomalous evolutions in noisy environments - Logic programming formalization and complexity results

In systems where agents are required to interact with a partially known and dynamic world, sensors can be used to obtain knowledge about the environment. However, sensors may be unreliable, that is, they may deliver wrong information (due, e.g., to hardware or software malfunctioning) and, consequently, they may cause agents to take wrong decisions, which is a scenario that should be avoided. The paper considers the problem of reasoning in noisy environments in a setting where no (either certain or probabilistic) data is available in advance about the reliability of sensors. Therefore, assuming that each agent is equipped with a background theory encoding its general knowledge about the world, a concept of detecting an anomaly perceived in sensor data and the related concept of agent recovering to a coherent status of information are defined. In this context, the complexities of various anomaly detection and anomaly recovery problems are studied. Finally, rewriting algorithms are proposed that transform recovery problems into equivalent inference problems under answer set semantics, thereby making them effectively realizable on top of available answer set solvers.