SP1

Distributed Search by Constrained Agents
Amnon Meisels and Roie Zivan

The tutorial will present distributed constraint satisfaction problems (DisCSPs) and optimization problems (DisCOPs) and search algorithms for solving them. Multiple families of complete and local search algorithms, privacy issues of distributed DisCSP search, measures of performance, and distributed heuristics.

Distributed search by agents is an important topic of distributed AI. In the last decade a sizable body of work on distributed constrained search has emerged. Traditionally, this field has been named "Distributed Constraints Satisfaction" (DisCSPs) and "Distributed constraints optimization" (DisCOPs). The tutorial includes three main parts that form its backbone. The first and most important part introduces in great detail search algorithms for DisCSPs and DisCOPs. The algorithmic part of the exposition will include ordering heuristics — both asynchronous heuristics and sequential ones.

The second part of the presentation of Distributed Search by Constrained Agents includes a comprehensive study of distributed performance measures for all algorithms. Based on the resulting coherent and asynchronous scale of performance, an extensive experimental evaluation can be constructed including behavior under message delays.

The third part of our presentation relates to the inherent distributed nature of DisCSPs and DisCOPs and addresses potential problems such as the privacy of information used during search.

Detailed outline of the tutorial:

• Introduction: Constraints satisfaction and constraints optimization problems
• Distributed constrained search - DisCSPs and DisCOPs
• DisCSP search algorithms - Asynchronous Backtracking; Asynchronous Forward-checking
• DisCOP algorithms - Asynchronous distributed optimization (ADOPT); Asynchronous
• Forward-Bounding;
• Concurrent Performance measures
• A note on Privacy
• Future directions - Cooperative search by self-interested Agents

Amnon Meisels has been a faculty member of the Department of Computer Science at Ben-Gurion University for the last 20 years. Served as head of the Computer Science Department from 2004 to 2006. The main field of research of Amnon Meisels is Constraints Processing and in the last 7 years mostly Distributed Constrained Search. His book, Distributed Search by Constrained Agents, was published by Springer Verlag in January 2008.

Since 2002 Professor Meisels has led a group of graduate students at BGU that have established algorithmic standards for distributed search on distributed constraints satisfaction problems (DisCSPs) and distributed constraints optimization problems (DisCOPs).

Professor Meisels has served on the program committees of all major AI conferences that deal with constraints-based reasoning over the last 5 years. Specifically for Constraints Processing (CP conferences); IJCAI 2003-7; ECAI 2004-8; and the series of PATAT conferences on Automatic Timetabling, where he serves on the steering committee since 2000. In addition he has been part of the organizing committee of the series of workshops on distributed constraints reasoning (DCR series) every year since 2003.

Roie Zivan is a faculty member of the department of Industrial Engineering and Management at Ben-Gurion University. Currently, he is on sabbatical with the Robotics Institute at Carnegie Mellon University. Dr. Zivan has completed his PhD on Concurrent Search for Distributed Constraints Satisfaction Problems in the Computer Science Dept. at Ben-Gurion University in 2007.

Dr. Zivan has served on the program committees of some of the last major AI conferences including AAAI 2007, 2008, AAMAS 2009, IJCAI 2009. He is among the organizers of this year's distributed constraints reasoning (DCR) workshop at IJCAI-09 in Pasadena.

(back)