Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms (Short Paper)
William Yeoh, Sven Koenig, Xiaoxun Sun · 2008
Abstract. Distributed Constraint Optimization (DCOP) is a key tech-nique for solving multiagent coordination problems. Unfortunately, find-ing minimal-cost DCOP solutions is NP-hard. We therefore propose two mechanisms that trade off the solution costs of two DCOP search algo-rithms (ADOPT and BnB-ADOPT) for smaller runtimes, namely the Inadmissible Heuristics Mechanism and the Relative Error Mechanism. The solution costs that result from these mechanisms are bounded by a more meaningful quantity than the solution costs that result from the existing Absolute Error Mechanism since they both result in solution costs that are larger than minimal by at most a user-specified percent-age. Furthermore, the Inadmissible Heuristics Mechanism experimentally dominates both the Absolute Error Mechanism and the Relative Error Mechanism for BnB-ADOPT and is generally no worse than them for ADOPT. 1