A hybrid tree-based algorithm to solve asymmetric distributed constraint optimization problems

摘要

Asymmetric distributed constraint optimization problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs only exploit local knowledge to calculate lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e.g., DPOP) for distributed constraint optimization problems are able to aggregate the global cost promptly but cannot be directly applied into ADCOPs due to a privacy concern. Thus, in this paper, we investigate the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete ADCOP algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and upper bounds, and a tree-based complete search algorithm to guarantee the optimality. Furthermore, we introduce two suboptimal variants of PT-ISABB based on bounded-error approximation mechanisms to enable trade-off between theoretically guaranteed solutions and coordination overheads. We prove the correctness of PT-ISABB and its suboptimal variants. Finally, the experimental results demonstrate that PT-ISABB exhibits great superiorities over other state-of-the-art search-based complete algorithms and its suboptimal variants can quickly find a solution within the user-specified bounded-error.