بخشی از مقاله
در این مقاله، برای افزایش تحملپذیری خطا در سیستمهای گسترده١ (توزیع شده) وبه ویژه سیستمهای چندعامله روشهایی پیشنهاد شده است. این روشها حتی با وجود شرایط نایقینی و در نظر گرفتن عاملهای غیرهمسان که برخی دارای قابلیتهای ویژهای هستند، با مبتنی بودن بر یک الگوریتم نسبتا بهینه برای تقسیم مجدد وظایف، عمل مینمایند . روشهای پیشنهادی این تحقیق، در تکمیل پژوهشهای قبلی و به ویژه [12]صورت گرفته اند. در این روش، عاملهای کمکرسان در صورت لزوم، بر اساس الگوریتمی گسترده و نسبتا بهینه٢ اقدام به انتخاب وظیفه میکنند و بدون برقراری ارتباط صریح، مناسبترین وظیفه را از لحاظ سرعت و توان پردازشی(عملیاتی) و قابلیت اعتماد خود و نیز درجه اهمیت وظیفه مورد نظر بر عهده میگیرند . بنابراین از این طریق همکاری ضمنی میان عاملهای کمکرسان برقرار میشود وتا زمانی که شرایط نیاز به کمک برطرف نشده، به این روش از کاهش کارایی سیستم جلوگیری میگردد. این مکانیزم جدید برای تقسیم وظیفه، عملکرد سیستم را در مقایسه با روشهای قبلی مطرح شده در پژوهشهای پیشین که راهکاری برای کنارآمدن با نایقینی و ناهمسانی عاملها، نداشتند به میزان قابل توجهی بهبود می بخشد
کلمات کلیدی : سیستم چندعامله، تحملپذیری خطا، الگوریتم تقسیم وظیفه، تصمیمگیری گسترده٣.
١. مقدمه
در سالهای اخیر، بخش قابلتوجهی از تحقیقاتی که در زمینه هوش ماشین و رباتیک انجام شده، معطوف به سیستمهای گسترده بوده است. دلایل زیر به صورت خاص برای توجیه گسترش و استفاده روزافزون سیستمهای چندرباتـه یـا چندعاملـه، عنـوان شـده اسـت:[1] گسـترده بـودن اغلـب کاربردهـای رباتیکی درمکان، زمان یاعملیات ، افزایش سرعتی که غالبا درصورت تقسیمشدن وظیفه بین مولفههای همکار که بصـورت مـوازی عمـل مـیکننـد، بـه دست می آید، افزایش قابلیت اطمینانی که با فراهم آوردن افزونگی (در قابلیتها یا تعداد عاملها) به دست می آید و بالاخره اینکه معمولاﹰ ساخت تعدادی ربات یا عامل با توانایی اندک که با همکاری یکدیگر قادر به انجام یک مأموریت باشند، بسیار ارزانتر و عملیتر از ساخت یک ربات یا عامل است که به تنهایی و با قابلیتاطمینان مطلوب بتواند کل ماموریت را انجام دهد. البته با وجود پژوهشهای فراوانـی کـه دردانشـگاهها و مراکزتحقیقـاتی در مـورد سیستمهای چندعامله یا چندرباته انجام شده، هنوز در عمل و در بسیاری ازکاربردهای دنیایواقعی، این تکنولوﮊی جایگزین روشهای موجود نشدهاست.
شاید دلیل اصلی این امر را بتوان در آسیبپذیری فراوان آنها نسبت به اشکالها وخرابیهای رایجی دانست که در مکانیزیمهای مختلـف سـازنده رباتهـا رخ میدهد، یا اینکه کنارنیامدن عاملها را با تغییرات فراوانی که درمحیط عملیاتی پویای آنها رخ میدهد، علت این مساله برشمرد. ایـن مـوارد یـا دلایـل مشابه اینها، لزوم افزودنقابلیت تحملپذیریخطا به رباتها و عاملها و در نتیجه طراحی سیستمهای چندعامله با قوام٤ بیشتر را تقویت میکند
این مقاله، به مساله ایجاد تحملپذیری خطا به کمک روشهای ساده، عملی و در عینحال کمهزینه، در کاربردهـایی مـیپـردازد کـه قابلیـت توزیعشدگی را دارند. چنین سیستمهایی با بهرهگیری از راهکارهایی که در این تحقیق معرفی شدهاند، میتوانند طوری تغییر یابند کـه حتـی در صـورت بروز خطا برای تعداد زیادی از عناصر سیستم تا جایی که سیستم حداقل تعداد عناصر سالمی را شـامل باشـد، از کـار بـاز نمانـد و حـداقل بحرانـیتـرین وظایفی که در زمان طراحی برایش تعیین شده را به درستی به انجام برساند. اگر توجه خود را در حالت کلی به سیستمهای گسترده معطوف نمـاییم، هـر
1 Distributed 2 Sub-Optimal 3 Distributed Decision-Making 4 Robustness
سیستم گسترده را میتوان به منزله تیمی از عاملهای همکار٥ دانست که هر یک وظیفه خاصی به عهده دارند و از تعامل آنها بـا یکـدیگر یـک عملکـرد واحد حاصل میشود. این شیوه نگرش موجب میشود که بتوان از ایده سیستمهای چندعامله برای توسعه یک سیستم گسترده تحملپذیر خطـا اسـتفاده نمود. ایده اساسی این تحقیق آن است که، به جای جایگزین نمودن یک عامل خراب با یک عامل دیگر از خارج، از قابلیـتهـای رزرو دیگـر عاملهـای موجود استفاده کرده، نقش عامل خراب را به نحوی بر دوش همکارانش قرار دهیم تا شرایط بحرانی با کمترین تاثیر نامطلوب بر کارایی مرتفع گردد. به بیان دیگر، بهرهگیری از خود عاملهای درگیر در حل مساله به منظور رفع خطا در سیستم مورد تاکید اسـت بـدون اینکـه از عامـل واسـطهای٦ بـه منظـور ایجاد هماهنگی در تنظیم وظایف جدید استفاده شود. در این مقاله پس از بررسی کارهای مشابه انجام شده در این زمینه و مرور دسـتاوردهای قبلـی ایـن تحقیق، به بیان نحوه تحقق بستر آزمون٧ میپردازیم. سپس روشهای پیشنهادی این مقاله را تشریح میکنـیم . در ادامـه معیـار ارزیـابی کـارایی شـرح داده میشود و بعد از توضیحی در مورد طراحی آزمایشها و نتایج شبیهسازی، نتیجهگیری و کارهای آینده مطرح میگردد.
٢. مروری بر کارهای مشابه
Deen در[2]محیطی توزیع شده برای سیستمهای توزیعشده همکار پیشنهاد داده است که در این محیط تحمـلپـذیری خطـا بـا جـایگزینی عامـلهـای خراب انجام میشود و پس از جایگزینی عامل در برنامه گروه تجدیدنظر صورت میگیرد. در [3] قابلیت سازماندهی مجدد در مدل یادگیری سازمانی بررسی شده است. این عمل با هدف حفظ کارآیی مجموعه رباتها در مواقع بروز خطا صورت میگیرد. هنگامی که در گروه رباتهـا تغییـری بوجـود آید(بدین صورت که تعدادی ازآنها معیوب شوند ویا از کار بیفتند) رباتها باید با تغییر سازمان سعی کنندکه وظیفه گروه را به انجام برسانند. روش فوق برای سیستمهای زمانحقیقی٨ روش مناسبی نیست. چون در این سیستمها زمان اهمیت زیادی دارد و علاوه برآن با توجه بـه اهمیـت میـدان عملیـاتی کـه خیلی از فرایندها برگشتپذیر نیستند جایی برای یادگیری وجود ندارد. در[4]عاملهای محـافظ بـه عنـوان روشـی بـرای ایجـاد تحمـلپـذیری خطـا در سیستمهای چند عامله پیشنهاد شدهاست. عاملهای محافظ ، به منظور حفظ یک سری ویژگیها و نیز جلوگیری از ورود به وضـعیتهـای ناخواسـته در سیستم قرار میگیرند. عاملهای محافظ یک ساختار کنترلی برای سیستمهای چندعامله پدید . در [5] استفاده از کارتیمی برای ساختن معماری مقـاومی که بتواند بر خطاهایی که برای واسطها به وجود میآید، فائق گردد پیشنهاد شدهاست. درALLIANCE [6] که یـک معمـاری کنترلـی توزیـع شـده تحملپذیرخطا برای رباتهای همکارغیر متجانس است و با انتخاب اعمال به صورت تطبیقی کنترل همکاری بـین رباتهـا را انجـام مـیدهـد، معرفـی شـده است. در این معماری، رباتها توانایی انجام تعدادی عملیات سطح بالا که در یک مأموریت، منجر به انجام وظیفه میشـوند را دارا هسـتند و در هـر زمـان
باید یک عمل مناسب را با توجه به نیازمندیهای مأموریت، فعالیتهای سایر رباتها، حالت محیط و حالات درونی ربات انتخاب کنند. در[7] که در ادامه معماری ALLIANCE معرفی شدهاست، معماری تکمیلیافتهای با نام L-ALLIANCE معرفی شدهاست که در آن تقسیموظیفه اولیـه بـه گونـهای انجام شده که مقداری همپوشانی در قابلیت انجام وظیفه میان رباتها موجود باشد. در این طرح دو عمل تقسیم مجدد وظیفه٩ و ترتیبدهی وظیفه١٠ توسط
رباتها صورت میگیرد. در فرایند کمکرسانی که در[1] شرح داده شده است، دو نکته بسیار مهم در کمک رسانی وجود دارد کـه عبارتنـد از مکـانیزم انتخاب عمل و هماهنگی بین رباتها در عملیات کمکرسانی. در این تحقیق قابلیت پشتیبانی کمک به معماری ALLIANCE اضافه شده است. در حالی که این تحقیق منحصر به رباتهایی با وظیفههایی مشخص است؛ مقاله حاضر مشابه همین ایده را به محدوده وسیعتری از سیسـتمها یعنـی سیسـتمهای گسترده توسعه می دهد بدون اینکه معماری خاصی مانند ALLIANCE را مدنظر داشته باشد.
[8] به عنوان اولین گام این تحقیقات، به بیان سادهترین روش کمکرسانی میپردازد که تنها مبتنی بر درجهاهمیت وظیفـه عامـلهاسـت.در ادامـه بـرای افزودن بر پویایی مکانیزم تصمیمگیری،[9] به بیان چند استراتژی ساده کمکرسانی مبتنـی بـر ریسـک مـیپـردازد و در[10] مفهـوم بـیصـبری بـرای کمکرسانی با تعریف سادهای معرفی شدهاست. مفهوم بیصبری در[11]توسعه یافتـه و از دانـش عاملهـا بـه نحـو جـامعتری اسـتفاده مـینمایـد. در[12]
استراتژیهای ساده و ترکیبی برای تعیین ترتیب کمکرسانی معرفی شدهاند، اما از تقسیم وظیفه گسترده میان عاملها در صورت بروز خطا و کنارآمدن با شرایط نایقینی و غیرهمسانی عاملها که در این مقاله بر آنها تاکید میگردد، بحثی به میان نیامده است. در[13] ساده ترین روش غیرقطعی کمـکرسـانی مبتنی بر الگوریتم تقسیم وظیفه نسبتا بهینه مطرح شدهاست.
5 Cooperative Agents 6 Middle Agents 7 Testbed 8 Real-Time Systems
9 Task Re-allocation 10 Task Ordering
٣. شرح سیستم
سیستمی که برای تحقق ایدههای این پژوهش برگزیده شدهاست، شبیه یک سیستم کنترل گسترده١١ ولی بسیار سادهتر است. علـت انتخـاب ایـن سیسـتم گسترده برای چنین منظوری آن است که این سیستم به علت داشتن عناصر مستقل و قابلیت تعریف انواع وظیفهها برای هـر عامـل، نمونـه خـوبی از یـک سیستم توزیعشده در حالت کلی است. البته انتخاب این سیستم از کلیت طرح و ایدهها نمیکاهد، چرا که وابستگی مفهومی میان ایدههـای پیشـنهادی در حالت کلی با این بستر آزمون وجود ندارد. در این سیستم هر عامل به منزله یک کنترلر است. دادههای مورد نیاز هر عامل توسط تولید کننده بسـته داده-
ای١٢ از سنسورهای موجود در محیط جمعآوری میشود و در اختیار عاملها قرار میگیرد. عاملها با دسترسی بـه بـاس مشـترک ورودی داده مـورد نظـر خود را برمیدارند و پس از انجام وظیفه موردنظر، نتیجه خروجی خود را بر روی باس خروجی قرار میدهند. آنچه شـرح داده شـد، عملکـرد سیسـتم در حالت عادی است. در صورتی که خطا در سیستم رخ بدهد، عامل نیازمند به کمک این مساله را به اطلاع بقیه می رساند. در صورتی که عـاملی خـود را واجد شرایط کمکرسانی بیابد ( که در مورد مساله واجد شرایط بودن و نحوه همکاری ضمنی میان عاملها کمی جلوتر بحث خواهـد شـد) پـس ازطـی مراحل لازم، کمکرسانی به وی را آغاز میکند.
۳- ۱ شرح وظایف سیستم
در این سیستم، هر عامل در حالت عادی انجام یک وظیفه را بر عهده دارد. وظیفه ها در حالت قطعی به صورت پریودیک و در حالت غیرقطعی با پیروی از یک الگوی تصادفی گوسی، به عاملها محول می شوند. در صورتی که یک عامل وظیفهای که به او محول شدهاست را پیش از به سـر رسـیدن مهلـت زمانیاش به انجام برساند و نتیجه خروجی را بر روی باس موردنظر قرار دهد، این وظیفه به طور موفقیتآمیزی به پایان رسـیدهاسـت. ویژگـی هـایی کـه یک وظیفه به کمک آنها توصیف می گردند، عبارتند از: حجم متوسط پردازشی١٣، طول زمان اجرا١٤، مهلت زمانی مقرر١٥ و درجه اهمیت١٦.
بستر آزمون در نظر گرفته شده برای تست، دارای مولفههای اصلی زیر است:
تولید کننده بسته دادهای : به منظور تولید داده های مربوط به هر عامل، این مولفه بستههای دادهای را تولید میکند و از طریق باس مشترک ورودی در اختیار همه عاملها قرار میدهد. از طریق این مولفه میتوانیم با نرخ ثابت یا به صورت متغیـر تصـادفی بـا توزیـع مشـخص بـه تولیـد داده بپـردازیم. در گونهای که نرخ آمدن داده های ورودی یکسان و ثابت است، هر عامل بسته های دادهای با پریود ثابت و برابر به عامل منسوب میشوند و عاملها هم از این نرخ آگاهند و با قطعیت کامل تصمیم میگیرند. در مدل غیرقطعی، فرکانس تولید دادهها بـرای هـر عامـل از یـک توزیـع نرمـال بـا میـانگین و واریـانس مشخص پیروی مینماید.
باس مشترک ورودی : این باس، باس مشترک ورودی سیستم است که توسط تولیدکننده بسته داده، تغذیه می شود.
باسهای مشترک به منظورکمکرسانی : به منظور اعلام نیاز به کمک و نیز اعلام انجام کمکرسانی به دیگر کمکرسانها به منظـور جلـوگیری از ارسال کمک تکراری، دو باس مشترک، هر یک به صورت رجیسترهایی به تعداد عاملها در سیستم قرار گرفته است.
عاملها: در این سیستم تعدادی عامل غیرهمسان از لحاظ ویژگیهای درونی وجود دارند که از تعامل آنها سیستم چندعاملـه مـوردنظر سـاخته مـیشـود.
هرعامل دارای یک ID خاص است که همین ویژگی، موجب ایجاد تفاوتهایی در هر عامل در مقایسه با دیگر هم تیمیهای وی میشود. ایـن تفاوتهـای درونی عبارتند از : سرعت ، قابلیت اعتماد( کمیت نسبی که میزان قابلیت اعتماد به عملکرد هر عامل را مشخص میکند) و نرخ یادگیری مجازی:( بـرای هر عامل اثری شبیه یادگیری فرض شده است که با افزایش این یادگیری، طول مدت زمان اجرای وظیفه عامل کاهش یافته، زمان آزادی او افـزایش مـی یابد. به عبارت دیگر هر چه تعداد وظیفههای تا بهحال انجام شده توسط هر عامل افزایش یابد، تسلط نسبی عامل بر انجام وظیفههای مشابه بعدی اضـافه میگردد. نرخ یادگیری مجازی هر عامل با دیگری متفاوت است. )
۳- ۲ فرضیات
در این سیستم به مساله تشخیص خطا پرداخته نشدهاست و فرض بر این است که هر عامل قادر است از رخداد خطای خود آگاهی یابد و این مسـاله را بـا ارسال درخواست کمک به بقیه نیز اطلاع دهد. علاوه بر این فرض شده است که یک عامل قادر است وظیفـه هـمتیمـیهـای خـود را طبیعتـا بـا سـطحی مختلف از لحاظ معیارهای کارایی در مواقع لزوم انجام بدهد. البته چنانچه پیشتر هم اشاره شد به دلیل غیرهمسان بودن عاملهـا کـه بـه منظـور افـزودن بـر جامعیت طرح در نظر گرفته شده است، تعدادی از عاملها با قابلیت ویژه فرض شدهاند و انجام وظایف آنها توسـط هـر عامـل دیگـری لزومـا امکـانپـذیر نیست و عاملها موظفند که در زمان تقسیم وظایف به این امر توجه نمایند..
