Coordinated constraint relaxation using a distributed agent protocol

The interactions among agents in a multi-agent system for coordinating a distributed, problem solving task can be complex, as the distinct sub-problems of the individual agents are interdependent. A distributed protocol provides the necessary framework for specifying these interactions. In a model of interactions where the agents' social norms are expressed as the message passing behaviours associated with roles, the dependencies among agents can be specified as constraints. The constraints are associated with roles to be adopted by agents as dictated by the protocol. These constraints are commonly handled using a conventional constraint solving system that only allows two satisfactory states to be achieved - completely satisfied or failed. Agent interactions then become brittle as the occurrence of an over-constrained state can cause the interaction between agents to break prematurely, even though the interacting agents could, in principle, reach an agreement. Assuming that the agents are capable of relaxing their individual constraints to reach a common goal, the main issue addressed by this thesis is how the agents could communicate and coordinate the constraint relaxation process. The interaction mechanism for this is obtained by reinterpreting a technique borrowed from the constraint satisfaction field, deployed and computed at the protocol level.The foundations of this work are the Lightweight Coordination Calculus (LCC) and the distributed partial Constraint Satisfaction Problem (CSP). LCC is a distributed interaction protocol language, based on process calculus, for specifying and executing agents' social norms in a multi-agent system. Distributed partial CSP is an extension of partial CSP, a means for managing the relaxation of distributed, over-constrained, CSPs. The research presented in this thesis concerns how distributed partial CSP technique, used to address over-constrained problems in the constraint satisfaction field, could be adopted and integrated within the LCC to obtain a more flexible means for constraint handling during agent interactions. The approach is evaluated against a set of overconstrained Multi-agent Agreement Problems (MAPs) with different levels of hardness. Not only does this thesis explore a flexible and novel approach for handling constraints during the interactions of heterogeneous and autonomous agents participating in a problem solving task, but it is also grounded in a practical implementation