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

• Main Authors: LAU, Hoong Chuin, ZHANG, Lei, LIU, Chang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2005
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/365; https://ink.library.smu.edu.sg/context/sis_research/article/1364/viewcontent/IAT05_OCOP.pdf
• Institution: Singapore Management University

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.