AsymDPOP: Complete Inference for Asymmetric Distributed ConstraintOptimization Problems
Abstract
Asymmetric distributed constraint optimization
problems (ADCOPs) are an emerging model for coordinating agents with personal preferences. However, the existing inference-based complete algorithms which use local eliminations cannot be applied to ADCOPs, as the parent agents are required
to transfer their private functions to their children.
Rather than disclosing private functions explicitly
to facilitate local eliminations, we solve the problem by enforcing delayed eliminations and propose
AsymDPOP, the first inference-based complete algorithm for ADCOPs. To solve the severe scalability problems incurred by delayed eliminations,
we propose to reduce the memory consumption by
propagating a set of smaller utility tables instead
of a joint utility table, and to reduce the computation efforts by sequential optimizations instead of
joint optimizations. The empirical evaluation indicates that AsymDPOP significantly outperforms
the state-of-the-art, as well as the vanilla DPOP
with PEAV formulation