Publication Type

Conference Proceeding Article

Version

submittedVersion

Publication Date

9-2005

Abstract

The Open Constraint Optimization Problem (OCOP) refers to the COP where constraints and variable domains can change over time and agents' opinions have to be sought over a distributed network to form a solution. The openness of the problem has caused conventional approaches to COP such as branch-and-bound to fail to find optimal solutions. OCOP is a new problem and the approach to find an optimal solution (minimum total cost) introduced in [1] is based on an unrealistic assumption that agents are willing to report their options in nondecreasing order of cost. In this paper, we study a generalized OCOP where agents are self-interested and not obliged to reveal their private information such as the order of their options with respect to cost. The objective of the generalized OCOP is to find a solution with low total cost and high overall satisfaction level of agents. A Two-Level Structured Multi-Agent Framework has been proposed: in the upper level, a neutral central solver allows agents report their preferred options in tiers and find a feasible initial solution from top tiers of options by constraint propagation and guided tiers expansion; in the lower level, agents form coalitions and negotiate among themselves on the initial solution by an argument of Persuasive Points. Experimental results have shown that this two-level structure yields very promising results that seek a good balance between the total cost of solution and the agents' overall satisfaction level in the long run.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

IEEE/WIC/ACM International Conference on Intelligent Agent Technology: Proceedings: Compiegne, France, September 19-22

First Page

558

Last Page

564

ISBN

9780769524160

Identifier

10.1109/IAT.2005.127

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/IAT.2005.127

Download

Share

COinS