Solving Generalized Open Constraint Optimization Problem Using Two-Level Multi-Agent Framework: Improved Results

Publication Type

Conference Paper

Publication Date

8-2006

Abstract

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

European Conference on AI (ECAI) 2006 Workshop on Distributed CSP (DisCSP), August 2006

City or Country

Verona, Italy

This document is currently not available here.

Share

COinS