Çok robotlu kapsama ve randevu için dağıtık algoritmalar
Distributed algorithms for multi robot rendezvous and coverage
Yazar: DENİZ ÖZSOYELLER
Danışman: PROF. DR. KAYHAN ERCİYEŞ ; DOÇ. DR. VOLKAN İŞLER
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı
Derece: Doktora, 2015
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Mobil robotikteki gelişmeler, düşük maliyetli, güvenilir robotların karmaşık ortamlarda dolaşmasını ve karmaşık işler gerçekleştirmesini mümkün hale getirmiştir. Bir grup robotla bir işin etkin bir şekilde yürütülebilmesi için etkili robot stratejileri tasarlamak önemlidir. Bu tezde temel bir problem olan, mobil robotlarla randevu arama problemini çalışılmıştır.
Randevu arama problemi bir ortamda birbirlerinden farklı konumlarda bulunan robotların en kısa zamanda nasıl buluşabileceği ile ilgilenir. Arama ve kurtarma bu problemin önemli uygulamalarından biridir. Kurtarıcılar (robotlar) afet ve patlama gibi durumlarda kurbanları veya hayatta kalanları arayabilir. Uydu alıcılarının olmadığı, gücün sınırlı olduğu veya ortamın geometrisinin elverişli olmadığı durumlarda robotların başarılı iletişim kurmak için aralarında görüş hattının sağlanması gerekir. Bu gibi bir durumda robotların iletişim kurmak için birbirlerinin yanında olması gerekir, yani buluşmaya ihtiyaçları vardır. Böyle durumlar için, randevu arama probleminin diğer uygulamaları da robotlar arasında ağ formasyonu, çoklu robot keşif ve haritalamadır. Bu tezde problemin simetrik versiyonu çalışılmıştır. Bu versiyonda, her robot aynı stratejiyi çalıştırır, çünkü önceden buluşup arama sırasında kullanacakları stratejilere karar verme şansları yoktur.
İlk olarak problem doğru üzerinde bulunan, aralarındaki başlangıç uzaklığını bilmeyen aynı özelliklere sahip iki robotla çalışılmış ve simetrik bir randevu arama stratejisi sunulmuştur. Robotların hem senkron olduğu, yani aramaya aynı anda başladıkları hem de asenkron oldukları yani aramaya farklı zamanlarda başladığı durumu düşünülmüştür. İkinci olarak, aynı problem engelli ve engelsiz düzlemsel ortamlarda iki ve ikiden çok robot ile çalışılmıştır. Bu ortamlar için simetrik bir randevu arama stratejisi tasarlanmıştır. Bu kısımda ayrıca engelli bir ortamın bir robot ile keşfi için de bir algoritma sağlanmıştır. Hem doğru hem de düzlemsel ortamlar için tasarlanan simetrik randevu stratejilerinin performası teorik olarak ispatlanmış ve simülasyonlarla ve deneylerle değerlendirilmiştir.
Anahtar Sözcükler: Doğrusal arama problemi, arama problemi, simetrik randevu, robot randevu, robot keşif ve kapsama.

Abstract:
The advancements in mobile robotics have made the low-cost and robust robots to navigate in complex environments and perform complex tasks. To execute a task efficiently with a group of robots, it is significant to design efficient robot strategies. In this thesis, the rendezvous search problem which is a fundamental problem in robotics is studied.
The rendezvous search problem considers how the robots that are located in different positions in an environment can meet as quickly as possible. Search and rescue tasks are one of the important applications of this problem, rescuers (robots) can search for the victims or the survivors who are in dangerous situations such as disasters and explosions. When there are no satellite receivers, the power is limited and the geometry of the environment is inconvenient, the robots should be in the line of sight of each other to communicate successfully. In such situations, robots should be close to each other to communicate, so they need to rendezvous. Other applications of rendezvous search for such situations are network formation and multi robot exploration and mapping. In this thesis, the symmetric version of this problem is studied. In this version, each robot executes the same strategy, because they do not have a chance to meet in advance to decide on the strategies they would perform during the search.
First, the rendezvous search problem is studied on the line for two identical robots that do not know the initial distance to each other and a symmetric rendezvous strategy is presented. Both the cases that is when the robots move synchronously in which they start searching at the same time and when the robots move asynchronously in which they start searching at different times are considered. Second, the same problem is studied in planar environments with and without obstacles with two and multiple robots. A symmetric rendezvous strategy for these environments is studied. In this part, an algorithm for the exploration of an environment with obstacles by a robot is also provided. The performances of the symmetric rendezvous strategies are theoretically analyzed and their performances are also evaluated in simulations and experiments.
Keywords: Linear search problem, rendezvous search, symmetric rendezvous, robot rendezvous, robot exploration and coverage.