برنامه ریزی حرکت چند روباتی با حرکات همزمان بر روی گراف

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