توصيفگر ها :
اجتناب از برخورد , طرح‌ريزي حركت , سيستم‌هاي چند ربات , الگوريتم‌هاي توزيع‌شده
چكيده فارسي :
در سال‌هاي اخير، سيستم هاي چند ربات به دليل استفاده گسترده و رو به رشد آنها در زمينه هاي مختلف، مورد استقبال گسترده جامعه تحقيقاتي قرار گرفته‌اند. از جمله، 1- انتقال كالا و تجهيزات در انبارهاي بزرگ، 2- حركات گروهي عامل‌ها در انيميشن و بازي‌هاي رايانه‌اي، 3- حمل و نقل هوشمند درون شهري، 4- نانو ربات‌هاي پزشكي، 5- نمايش‌هاي هوايي در آسمان شب و موارد متعدد ديگر. يك بخش مهم در سيستم‌هاي رباتيك، مديريت حركت عامل‌ها يا اصطلاحاً طرح‌ريزي حركت است. در كاربردهاي جمعي طرح‌ريزي حركت، هدف آن است كه عامل‌ها از يك حالت اوليه به يك حالت نهايي، به نحو مطلوب تغيير مكان دهند و چالش اصلي و مهم در اين بين، اجتناب از برخورد عامل‌ها با يكديگر و با موانع موجود در محيط است. روش‌هاي متنوعي كه در اين حوزه معرفي مي‌شوند همگي قابليت مديريت حركت عامل‌ها از مبدأ به مقصد را دارند و ملاك كارايي عملكرد آنها، زمان همگرايي مسئله و همچنين طول مسيري است كه عامل‌ها براي رسيدن به حالت نهايي طي مي‌كنند.
در اين تحقيق تعدادي از روش‌هاي مهم و كاراي قبلي مورد بررسي قرار مي‌گيرند و در ادامه يك روش اجتناب از برخورد توزيع‌شده در سيستم‌هاي جمعي با نام ASCA معرفي مي‌شود. ASCA يك روش بلادرنگ است و قابليت اجرا در محيط‌هاي دوبعدي و سه‌بعدي با تراكم جمعيتي زياد را دارد. نحوه حركت روش ASCA مبتني بر محاسبات زاويه‌اي هر عامل با توجه به جهت قرارگيري عامل‌هاي همسايه، در طول گام‌هاي زماني حركت بوده و با توجه به نوع محاسبات، از لحاظ بار پردازشي بسيار كم‌هزينه است. همچنين نشان داده مي‌شود كه الگوريتم ASCA يك روش كامل و بدون امكان برخورد است. همچنين نشان داده مي‌شود كه الگوريتم ASCA در محيط‌هايي با تراكم بالاي كوادكوپترها كه موجب ايجاد پديده پايين رانش مي‌شود، قابليت كاركرد مطلوب و بدون نقص را دارد.
در اين تحقيق براي صحت‌سنجي عملكرد الگوريتم ASCA و همچنين مقايسه آن با ديگر روش‌ها جهت مشخص شدن ميزان كارايي، آزمايش‌هاي مختلفي گردآوري و طراحي شده است كه هركدام براي سنجش يكي از جنبه‌هاي عملكردي روش‌هاي مورد ارزيابي، به كار گرفته مي‌شوند. نشان داده مي‌شود كه ASCA در آزمايش‌ها نسبت به دو روش FMP و ORCA، از لحاظ سرعت همگرايي به ترتيب حداقل 7 درصد و حداقل 25 درصد بهبود حاصل كرده است و از لحاظ طول مسيرهاي پيموده شده، قابل رقابت با دو الگوريتم ديگر است. از طرف ديگر، نشان داده مي‌شود كه ASCA به نسبت دو الگوريتم FMP و ORCA قابليت اطمينان و ساختار يافتگي بالاتري دارد كه به تبع آن پيش‌بيني‌پذيرتر از دو روش ديگر است. در نهايت، با به كارگيري اين روش در يك محيط با حضور 8 عدد كوادكوپتر Crazyflie نشان داده مي‌شود كه به صورت كاملاً هوشمند، قابليت اجرا در شرايط حقيقي و خارج از محيط شبيه‌سازي را نيز دارا مي‌باشد.
چكيده انگليسي :
In recent years, multi-robot systems attracted many researchers thanks to their widespread and growing use in various fields such as moving objects in large warehouses using robots, group movement of agents in animations or computer games, intelligent and autonomous public transportation, drug delivery in blood vessels by nanobots, aerial shows and light painting at night, etc. An important part of robotic systems is the motion management of agents or so-called motion planning. The goal of swarm motion planning is to move the robots from their initial state to the target states. The main challenge in this regard is to avoid the collision of agents with each other and with the obstacles in the environment. The various methods introduced in this field all can manage the movement of agents from initial to destination positions, and the criterion for their performance efficiency is the time of convergence and the length of the path that agents take to reach their final state.
In this research, the previous efficient methods are examined and then a method is introduced named ASCA for distributed collision avoidance in multi-robot systems. ASCA is a real-time algorithm for
dense and complex environments in both two- and three- dimensional spaces. ASCA movements are based on angular calculations of each agent according to the position of neighboring agents during the time steps. According to these calculations, ASCA is a low-cost algorithm and also it is shown that this method is complete and collision-free. On the other hand, it is shown that ASCA can solve the downwash effect of quadcopters in dense environments.
In this research, ASCA compares with two other powerful algorithms named FMP and ORCA to determine the efficiency and for this purpose, various benchmarks have been collected and designed that each one measures one performance aspect of the evaluated algorithms. The results show that ASCA is at least 25% faster than ORCA and at least 7% faster than FMP and also more reliable, structured and predictable than both methods. Finally, by using ASCA in an environment with 8 Crazyflie quadcopters, it has been shown that it can be run fully intelligent in real-world areas outside the simulation environments.
