Title
BD-ADOPT: a hybrid DCOP algorithm with best-first and depth-first search strategies
Abstract
Distributed Constraint Optimization Problem (DCOP) is a promising framework for modeling a wide variety of multi-agent coordination problems. Best-First search (BFS) and Depth-First search (DFS) are two main search strategies used for search-based complete DCOP algorithms. Unfortunately, BFS often has to deal with a large number of solution reconstructions whereas DFS is unable to promptly prune sub-optimal branch. However, their weaknesses will be remedied if the two search strategies are combined based on agents’ positions in a pseudo-tree. Therefore, a hybrid DCOP algorithm with the combination of BFS and DFS, called BD-ADOPT, is proposed, in which a layering boundary is introduced to divide all agents into BFS-based agents and DFS-based agents. Furthermore, this paper gives a rule to find a suitable layering boundary with a new strategy for the agents near the boundary to realize the seamless joint between BFS and DFS strategies. Detailed experimental results show that BD-ADOPT outperforms some famous search-based complete DCOP algorithms on the benchmark problems.
Year
DOI
Venue
2018
https://doi.org/10.1007/s10462-017-9540-z
Artif. Intell. Rev.
Keywords
Field
DocType
Multi-agent systems,Distributed constraint optimization problem,Depth-first search strategy,Best-first search strategy,BD-ADOPT
Distributed File System,Mathematical optimization,Distributed constraint optimization problem,Computer science,Breadth-first search,Layering,Algorithm,Multi-agent system
Journal
Volume
Issue
ISSN
50
2
0269-2821
Citations 
PageRank 
References 
1
0.37
21
Authors
4
Name
Order
Citations
PageRank
Zi-yu Chen1177.24
Chen He2714101.22
Zhen He322.75
Minyou Chen410.37