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

نوع مقاله: مقاله پژوهشی

نویسندگان

1 کارشناسی ارشد، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس تهران، ایران.

2 دانشیار، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس تهران، ایران.

چکیده

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

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

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

نویسندگان [English]

  • Hassan Youssefi Halvaei 1
  • Ellips Masehian 2
1 Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran.
2 Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran.
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Multiple Robots
  • Environment Covering
  • Online Path Planning
  • Task Allocation
  • Genetic Algorithm