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 mode...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2007
|
| Subjects: | |
| Online Access: | http://scholars.utp.edu.my/id/eprint/2135/ http://scholars.utp.edu.my/id/eprint/2135/1/Constraint_relaxation_thesis.pdf |
| _version_ | 1848659207045251072 |
|---|---|
| author | Hassan, M.F. |
| author_facet | Hassan, M.F. |
| author_sort | Hassan, M.F. |
| building | UTP Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-13T07:26:45Z |
| format | Thesis |
| id | oai:scholars.utp.edu.my:2135 |
| institution | Universiti Teknologi Petronas |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-13T07:26:45Z |
| publishDate | 2007 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | oai:scholars.utp.edu.my:21352017-01-19T08:27:03Z http://scholars.utp.edu.my/id/eprint/2135/ Coordinated Constraint Relaxation Using a Distributed Agent Protocol Hassan, M.F. QA75 Electronic computers. Computer science QA76 Computer software 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. 2007 Thesis NonPeerReviewed application/pdf en http://scholars.utp.edu.my/id/eprint/2135/1/Constraint_relaxation_thesis.pdf Hassan, M.F. (2007) Coordinated Constraint Relaxation Using a Distributed Agent Protocol. PhD. thesis, Centre for Intelligent Systems & Their Applications (CISA), School of Informatics, University of Edinburgh, UK. |
| spellingShingle | QA75 Electronic computers. Computer science QA76 Computer software Hassan, M.F. Coordinated Constraint Relaxation Using a Distributed Agent Protocol |
| title | Coordinated Constraint Relaxation Using a
Distributed Agent Protocol |
| title_full | Coordinated Constraint Relaxation Using a
Distributed Agent Protocol |
| title_fullStr | Coordinated Constraint Relaxation Using a
Distributed Agent Protocol |
| title_full_unstemmed | Coordinated Constraint Relaxation Using a
Distributed Agent Protocol |
| title_short | Coordinated Constraint Relaxation Using a
Distributed Agent Protocol |
| title_sort | coordinated constraint relaxation using a
distributed agent protocol |
| topic | QA75 Electronic computers. Computer science QA76 Computer software |
| url | http://scholars.utp.edu.my/id/eprint/2135/ http://scholars.utp.edu.my/id/eprint/2135/1/Constraint_relaxation_thesis.pdf |