Solving coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd.

Basharu, Muhammed; Arana, In�s; Ahriz, Hatem

Abstract

We present Multi-DisPel, a penalty-based local search distributed algorithm which is able to solve coarse-grained Distributed Constraint Satisfaction Problems (DisCSPs) efficiently. Multi-DisPeL uses penalties on values in order to escape local optima during problem solving rather than the popular weights on constraints. We also introduce DisBO-wd, a stochastic algorithm based on DisBO (Distributed Breakout) which includes a weight decay mechanism. We compare Multi-DisPeL and DisBO-wd with other algorithms and show, empirically, that they are more efficient and at least as effective as state of the art algorithms in some problem classes.

Citation

BASHARU, M., ARANA, I. and AHRIZ, A. 2007. Solving coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd. In Lin, T.Y., Bradshaw, J.M., Klusch, M., Zhang, C., Broder, A. and Ho, H. (eds.) Proceedings of the 2007 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2007), 2-5 November 2007, Silicon Valley, USA. Los Alamitos: IEEE Computer Society [online], article number 4407307, pages 335-341. Available from: https://doi.org/10.1109/IAT.2007.68

• Conference Name: 2007 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2007)
• Conference Location: Fremont, USA
• Start Date: Nov 2, 2007
• End Date: Nov 5, 2007
• Acceptance Date: Dec 31, 2007
• Online Publication Date: Dec 31, 2007
• Publication Date: Dec 31, 2007
• Deposit Date: Feb 13, 2009
• Publicly Available Date: Feb 13, 2009
• Publisher: IEEE Computer Society
• Article Number: 4407307
• Pages: 335-341
• ISBN: 0769530273; 9780769530277
• DOI: https://doi.org/10.1109/IAT.2007.68
• Keywords: Multi-DisPeL; DisBO-wd; Algorithms; Distributed constraint satisfaction problems; DisCSPs
• Public URL: http://hdl.handle.net/10059/305