Geri Dön

A probabilistic guidance approach to swarm-to-swarm engagement problem

Sürüler arası angajman problemine olasılıksal güdüm yaklaşımı

PDF İndir

  1. Tez No: 643599
  2. Yazar: SAMET UZUN
  3. Danışmanlar: DOÇ. DR. NAZIM KEMAL ÜRE
  4. Tez Türü: Yüksek Lisans
  5. Konular: Uçak Mühendisliği, Aircraft Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri 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ı: 89

Özet

Sürü davranışı doğada oldukça yaygın bir şekilde gözlemlenebilmektedir. Arılar veya karıncalar gibi hayvan kolonileri bir araya gelirler ve yiyecek toplamak veya tehditlerden kaçınmak gibi toplu davranışlar sergilerler. Bu davranış, bu hayvanların bir çok zorlu görevin üstesinden gelmelerine ve uzun vadeli hayatta kalma şansını artırmasına olanak tanır. Pek çok bilim adamı, sürü davranışlarının bu doğal görüntüsünden ilham almaktadır ve bu tarz davranışları, tasarlanmış çok-ajanlı sürü sistemlerin kontrolüne uyarlamaya çalışmaktadırlar. Birkaç büyük ve karmaşık ajan kullanmak yerine, çok fazla küçük ve basit ajan içeren bir sürü kullanmak, bazı zorlu görevleri tamamlamak için daha verimli ve dayanıklı olabilmektedir. Bu tür sistemleri uygulamak için geliştirilmesi gereken en önemli kısımlardan biri ise sürünün güdüm konusudur. Daha önce sürü güdümü için bir çok yöntem geliştirilmiştir. Bu tez, sürüler arası angajman problemi için olasılıksal bir güdüm yaklaşımı getirmektedir. Bildiğimiz kadarıyla bu çalışma, sürüler arası angajman problemini inceleyip bir çözüm getiren ilk çalışmadır. Fikir, rakip sürünün tüm ajanlarını ortadan kaldırmak için kontrollü (mavi) bir sürüyü rakip (kırmızı) sürüye doğru sürmeye dayanıyor. Burada rakip sürü, savunulan bir üs konumuna karşılık gelen sabit bir dağılıma yakınsamayı hedefliyor. Önceki literatürde önerilen olasılıksal sürü rehberliği yaklaşımları, sürünün durağan bir dağılıma yakınsamayı amaçladığı varsayımı altında çalışırlar. Bu nedenle, bu yöntemler, kontrol edilen sürünün, rakip sürünün tüm ajanlarını ortadan kaldırmak için rakip sürünün zamanla değişen dağılımına yakınsanması gereken sürüden sürüye angajman problemlerine doğrudan uygulanamaz. Sürüler arası angajman, gelecekteki askeri sahnenin kilit yönlerinden biri olma potansiyeline sahiptir. Örneğin, DARPA'nın OFFSET programı, saldırgan sürüler için hızlı taktiklerin geliştirilmesine odaklanmaktadır. Konvansiyonel füze savunma sistemleri, bu tür rakip sürü saldırılarına karşı savunmada maliyet gibi bir çok etmen açısından etkin olmadığından, savunma sürüsü kullanmanın ve sürüden sürüye angajman algoritmalarından yararlanmanın bu tür saldırılara karşı çok daha etkili bir çözüm sağlayabileceğine inanıyoruz. Yapılan önceki çalışmalarda daha önce ortaya çıkan çeşitli sürü güdüm yöntemleri vardır. 10-20'ye kadar ajan içeren sürüler için yararlı olan bir takım deterministik yöntemler geliştirilmiştir lakin yüzlerce ila on binlerce arasında değişen ajan içeren sistemler için hesaplanabilirlik açısından uygun olmamışlardır. Bu ölçeklenebilirlik sorununun üstesinden gelmek için hem ayrık hem de sürekli durum uzayları için yoğunluk temelli deterministik ve olasılıksal güdüm yöntemleri geliştirilmiştir. Sürekli durum uzayı için hem deterministik hem de olasılıksal yoğunluk temelli sürü güdümü yöntemleri geliştirilmiştir. Düzleştirilmiş Parçacık Hidrodinamiğinden (Smoothed Particle Hydrodynamic) esinlenen ve sürü hareketi için itici kuvvetleri kullanan deterministik bir yoğunluk kontrol yöntemi vardır. Ajanların sürüsünü istenen yoğunluk dağılımına düzgün bir şekilde sürmek için bir deterministik hız alanı yöntemi de daha önceden sunulan çalışmalar arasındadır. Sürekli ortamda olasılıksal bir yoğunluk kontrolü kavramı ise altta yatan bir skaler uzayın yerel ölçümlerini baz alan dağınık bir ajan sürüsünü önceden belirlenmiş bir dağılıma yakınsatmak için sunulmuştur. Ayrıca sürünün ayrık bir durum uzayında yönlendirilmesi için bazı olasılık yöntemleri de vardır. Bu olasılıksal yöntemler sürüyü istatistiksel bir topluluk olarak görür ve güdüm problemini istenen sürü yoğunluğu dağılımına yakınlaştırma amacını taşır. Bir Markov zinciri, sürü ajanlarını ayrık bir durum uzayında istenen sürü yoğunluğu dağılımına güdümü için Metropolis-Hastings algoritması kullanılarak tasarlanmıştır. Karşılık gelen Markov zincirinin tasarımı için objektif fonksiyonu ve kısıtların doğrusal matris eşitsizlikleri (linear matrix inequalities) ile modellenmesiyle çeşitli konveks optimizasyon teknikleri de kullanılmıştır. Bu çalışma, yakınsama oranını artırmak için yoğunluk geri bildirimi kullanarak sürü ajanlarının kontrolünü sağlamak için genişletilmiştir. Bu çalışmaları temel alarak Markov zincirinin tasarımında belli noktalarda toplanabilecek en fazla ajan yoğunluğu gibi bazı güvenlik kısıtlamaların da dikkate alındığı çeşitli çalışmalar da mevcuttur. Bu yöntemler homojen Markov zincirine dayanır ve ajanların toplam yer değiştirme miktarlarını dikkate almaz. Daha sonra yapılan bir çalışmada sürü güdümü, ajanların geçiş sayısını en aza indirgemek için optimal bir taşıma problemi olarak da formüle edilmiştir, ancak algoritmanın hesaplama süresi, durum uzayının boyutunun arttırılmasıyla çok hızlı artar, ayrıca algoritmanın performansı, mevcut sürünün dağılımı hakkında oluşan tahmin hatalarıyla hızla düşer. Bir takım geri besleme temelli homojen olmayan Markov zinciri tasarlama yaklaşımları, hesaplama olarak maliyetsiz olacak şekilde ajanların geçiş sayısını en aza indirmek için geliştirilmiştir. Bu yöntemler hesaplama açısından etkili olmalarının yanısıra tahmin hatalarıyla makul sonuçlar verir. Bununla birlikte, belirtilen geri bildirim tabanlı yöntemlerin tümü, küresel güncel dağılım geri bildirimini gerektirir. Küresel güncel dağılımı hesaplamak için tüm bölmeler arasında iletişim kurulmalıdır ve bazı tahmin hataları da meydana gelebilir. Olasılıksal güdüm problemi için sadece yerel bilgi gerektiren alternatif Markov zinciri tasarlama yaklaşımı da geliştirilmiştir. Bu çalışmada ise farklı amaçlar için 3 farklı yöntem sunulmuştur. Birincisi, bir önceki bahsedilen algoritmaya benzer geçişlerin sayısını en aza indirmeye dayanmaktadır. İkinci yaklaşım yakınsama hızını en üst düzeye çıkarmaya dayanır. Üçüncü yöntem ise quorum model olarak adlandırılan bir bölgenin önceden tanımlanmış eşikten fazla doldurulmasını önlemeye yöneliktir. Bu tezde ise sürüler arası angajman problemi için bir formülasyon geliştiriyoruz ve problemi çözmek için etkili algoritmalar öneriyoruz. Önerilen algoritmalar kontrol edilen sürünün rakip sürürnün zamanla değişen dağılımına en kısa zamanda yakınsamasına ya da rakip sürüden savunulan merkez üs konumuna girecek olan rakip ajan sayısının belli oranlar ile sınırlandırılmasına dayanır. Bu amaç doğrultusunda tasarlanan algoritmalar kontrol edilen sürü için bir hedef dağılım önerir. Bu hedef dağılıma yakınsamak içinse literatürde daha önce çalışılan Metropolis-Hastings algoritması, konveks optimizasyon temelli yaklaşım ve bu tezde ortaya konacak olan yerel bilgi tabanlı zamana bağlı homojen olmayan bir Markov zinciri tasarlamaya yönelik bir algoritma kullanılmıştır. Tezde sunulan katkılar genel olarak şu şekildedir: İlk olarak kontrollü ve rakip sürülerin hedeflerini ve birbirlerini yok ettikleri angajman dinamiklerini sunuyoruz. Daha sonra, kontrollü sürü için rakip sürünün zamana göre değişen dağılımını dikkate alıp rakip sürünün o dağılımına yakınsayacağı ve tüm ajanlarını yok edebileceği iki farklı yöntem sunuyoruz. İlk yöntem, kırmızı sürünün zamanla değişen dağılımına en az sürede yakınsamaya dayanır. Kırmızı sürünün tüm ajanları, kırmızı sürünün bazı politika kısıtlamaları altında savunulan üs konuma girilmeden önce ortadan kaldırılabilir. Sunulan algoritmanın kontrol edilen sürü için basit kabuller altında sonlu zaman içerisinde istenilen miktarda yakınsanabilecek bir dağılım üreteceğini de ispat ediyoruz. Diğer yöntem ise kırmızı sürünün savunulan üs bölgesine ulaşmadan önce yok edilen ajan sayısının istenen uygun bir miktarın üzerinde olmasını bir politika kısıtlamasına ihtiyaç olmadan sağlamaktadır. Kırmızı sürünün yok edileceği bölgeye karar verildikten sonra merkez üs bölgesine girecek olan ortalama ajan sayısının belli bir sınırın altında olacağını ispat ediyoruz. Bu yöntemde kırmızı sürüden savunulan üs bölgesine girecek olan ajan sayısını belli bir sınırın altında tutarak kırmızı sürünün ajanların yok edildiği bölge ile merkez üs arasındaki mesafeyi en fazla olacak şekilde ayarlayabiliyoruz. Metropolis-Hastings algoritmasını andıran, yalnızca yerel bilgi gerektiren ve büyük durum uzayları için de uygun olan, zaman açısından homojen olmayan bir Markov zinciri tasarım yöntemi öneriyoruz. Bu yöntem koveks optimizasyon algoritmasına göre büyük durum uzayları için hesaplama açısından büyük avantaj sağlarken Metropolis-Hastings algoritmasına göre de empirik olarak yapılan gözlemlere göre daha yüksek bir yakınsama hızı sağlamaktadır. Ayrıca homojen Markov zinciri tasarlanan algoritmalara göre ajanların toplam yer değiştirme sayıları çok daha düşük olmakta, bu da gerçek sistemlerde büyük enerji tasarrufları sağlamaktadır. Yakınsanması isenen hedef dağılımın sıfır değerine sahip durumları için yeni bir yoğunluk difüzyon algoritması öneriyoruz. Bu yöntem, hem yakınsama hızını hem de hesaplama süresini iyileştirmek için diğer Markov zinciri tasarlama yöntemleri ile birlikte kullanılabilmekte ve sürüler arası angajman problemimi için önemli avantajlar sağlayabilmektedir. Önerilen tüm Markov matris sentez yöntemleri, ancak istenen dağılımın sıfır olmayan tüm durumları kendi aralarında güçlü bir şekilde bağlıysa yani sadece sıfır olmayan durumları kullanaarak birbirleri arasında geçiş yapılabiliyorsa yakınsama garanti eder. Kontrol edilen sürü içinse rakip sürünün dağılımı açısından bu tarz bir kabul yapmak her zaman mümkün değildir. Dolayısıyla yakınsanmak istenen dağılımın sıfır olmayan tüm durumlarının kendi aralarında güçlü bir şekilde bağlı olmadığı durumlarda uygulanabilecek olan bir algoritma sunulmuştur. Bu algoritma kontrol edilen sürürnün bölünerek hedef dağılımınının bağlı olamayan her parçasına ayrı ayrı yakınsayarak global bir yakınsama elde etmesine yöneliktir.

Özet (Çeviri)

This thesis introduces a probabilistic guidance approach for the swarm-to-swarm engagement problem. The idea is based on driving the controlled swarm towards an adversary swarm, where the adversary swarm aims to converge to a stationary distribution that corresponds to a defended base location. The probabilistic approach is based on designing a Markov chain for the distribution of the swarm to converge a stationary distribution. This approach is decentralized, so each agent can propagate its position independently of other agents. Our main contribution is the formulation of the swarm-to-swarm engagement as an optimization problem where the population of each swarm decays with each engagement and determining a desired distribution for the controlled swarm to converge time-varying distribution and eliminate agents of the adversary swarm until adversary swarm enters the defended base location. We propose a novel time-inhomogeneous Markov chain method, which resembles the Metropolis-Hastings algorithm in some aspects. This algorithm is local-information based, and designing a Markov chain is feasible for large state-spaces. In the time-inhomogeneous Markov chain method, unlike some homogeneous Markov chain methods such as Metropolis-Hastings algorithm or convex optimization based linear matrix inequality approach, the number of transitions of the agents decreases as convergence increases. We also propose a novel density diffusion based method to design a Markov chain for the zero states of the desired distribution. This method can be used in conjunction with other proposed Markov chain designing methods to improve both the convergence rate and the computation time of the engagement solution. All proposed Markov chain designing methods guarantee convergence only if all non-zero states of the desired distribution are strongly connected amongst themselves which means that transition between any two non-zero states is possible only using other non-zero states. However, non-zero states of the desired distribution may not be strongly connected eventually for the blue swarm since the distribution of the red swarm cannot be controlled. We also propose a strategy for these situations to converge each strongly connected part of the desired distributions separately to converge to the global desired distribution. We demonstrate the validity of all proposed approaches on several swarm engagement scenarios.

Benzer Tezler

  1. Tez No

    692422

    Hybridization of probabilistic graphical models and metaheuristics for handling dynamism and uncertainty

    Değişimin ve belirsizliğin ele alınması için olasılıksal çizgesel biçelerin ve sezgi-üstlerinin melezleştirilmesi

    GÖNÜL ULUDAĞ

    Doktora

    İngilizce

    İngilizce

    2021

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE ŞİMA UYAR

  2. Tez No

    811408

    A retinal vasculature tracking system guided by a deep architecture

    Derin Bir Mimari İle Yönlendirilmiş Retina Damar Takip Sistemi

    FATMATÜLZEHRA USLU

    Doktora

    İngilizce

    İngilizce

    2017

    BiyomühendislikImperial College London

    Biyomühendislik Ana Bilim Dalı

    DOÇ. DR. ANİL ANTHONY BHARATH

  3. Tez No

    387376

    Case-based mobile manipulation

    Durum tabanlı hareketli manipülasyon

    TEKİN ALP MERİÇLİ

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. HÜSEYİN LEVENT AKIN

  4. Tez No

    418978

    Flight deck centered cost efficient 4D trajectory planning

    Kokpit otomasyonu tabanlı 4D rota planlaması

    MEVLÜT UZUN

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Havacılık Mühendisliğiİstanbul Teknik Üniversitesi

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

    PROF. DR. GÖKHAN İNALHAN

  5. Tez No

    716468

    Fen bilimleri öğretmenlerinin mühendislik tasarım süreçlerini içeren ders planlarını oluşturmada ve değerlendirmede kullandıkları ölçütlerin belirlenmesi

    Determining the criteria used by science teachers in creating and evaluating lesson plans involving engineering design process

    ŞÜKRAN ÖZEN GÖKTAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Eğitim ve ÖğretimEge Üniversitesi

    Fen ve Matematik Alanlar Eğitimi Ana Bilim Dalı

    PROF. DR. HÜLYA YILMAZ

Geri Dön