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

Distributed Constraint Optimization Problem(DCOP)is a fundamental model for multi-agent coordination and optimization problems in which agents cooperatively find assignments to optimize a global objective.DCOPs have been successfully applied to model many real-world problems where information and controls are inherently distributed among agents such as distributed scheduling,smart-grids and cognitive radio.As an important class of DCOP solvers,inference algorithms have great significance to both academic and practical research.However,the existing inference algorithms suffer from high memory and time consumption.Therefore,this thesis is devoted to improving the scalability of such algorithms to promote their applications in real-world scenarios.Specifically,the main contributions of this thesis to complete algorithm MB-DPOP and incomplete algorithm Max-sum are as follows:(1)This thesis systematically analyzes the scalability of the memory-bounded inference complete algorithms,and proposes RMB-DPOP.Specifically,this thesis analyzes the main factors that limit the scalability of MB-DPOP,and points out that the redundant inference stems from a large number of non-concurrent instantiations since the agents select a large number of CC(Cycle-cut)nodes,and the cluster roots enumerate all instantiations.To this end,this thesis proposes a distributed enumeration mechanism,an iterative selection mechanism,and a caching mechanism.Among them,the distributed enumeration mechanism solves the problem of non-concurrent instantiations enumeration,the iterative selection mechanism solves the problem that agents blindly select CC nodes according to local knowledge,and the caching mechanism solves the problem that the historical results cannot be reused.In addition,this thesis theoretically proves that the number of iterative inferences incurred by RMB-DPOP is no more than MB-DPOP,and the experimental results show that RMB-DPOP can significantly improve the scalability of MB-DPOP.(2)Based on an in-depth analysis of FDSP for accelerating Max-sum,this thesis proposes a series of multi-solution belief propagation acceleration methods to solve the problems such as the low quality of the lower bound and the blind enumeration based on branch and bound algorithms.Specifically,this thesis points out that in the case of the highly structured utility function,the depth-first state pruning algorithm cannot effectively compress the solution space,which limits the scalability of FDSP.Therefore,this thesis proposes CONC?FDSP based on concurrent search and BFS?FDSP based on best-first search,respectively.The former executes multiple depth-first search processes concurrently to reduce the time to obtain high-quality lower bounds;the latter uses partial solution upper bounds to sort the solution space,and continuously expands the partial solutions with highest upper bound to quickly obtain the best utility.In addition,we theoretically analyze the complexity of CONC?FDSP and proves that the pruning rate of BFS?FDSP is better than all FDSP-based acceleration algorithms.The experimental results show that CONC?FDSP and BFS?FDSP can significantly improve the scalability of incomplete inference algorithms based on belief propagation.