Hierarchical variable ordering for distributed constraint optimization
John Davin, Pragnesh Jay Modi · 2006
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. We introduce the AdoptMVA algorithm, an extension of the existing Adopt algorithm, designed to take advantage of MAP domains where agents often control multiple variables. We also propose an approach to agent ordering which leverages known ordering techniques from the centralized and distributed constraint satisfaction literature and applies them to MAPs. By combining ordering at the agent level with orderings at the variable level, we hope to obtain efficient global orderings. While the contributions discussed in this paper are applicable to general DCOPs, we focus our evaluation on MAPs because we feel it is a significant problem class worthy of specific attention.