انسانی غیرقابل پیش ­بینی حرکت کرده است. ربات­های امروزی می­بایست در محیط­های ساخت­نیافته و پویا فعالیت کنند. ربات­ها به طور گسترده در منازل، اداره­ها، بیمارستان­ها، امدادرسانی در نواحی خطرناک یا غیرقابل دسترس، یاری­رسانی به افراد معلول، تولید و مونتاژ و بسته­بندی، حمل و نقل، اکتشافات زمینی و فضایی، جنگ افزارها و تحقیقات آزمایشگاهی به کار می­روند.
تعاریف اولیه در رباتیک
یک تعریف ساده از ربات می ­تواند این باشد: مکانیزمی که قادر به حس و درک محیط پیرامون و حرکت و واکنش باشد. در تعریفی دقیق­تر و جزیی­تر می­توان ربات را مجموعه ­ای از زیر سامانه­های ادوات حسگری، واحد تصمیم ­گیری، کنترل­ کننده، محرک­ها، بازوهای مکانیکی و منابع تغذیه دانست [۲]. برای ناوبری ربات­­­های متحرک ممکن است از حسگرهای مختلف استفاده شود که لزوماً از یک نوع نیستند. بعضی از حسگرها اطلاعات یکدیگر را تکمیل و برخی دیگر، اطلاعات یکدیگر را تصحیح می­نمایند. ربات از حسگرهای با محرک خارجی مانند دوربین، حسگر فراصوت یا مادون­قرمز برای مشاهده­ حالت محیط استفاده می­ کند؛ و از حسگرهایی با محرک داخلی مانند قطب­نما یا رمزگذارمحور^[۳] (بر روی چرخ­ها) برای مشاهده­ موقعیت، سرعت و شتاب پیوندها و مفاصل مختلف خود بهره می­گیرد. اطلاعات به دست آمده از حسگرها به منظور ترکیب و تفسیر به واحد تصمیم ­گیری ارسال می­شوند، که مغز ربات تلقی می­ شود و مهمترین نقش را در برنامه­ ریزی­های ربات ایفا می­ کند. پس از تحلیل داده ­های حسگرها و اخذ تصمیم، فرمان مناسب به کنترل­ کننده ارسال می­ شود. وظیفه­ی کنترل­ کننده تولید سیگنال­های لازم جهت درایو محرک­ها می­باشد. محرک­ها، سیگنال­های دریافتی از کنترل­ کننده را به حرکت تبدیل می­نمایند. بازوهای مکانیکی مانند بازوهای رباتیک یا محور چرخ­ها مجموعه ­ای از پیوندها هستند که توسط مفاصل به هم متصل شده ­اند و توانایی تاثیرگذاری در محیط را دارند (حرکت دادن یا گرفتن اجسام). منابع تغذیه سامانه­های قدرتی می­باشند که برای تولید و تنظیم انرژی مورد نیاز محرک­ها و درایورها به کار می­روند.

چالش­های ناوبری خودمختار
به رغم پیشرفت­های قابل توجه در زمینه رباتیک خودمختار در سال­های اخیر هنوز تعدادی مسایل حل نشده باقی مانده است. اکثر مشکلات از طبیعت محیط­های ساخت­نیافته­ی دنیای واقعی و عدم قطعیت­های وسیع ذاتی آنها سرچشمه می­گیرند [۱]. اولاً دانش پیشین درباره محیط معمولاً ناقص، غیرقطعی و تقریبی است. برای مثال در نقشه‌هایی که ربات از محیطش می­سازد معمولاً برخی جزییات و مشخصه­های موقتی حذف می­شوند، روابط مکانی میان اشیا ممکن است از زمانیکه نقشه ساخته شده است تغییر کرده باشند و اطلاعات متریک شاید غیر دقیق و ناصحیح باشند. دوماً اطلاعات ادراکی به دست آمده معمولاً غیر قابل اطمینان هستند. گستره محدود، ترکیب شده با اثر مشخصه­های مکانی (مانند انسداد) و شرایط نابسامان مشاهدات (مانند روشنایی ضعیف)، منجر به اطلاعات نویزی و غیر دقیق می­شوند؛ و خطاهای موجود در فرایند تفسیر اندازه ­گیری­ها ممکن است منجر به باورهای ناصحیح شوند. سوماً محیط­های دنیای واقعی معمولاً دارای دینامیک پیچیده و غیر قابل پیش ­بینی می­باشند: اشیا می­توانند حرکت کنند، سایر عوامل می­توانند محیط را تغییر دهند و مشخصه­های نسبتاً پایدار ممکن است با زمان تغییر کنند (مانند تغییرات فصلی). نهایتاً اثر عمل­های کنترلی کاملاً قابل اعتماد نیستند: چرخ­ها ممکن است سر بخورند، و یک گیرنده ممکن است شیئ را رها کند.
از لحاظ لغوی عدم قطعیت مشخصه­ی اطلاعات نیست بلکه مشخصه­ی عامل است. یک عامل ممکن است در مورد وجود شیئ، مقدار یک مشخصه، صحت یک پیش­فرض یا انجام عملی نامطمئن باشد. با این وجود بسیار معمول است که از اطلاعات غیرقطعی صحبت کنیم. رباتی را در نظر بگیرید که قصد دارد جعبه ای را بگیرد؛ این عمل نیازمند اطلاع از موقعیت جعبه با حد زیادی از دقت می­باشد- چقدر “زیاد” به مکانیزم گیرنده‌ی ربات بستگی دارد. مثال­هایی از حالت‌های ممکن اطلاعات غیر‌قطعی می­توانند به صورت زیر باشند:
“جعبه روی میز است": برای انجام عمل بسیار ضعیف است چون موقعیت یکتایی به دست نمی‌دهد.
“جعبه حدوداً در وسط میز است": مبهم است چون موقعیتی واضح به‌دست نمی‌دهد.
“جعبه دیروز در مختصات (۱و۳) دیده شد": غیر قابل اطمینان است چون جعبه ممکن است دیگر آنجا نباشد.
همه این حالات می توانند غیرقطعی در نظر گرفته شوند چون عامل را در حالت عدم اطمینان از موقعیت واقعی جعبه قرار می­ دهند. توجه شود که غیرقطعی در نظر گرفتن یک اطلاع ممکن است به آن عمل مشخص بستگی داشته باشد مثل حالت (۱)، یا به منبع اطلاع مانند حالت (۳).
روش­های حل مساله­ی ناوبری ربات
سه نگرش کلی برای هدایت ربات وجود دارد: الگوریتم­های سلسله مراتبی^[۴] یا طرح مسیر سراسری^[۵]، الگوریتم­های واکنشی^[۶] یا مبتنی بر رفتار^[۷] یا طرح مسیر محلی^[۸] و الگوریتم­های ترکیبی^[۹] [۳]. الگوریتم­های اولیه­ ناوبری ربات در محیط­هایی کاملاً شناخته­شده، که ربات اطلاعات کاملی در مورد موانع و شکل هندسی آنها در دست داشت، توسعه یافتند. لذا در این حالت، ربات در زمان غیر حقیقی تصمیم­های لازم را جهت رسیدن به هدف و برخورد نکردن با موانع اتخاذ کرده و سپس به سمت هدف حرکت می­ کند. در این الگوریتم­ها مطلوب، یافتن مسیری بهینه بین نقطه شروع اولیه و هدف در مرحله طراحی و سپس هدایت ربات در آن مسیر در مرحله اجرا می­باشد. اینگونه روش­های طرح مسیر سراسری تا هدف تنها جهت تعیین مسیر به صورت غیر­لحظه­ای مناسبند و برای پرهیز از مانع به صورت بلادرنگ، که یکی از موضوعات مهم در محیط­های پویا می­باشد، کافی به نظر نمی­رسند. اگر یک مانع متحرک ظاهر شود مسیر می­بایست تغییر کند، یعنی دوباره محاسبه شود که ممکن است زمان زیادی نسبت به حرکت مانع بگیرد. بنابراین رفتار ربات به اندازه کافی واکنشی نیست. دنبال کردن مسیری از پیش محاسبه شده راهی مؤثر برای رساندن ربات به موقعیت هدف است اگر دو شرط برقرار باشند: فرضیات به کار رفته هنگام محاسبه­ی مسیر هنوز در زمان اجرا معتبر باشند (برای مثال محیط به طور صحیح مدل شده باشد و بعد از آن تغییر نکرده باشد)؛ ربات قادر باشد به طور قابل اطمینانی موقعیت خود را نسبت به مسیر به دست آورد. در این روش­ها محققین تلاش کرده ­اند با طراحی دقیق مکانیک و حسگرهای ربات یا مهندسی محیط و یا هردوی اینها بر بعضی از مشکلات ناوبری ربات غلبه کنند. مهندسی دقیق ربات و محیط هزینه­ها را افزایش می­دهد، خودمختاری ربات را کاهش می­دهد، و نمی تواند برای تمامی محیط­ها به کار رود.
هر الگوریتم برای کنترل یک سامانه نیازمند دانش یا مدلی از آن سامانه تحت کنترل می­باشد. در مورد ربات این سامانه از خود ربات به علاوه محیطی که در آن فعالیت می­ کند تشکیل شده است. گرچه مدلی از خود ربات به طور معمول می ­تواند به دست آید، در مورد محیط­های ساخت­نیافته دنیای واقعی متأسفانه شرایط متفاوت است. همان­طور که اشاره شد این محیط­ها با حضور فراگیر عدم قطعیت­ها توصیف می­شوند. چالش اصلی رباتیک خودمختار امروز ساخت الگوریتم­های قدرتمند طراحی مسیر است که علی­رغم عدم قطعیت­ها وظایف پیچیده را به طور قابل اطمینانی انجام دهند. یک استراتژی معمول برای کنار آمدن با این مقدار وسیع عدم قطعیت، رها کردن ایده‌ی مدل کردن کامل محیط در مرحله‌ی طراحی است، و اینکه به ربات این قابلیت داده شود که این مدل را خودش و به صورت برخط بسازد.
دسته‌ی دوم الگوریتم­های ناوبری بر خلاف دسته‌ی اول محیط را ناشناخته فرض کرده و واحد تصمیم ­گیری ربات را به گونه ­ای طراحی می­ کنند که بتواند در زمان حقیقی رفتار صحیح را تشخیص داده و ربات را به سمت هدف مورد نظر هدایت کند. به علت تفاوت مهمی که در دو نگرش فوق در مورد هدایت یک ربات وجود دارد، الگوریتم­هایی که برای اجرای این دو نگرش پیاده سازی می­شوند با دو نام مختلف شناخته شده و در مقالات به آنها اشاره می­ شود. در مورد دسته اول اصطلاح مسیریابی و در مورد دسته دوم اصطلاح ناویری استفاده می­ شود. در روش ناوبری مبتنی بر رفتار، رفتارهای پیچیده با ترکیب برخی اجزای رفتاری قابل حل و ساده­تر مانند رفتارهای جستجوی هدف و دوری از موانع به دست می ­آید. در الگوریتم­های مبتنی بر رفتار مسیر به صورت محلی و نه سراسری طرح می­ شود. روش طرح مسیر محلی نیازمند هیچ مرحله پیش محاسبه سنگینی پیش از شروع جستجوی مسیر نیست. روش­های طرح مسیر محلی اطلاعات کنونی حسگر را به صورت بلادرنگ به دست می­آورند تا ربات را از موانع محلی دور نگاه دارند. به دلیل آنکه الگوریتم­های محلی هیچگاه قسمت­ های مختلف مسیر را از پیش محاسبه نمی­کنند.
با این حال الگوریتم­های طرح مسیر محلی یافتن مسیر بهینه را تضمین نمی­کند. ممکن است موقعیت­هایی پیش بیاید (کمینه­های محلی) که الگوریتم­های طرح مسیر محلی در یافتن موقعیت هدف شکست ­بخورد. اگر تعداد موانع به طور محسوسی کم باشد، ممکن است ثابت شود که این روش­ها بهترین راه حل را ارائه می­ دهند. هر دو روش طرح مسیر سراسری و محلی می­توانند برای وظایف متعددی مناسب باشند و مزایا و معایب خاص خود را دارا هستند. اما به منظور تعیین مسیر در محیط­های پویا هیچکدام راه حلی کارآمد ارائه نمی­دهند. دسته سوم الگوریتم­های ناوبری ربات، ترکیبی از روش­های طرح مسیر سراسری و مبتنی بر رفتار می­باشند. در این روش­ها از ماژول طرح مسیر سراسری برای رسیدن به هدف و از ماژول مبتنی بر رفتار برای پاسخ به وقایع محیط، مانند دوری از موانع، بهره گرفته می­ شود.
اهداف و نتایج
در این پژوهش الگوریتمی ساده و کارآمد به منظور ناوبری ربات خودمختار از یک نقطه شروع معلوم به سمت هدفی مشخص در محیطی کاملاً ناشناخته و در حضور موانع ایستا ارائه شده است. الگوریتم پیشنهادی از مزایای ترکیب منطق فازی و یادگیری Q برای تامین نیازهای ناوبری خودمختار بهره می­گیرد. دو رفتار ساده­تر حرکت به سمت هدف و دوری از موانع در یک مجموعه قانون فازی پیاده­سازی شده‌اند. مهم­ترین ویژگی منطق فازی عملکرد کارآمد آن در مواجه با عدم قطعیت­های محیط است. ربات اطلاعات به دست آمده از جهان پیرامون را به مجموعه ­ای از حالت­های فازی خلاصه می­ کند. برای هر حالت فازی، تعدادی عمل پیشنهادی وجود دارند. حالت­ها توسط قوانین اگر-آنگاه فازی، که با منطق انسان طرح شده ­اند، به عمل­های نظیرشان مربوط می­شوند. برای هر حالت، ربات بهترین عمل را با یادگیری Q و از طریق تجربیات برخط انتخاب می­ کند. یادگیری Q با توجه به حالت فعلی و حافظه­ای از حالت­های پیشین ربات، خروجی هر قانون فازی را به نحوی انتخاب می­ کند که حتی­الامکان ربات با تضمین دوری از موانع به سمت هدف حرکت نماید. مشخصه قابل توجه یادگیری Q عدم نیاز به مربی و مدل محیط، ساختار پویا و پیاده سازی آسان آن می­باشد.
تمرکز اصلی این پایان نامه بر طراحی واحد تصمیم ­گیری ربات می­باشد. ربات ساده و کوچک کپرا^[۱۰] برای شبیه­سازی­ها به کار رفته است، که می­توان از مدل نقطه­ای برای آن بهره گرفت. بدین ترتیب الگوریتم پیشنهادی به راحتی قابل انتقال به محیط­های دیگر و پیاده­سازی بر سایر ربات­ها باشد. حسگرهای ربات کپرا از نوع مادون­قرمز می­باشند که خروجی­های دیجیتال آنها بدون نیاز به مرحله پیش پردازش به عنوان ورودی­های فازی مورد استفاده قرار می­گیرند و بیانگر حالت قرارگیری ربات نسبت به موانع می باشند. خروجی­های قوانین فازی میزان سرعت انتقالی و زاویه چرخش چرخ­های ربات می­باشند. ربات کپرا به صورت دیفرانسیلی حرکت می­­کند.
روش پیشنهادی مستقل از مدل محیط و دانش پیشین از محیط می­باشد. تنها منبع اطلاعات از محیط توسط حسگرهای مادون­قرمز ربات به دست می ­آید. همچنین فرض می­ شود ربات مجهز به سامانه موقعیت یاب محلی است و در هر گام از موقعیت خود نسبت به هدف مطلع می­باشد. فاصله تا هدف از روش محاسبه فاصله اقلیدسی با معلوم بودن مختصات ربات و هدف در هر گام به دست می ­آید. برای خروجی زاویه چرخش هر قانون فازی تعدادی گزینه پیشنهادی وجود دارد که به هرکدام یک مقدار q منتسب می­ شود. ربات در هر گام بهترین خروجی (دارای بیشترین مقدار q) را توسط یادگیری Q و از طریق تعاملات برخط با محیط انتخاب می­ کند. مقادیر q پس از دریافت سیگنال تشویق یا جریمه به روز می­شوند. تنظیم برخط سامانه استنباط فازی^[۱۱]، منجر به واحد تصمیم ­گیری انعطاف پذیری می­ شود که می ­تواند خود را با محیط­های مختلف و موانع متنوع تطبیق دهد.
در روش پیشنهادی، یادگیری Q بدون هیچ مرحله یادگیری یا اکتشافی به کار گرفته شده است. بدین معنی که هر بار اجرای الگوریتم با مقادیر q اولیه صفر آغاز می­ شود. یادگیری Q بدون مرحله اکتشافی (یادگیری قبل از آزمایش) به کار گرفته شده­است. بدین معنی که مقادیر q در هر آزمایش بدون پیش­فرض و از مقدار اولیه صفر شروع می­شوند، لذا محیط یادگیری جهت مقداردهی اولیه به مقادیر q وجود ندارد. پارامترهای کلیدی مجموعه فازی و یادگیری Q، شامل پارامترهای توابع عضویت ورودی فازی و همچنین مقدار عامل فراموشی یادگیری Q، توسط بهینه­سازی کلونی زنبور مصنوعی به صورت غیربرخط، پیش از قرار گرفتن ربات در محیط­های آزمایش، به دست آمده­اند. محیط بهینه­سازی شامل موانعی است که انتظار می‌رود خود یا ترکیبی از آنها در محیط­های آزمایش دیده شوند.
برای آزمایش الگوریتم پیشنهادی ۶۰ محیط شبیه­سازی دو بعدی به طور تصادفی ایجاد ­شدند. شکل، مساحت و مکان موانع، محل اولیه ربات و مختصات هدف در این محیط­ها به طور تصادفی انتخاب ­شدند. موانع تولید شده، گستره وسیعی از شکل­های هندسی منظم و نامنظم شامل چند ضلعی­ها، شکل­های محدب یا مقعر، زاویه­دار یا با گوشه­های محدب و غیره را در بردارند. این شکل­ها تقریبا تمامی انواع موانعی، که ربات ممکن است در محیط واقعی با آن مواجه شود، را شامل می­شوند. محیط­های شبیه­سازی از نظر نوع موانع موجود و مساحت اشغال شده توسط موانع به سه سطح ساده، معمولی و پیچیده تقسیم بندی ­شدند. عملکرد ربات با توجه به اندازه ­گیری­های کمی معیارهایی چون درصد موفقیت رسیدن به هدف (طی اجراهای مختلف الگوریتم پیشنهادی)، امنیت مسیر طی شده تا هدف (نسب تعداد برخوردها با موانع به کل گام­های طی شده) و سرعت مسیر طی شده تا هدف (تعداد گام­های طی شده نسبت به زمان سپری شده) سنجیده ­شد. به منظور معتبر بودن و تکرارپذیری نتایج، هر آزمایش ۱۰ بار تکرار شده است و نتیجه گزارش شده میانگین نتایج حاصل از این ۱۰ بار اجرا بوده است.
نتایج نشان دادند که الگوریتم تصمیم ­گیری پیشنهادی قادر است با موفقیت ربات را به سمت هدف هدایت کرده و از برخورد آن با موانع جلوگیری نماید. به منظور آشکار کردن نقش موثر یادگیری Q در افزایش کارایی الگوریتم پیشنهادی آزمایش­های مشابه­ای با مجموعه قوانین فازی مشابه بدون یادگیری Q تکرار شدند. مقایسه نتایج نشان داد تنظیم برخط قوانین فازی توسط یادگیری Q عملکرد آن را از نظر معیارهای عملکردی مطرح شده و انعطاف­پذیری در مواجه با انواع محیط­های ساده تا پیچیده، بهبود می­بخشد.
ساختار پایان نامه
فصل های بعدی این پایان نامه شامل مطالب زیر هستند:
فصل دوم به مرور، دسته­بندی و مقایسه کیفی برخی روش­های ناوبری ربات می ­پردازد. فصل سوم مبانی و ابزار لازم برای معرفی الگوریتم پیشنهادی شامل منطق فازی^[۱۲]، یادگیری Q و الگوریتم بهینه­سازی کلونی زنبور مصنوعی^[۱۳] را توصیف می­ کند. فصل چهارم به توصیف ربات کپرا و توضیح الگوریتم پیشنهادی می ­پردازد. الگوریتم مطرح شده یک سامانه تصمیم ­گیری فازی ناوبری ربات است، که بدون دانش پیشین از محیط طراحی می­ شود و سپس به طور برخط توسط یادگیری Q و در مواجه با محیط تنظیم می­ شود. پارامترهای کلیدی مجموعه فازی و یادگیری Q، شامل پارامترهای توابع عضویت ورودی فازی و همچنین مقدار عامل فراموشی یادگیری Q، توسط بهینه­سازی کلونی زنبور مصنوعی به صورت غیربرخط، پیش از قرار گرفتن ربات در محیط­های آزمایش، به دست آمده­اند. در نهایت فصل پنجم پس از توصیف نرم­افزار شبیه­سازی KiKS و محیط­های آزمایش، نتایج حاصل از شبیه سازی­ها را ارائه می­دهد. سپس نتایج شبیه­سازی­ها تحلیل می­شوند و پیشنهادهایی برای ادامه کار مطرح می­گردند.
فصل دوم
بررسی روش های پیشین

بررسی روش­های پیشین

مقدمه
از اوایل سال ۱۹۶۰، تعداد محققین روی مساله ناوبری ربات‌های متحرک به تدریج افزایش یافته­است. کاربردهای مختلف ربات‌های متحرک منجر به ارائه راه­ حل­های متفاوتی برای حل مساله ناوبری آنها می­شو‌د. برای ربات‌های هوشمند متحرک ضروری است که محیط را حس و درک کنند، مسیری را طراحی کنند، تصمیمی اتخاذ کنند و رفتار مناسب را با بهره گرفتن از این اطلاعات اجرا کنند [۴]. معماری‌های مختلف ناوبری ربات تعریف می‌کنند که این توانایی‌ها چگونه بایستی مجتمع شوند تا نتایج مطلوب به دست آیند. معماری‌های مختلفی برای طرح و توسعه‌ی ناوبری مقاوم، انعطاف پذیر، قابل اطمینان و با عملکرد عالی ربات‌های متحرک پیشنهاد شده ­اند. بنابراین دسته­بندی روش­های ناوبری ربات جهت مروری منسجم­تر بر آنها، مفید به نظر می­رسد. سه دسته­ی کلی این معماری­ها عبارتند از: سلسله مراتبی یا طرح مسیر سراسری، واکنشی یا مبتنی بر رفتار یا طرح مسیر محلی و ترکیبی.
معماری سلسله مراتبی
معماری سلسله مراتبی قدیمی‌ترین طرح ناوبری ربات در هوش مصنوعی است. در این معماری [۵-۱۰] از مدل سراسری محیط که توسط داده ورودی کاربر یا حسگرها تهیه شده است برای تولید عمل­های مناسب برای رساندن ربات به هدف بهره ‌گرفته می­ شود. همان‌طور که در شکل(‏۲‑۱) نشان داده شده است، این معماری از چهار ماژول اصلی تشکیل شده است: حس کردن، مدل کردن، تصمیم گیری و عمل کردن. ابتدا ربات محیط اطراف را حس می‌کند و با بهره گرفتن از ترکیب اطلاعات حسگرها مدل سراسری محیط ایستا را ایجاد می‌کند، سپس ماژول تصمیم گیری را برای یافتن مسیر بهینه تا هدف را به کار می‌گیرد و مسیری جهت دنبال کردن برای ربات طرح می‌کند. در نهایت ربات عمل­های مطلوب را تا رسیدن به هدف اجرا می‌کند. پس از یک عمل موفقیت آمیز، ربات متوقف می‌شود و اطلاعات خود را برای انجام حرکت بعدی به روز می‌کند. سپس این فرایند را تا رسیدن به هدف تکرار می‌کند [۱۱, ۱۲].

شکل(‏۲‑۱): معماری سلسله مراتبی جهت ناوبری ربات [۳]

معماری سلسله مراتبی زمانی به کار گرفته می­ شود که محیط برای ربات کاملاً شناخته شده و همچنین در حین حرکت ربات به سمت هدف بدون تغییر (ایستا) باشد. در این صورت می­توان مسیر بهینه را قبل از حرکت محاسبه کرد. روش­های متعددی برای این حالت از مساله­ی ناوبری ربات ارائه شده ­اند مانند: نمودار ورونی، گراف دیداری، میدان پتانسیل، روش شبکه­ ای و تجزیه سلولی. همچنین روش­های مبتنی بر الگوریتم­های بهینه­سازی نیز برای طرح مسیر بهینه مورد استفاده قرار می­گیرند [۱۳]. به عنوان مثال داویدر^[۱۴] [۱۴] الگوریتم ژنتیکی برای طرح مسیر بهینه ارائه داد. همچنین نیرچو^[۱۵] [۱۵] از تعداد راس­های گراف دیداری برای ساختن الگوریتم ژنتیک استفاده کرد و توانست یک مسیر نزدیک به بهینه را برای این نوع مساله حل کند. در ذیل خلاصه ای از اساس کار سه نمونه از روش­های متداول ذکر شده در بالا توضیح داده می­شوند:
روش گراف دیداری
این روش زمانی استفاده می­ شود که هندسه محیط برای ربات مشخص باشد. ایده اصلی این روش این است که اگر یک مسیر بدون برخورد بین دو نقطه وجود داشته باشد، آنگاه کوتاهترین مسیر بین این دو نقطه تنها در راس­های موانع شکسته می­ شود. گراف دیداری گرافی است که راس­های آن شامل نقطه آغاز، نقطه پایان و راس­های موانع هستند. یال­های گراف دیداری بین راس­هایی وصل می­شوند که نقاط متناظر آنها همدیگر را می­بینند. با داشتن گراف دیداری می توان از روش­های موجود برای پیدا کردن کوتاهترین مسیر بین دو راس در یک گراف و در نتیجه کوتاهترین مسیر ربات استفاده کرد. از معایب این روش زمان اجرای بالای آن است هنگامی که موانع زیاد باشند گراف پیچیده می­ شود و الگوریتم­های مبتنی بر این روش کند عمل می­ کنند [۱۶].
روش تجزیه سلولی
در این روش محیط به صورت شطرنجی به مربعات (سلول­ها) تقسیم می­ شود، که معمولا هر سلول به صورت مربع ساده در نظر گرفته می­ شود. در این حالت هر مربع سه وضعیت دارد: فصای خالی، به طور کامل توسط مانع اشغال شده­است یا قسمتی از فضای آن آزاد و قسمتی از آن توسط مانع اشغال شده­است. یک سلول مرکب شامل فضای آزاد و موانع است و یک سلول پر فقط شامل مانع است. در این روش هدف، یافتن سلول­های آزادی است که نقطه اولیه را به نقطه هدف مرتبط کند. اگر سلولی دارای حالت ترکیبی باشد (شامل فضای آزاد و مانع) دوباره به سلول­های کوچکتر تجزیه می­ شود و سلول­ها برای پیدا کردن دنباله مسیر آزاد، از نقطه آغاز به هدف، جستجو می­شوند [۱۷].
روش میدان پتانسیل
در این روش تابع پتانسیل فضای آزاد به صورت جمع پتانسیل­های جاذب، که ربات را به سمت موقعیت هدف می­رانند، و پتانسیل­های دافع، که آن را از موانع دور می­ کنند، تعریف می­ شود. و در هر تکرار نیرویی مصنوعی که توسط تابع پتانسیل در موقعیت فعلی القا می­ شود به عنوان جهت مناسب حرکت در نظر گرفته می­ شود. از مزیت­های روش پتانسیل، قابلیت تعمیم آن در فضاهای با ابعاد بالاتر است، اما امکان افتادن در مینمم­های محلی و مشکلات تعریف درست موانع از نواقص آن می­باشد. امروزه از این روش در ترکیب روش­های دیگر استفاده می­ شود [۱۶].
رویکرد بالا به پایین در ماژول تصمیم‌­گیری مشخصه مهم معماری سلسله مراتبی است که در آن محدودیت‌های سطح بالا به فرامین سطح پایین شکسته می‌شوند. این معماری می‌تواند اهداف و محدودیت‌های چندگانه را در یک محیط پیچیده جمع کند [۱۱]. با این وجود، در این روش ناوبری ربات، مدل دقیق محیط برای طرح مسیر سراسری کارآمد نیاز است. برای دنبال کردن مسیر طراحی شده بایستی ربات نقشه­ای از محیط تهیه کند و موقعیت خود را نسبت به محیط بداند. به دست آوردن نقشه از محیط و مکان­ یابی ربات مستلزم داشتن اطلاعات کامل و دقیق از محیط می­باشد که همیشه در دسترس نیست یا به دست آوردن آن مشکل است. به علاوه برای انجام محاسبات لازم، قابلیت‌های پردازش و حافظه قابل توجه‌ای مورد نیاز است.همچنین، رویکرد بالا به پایین در تصمیم ­گیری تأخیر ایجاد می‌کند و اگر یکی از ماژول‌ها به درستی کار نکند تمام سیستم مختل می‌شود. بنابراین، این رویکردها در حضور عدم قطعیت در دنیای پویای واقعی مناسب نیستند.
معماری مبتنی بر رفتار
معماری مبتنی بر رفتار توسط بروکس^[۱۶] در سال ۱۹۸۶ [۱۸] مطرح شد تا مشکلات معماری سلسله مراتبی را در محیط‌های پویا و ناشناخته حل کند. این رویکردها فرامین کنترلی را بر اساس اطلاعات حسگری فعلی تولید می‌کنند. برای عمل کردن، ربات مدل محلی محیط را بدون فرایند تصمیم‌گیری به کار می­گیرد. بنابراین، نیار به ساخت مدل کامل و دقیق محیط نمی‌باشد. رویکرد پایین به بالا برای تصمیم‌گیری در معماری مبتنی بر رفتار استفاده می‌شود که در آن محدودیت‌های سطح بالا در فرایند تولید عمل مجتمع می‌شوند. هدایت مبتنی بر رفتار پاسخی سریع در محیط پویا و ناشناخته دارد. شکل(‏۲‑۲) معماری کلی رویکردهای مبتنی بر رفتار را نمایش می‌دهد.
شکل(‏۲‑۲): معماری مبتنی بر رفتار جهت ناوبری ربات [۳]
در لایه اول، ربات اطلاعات حسگری را جمع‌ می­ کند. سپس یک تابع انتقال که رفتار نامیده می‌شود درک مشخصی از ورودی حسگری دریافت می‌کند و آنها را به پاسخ‌های از پیش تعیین شده تبدیل می کند. در نهایت، ربات عملی را بر اساس خروجی رفتارهای فعال اجرا می‌کند. در واقع وظیفه پیچیده­ هدایت ربات به چندین وظیفه سطح پایین ساده‌تر و کوچک‌تر (رفتار) خرد می‌شود، این رویکرد عملکرد کلی سامانه ناوبری را بهبود می‌بخشد. دو معماری پایه مبتنی بر رفتار، شامل معماری رده بندی^[۱۷] [۱۸] و الگوهای حرکتی^[۱۸] [۱۹] می‌باشند.
معماری رده­بندی نخستین بار توسط بروکس در سال ۱۹۸۶ معرفی شد. سامانه مبتنی بر رده­بندی از چندین لایه رفتار تشکیل شده است که در آن هر رفتار می‌تواند اطلاعات حسگری را برای انجام عمل خواسته شده (دوری از موانع، تعقیب دیوار، جستجوی هدف و غیره) دریافت نماید. فرایند به انجام رساندن وظیفه­های ساده­تر، قابلیت پاسخ­گوبی سامانه ناوبری را در محیط‌ پویا و ناشناخته افزایش می‌دهد و از پیچیدگی آن می­کاهد. در معماری رده بندی، ماژول تصمیم‌گیری از معماری حذف می‌شود و تمرکز منحصراً روی ماژول‌های حس‌کردن و عمل کردن می‌باشد. برخلاف معماری سلسله مراتبی، رفتارها کوپلاژ مستقیمی میان ورودی‌های حسگری و عمل­های ربات ایجاد می‌کنند. همانطور که شکل(‏۲‑۳) نشان می‌دهد، در معماری رده­بندی، رفتارها لایه‌بندی می‌شوند. هر رفتار، اطلاعات حسگری مشخصی را دریافت می کند. تلفیق لایه‌های رفتارها منجر به انتخاب مبتنی بر اولویت می‌شود. انتخاب مبتنی بر اولویت، فرایند تصمیم‌گیری در این مورد است که کدام رفتار پیروز ‌شود وقتی چندین رفتار متضاد باهم فعال می‌شوند [۲۰]. بنابراین، ماژول رفتاری با بالاترین درجه فعالیت^[۱۹]، خروجی کلی را تعیین می‌کند.

شکل(‏۲‑۳): معماری رده­بندی جهت ناوبری ربات [۳]

معماری مبتنی بر رفتار دیگر که توسط آرکین^[۲۰] در سال ۱۹۹۸پیشنهاد شد، معماری الگوهای حرکتی می­باشد (شکل(‏۲‑۴)). تئوری الگوهای حرکتی، رفتارهای حرکتی را از نظر کنترل همزمان فعالیت‌های مختلف بسیار توصیف می‌کند. هر رفتار می‌توند خروجی‌ای در فرم یک بردار تولید کند. این خروجی‌ها ترکیب می‌شوند و سپس پاسخ نهایی سامانه با جمع برداری به‌دست می‌آید. برای مثال یک میدان پتانسیل می‌تواند به‌عنوان خروجی هر الگو تعریف شود. حرکت نهایی برداری است که حاصل از انطباق تمام میدان‌ها است. معماری رده­بندی به انتخاب رقابتی رفتارها اختصاص دارد، حال آنکه معماری الگوهای حرکتی بر اساس تلفیق تعاونی رفتارها استوار می‌باشد. معماری الگوهای حرکتی قابلیت استفاده همزمان از خروجی های بیش از یک رفتار را با در نظر گرفتن اثر آنها روی خروجی نهایی فراهم می آورد [۴].

شکل(‏۲‑۴): معماری الگوهای حرکتی جهت ناوبری ربات [۳]

مزایای کلی معماری مبتنی بر رفتار عبارتند از:
قابلیت ساخت سامانه ناوبری ربات با روند افزایشی به صورت لایه روی لایه
عکس العمل سریع به محیط پویا و ناشناخته