روش جستجوی تدریجی جدید برای طراحی مسیر سیستم‌های چندرباتی

یکی از این چالش‌های مساله طراحی مسیر چندرباتی، افزایش ابعاد فضای جستجو به صورت نمایی همراه با افزایش تعداد ربات‌ها در محیط عملیات است. بنابراین، به الگوریتم‌هایی نیاز است که دارای کارایی محاسباتی بوده و بتوانند مسیرهای بهینه و بدون برخورد ربات‌ها را در زمان محدود طراحی کنند. در این مقاله یک الگوریتم طراحی مسیر مرکزی برای هدایت ربات‌ها در محیط عملیات مشترک ارائه شده است. این الگوریتم یک روش جستجوی اکتشافی تدریجی است که در آن الگوریتم ‎d* lite‎ به منظور تطبیق با حالت چندرباتی توسعه داده شده است. هماهنگی در طراحی مسیر برای تمام ربات‌ها بر اساس مفهوم زمان تصرف بوده که در ساختار مدل مفهومی محیط پیاده‌سازی شده است. همچنین، یک تابع مرکزی جهت به‌روزرسانی اطلاعات مدل مفهومی محیط و حرکت تدریجی ربات‌ها توسعه داده شده است. به منظور ارزیابی روش پیشنهادی، دو گروه شبیه سازی های استاتیک و پویا انجام شده است. در دسته اول، تمرکز بر مطالعه اثر پارامترهای الگوریتم است. نتایج نشان می دهد که الگوریتم پیشنهادی قابلیت طراحی مسیر برای 40 ربات در محیطی با 55 درصد فضای آزاد را دارد و نیز رابطه زمان محساباتی و تعداد ربات ها غیر نمایی است. دسته دوم شبیه سازی ها در محیط سه بعدی gazebo انجام شده که به صورت برخط و پویا است. نتایج روش پیشنهادی با روشی بر اساس میدان های پتانسیل مصنوعی برای تعداد 14 ربات مورد مقایسه قرار گرفته است. نتایج نشان می دهد که با افزایش تعداد ربات ها از 9 عدد، زمان انجام عملیات برای روش مبتنی بر میدان پتانسیل افزایش زیادی پیدا کرده و یا غیرممکن می شود.

a new incremental search method for multi-robot path planning

multi-robot path planning problem involves some challenges. one of them is the exponential increase in the size of the search space as a result of increasing the number of robots in the operating environment. therefore, there is a need for algorithms with high computational performance to plan optimal and collision-free paths in a limited time. in this article, a centralized path planning algorithm is presented. the algorithm is a heuristic incremental search, in which the d* lite algorithm has been adapted for the multi-robot case. the concept of occupancy time has been embedded into the environment model to avoid path interference. a centralized function has been designed to update the environment model and robot data. to evaluate the method, two groups of simulations of static and dynamic types were carried out. the static simulations focused on studying the effect of algorithm parameters, and it was shown that the algorithm can plan paths for up to 40 robots in an environment having 55 percent free space. the dynamic simulations were carried out in gazebo, a real-time and dynamic physical simulator. the results were compared to a baseline method based on potential fields. the number of robots was increased to 14, and it was demonstrated that for 9 robots and more, the potential field approach either fails or has a rapid increase in computation time, while the proposed method can find feasible solutions in a limited time.