Execution Monitoring in Multi-Agent Environments

Citation:

Gal Kaminka. 2000. “Execution Monitoring in Multi-Agent Environments ”. Thesis Type: PhD thesis.

Abstract:

Agents in complex, dynamic, multi-agent environments face uncertainty in the execution of their tasks, as their sensors, plans, and actions may fail unexpectedly, e.g., the weather may render a robots camera useless, its grip too slippery, etc. The explosive number of states in such environments prohibits any resource-bounded designer from predicting all failures at design time. This situation is exacerbated in multi-agent settings, where interactions between agents increase the complexity. For instance, it is difficult to predict an opponent's behavior. Agents in such environments must therefore rely on runtime execution monitoring and diagnosis to detect a failure, diagnose it, and recover. Previous approaches have focused on supplying the agent with goal-attentive knowledge of the ideal behavior expected of the agent with respect to its goals. These approaches encounter key pitfalls and fail to exploit key opportunities in multi-agent settings: (a) only a subset of the sensors (those that measure achievement of goals) are used, despite other agents' sensed behavior that can be used to indirectly sense the environment or complete the agent's knowledge; (b) there is no monitoring of social relationships that must be maintained between the agents regardless of achievement of the goal (e.g., teamwork); and (c) there is no recognition of failures in others, though these change the ideal behavior expected of an agent (for instance, assisting a failing teammate). To address these problems, we investigate a novel complementary paradigm for multi-agent monitoring and diagnosis. Socially-Attentive Monitoring (SAM) focuses on monitoring the social relationships between the agents as they are executing their tasks, and uses models of multiple agents and their relationships in monitoring and diagnosis. We hypothesize that failures to maintain relationships would be indicative of failures in behavior, and diagnosis of relationships can be used to complement goal-attentive methods. In particular, SAM addresses the weaknesses listed above: (a) it allows inference of missing knowledge and sensor readings through other agents' sensed behavior; (b) it directly monitors social relationships, with no attention to the goals; and (c) it allows recognition of failures in others (even if they are not using SAM!). SAM currently uses the STEAM teamwork model, and a role-similarity relationship model to monitor agents. It relies on plan-recognition to infer agents' reactive-plan hierarchies from their observed actions. These hierarchies are compared in a top-down fashion to find relationship violations, e.g., cases where two agents selected different plans despite their being on the same team. Such detections trigger diagnosis which uses the relationship models to facilitate recovery. For example, in teamwork, a commitment to joint selection of plans further mandates mutual belief in preconditions. Thus a difference in selected plans may be explained by a difference in preconditions, and can lead to recovery using negotiations. We empirically and analytically investigate SAM in two dynamic, complex, multi-agent domains: the ModSAF battlefield simulation, where SAM is employed by helicopter pilot agents; and the RoboCup soccer simulation where SAM is used by a coach agent to monitor teams' behavior. We show that SAM can capture failures that are otherwise undetectable, and that distributed monitoring is better (correct and complete) detection) and simpler (no representation of ambiguity) than a centralized scheme (complete and incorrect, requiring representation of ambiguity). Key contributions and novelties include: (a) a general framework for socially-attentive monitoring, and a deployed implementation for monitoring teamwork; (b) rigorously proven guarantees on the applicability and results of practical socially-attentive monitoring of teamwork under conditions of uncertainty; (c) procedures for diagnosis based on a teamwork relationship model. Future work includes the use of additional relationship models in monitoring and diagnosis, formalization of the social diagnosis capabilities, and further demonstration of SAM's usefulness in current domains and others.
See also: 2000