Penalty-driven Algorithms for Distributed Constraint Satisfaction

Iterative improvement search has the advantage, over constructive search, of being able to converge quicker on large problems. However, it also has a propensity to converge to local optima in the process. We have developed a new approach for dealing with local optima in distributed iterative improvement by modifying the cost landscape with two forms of penalties which are attached to individual domain values. We use one type of penalty to perturb solutions and the other to help agents learn about (and avoid) domain values frequently associated with local optima. Based on these two forms of penalties, we have developed the DisPeL family of algorithms for solving DisCSPs. We have compared these algorithms to state—of—the—art distributed iterative improvement algorithms. The results of our evaluations show that the DisPeL algorithms are effective alternatives to state of the art distributed iterative improvement algorithms — they solved more problems and typically incurred lower costs in the process.

Funding

• School of Computing (RGU)

Research Team

• Hatem Ahriz
• Ines Arana (PI)
• Muhammed Basharu (PhD Student - completed)

Related Project

• Distributed Constraint Satisfaction in Dynamic Environment
• Hybrid Algorithms for Distributed Constraint Satisfaction

Publications

Arana, I, Ahriz, H, & Basharu, M,(2009). Solving Coarse-Grained DisCSPs with Local Search. To appear in Web Intelligence and Agent Systems - An International Journal, IOS Press.

Basharu, M, Arana, I, & Ahriz, H (2007). Solving coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd. IEEE/ACM International Conference on Intelligent Agent Technology, IAT2007, California, USA , 335-341, 2-5 November 2007. DOI 10.1109/IAT.2007.68.

Basharu, M, Arana, I, & Ahriz, H (2007). Escaping Local Optima: Constraint Weights vs. Value Penalties. In: Bramer, M., Coenen, F. and Petridis, M. (eds.), Research and Development in Intelligent Systems XXIV, Springer-Verlag, 2007, pp. 51-64. ISBN 978-1-84800-093-3.

Basharu, M, Arana, I, & Ahriz, H (2007). Escaping Local Optima: Constraint Weights vs. Value Penalties. In: Bramer, M., Coenen, F. and Petridis, M. (eds.), Research and Development in Intelligent Systems XXIV, Springer-Verlag, 2007, pp. 51-64. ISBN 978-1-84800-093-3.

Basharu, M, Arana, I, & Ahriz, H (2007). DisBO-wd: a distributed constraint satisfaction algorithm for coarse-grained distributed problems. In: Bramer, M., Coenen, F. and Petridis, M. (eds.), Research and Development in Intelligent Systems XXIV, Springer-Verlag, 2007, pp. 23-36. ISBN 978-1-84800-093-3.

Basharu, M, Arana, I, & Ahriz, H (2007). Stoch-DisPeL: Exploiting Randomisation in DisPeL. 7th International Workshop on Distributed Constraint Reasoning, DCR2006, 117-131, Hakodate, Japan , 8 May 2006.

Basharu, M, Arana, I, & Ahriz, H (2005). Escaping Local Optima with Penalties in Distributed iterative Improvement Search. IJCAI-05 Workshop on Distributed Reasoning, DCR2005 , 192-206, on 30 July 2005.

Basharu, M., Arana, I., & Ahriz, H. (2005). Solving DisCSPs with Penalty-Driven Search. AAAI 2005 - the Twentieth National Conference of Artificial Intelligence , 47-52, Pittsburgh, Pennsylvania, on 9-11 July. AAAI Press.

Basharu, M., Arana, I., & Ahriz, H. (2005). Distributed guided local search for solving binary DisCSPs. Proceedings of the 18th FLAIRS Conference , 660-665, on 15-17 May, AAAI Press.

Basharu, M., Ahriz, H., & Arana, I. (2003). Escaping Local Optima in Multi-Agent Oriented Constraint Satisfaction. Proceedings of the Twenty-third SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence ,97-110, December,Cambridge. Springer-Verlag.