OpenAIR @ RGU >
Design and Technology >
Computing >
Conference publications (Computing) >

Please use this identifier to cite or link to this item:
This item has been viewed 5 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
Ahriz 2009 IEEE WIandIAT conf.pdf145.02 kBAdobe PDFView/Open
Title: Multi-hyb: a hybrid algorithm for solving DisCSPs with complex local problems.
Authors: Lee, David
Arana, Ines
Ahriz, Hatem
Hui, Kit-Ying
Keywords: Agent cooperation
Artificial Intelligence
Constraint satisfaction
Distributed constraint satisfaction
Distributed problem solving
Issue Date: Sep-2009
Publisher: IEEE Computer Society.
Citation: LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y., 2009. Multi-hyb: a hybrid algorithm for solving DisCSPs with complex local problems. In: P. BOLDI, G. VIZZARI, G. PASI and R. BAEZA-YATES eds. Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on , vol.2. 15-18 September 2009, Los Alamitos, California: IEEE Computer Society. Pp. 379-382.
Abstract: A coarse-grained Distributed Constraint Satisfaction Problem (DisCSP) is a constraint problem where several agents, each responsible for solving one part (a complex local problem), cooperate to determine an overall solution. Thus, agents solve the overall problem by finding a solution to their complex local problem which is compatible with the solutions proposed by other agents for their own local problems. Several approaches to solving DisCSPs have been devised and can be classified as systematic search and local search techniques. We present Multi-Hyb, a two-phase hybrid algorithm for solving coarse-grained DisCSPs which uses both systematic and local search during problem solving. Phase 1 generates key partial solutions to the global problem using systematic search. Concurrently, a penalty-based local search algorithm attempts to find a global solution to the problem using these partial solutions. If a global solution is not found in phase 1, the information learnt from phase 1 is used to inform the search carried out during the next phase. Phase two runs a systematic search algorithm on complex variables guided by the following knowledge obtained in phase 1: (i) partial solutions and; (ii) complex local problems which appear more difficult to satisfy. Experimental evaluation demonstrates that Multi-Hyb is competitive in several problem classes in terms of: (i) the communication cost and (ii) the computational effort needed.
ISBN: 9780769538013
Appears in Collections:Conference publications (Computing)

All items in OpenAIR are protected by copyright, with all rights reserved.


   Disclaimer | Freedom of Information | Privacy Statement |Copyright ©2012 Robert Gordon University, Garthdee House, Garthdee Road, Aberdeen, AB10 7QB, Scotland, UK: a Scottish charity, registration No. SC013781