Complete Distributed Search Algorithm for Cyclic Factor Graphs

Toshihiro Matsui, Hiroshi Matsuo

2014

Abstract

Distributed Constraint Optimization Problems (DCOPs) have been studied as fundamental problems in multiagent systems. The Max-Sum algorithm has been proposed as a solution method for DCOPs. The algorithm is based on factor graphs that consist of two types of nodes for variables and functions. While the Max-Sum is an exact method for acyclic factor-graphs, in the case that the factor graph contains cycles, it is an inexact method that may not converge. In this study, we propose a method that decomposes the cycles based on crossedged pseudo-trees on factor-graphs. We also present a basic scheme of distributed search algorithms that generalizes complete search algorithms on the constraint graphs and Max-Sum algorithm.

Paper Citation

in Harvard Style

Matsui T. and Matsuo H. (2014). Complete Distributed Search Algorithm for Cyclic Factor Graphs . In Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-016-1, pages 184-192. DOI: 10.5220/0004824301840192

in Bibtex Style

@conference{icaart14,
author={Toshihiro Matsui and Hiroshi Matsuo},
title={Complete Distributed Search Algorithm for Cyclic Factor Graphs},
booktitle={Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2014},
pages={184-192},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004824301840192},
isbn={978-989-758-016-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Complete Distributed Search Algorithm for Cyclic Factor Graphs
SN - 978-989-758-016-1
AU - Matsui T.
AU - Matsuo H.
PY - 2014
SP - 184
EP - 192
DO - 10.5220/0004824301840192