The Study On Inference-based Algorithms For Distributed Constraint Optimization Problems

Distributed Constrained Optimization Problems(DCOP)is the fundamental framework of Multi-Agent System(MAS),which plays an important role in modeling distributed problem solving and multi-agent coordination.DCOP has been successfully applied to task scheduling,power system and other fields.Asymmetric Distributed Constraint Optimization Problems(ADCOP)extends DCOP by adding private preferences for each agent.Thus it has stronger modeling capabilities and greater application prospects.Inference-based algorithms,represented by the Max-sum algorithm,are important techniques for solving DCOP/ADCOP and are widely applied into many real applications.However,the existing incomplete inference-based algorithms usually fail to converge and cannot produce high-quality solutions.In addition,due to the privacy concerns in ADCOP,the traditional inference-based complete algorithms for DCOP cannot directly solve ADCOP.On the other hand,the existing complete search-based algorithms for ADCOP cannot solve large scale problems and usually leak a lot of private information.Against the above background,this paper aims to study the incomplete inference-base algorithms for solving DCOP and complete algorithms for solving ADCOP.The main contributions of the paper are listed as follows:(1)The paper provides substantial analysis of the impact of the value propagation mechanism to Max-sum.We theoretically show that although value propagation can greatly improve the performance of Max-sum,it also blocks the belief propagation of the Max-sum.In particular,we prove that when the value propagation is continuously performed on the alternated directed acyclic graphs,the agent cannot utilize the global accumulated beliefs and the algorithm will be equivalent to a sequential greedy local search algorithm.Thus,how to efficiently balance exploration and exploitation after enabling value propagation becomes an ugent need.(2)To solve the above problem,the paper proposes a class of Max-sum algorithms based on non-consecutive value propagation strategies,including Max-sum_AD with Single-side Value Propagation(Max-sum_ADSSVP),Max-sum with hybrid belief/value propagation(Max-sum_HBVP)and Max-sum_AD with probabilistic value propagation(Max-sum_ADPVP).By avoiding to continuously perform value propagation on directed acyclic graphs,these algorithms allow agents to consider both individual benefits and the global benefit when making decisions.We then theoretically show that the above algorithms cannot be equivalent to a greedy local search algorithm,and analyze their space-time complexity.The experimental results demonstrate that our proposed algorithms are significantly superior to the traditional incomplete inference-based algorithms,and are less sensitive to the timing of starting value propagation.(3)Considering the privacy requirement of ADCOP,we propose a novel algorithm called PT-ISBB that is based on both search strategy and inference strategy.The algorithm first employs a complete inference-based algorithm to solve constraints in a direction.In the search phase,a problem is divided into smaller sub-problems in every branch node,and each sub-problem can be solved independently.On each node,the subtrees' inference results are used as a lower bound to accelerate pruning.We then prove its completeness theoretically and analyze its complexity.Experimental results show that PT-ISBB outperforms traditional search algorithms on various benchmarks.