بخشی از مقاله
چکیده
مسیریابی یکی از مهمترین مسائل در سیستمهاي ربات متحرك است که کاربردهاي متعددي در زمینه هوشمصنوعی، حرکت رباتها، واقعیت مجازي و شبیهسازي رفتار عامل دارد. مسئله مسیریابی، یافتن یک مسیر عاري از مانع براي یک ربات خودمختار مابین دو نقطه مشخص شده در محیط است. روشهاي متعددي با به کارگیري آتوماتاي سلولی به منظور مسیریابی بلادرنگ رباتها معرفی شدهاند که مشکل عمده این روشها عدم توانایی در عبور از مانع مقعر است. در روشهاي دیگر سعی در رفع این مشکل شد اما بازدهی این روشها نیز پایین بود یا در شرایط خاص رباتها قادر به ادامه مسیر نبودند. در این مقاله روشی براي مسیریابی رباتهاي سیار براي عبور از موانع مقعر با استفاده از آتوماتاي یادگیر سلولی ارائه گردیده است. نتایج بدست آمده از شبیهسازيهاي انجام شده با استفاده از روش جدید، توانایی عبور ربات از مانع مقعر با بازدهی بالاتر نسبت به روشهاي پیشین را نشان داده است.
واژههاي کلیدي
مسیریابی، مسیریابی بلادرنگ، عامل هوشمند، آتوماتاي سلولی، آتوماتاي یادگیر سلولی.
١- مقدمه
در چند سال اخیر ربات هاي متحرك بـه دلیـل کـاربرد آن هـا بـراي طیـف وسیعی از وظایف در صنعت، کارهاي نیروي انسانی و غیره، یک موضوع مهم براي تحقیق و توسعه بودهاند. مسیریابی یکی از مهمترین مسائل در سیستم رباتهاي متحرك است. مسئله مسیریابی به طور معمـول عبـارت از یـافتن یک مسیر بهینه براي رسیدن به یک نقطه مشخص شـده در فضـاي کـاري ربات است.
مانعهایی که در مسیر حرکت ربات یافت می شوند میتواننـد ایسـتا یـا پویا باشند. در حالت ایستا تمام اطلاعات مربوط به موقعیت مانعهـا از قبـل مشخص است، اما در حالت پویا اطلاعات محدودي در دسـترس اسـت و یـا هیچ اطلاعاتی در دسترس نیست.
روشهاي ارائه شده براي مسیریابی در حالت ایستا را مـیتـوان در سـه دسته کلـی دسـته بنـدي نمـود]٤-٣:[ تجزیـه سـلولی، نقشـه راه و میـدان پتانسیل . در روشهاي تجزیه سلولی، فضاي کـاري بـه صـورت شـبکهاي از سلولها تقسیمبندي میشود و سپس با اتصال سلولهاي مجاور یک گـراف
اتصال ساخته می شود. با جستجو در این گراف، مسیري از مبـدا بـه مقصـد پیدا میشود. روشهاي نقشه راه، فضاهاي آزاد متصل به هم فضاي کاري را به صورت شبکه یک بعدي از راههاي استاندارد مدل میکنند که مسیر ربات باید درون این شبکه جستجو شود. در روشهاي میدان پتانسیل، ربـات بـه عنوان یک نقطه در فضـاي حـرکتش در نظـر گرفتـه مـیشـود کـه مسـیر حرکتش تحت تاثیر پتانسیل هاي مصنوعی که توسط مقصد و مانعها ایجـاد میشوند، است. مقصد، پتانسیل جذب کننده و مانع ها پتانسیل دفع کننـده ایجاد میکنند. تمام این روشها نیازمند داشتن اطلاعـات کامـل از فضـاي کاري هستند و این امر مستلزم انجام مسیریابی مسیر بهینـه در زمـان غیـر بلادرنگ و با صرف هزینه محاسباتی زیاد است.
اما در حالت پویا این روش هـا قابـل اسـتفاده نیسـتند بـه خصـوص در مواردي که هیچ اطلاعاتی از موقعیـت مـانع هـا در دسـترس نیسـت. بـراي مسیریابی در این حالت روش هایی بـه صـورت بلادرنـگ ارائـه شـدهانـد. از کارهاي انجام شده در این زمینه میتوان به کـار انجـام شـده توسـط آقـاي بهرینگ و همکاران]٥[ اشاره نمـود. نویسـندگان از آتوماتـاي سـلولی بـراي
مسیریابی مسیر بهینه به صورت بلادرنگ استفاده نمودنـد. همچنـین آقـاي عادل اکبريمجد و کارولوکاس نیز از آتوماتاي سلولی براي مسیریابی مسـیر بهینه استفاده کردند]٩-٦.[ روشهاي ارائه شده قابلیت عبـور از مـانعهـاي مقعر را دارا نبودند. در ادامه آقاي عادل اکبريمجد]٢[ یک روش مسیریابی براي رباتهاي متحرك همکار در محیط هاي پویا براساس آتوماتاي سـلولی ارائه نمود. این روش به منظور عبور از مانعهاي مقعر توسط تکنیک کلـونی مورچهها1 بهبود داده شده است.
مشکل عدم توانایی عبور از مانعهاي مقعر ناشی از عـدم وجـود حافظـه براي یـادآوري حرکـت هـاي قبلـی و محـدودیت قـوانین آتوماتـاي سـلولی میباشد. در روشهاي اولیه ارائه شده ربات با رسیدن به مانع افقی به سمت چپ یا راست حرکت نموده و در صـورت برخـورد بـا مـانع عمـودي مسـیر حرکت خود را 180 درجه تغییر میدهد]١٠.[ با اسـتفاده از ایـن مکـانیزم ربات در مانع مقعر شکل در تله افتاده و توانایی خارج شدن از آن را نـدارد. در مکانیزم دیگري که به منظور بهبود روش قبـل ارائـه شـده اسـت، ربـات هنگام برخورد با مانع عمودي مسیر حرکت خود را 90 درجه تغییر میدهد. اما این روش نیز داراي دو عیب است. ممکن است مانع واقعا مقعـر نبـوده و امکان عبور از آن با تغییر مسیر حرکت با زاویه 180 درجه امکانپذیر باشد و از اینرو استفاده از زاویه 90 درجه باعث افزایش تعداد گامهاي ربـات شـود. عیب دیگر هنگام مواجهه با مانعهایی است که به دیوارههـاي فضـاي کـاري چسبیده باشند . در هنگام مواجه شدن با چنین مانعهایی و اسـتفاده از ایـن روش، ربات در گوشه هاي بالاي فضاي کـاري در تلـه گیـر افتـاده و امکـان حرکت ندارد. امکان اصلاح قوانین آتوماتاي سلولی بـراي رفـع ایـن معایـب وجود دارد اما این اصلاحات باعـث افـزایش بـیش از انـدازه جـدول قـوانین میشود. در تحقیق]١[ سعی در حل این عیبهاي ذکر شـده بـا اسـتفادهي همزمان از آتوماتاي سلولی و آتوماتاي یادگیر شـده اسـت. در ایـن تحقیـق همانند روشهاي قبل از آتوماتاي سلولی براي عبور از مانعها و از آتوماتـاي یادگیر براي انتخاب راه حل مناسب (چرخش 180 درجه یا 90 درجـه) بـه منظور عبور از مانع مقعر شکل استفاده شـده اسـت. عیـب ایـن روش عـدم همکاري بین رباتهاي مستقل یا اجراهاي متعـدد در یـک محـیط یکسـان است بدین معنی که عبور از یک مانع مقعر شکل بدون توجه بـه عبورهـاي انجام شده قبلی از آن مانع صورت میپذیرد.
