Access Restriction

Author Davin, John
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Agent Level ♦ Order Variable ♦ General Dcops ♦ Variable Level ♦ Significant Problem Class Worthy ♦ Effective Agent Ordering ♦ Special Form ♦ Multiagent Agreement Problem ♦ Sequential Constraint Satisfaction Literature ♦ Distributed Constraint Optimization ♦ Promising Technique ♦ Partial Centralization ♦ Map Domain ♦ Hierarchical Approach ♦ Dcop Require Variable ♦ Equality Constraint ♦ Multiple Variable ♦ Effective Variable Ordering ♦ Efficient Global Ordering ♦ Adopt Algorithm ♦ Solution Approach ♦ Adoptmva Algorithm ♦ Guarantee Optimality ♦ Specific Attention
Description The Multiagent Agreement Problem (MAP) is a special form of Distributed Constraint Optimization (DCOP) that requires agents to choose values for variables to satisfy not only their own constraints, but also equality constraints with other agents. For solving MAPs, we introduce the AdoptMVA algorithm which is an extension of the existing Adopt algorithm designed to take advantage of the partial centralization that exists in MAP domains where agents control multiple variables. Second, while existing solution approaches to DCOP require variables to be prioritized in some fashion in order to guarantee optimality, it is unclear how to order variables effectively when agents own multiple variables. We investigate a hierarchical approach which leverages known ordering techniques from the sequential constraint satisfaction literature by combining ordering at the agent level with orderings at the variable level to obtain efficient global orderings. Finally, we identify a promising technique for converting known effective variable orderings into effective agent orderings and identify an intra-agent variable ordering heuristic for MAP that is the most efficient of the ones tested. While the contributions presented in this paper are applicable to general DCOPs, we focus our discussion on MAPs because we feel it is a significant problem class worthy of specific attention. 1.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01