پويش محيط ناشناخته و تخصيص كار توسط ربات هاي چندگانه با استفاده از يك معماري دو سطحي و الگوريتم ژنتيك

Multi Robot Exploration and Task Allocation through a Two-layer Architecture and Genetic Algorithm

سيستم ربات‌هاي چندگانه جهت انجام كارهايي كه ماهيت توزيع شده در فضا، زمان و يا عملكرد دارند، بسيار مناسب مي‌باشند. براي مسائلي نيز كه قابليت تفكيك به زيرمسائل مستقل از هم را دارند، استفاده از سيستم ربات‌هاي چندگانه به دليل كاهش زمان تكميل كار به صرفه خواهد بود. به كارگيري چنين سيستم‌هايي مستلزم تخصيص مناسب كارها در بين ربات‌ها است كه از جمله مسائل NP-hard مي‌باشد. در اين مقاله، يك معماري دو سطحي جهت حل مسئله پويش محيط و يافتن كارهاي موجود در آن توسط ربات‌هاي غير همگن ارائه گرديده و پس از تخصيص كار بين ربات‌ها، مسيريابي ربات به سمت كارهاي مورد نظر صورت مي‌پذيرد. در سطح اول كه از رويكرد توزيع شده استفاده شده است، ربات‌ها به صورت غيرمتمركز و با استفاده از الگوريتم Multi SRT به پويش محيط پرداخته و مسيريابي آنها به سمت كارهاي مورد نظر با استفاده از الگوريتم Multi Tangent Bug انجام مي‌گيرد. در سطح دوم، به صورت متمركز و با استفاده از الگوريتم ژنتيك ارائه شده (FGA)، ربات‌ها به كارهاي مورد نظر تخصيص مي‌يابند. انجام هر يك از كارها باعث ايجاد مطلوبيت براي سيستم شده و انجام تمامي كارها هدف غائي سيستم تلقي مي‌شود. در ادامه، نتايج حاصل از شبيه‌سازي مسائل آزماينده مختلف، قابليت اطمينان معماري ارائه شده در سطح اول و همچنين دقت و سرعت جواب‌هاي به دست آمده در سطح دوم را به اثبات رسانده و در پايان جهت اعتبارسنجي الگوريتم ژنتيك ارائه شده نتايج آن با الگوريتم ژنتيك NSGA-II مقايسه شده است.

Multi-robot systems are preferable for tasks that are inherently distributed in space, time, or functionality. For the problems that can be decomposed into independent subproblems, using a multi-robot system offers a potential for reducing the overall task completion time. For effective employment of multi robot systems, it is necessary to properly implement Task Allocation, which is an NP-hard problem. In this paper, a two-layer architecture for exploring and covering an unknown environment by multiple heterogeneous robots is developed. At the first layer of the architecture, the Multi-SRT algorithm is developed for exploration and covering of the environment and the Multi-Tangent-Bug is used for online path planning and obstacle avoidance in a distributed manner. In the second layer, by means of a centralized approach, a Fast Genetic Algorithm (FGA) is proposed for solving the multi-robot task allocation problem. Performing each task enhances the utility of the system, and completing all tasks is the ultimate goal of the system. For evaluating the efficiency of the FGA, a number of scenarios were run and the results were compared to NSGA-II algorithm. Simulation results showed the reliability of the developed architecture at the first layer and the precision and quality of the task allocation at the second layer.