Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Principles and Practice of Multi-Agent Systems
Guest editors: Michael Winikoffx, Nirmit Desaiy and Alan Liuz
Article type: Research Article
Authors: Okimoto, Tenda; * | Iwasaki, Atsushi | Yokoo, Makoto
Affiliations: Department of Informatics, Kyushu University, Fukuoka, Japan | [x] Department of Information Science, University of Otago, Dunedin, New Zealand | [y] IBM Research, Bangalore, India | [z] Department of Electrical Engineering, National Chung Cheng University, Chiayi, Taiwan
Correspondence: [*] Corresponding author: Tenda Okimoto, Department of Informatics, Kyushu University, Fukuokashi Nishiku Motooka 744 Ito campus-west 2-8-824, Fukuoka 8190395, Japan. Tel.: +81 92 802 2999; E-mail: tenda@agent.inf.kyushu-u.ac.jp
Abstract: A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms/heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm (ABT) as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. In the evaluations, we show that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point where the required cycles are maximum.
Keywords: Distributed constraint satisfaction problem, variable-ordering, scale-free
DOI: 10.3233/MGS-2012-0189
Journal: Multiagent and Grid Systems , vol. 8, no. 2, pp. 127-141, 2012
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl