Geri Dön

Multi agent planning under uncertainty using deep Q-networks

Derin Q-ağları kullanımı ile belirsizlik altında çoklu ajan planlaması

PDF İndir

  1. Tez No: 863741
  2. Yazar: FARABİ AHMED TARHAN
  3. Danışmanlar: DOÇ. DR. NAZIM KEMAL ÜRE
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Uçak ve Uzay Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Uçak ve Uzay Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 104

Özet

Ticari insansız hava araçlarının popülaritesi, son mil teslimatı için uygunlukları nedeniyle e-ticaret endüstrisinden büyük ilgi görmüştür. Ancak, birden fazla hava aracını kısıtlamalar ve belirsizlikler içinde teslimat için etkin bir şekilde organize etmek hala bir sorundur. Planlamanın ana zorluğu ölçeklenebilirliktir, çünkü planlama alanı, ajan sayısına exponansiyel olarak büyür ve büyük ölçekli ayarlar için insan düzeyindeki gözetmenlerin problemin yapılandırılmasına izin vermek verimli değildir. Karar verme problemlerini çözmede Derin Q-Ağlarına dayalı algoritmalar beklenmedik bir başarı elde etti. Bu algoritmaların çoklu ajan problemlerine genişletilmesi ölçeklenebilirlik sorunları nedeniyle sınırlıdır. Bu çalışma, problem karmaşıklığını düşürmek için durum ayrıştırmalarını, keşif karmaşıklığıyla başa çıkmak için Müfredat Öğrenimini ve kombinatoryal çözüm alanında etkin paket-hava aracı eşleştirmesi aramak için Genetik Algoritmaları kullanarak Derin Q-Ağlarının çoklu hava araçları ile teslimat problemlerindeki performansını iyileştiren bir yaklaşım önermektedir. Önerilen yöntemin performansı, $10$ ajan ve yaklaşık $10^{77}$ durum-aksiyon çiftine sahip çoklu ajanlı hava aracı ile teslimat problemi üzerinde gösterilmiştir. Önerilen yöntemin üstünlüğünü göstermek için karşılaştırmalı simülasyon sonuçları sağlanmıştır. Önerilen Genetik-Algoritma destekli çoklu ajanlı Derin Destekli Öğrenme, ölçeklenebilirlik ve yakınsak davranış açısından diğerlerini geride bırakmıştır. Kooperatif teslimat ekibinin her bir üyesi, yetersiz araç modelleri, çevre dinamikleri, bileşen arızaları vb. nedenleriyle belirsizliklerle dolu ardışık dinamiklere sahip bir ajan tarafından simüle edilir. Bu tür çoklu ajan planlama problemleri, Markov Karar Süreçlerinin (MDP) çoklu ajan varyantları olarak formüle edilebilir. Bu bağlamda bir MDP'yi çözmenin ana zorluğu ölçeklenebilirliktir, çünkü planlama alanı ajan sayısına göre üssel olarak büyür ve bu kadar büyük ölçekli ayarlar için insan düzeyindeki gözetmenlerin probleme yapı kazandırması verimli değildir. Son gelişmelerle, Derin Q-Ağları (DQN) gibi modern yapay zeka yöntemleri, Derin Sinir Ağlarının (DNN) temsil yeteneğini Pekiştirmeli Öğrenme (RL) ile birleştirerek, dinamik bir ortamdaki ajanların gelecekteki toplam ödülleri maksimize etmek için nasıl hareket etmeleri gerektiğini hesaplamak için kullanılır. DQN ve varyantları tekli ajan problemleriyle başa çıkarken umut verici sonuçlar göstermiş olsa da, büyük durum uzaylarını barındıran çoklu ajan problemleri için bu sonuçların genişletilmesi hala açık bir araştırma alanıdır. Bu tez çalışması, durumların ayrıştırılmasını, bir düzeltme ağı öğrenilmesini ve öncelikli deneyim tekrarını ve Müfredat Öğrenimi tekniklerini kullanarak DQN'nin çoklu ajan planlama problemleri üzerindeki performansını iyileştiren bir yaklaşım önermektedir. Önerilen yöntemin performansı, geleneksel DQN tekniklerinin birçok ajan içinde hızla çözümsüz hale geldiği büyük ölçekli bir drone teslimat problemi üzerinde gösterilmiştir. Tez kapsamında, DQN ve Derin Düzeltme gibi Takviyeli Öğrenme tekniklerinin çoklu ajan senaryosunun yüksek boyutluluğuyla, özellikle birçok drone ve paketi hızla koordine etmede zorluklarla mücadele ettiğini ortaya koyar. Bunu hafifletmek için, iki aşamalı bir strateji tanıtılmıştır. İlk aşama, problemi basitleştiren, drone ile paket eşleştirmesini etkin bir şekilde yapmak için bir Genetik Algoritma (GA) kullanır. Bunu takiben, sofistike bir tekli ajan modeli, GA'nın görev atadığı drone teslimatında etkili karar verme için DQN, Önceliklendirilmiş Deneyim Tekrarı ve Müfredat Öğrenimini kullanır. Bu yaklaşım, hesaplama verimliliğini artırır ve karmaşık teslimat operasyonlarını yönetmede çoklu ajan sistemlerinin yeteneklerini sergiler. DQN'nin daha büyük ayarlarında sınırlılıklarını ve no-fly bölgeleri ve yakıt sınırları gibi kısıtlamalarla senaryoları yönetmede derin düzeltme algoritmaları gibi ileri yöntemlerin etkinliğini vurgulayan bu çalışma farklı stratejileri karşılaştırır. Sonuçlar, modelin belirsiz ortamlarda öğrenme ve uyum sağlama kapasitesini ve GA aracılığıyla paket dağıtımı ile problem karmaşıklığını azaltmanın etkinliğini gösterir. Drone teslimat senaryolarındaki çeşitli çoklu ajan yapılandırmalarında hesaplama süreleri de incelenmiştir, ajan ölçeklenebilirliği ve verimliliğinin karmaşık dinamiklerini vurgulamaktadır. Çoklu ajan sistemlerinin dinamik alanında, çoklu ajan drone teslimat zorlukları için özel olarak hazırlanmış kapsamlı bir simülasyon ortamı da sunulmuştur. Yakalanan anlık görüntüler aracılığıyla, 10 $\times$ 10 ızgarada yapılan simülasyon sonuçları önerilen stratejilerin sinerjisini göstermiştir. 25 km'yi aşan mesafelere yük taşıma kapasitesine sahip modern kamuoyuna açık ticari teslimat dronlarının yetenekleri ışığında, modelimiz önemli pratik bir öneme sahip oluyor. Örneğin, Londra'nın kentsel düzenini dikkate alındığında, Enfield'in kuzey bölgesi ile Croydon'un güney bölgesi arasındaki ortalama 32 km mesafe, bu dronların etkili bir şekilde çalışabileceği operasyonel yarıçapı destekler. Bu tür mesafeleri kapsama olanağı, dronların operasyonel dayanıklılığını artıran şarj istasyonlarının stratejik yerleştirilmesiyle daha da desteklenmektedir. Bu bağlam, modelimizin pratikliğini sadece vurgulamakla kalmaz, aynı zamanda gerçek dünya kentsel teslimat sistemlerinin lojistik talepleri ve coğrafi zorluklarıyla da yakından uyum sağlar. Drone ile teslimat simülasyonu, uçuşa yasak bölgeler, sınırlı yakıt ve yerleştirme senaryosu gibi karmaşık ayarlar sonucunda, GA aracılığıyla paket dağıtımı kullanan önerilen yöntemin, görevi çözmek için $10$ ajanı dakikalar içerisinde etkili bir şekilde basitleştirebileceğini göstermiştir. Azaltılmış problem daha sonra Müfredat Öğrenimi ve Önceliklendirilmiş Deneyim Tekrarı ile desteklenen DQN çıkarım modelleri tarafından milisaniyeler içinde gerçekleştirildi. İki katmanlı önerilen yöntem, çevrenin eylemleri değiştirebileceği belirsiz bir ortamda, alan bilgisi girişine ihtiyaç duymadan teslimat probleminin dinamiklerini öğrendi. Çeşitli zaman adımlarında gerçekleştirilirken alınan anlık görüntüler aracılığıyla da gösterildiği üzere, Genetik Algoritma tarafından gerçekleştirilen paket dağıtımı bileşeni sayesinde, Müfredat Öğrenimi ve Önceliklendirilmiş Deneyim Tekrarı çerçevesi ile önerilen temel DQN modeli, kabul edilebilir bir zaman çerçevesi ve hesaplama kaynakları içinde diğer keşfedilen çözümlerle mümkün olmayan $10$ ajanı ölçeklendirebilir. Önerilen yaklaşım, drone sistemleriyle çoklu ajan teslimatında önemli ilerlemeler gösterdi, ancak çözümümüzün özellikle drone güvenilirliğine yönelik aşırı çevresel koşullar, dinamik paket dağıtımı ve engel ve çarpışma önleme gibi daha karmaşık kısıtlamaları ele alırken sınırlamaları var. Çerçevenin belirli belirsizliklere karşı dayanıklılığı, mekanik arızalar veya operasyonel kesintiler içeren senaryolarda yetersiz kalıyor. Ayrıca, dronların bakım ve onarım lojistiğini dahil etme ihtiyacı, yanı sıra daha karmaşık operasyonel zorlukları araştırmanın önemini vurguluyor. Bu odak alanları, drone teslimat teknolojilerini gerçek dünya uygulamalarının karmaşıklıklarını ele alacak şekilde ilerletmek için hayati öneme sahiptir, böylece kentsel ortamlarda ölçeklenebilirliklerini, verimliliklerini ve güvenilirliklerini artırırlar. Bu çalışma; Derin Q-Ağları, Derin Düzeltme ve Genetik Algoritma gibi algoritmaları analiz ederek çoklu ajanlı drone ile teslimat sistemlerinin bir keşfini sunar. Öğrenme performansındaki farklılıkları vurgulayarak, Müfredat Öğrenimi ve Önceliklendirilmiş Deneyim Tekrarı'nın geleneksel Derin Q-Ağları üzerindeki avantajlarını not eder. Hesaplama zamanı analizi, mevcut yaklaşımların sınırlamalarını ve pratik kentsel teslimat senaryoları için kritik olan gerçek zamanlı karar verme için etkin algoritmaların gerekliliğini vurgular. Ticari dronların ve şarj istasyonları gibi altyapının kapasitelerini dikkate alarak, gerektiğinde genişletilebilen 10 $\times$ 10 bir alanda, metropolitan alanların lojistik gerçekliklerini yansıtarak, modelin kentsel bağlamlardaki ölçeklenebilirliğini ve pratik uygulanabilirliğini sergiler. Mümkün olan çoklu ajan uygulamalarının belirli bir alt kümesini araştırır ve önerilen karar verme çerçevesi, daha karmaşık ayarlar için umut verici yöntemler sunar. Eylemlerdeki belirsizlikler ve yakıt dağıtımı tarafından tanıtılan karmaşıklıklar, çoklu ajan drone teslimatı problemi içindeki gerçek dünya zorluklarını ele alırken yakıt odaklı stratejilerin ve optimizasyon algoritmalarının önemini vurgular. Gelecek çalışmalarda, sürekli durum ve eylem uzaylarının olduğu bir probleme, yeniden yakıt ikmali yapılabilen ve uçuşa yasak bölgelerin dinamik olabileceği ve ajanların operasyon sırasında bir miktar yakıtı ortaklaşa paylaşabileceği metodolojilerin uygulanması gerekliliğine dikkat çekmektedir.

Özet (Çeviri)

The extensive popularity of commercial unmanned aerial vehicles has drawn great attention from the e-commerce industry due to their suitability for last-mile delivery. However, the organization of multiple aerial vehicles efficiently to deliver the given set of goods within the existence of no-fly zones, numerous warehouses, limited fuel, and uncertainties are still a problem for traditional algorithms. The main challenge of planning is scalability, since the planning space grows exponentially with respect to the number of agents, and it is not efficient to let human-level supervisors structure the problem for such large-scale settings. With the recent advancements in deep reinforcement learning, algorithms such as Deep Q Networks (DQN), had unprecedented success in solving single-agent decision-making problems. Extension of these algorithms to multi-agent problems such as multi-drone delivery is very limited due to scalability issues. This work proposes an approach that improves the performance of DQN on multi-agent drone delivery problems by utilizing state decompositions for lowering the problem complexity, curriculum learning for handling the exploration complexity of delivery environments, and genetic algorithms (GA) for searching efficient packet-drone matching across the combinatorial solution space. The performance of the proposed method is shown in a multi-agent delivery by drone problem that has $10$ agents and $\approx10^{77}$ state-action pairs. Comparative simulation results are provided to demonstrate the merit of the proposed method. Compared with the conventional DQN schemes, and recently developed utility decomposition techniques, the proposed genetic algorithm-aided multi-agent DRL outperformed the rest in terms of scalability and convergent behavior. The prior techniques become intractable quickly at a large number of agents within the context of delivery by drone problem. The basic DQN algorithm fails to find a solution for three agents in a 10x10 drone delivery scenario within a reasonable number of steps, but the deep correction method successfully converges after approximately 1 million Bellman updates. Furthermore, applying the deep correction method increases the learning capacity to five agents and converges around 35 million Bellman updates. However, using this method does not lead to convergence with ten agents in a manageable way. With powerful computing resources, it becomes clear that while single-agent models set an initial computational standard, increasing the number of agents introduces complexity, as seen through immediate convergence difficulties in a three-agent DQN setup. Although there is promise with three- and five-agent configurations using Deep Correction, the model with ten agents exceeds the threshold for convergence within 24 hours, emphasizing the delicate balance between agent quantity and computational feasibility. The utilization of drone delivery simulation presents intricate challenges, including restricted airspace, fuel limitations, and the pick-and-place scenario. The study demonstrates that employing a method involving packet distribution through genetic algorithms effectively minimizes the complexity in resolving tasks for 10 agents within 5.74 minutes. Subsequently, the reduced problem is handled by deep Q-network inference models with Curriculum Learning and Prioritized Experience Replay, achieving execution times measured in milliseconds. This two-fold approach skillfully learns the dynamic nature of delivery problems without requiring prior domain knowledge input amid uncertain environmental conditions prone to altering actions. Furthermore, visual evidence at various time steps during execution illustrates how integrating GA-based packet distribution empowers the proposed base DQN model with Curriculum Learning and PER framework to tackle scenarios involving 10 agents – an accomplishment deemed unattainable by other explored solutions within reasonable time frames and computational resources. In conclusion, the combination of deep reinforcement learning and genetic algorithms provides a promising approach for efficient and effective delivery with multi-agent drones under uncertainty.

Benzer Tezler

  1. Tez No

    657666

    A social navigation approach for mobile assistant robots

    Asistan mobil robotlar için sosyal bir navigasyon yaklaşımı

    HASAN KIVRAK

    Doktora

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HATİCE KÖSE

  2. Tez No

    270612

    Multi-agent approach for the scheduling of manufacturing systems

    Üretim sistemlerinin çizelgelenmesi için çoklu ajan yaklaşımı

    CENK ŞAHİN

    Doktora

    İngilizce

    İngilizce

    2010

    Endüstri ve Endüstri MühendisliğiÇukurova Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. RIZVAN EROL

  3. Tez No

    540699

    Development of an integrated multi agent risk management platform for flood disaster management

    Sel afet yönetimi için çok aracılı bütünleşik bir risk paylaşım platformu geliştirilmesi

    KERİM KOÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    İnşaat MühendisliğiYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ZEYNEP IŞIK

  4. Tez No

    284135

    Modeling and solving truck-load consolidation problems by using multi-agent technology

    Yük birleştirme problemlerinin etmen teknolojisi kullanılarak modellenmesi ve çözülmesi

    VAHİT KAPLANOĞLU

    Doktora

    İngilizce

    İngilizce

    2011

    Endüstri ve Endüstri MühendisliğiGaziantep Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ADİL BAYKASOĞLU

  5. Tez No

    776455

    Scalable planning and learning framework development for swarm-to-swarm engagement problems with reinforcement learning

    Pekiştirmeli öğrenme ile sürüden sürüye angajman problemleri için ölçeklenebilir planlama ve öğrenme sistemi geliştirilmesi

    UMUT DEMİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Savunma ve Savunma Teknolojileriİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NAZIM KEMAL ÜRE

Geri Dön