Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent Systems

وقتی چندین عامل در یک محیط مشترک هستند، معمولاً محدودیت‌هایی در بین اقدامات احتمالی این عوامل وجود دارد. مشکل رضایت محدودیت توزیع شده (CSP توزیع شده) مشکلی است که در آن هدف یافتن ترکیبی سازگار از اقدامات است که این محدودیت‌های بین عاملی را برآورده می‌کند. به طور خاص، یک CSP توزیع شده یک مشکل رضایت محدودیت (CSP) است که در آن چندین عامل دخیل هستند. مشکل رضایت محدودیت مشکلی است که در آن هدف یافتن یک تخصیص ثابت از مقادیر به متغیرها است. حتی اگر تعریف CSP بسیار ساده است، طیف گسترده ای از مشکلات هوش مصنوعی (AI) را می توان به عنوان CSP رسمی کرد. بنابراین، تحقیق در مورد CSP ها سابقه طولانی و متمایز در هوش مصنوعی دارد (Mackworth 1992؛ Dechter 1992؛ Tsang 1993؛ Kumar 1992). یک CSP توزیع شده یک CSP است که در آن متغیرها و محدودیت ها بین چندین عامل مستقل توزیع می شوند. مشکلات کاربردی مختلف در سیستم‌های چند عامله (MAS) که مربوط به یافتن ترکیبی سازگار از اقدامات عامل است، می‌تواند به عنوان CSPهای توزیع شده رسمیت یابد. بنابراین، می‌توانیم CSP‌های توزیع‌شده را به‌عنوان چارچوبی کلی برای MAS، و الگوریتم‌هایی برای حل CSP‌های توزیع‌شده را به‌عنوان زیرساخت‌های مهم برای همکاری در MAS در نظر بگیریم. CSPs. در فصل 1. ما تعریف مسئله CSPهای معمولی و متمرکز را نشان می‌دهیم و الگوریتم‌هایی را برای حل CSPها توصیف می‌کنیم.

When multiple agents are in a shared environment, there usually exist con­ straints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem in which the goal is to find a consistent combination of actions that satisfies these inter-agent constraints. More specifically, a distributed CSP is a constraint satisfaction problem (CSP) in which multiple agents are involved. A constraint satisfaction problem is a problem in which the goal is to find a consistent assignment of values to variables. Even though the definition of a CSP is very simple, a surprisingly wide variety of artificial intelligence (AI) problems can be formalized as CSPs. Therefore, the research on CSPs has a long and distinguished history in AI (Mackworth 1992; Dechter 1992; Tsang 1993; Kumar 1992). A distributed CSP is a CSP in which variables and constraints are distributed among multiple autonomous agents. Various application problems in Multi-agent Systems (MAS) that are concerned with finding a consistent combination of agent actions can he formalized as dis­ tributed CSPs. Therefore, we can consid(~r distributed CSPs as a general framework for MAS, and algorithms for solving distributed CSPs as impor­ tant infrastructures for cooperation in MAS. This book gives an overview of the research on distributed CSPs, as well as introductory material on CSPs. In Chapter 1. we show the problem defi­ nition of normal, centralized CSPs and describe algorithms for solving CSPs.