Multi-agent path planning for a mobile robot in an unknown dynamic environment
Bilinmeyen dinamik bir ortamda mobil bir robot için çok ajanlı yol planlaması
- Tez No: 933690
- Danışmanlar: DOÇ. DR. OĞUZ ATA, DOÇ. DR. DOĞU CAĞDAŞ ATİLLA
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Altınbaş Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 129
Özet
Bu çalışma, çok aracılı sistemler için robot yolu planlama sorununu ele almaktadır. Ajanların çarpışma olmadan aynı anda hareket etmesini sağlama sürecini içerir. Her temsilcinin, tüm temsilciler tarafından paylaşılan bir ortamda ulaşmak için bir hedefi vardır. Bununla birlikte, dinamik ve öngörülemeyen ortamlarda haritada veya hedefte beklenmedik değişiklikler, performanslarda sorunlara veya kişinin hedeflerine ulaşmada tam başarısızlıklara yol açabilir. Sonuç olarak, öncelikli mirasın da bu gibi durumlarda çok önemli olduğu kanıtlandı. Yol planlama ve/veya ani değişikliklere adaptasyondaki verimlilik, öncelikli kalıtım tarafından etkileyici bir şekilde belirlenir. Bu iki zorlukla ilgili olarak, bu araştırma yeni bir Çatışma Tabanlı Arama yaklaşımı sunar ve çok robotlu yol planlaması için en uygun şekilde tasarlanmış yeni bir hiyerarşik arama mekanizması sunar. Doğal olarak, en önemli amaç, çeşitli ortamlarda bir algoritmanın esnekliğini ve uyarlanabilirliğini artırmaktır. Ayrıca etkinliğini üç farklı senaryoda test eder: algoritmanın bilinmeyen sabit ve mobil ortamlarda uygulanmasını göz önünde bulundurarak ilki, verimli yol uzunluğu optimizasyonu ile ortalama 2,3 saniyelik zaman kullanımı ile mükemmel sonuçlar verir. İkinci senaryoyu, bu senaryoda ortalama varış süresinin algoritma tarafından 2,6 saniye olduğu ve yol uzunluğunun optimum kaldığı keskin köşelere ve bilinmeyen engellere sahip karmaşık sahneler izledi. Son senaryo, sabit, mobil ve çok hedefli engellere sahip bir depo ortamında gerçekleştirildi; algoritma, en karmaşık ayarlar altında maksimum 100,4 s süre ile iyi performans gösteriyordu. PRM, RRT, A*, D*, Dijkstra, GA, ACO, PSO, VO ve QL gibi çeşitli yol bulma algoritmaları, çevre, karmaşıklık ve MAPF alanındaki ajan sayısı ile ilgili artıları, eksileri ve sınırlamalarına sahiptir ve önerilen CBS yaklaşımının son derece etkili, verimli ve çok yönlü olduğunu, dolayısıyla çok çeşitli zor ortamlar için uygun olduğunu göstermektedir.
Özet (Çeviri)
This work addresses the problem of robot path planning for multi-agent systems. It involves the process of enabling agents to move around simultaneously without collisions. Each agent has its destination to reach in an environment shared by all agents. However, unexpected changes in either the map or the goal in dynamic and unpredictable environments could lead to problems in performances or complete failures to achieve one's goals. In consequence, priority inheritance also proved to be very important in such cases. Efficiency in path planning and/or adaptation to sudden changes is impressively determined by priority inheritance. Regarding these two challenges, this research introduces a novel Conflict-Based Search approach and presents a new hierarchical search mechanism optimally designed for multi-robot path planning. Naturally, the most important aim is to increase the flexibility and adaptiveness of an algorithm in various environments. It also tests its efficacy in three different scenarios: the first one considering the application of the algorithm in unknown stationary and mobile environments yields excellent results, averaging 2.3 seconds of time usage with efficient path length optimization. The second scenario was followed by complex scenes with sharp corners and unknown obstacles, for which the average arrival time in this scenario was 2.6 seconds by the algorithm, the path length remaining optimal. The final scenario was performed in a warehouse environment with fixed, mobile, and multi-target obstacles; the algorithm was performing well, with a maximum time of 100.4 s under the most complex settings. Various pathfinding algorithms, such as PRM, RRT, A*, D*, Dijkstra, GA, ACO, PSO, VO, and QL, have their respective pros, cons, and limitations concerning the environment, complexity, and the number of agents in the MAPF domain were compared and demonstrate that the proposed CBS approach is highly effective, efficient, and versatile, hence suitable for a wide range of difficult environments.
Benzer Tezler
- Multi – objective trajectory tracking for an autonomous mobile robot in dynamic environments using evolutionary algorithms
Dinamik ortamlarda otonom hareketli bir robot için evrimsel algoritmalar kullanarak çok amaçlı yüzey takibi
MAHYAR TEYMOURNEZHAD
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Kültür ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZGÜR KORAY ŞAHİNGÖZ
- Realization of reactive control for multi purpose mobile agents
Genel amaçlı mobil robotlar için tepkin kontrolün gerçeklenmesi
SELİM YANNİER
Yüksek Lisans
İngilizce
2002
Makine MühendisliğiSabancı ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DR. AHMET ONAT
PROF. DR. ASIF ŞABANOVİÇ
- A social navigation approach for mobile assistant robots
Asistan mobil robotlar için sosyal bir navigasyon yaklaşımı
HASAN KIVRAK
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HATİCE KÖSE
- How cryptographic implementations affect mobile agent systems
Şifreleme gerçekleştirmelerinin gezgin aracı internet sistemlerini nasıl etkilediği
İSMAİL ULUKUŞ
Yüksek Lisans
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiSistem ve Kontrol Mühendisliği Ana Bilim Dalı
PROF. DR. EMİN ANARIM
- Optimizing path planning for reduced congestion using reinforcement learning
Pekiştirmeli öğrenme ile trafik sıkışıklığını azaltmada yol planlamasının optimizasyonu
BERDAN DENİZ BOLAT
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TUNA TUĞCU