Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems

DisCSP (مسئله رضایت از محدودیت توزیع شده) یک چارچوب کلی برای حل مشکلات توزیع شده ناشی از هوش مصنوعی توزیع شده است.
طیف گسترده ای از مسائل در هوش مصنوعی با استفاده از الگوی مشکل رضایت محدودیت حل می شوند. با این حال، چندین برنامه کاربردی در هماهنگی چند عاملی وجود دارد که ماهیت توزیع شده دارند. در این نوع کاربرد، دانش در مورد مسئله، یعنی متغیرها و محدودیت ها، ممکن است به صورت منطقی یا جغرافیایی بین عوامل توزیع شده فیزیکی توزیع شود. این توزیع عمدتاً به دلیل حفظ حریم خصوصی و/یا الزامات امنیتی است. بنابراین، یک مدل توزیع‌شده که امکان یک فرآیند حل غیرمتمرکز را فراهم می‌کند برای مدل‌سازی و حل چنین مسائلی مناسب‌تر است. مسئله رضایت از محدودیت توزیع شده دارای چنین ویژگی هایی است.

محتوا

مقدمه
بخش 1. پیشینه استدلال محدودیت متمرکز و توزیع شده
1. مشکلات رضایت از محدودیت
2. مشکلات رضایت از محدودیت توزیع شده
بخش 2. الگوریتم های جستجوی همزمان برای DisCSP ها
3. بررسی پیش رو ناهمزمان مبتنی بر Nogood (AFC-ng)
4. درخت چک کردن پیشرو ناهمزمان (AFC-tree)
5. حفظ سازگاری قوس به صورت ناهمزمان در جستجوی توزیع شده همزمان
بخش 3. الگوریتم های جستجوی ناهمزمان و اکتشافی ترتیب برای DisCSP ها
6. تصحیح "ترتیب عطف به ماسبق در دامنه حداقل برای ردیابی ناهمزمان"
7. Agile Asynchronous BackTracking (Agile-ABT)
بخش 4. DisChoco 2.0: بستری برای استدلال محدودیت های توزیع شده
8. DisChoco 2.0
9. نتیجه‌گیری

درباره نویسندگان

محمد وهبی در حال حاضر استادیار دانشگاه Ecole des Mines de Nantes در فرانسه است. او مدرک دکترای خود را در رشته علوم کامپیوتر از دانشگاه مونپلیه 2 فرانسه و دانشگاه محمد پنجم-آگدال مراکش در سال 2012 دریافت کرد و تحقیقاتش بر روی استدلال محدودیت توزیع شده متمرکز بود.

DisCSP (Distributed Constraint Satisfaction Problem) is a general framework for solving distributed problems arising in Distributed Artificial Intelligence.
A wide variety of problems in artificial intelligence are solved using the constraint satisfaction problem paradigm. However, there are several applications in multi-agent coordination that are of a distributed nature. In this type of application, the knowledge about the problem, that is, variables and constraints, may be logically or geographically distributed among physical distributed agents. This distribution is mainly due to privacy and/or security requirements. Therefore, a distributed model allowing a decentralized solving process is more adequate to model and solve such kinds of problem. The distributed constraint satisfaction problem has such properties.

Contents

Introduction
Part 1. Background on Centralized and Distributed Constraint Reasoning
1. Constraint Satisfaction Problems
2. Distributed Constraint Satisfaction Problems
Part 2. Synchronous Search Algorithms for DisCSPs
3. Nogood Based Asynchronous Forward Checking (AFC-ng)
4. Asynchronous Forward Checking Tree (AFC-tree)
5. Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search
Part 3. Asynchronous Search Algorithms and Ordering Heuristics for DisCSPs
6. Corrigendum to “Min-domain Retroactive Ordering for Asynchronous Backtracking”
7. Agile Asynchronous BackTracking (Agile-ABT)
Part 4. DisChoco 2.0: A Platform for Distributed Constraint Reasoning
8. DisChoco 2.0
9. Conclusion

About the Authors

Mohamed Wahbi is currently an associate lecturer at Ecole des Mines de Nantes in France. He received his PhD degree in Computer Science from University Montpellier 2, France and Mohammed V University-Agdal, Morocco in 2012 and his research focused on Distributed Constraint Reasoning.