---

  - به موازات توسعه نسل روبات های هوشمند و گسترش کاربرد آنها در صنایع مختلف، حوزه برنامه­ریزی حرکت روبات­ها که زیر شاخه مهمی از علوم کامپیوتر و مهندسی کنترل می باشد بیش از پیش اهمیت و گسترش یافته است. در این حوزه اغلب به مسائل پرهیز از موانع یا الگوریتم های بهینه­سازی مسیرهای حرکت روبات پرداخته می شود. در این مقاله روشی جدید برای حل مسئله برنامه­ریزی حرکت چند روبات در شرایطی که روبات­ها مجاز به حرکت یا توقف بر روی گره­های یک گراف همبند و مسطح هستند ارائه شده است. همچنین، شرایط دیگری مانند ویژگی­های گراف مسیر از لحاظ طول و ظرفیت یال­ها و امکان حرکت همزمان روبات­ها مد نظر قرار گرفته­اند. چالش اساسی مسائل برنامه ریزی حرکت چند روباتی، وقوع حالات قفل­شدگی (تمایل به اشغال یک مکان واحد در زمان واحد) می باشد که همین امر آنرا در دسته مسائل سخت (NP-complete) قرار داده است. روش ارائه شده ترکیبی ابتکاری از رویکردهای برنامه ریزی حرکت متمرکز و غیرمتمرکز است و بدین جهت از ویژگی­های مثبت هر دو رویکرد بهره­مند است. جهت سنجش کیفیت جواب­های تولید شده از معیارهای کمینه سازی زمان حل و تعداد حرکات لازم به طور توأم استفاده شده است. الگوریتم توسعه داده شده دارای پیچیدگی زمانی چندجمله­ای بوده و به­وسیله نرم­افزار MATLAB شبیه سازی شده است. نتایج حل مثال­های متعدد با اندازه­ها و پیچیدگی­های مختلف نشان دادند که تحت روش ارائه شده، تعداد کل حرکات لازم جهت رفع قفل شدگی­ها تفاوت کمی با حداقل تعداد ممکن حرکات بدون رفع قفل شدگی ها دارد.

---