وبلاگ

از سال 1974، مسائل ارضاء محدویت (CSP[1]) در مسأله پردازش تصویر پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر و رنگ آمیزی گراف گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی و تخصیص منابع و دیگر مسائل کاربردی بزرگ می­توانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف می­شوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکان پذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار می­روند [4].

از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در

 چنین مواقعی عاملها برای رسیدن به یک هدف مشترک تلاش می­ کنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می­ کنند [4].

مسأله ارضاء محدودیت توزیع شده (DCSP[8]) در واقع حالت توزیع شده­ی مسأله­ ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شده ­اند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک می­شوند و مقدار آن را کنترل می­ کنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم می­گیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها می ­تواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی می­ کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را می­توان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب می­ شود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر می­باشد [4] و [22]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است می ­تواند به عنوان DCSP طرح ریزی شود.

در این تحقیق به مسائل ارضاء محدودیت توزیع شده پرداخته می­ شود که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله تلاش می­ کنند.

[1] Constraint Satisfaction Problem

[2] image processing

[3] n-queen

[4] graph coloring

[5] scheduling

[6] recourse allocation

[7] agents

[8] Distributed Constraint Satisfaction Problem