Conflict Resolution Advisor-AGENTS

CRA.gif (7417 bytes) Conflict Detection and Classification for Sensible Agents

Introduction

Effective coordination in multi-agent systems should increase the degree of mutual predictability, decrease conflicts, and therefore increase system performance. Coordination is the process by which agents reason about and manage the interdependencies among their behaviors and try to ensure that every member of the system act consistently. Through coordination, agents within a system can work together to ensure coherent action. Although conflict resolution (CR) is the essential and necessary part to achieving coordination, coordination and conflict resolution differ. Coordination is a continuous process in the system, while conflict resolution is an event driven process triggered once a conflict is detected. Conflicts occurring among agents are intrinsic and direct when the goals or beliefs that agents hold are logically inconsistent. Conflicts can also be indirect and implicit when the goals or beliefs are indirectly contradictory to each other. The generic conflict resolution process includes conflict detection, search for solutions, and communication among agents to reach agreement with regard to the solutions that will be pursued.

Conflict Detection and Classification

Conflict detection is the triggering event for conflict resolution; in addition, conflict detection is one way to verify coordination. Since various kinds of conflicts may co-exist at the same time within a multi-agent system, conflict detection can be very complicated and time-consuming process. Communication or behavior inference may be needed to acquire agents’ intentions before conflict detection starts.

Conflict classification is an integral part of understanding the nature of a conflict. Pinpointing the nature of a conflict reduces the search space of possible resolution strategies and/or modification mechanisms, allowing agents to focus on behaviors that are most effective for the type of conflict they are attempting to resolve. There are three layers at which conflict detection occurs in Sensible Agents [1]. The first layer is the goal structure, which represents the interdependencies among the goals of system agents. The second layer is the plan space, which shows the causal and temporal relationships among the actions of system agents. The third layer is the belief space that represents the relationships among the beliefs of system agents. All layers are related to one another through logical relationships and resource interactions.

Goal conflict detection starts with the agent comparing its Intended Goal Structure to the Intended Goal Structures of other agents. If inconsistent goals are detected, potential goal conflicts are found. By tracing supporting beliefs, an agent can determine whether there are conflicting beliefs that led to these goal conflicts. If goals cannot coexist at the same time and agents do not need to hold them concurrently, proper order constraints should be added before agents start generating plans and scheduling their actions

Based on existing literature in the operations research and project management fields, we adapt and extend PERT/CPM charts for plan representation and detection of plan conflicts during plan integration [2]. Links represent activities (e.g. Act1, Act2, Act3) and are attached with required time (e.g. T1, T2, T3) and required resources (e.g. R1, R2, R3). Nodes represent the beginning and ending of related activities. The sequences or ordered links are equivalent to the plans that agents need to execute to reach their goals. PERT diagrams were originally designed to represent a manager’s perspective. Some modifications were made to adapt PERT for use in multi-agent systems. During integration of agent PERT diagrams, the interactions among the actions, including resource dependencies become obvious.

Conflict Recommendation

After detection and classification, the agent must proceed to resolve the conflicts. As there is no single best method for performing conflict resolution in all situations, the agent may then perform meta-level reasoning about what method to use for the current situation. The selecting of proper conflict resolution strategies considers: (1) the nature of conflicts (2) the agent organization in conjunction with the agent’s roles in that organization, and (3) the agent’s solution preferences [3].