بخشی از مقاله
چکیده
یکی از بهترین روشهای جستجوی اگاهانه در مسائل هوش مصنوعی روش SMA* یا جستجو با مدیریت بهینه حافظه می باشد. این جستجوی آگاهانه در مقایسه با روشهای دیگر دارای مزایای قابل توجهی است از جمله پیچیدگی مکانی پایین - مدیریت حافظه - , بهینگی و کامل بودن. در جستجوی SMA* دو تابع g - n - ,h - n - نقش کلیدی ایفا می کنند. در خیلی از مسائل جستجو و مسیر یابی مخصوصا در دنیای واقعی که دارای دینامیک بالایی هستند تعیین مقادیر دقیق این دو تابع کار بسیار مشکل یا تقریبا غیر ممکنی است.
در این مقاله با استفاده ازمنطق فازی که یک ابزار مناسب جهت مدلسازی و استنتاج دانش غیرقطعی و تبدیل آن به دانش قطعی است توابع h - n - ,g - n - فازی سازی شده و روش جدید fuzzy-SMA* ارائه گردیده است. همچنین جهت بهبود عملکرد جستجو یک تابع جدید به نام digress تعریف شده است که میزان فازی ناخوشایندی مسیر را برآورد می نماید. روش پیشنهادی با روشهای جستجوی عمقی تکرار شونده , - IDS - جستوجی اگاهانه A* و SMA* از نقطه نظر هزینه جستجو و میانگین فاکتور انشعاب مقایسه گردید. نتایج نشان دهنده عملکرد بهینه روش پینهادی در مقایسه با روشهای مشابه است .
مقدمه
مقالات روشهای گوناگون زیادی جهت جستجوی آگاهانه هدف توسط ربات جستجوگر ارائه شده است , که از بهترین این روشها می توان به روش A* اشاره نمود - . - Russell and Norvig ,2003 البته این روش خوب دارای نواقصی می باشد . از جمله زمان نمایی جستجو و حافظه زیادی است که برای رسیدن به هدف نیاز دارد. جهت حل مشکل حافظه ترکیب روش جستجوی عمقی تکرار شونده با جستجوی A* پیشنهاد شد - IDA* . - IDA* برای مسائل با هزینه مرحله ای مناسب است و نیازی به نگهداری صف مرتبی از گره ها ندارد.اما متاسفانه مانند نسخه جستجوی تکرار شونده با هزینه یکنواخت, تعداد تکرار منجر به افزایش محاسبات و بالا رفتن زمان جستجو می گردد.
روش SMA* با مدیریت بهینه حافظه توانسته مشکلات روش A* را تاحدود زیادی حل نماید. در جستجوی SMA* دو تابع g - n - ,h - n - نقش کلیدی ایفا می کنند. در خیلی از مسائل جستجو و مسیر یابی مخصوصا در دنیای واقعی که دارای دینامیک بالایی هستند تعیین مقادیر دقیق این دو تابع کار بسیار مشکل یا تقریبا غیر ممکنی است. تابع g - n - هزینه مسیر از نود جاری تا نود n و h - n - هزینه تخمینی ارزانترین مسیر از گره n تا گره هدف است.
اگر محیط قطعی , ایستا , گسسته و قابل دسترسی باشد تخمین این دو تابع ساده بوده اما در غیره این صورت نمی توان این مقادیر را به راحتی تخمین زد. بهره بردن از منطق فازی در محیطهای که با عدم قطعیت همراه هستند یک راه حل بهینه و مناسب خواهد بود. منطق فازی یک ابزار مناسب جهت مدلسازی و استنتاج دانش غیرقطعی و تبدیل آن به دانش قطعی است . در این فصل روش fuzzy-SMA* معرفی و ارزیابی می گردد.
مروری بر تحقیقات انجام شده:
روش Hybrid Fuzzy A* را جهت مسیریابی بهتر ربات پیشنهاد شده و نتایج خوبی بدست آمده است - Gerdelan and Reyes, 2006 - و در مسائل مختلف از این روش استفاده شده است - Gerdelan et al,2006 - استفاده از منطق فازی - - Gerdelan and Reyes, 2006 و جستجوی A* در مسیریابی رباتهای زیر آبی بدون ناظر - Anwary, , 2008 - یکی دیگر از کاربردهای منطق فازی در مسیریابی تعمیم مسیریابی شبه حلقه ای با استفاده از کوتاهترین مسیر فازی است - , - Boulmakoul,2004 و مسیریابی بر اساس چند عامل فازی , - Soltani, Fernando,2004 - استفاده از اعمال فازی در راهبری ربات در محیطهای مجازی - Jaafar et al, 2007 - ومسیریابی فازی براساس فیلد پتانسیل مصنوعی - Tanasieand Dorian ,2007 - هدایت و مسیر یابی ربات در محیطهای غیره قطعی با استفاده از نگاشت فازی و شبکه بندی - karaman and Hakan ,2005 - از جمله تحقیقاتی بود که در این زمینه انجام شده بود .
جستجوی آگاهانه Fuzzy Simplified Memory-Bounded A*
جستجوی SMA* علاوه بر تمام مزایایش دارای نواقصی نیز می باشد. عملکرد این جستجو وابستگی شدیدی به استراتژی تعریف دو تابع h - n - , g - n - دارد. به طوری که اگر این توابع به درستی تعریف و انتخاب نشوند بهینگی و حتی کامل بودن این روش زیر سئوال می رود. در حقیقت اگر محیط استاتیک و قطعی باشد و دارای پیچیدگی بالایی نباشد تعریف این توابع چندان سخت نیست مثلا تعیین مسیر بهینه بین دو شهر در یک کشور اما اگر بخواهیم مسیر بهینه برای یک ربات مین یاب را در یک میدان قدیمی مین که با موانع طبیعی گوناگون از جمله پوشش ناپیوسته گیاهان , گودالها , جویبارها و حوضچه های آب , سنگها و غیره پوشیده شده باشد تعریف نماییم کار بسیار مشکلی است.
