Distributed Search by Constrained Agents: Algorithms, Performance, Communication

ISBN-13: 9781849967105 / Angielski / Miękka / 2010 / 216 str.

Amnon Meisels

Opis

Distributed search by agents is an important topic of distributed AI and has not been treated thoroughly as such. While the scope of work on multi-agent systems has grown steadily over the last decade, very little of it has spilled into distributed search. In conrast, the constraints processing community has produced a sizable body of work on distributed constrained search. Parado- cally, a community that concentrates on search algorithms and heuristics has created a distributed model for agents that cooperate on solving hard search problems. Traditionally, this ?eld has been named Ditributed Constraints S- isfaction and lately also distributed constraints optimization. The present book attempts to prompt deeper response from the MAS community and hopefully to give rise to cooperative work on distributed search by agents. In order to achieve this high goal, the book presents the large body of work on distributed search by constrained agents. The presentation emphasizes many aspects of distributed computation that connect naturally to multi-agent systems, - pecially measures of performance for distributed search algorithms and the impact of delays in communication. Distributed Constraints Satisfaction Problems (DisCSPs) have been st- ied over the last decade, starting with the pioneering proposal by Makoto Yokoo 18]. The ?rst distributed search algorithm for DisCSPs - As- chronous Backtracking (ABT) - was ?rst published in complete format in 1998 64]. The ?rst book on Distributed Constraints Satisfaction Problems has appeared as early as 2000 61].

Spis treści

Constraints Satisfaction Problems - CSPs.- Constraints Optimization Problems - COPs.- Distributed Search.- Asynchronous Backtracking (ABT).- Asynchronous Forward-Checking.- Concurrent Dynamic Backtracking.- Distributed Ordering Heuristics.- Asynchronous Ordering Heuristics.- Performance measures for distributed search.- Experimental Evaluation of DisCSP Algorithms.- The Impact of Communication - Message Delays.- Message Delays and DisCSP Search Algorithms.- Distributed Constraint Optimization Problems (DisCOPs).- Asynchronous Optimization for DisCOPs.- Asynchronous Forward-Bounding.- Extending AFB - BackJumping.- Empirical Evaluation of DisCOP algorithms.

Blurb

Agent technology is evolving as a leading field of research connected to diverse areas such as A.I., E-commerce, robotics and information retrieval. Agents systems use reasoning and constraint-based reasoning that has a wide potential for representing multiple types of problems. A fundamental building block within all these areas is the ability to perform search and an inherent part of all agents must therefore relate to distributed and cooperative methods of search.

This book presents a comprehensive discussion on the field of distributed constraints, its algorithms and its active research areas. It introduces distributed constraint satisfaction and optimization problems and proceeds to present a complete state-of-the-art in DisCSP & DisCOP research. The presentation assumes no prior knowledge of constraints or distributed constraints.

Features and topics:

• Introduces in great detail search algorithms for DisCSPs and DisCOPs

• Presents a comprehensive study of distributed performance measures for all algorithms, allowing an extensive experimental evaluation to be constructed

• Addresses potential problems following current research on DisCSPs and DisCOPs

• Discusses the impact of communication quality on distributed search (for example message delays)

• Describes the most significant recent research in the field of distributed constraints satisfaction and optimization, including its difficulties

This exposition of the many elements of distributed search algorithms for DisCSPs and DisCOPs will be a research asset and an invaluable read for researchers and graduate students who focus on distributed CSPs and COPs. In addition, the book’s comprehensiveness and style make it an ideal tool for a graduate course on distributed search in AI.

Professor Amnon Meisels has an active research group who have worked in distributed constraints for a number of years and has published extensively in the field. He is a member of the Department of Computer Science at Ben-Gurion University, Beer-Sheva, Israel.