Distributed Search by Constrained Agents

1. Front Matter

   Pages I-XX

   PDF

2. Introduction

   • Amnon Meisels

   Pages 1-5

3. Constraints Satisfaction Problems - CSPs

   • Amnon Meisels

   Pages 7-17

4. Constraints Optimization Problems - COPs

   • Amnon Meisels

   Pages 19-26

5. Distributed Search

   • Amnon Meisels

   Pages 27-35

6. Asynchronous Backtracking (ABT)

   • Amnon Meisels

   Pages 37-51

7. Asynchronous Forward-Checking

   • Amnon Meisels

   Pages 53-61

8. Concurrent Dynamic Backtracking

   • Amnon Meisels

   Pages 63-82

9. Distributed Ordering Heuristics

   • Amnon Meisels

   Pages 83-87

10. Asynchronous Ordering Heuristics

    • Amnon Meisels

    Pages 89-104

11. Performance measures for distributed search

    • Amnon Meisels

    Pages 105-120

12. Experimental Evaluation of DisCSP Algorithms

    • Amnon Meisels

    Pages 121-136

13. The Impact of Communication - Message Delays

    • Amnon Meisels

    Pages 137-142

14. Message Delays and DisCSP Search Algorithms

    • Amnon Meisels

    Pages 143-158

15. Distributed Constraint Optimization Problems (DisCOPs)

    • Amnon Meisels

    Pages 159-168

16. Asynchronous Optimization for DisCOPs

    • Amnon Meisels

    Pages 169-182

17. Asynchronous Forward-Bounding

    • Amnon Meisels

    Pages 183-191

18. Extending AFB - BackJumping

    • Amnon Meisels

    Pages 193-201

19. Empirical Evaluation of DisCOP algorithms

    • Amnon Meisels

    Pages 203-207

20. Back Matter

    Pages 209-216

    PDF

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].

• Constraint Satisfaction
• Constraints optimization
• Constraints satisfaction
• Distributed constraints
• Distributed search
• agents
• algorithm
• algorithms
• artificial intelligence
• communication
• heuristics
• optimization
• robot
• robotics
• search algorithm
• algorithm analysis and problem complexity

• Department of Computer Science, Ben-Gurion University, Israel

  Amnon Meisels

Policies and ethics