شکرانه خشخاشی مقدم - دانشگاه تربیت مدرس
الیپس مسیحی - دانشگاه تربیت مدرس

مسئله برنامه­ریزی حرکت با موانع جابه جاشونده، (NAMO)3، عبارت از یافتن مسیرهایی بدون تصادم برای روبات است؛ این در حالی است که روبات برای یافتن یک مسیر، می­تواند برخی موانع را جابه­جا کند. NAMOیکمسئله NP-Complete و در زمره مسائلی از مسیریابی حرکت روبات قرار می­گیرد که دارای محیط­های متغیر هستند. در این حوزه یک برنامه بهینه برای روبات می­تواند با توجه به فاکتورهای مختلف هم­چون طول مسیرهای انتقال و جابه­جایی، تعداد اجسام جابه جاشونده، تعداد دفعات جابه­جایی اجسام و زمان تعیین شود. در این مقاله با استفاده از مفاهیمی هم­چون گراف دید نگار4،و عمق نفوذ5، الگوریتم بازگشتی ارائه شده قادر است مسائل مختلف NAMO را در زمان معقولی حل کند. هم چنین به کارگیری الگوریتم پیشنهادی برای حل برخی مسائل موجود در ادبیات، موجب کاهش چشمگیر تعداد اجسام جابه­جا شده و تعداد دفعات جابه­جایی اجسام جابه جاشونده شده است.

مسیریابی حرکت روبات, موانع جابه جاشونده, گراف دیدنگار, عمق نفوذ, جمع مینکوفسکی