Dynamic agent prioritisation with penalties in distributed local search.

Abstract

Distributed Constraint Satisfaction Problems (DisCSPs) solving techniques solve problems which are distributed over a number of agents.The distribution of the problem is required due to privacy, security or cost issues and, therefore centralised problem solving is inappropriate. Distributed local search is a framework that solves large combinatorial and optimization problems. For large problems it is often faster than distributed systematic search methods. However, local search techniques are unable to detect unsolvability and have the propensity of getting stuck at local optima. Several strategies such as weights on constraints, penalties on values and probability have been used to escape local optima. In this paper, we present an approach for escaping local optima called Dynamic Agent Prioritisation and Penalties (DynAPP) which combines penalties on variable values and dynamic variable prioritisation for the resolution of distributed constraint satisfaction problems. Empirical evaluation with instances of random, meeting scheduling and graph colouring problems have shown that this approach solved more problems in less time at the phase transition when compared with some state of the art algorithms. Further evaluation of the DynAPP approach on iteration-bounded optimisation problems showed that DynAPP is competitive.

Citation

SAMBO-MAGAJI, A., ARANA, I. and AHRIZ, H. 2013. Dynamic agent prioritisation with penalties in distributed local search. In Filipe, J. and Fred, A. (eds.) Proceedings of the 5th International conference on agents and artificial intelligence (ICAART 2013), 15-18 February 2013, Barcelona, Spain. Setúbal: Science and Technology Publications [online], volume 1, pages 276-281. Available from: https://doi.org/10.5220/0004259202760281

• Conference Name: 5th International conference on agents and artificial intelligence (ICAART 2013)
• Conference Location: Barcelona, Spain
• Start Date: Feb 15, 2013
• End Date: Feb 18, 2013
• Acceptance Date: Feb 18, 2013
• Online Publication Date: Feb 18, 2013
• Publication Date: Dec 31, 2013
• Deposit Date: Oct 15, 2014
• Publicly Available Date: Oct 15, 2014
• Publisher: Science and Technology Publications
• Pages: 276-281
• ISBN: 9789898565389
• DOI: https://doi.org/10.5220/0004259202760281
• Keywords: Distributed problems solving; Local search; Distributed constraint satisfaction; Heuristics
• Public URL: http://hdl.handle.net/10059/1058