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 Chen | 1 | 17 | 7.24 |
Chen He | 2 | 714 | 101.22 |
Zhen He | 3 | 2 | 2.75 |
Minyou Chen | 4 | 1 | 0.37 |