The Study On Tree-based Complete Algorithms For Distributed Constraint Optimization Problems

Distributed Constraint Optimization Problem(DCOP)is a fundamental framework for Multi-Agent Systems(MAS)where agents cooperate with each other to optimize a global objective.It is an important technique for modeling multi-agent coordination and has been successfully applied to task scheduling,sensor network,smart grid and many others.Tree-based complete algorithms are important techniques for solving a DCOP and have great significance to both academic and practical research.However,the existing tree-based complete algorithms suffer from high communication and time consumption and fail to solve large-scale problems.Therefore,this thesis aims to enhance the efficiency,scalability and solution speed of such algorithms so as to promote their applications in real-world scenarios.The main contributions of the thesis are listed as follows:(1)The thesis proposes a Bound-Independent Pruning(BIP)technique.Specifically,we first present the defination of POS(Primary Optimal Support)with the following two properties: 1)POS can be used to calculate a subset of the solution space containing the optimal solution;2)POS can be computed by exploiting only part of the information in a utility table.Based on the above two properties of POS,we propose BIP which can prune the solution space only by utilizing local constraints and the assignments to some neighbors,and thus greatly improve the efficiency of the complete algorithms and reduce their running time.We theoretically prove the correctness of BIP.(2)We apply BIP to existing tree-based asynchronous and synchronous complete search algorithms,and analyze and resolve the potential problem arising from the implementation of BIP.Specifically,when enforcing BIP,each agent can not only prune domain for itself but also suggest its children to remove some values from their respective domain.However,the latter may expand the context on which the search results of each agent depends so that there is not enough information for the existing context-compatibility checking mechanism in tree-based complete search algorithms to determine the validity of search results produced by these algorithms when enforcing BIP.Therefore,we further propose an acceptability testing mechanism(ATM)which can filter out unacceptable search results by checking the changes of domain to ensure the completeness of the original algorithms.We theoretically show the correctness of enforcing BIP and ATM in tree-based complete search algorithms,and analyze their complexity.The experimental results demonstrate that BIP substantially improves state-of-the-art tree-based complete search algorithms in both scalability and running time.(3)We apply BIP to existing tree-based memory-bounded inference algorithms.Specifically,for a given instantiation of cycle-cut(CC)nodes,BIP can determing a subset of solution space containing optimal solution by solely utilizing local constraints and this instantiation.Then,each CC node can prune its domain based on this subset to reduce the number of iterative inferences required by the original algorithms,and thus improves the efficiency and speed of the original algorithms.We theoretically prove the correctness of enforcing BIP in tree-based memory-bounded inference algorithms.The experimental results show that BIP greatly improves original memory-bounded inference algorithms on various benchmarks.