Geri Dön

Hybrid generalized multi-agent pathfinding: a hierarchical method using ASP

Çoklu etmenler için çözüm kümesi programlama ile hiyerarşik olarak melez yol bulma

PDF İndir

  1. Tez No: 488367
  2. Yazar: OMID KHORSAND KAZEMY
  3. Danışmanlar: DOÇ. DR. ESRA ERDEM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 80

Özet

Tek bir etmen için yol bulma problemi, bir başlangıç noktasından hedef noktasına gitmek için hiç bir engelle çarpışmayacak bir şekilde takip edeceği bir patika bulmadır. Çoklu etmenler için yol bulma problemi (MAPF) de her etmen için benzer bir patika bulmayı hedeflemektedir; öyle ki, herhangi iki etmen patikalarını takip ederken birbiriyle çarpışmasın. MAPF hesaplama karmaşıklığı açısından zor bir problemdir. Bu tezde, MAPF probleminin robotikteki uygulamalarından esinlenerek daha genel bir problem (GMAPF) üzerinde çalışılmıştır; bu problemde, her etmen gideceği yere varmadan önce bazı yerlere de uğramak isteyebilir. GMAPF problemini çözmek için çözüm kümesi programlama (ASP) kullanılarak ve hesaplanan yolların robotlar tarafından uygulanabilirliği ile ilgili testler entegre edilerek, yeni bir algoritma geliştirilmiştir. Geniş ortamlarda tanımlanmış ve çok sayıda etmen içeren problemlerin çözümlerinin daha verimli bir şekilde hesaplanabilmesi için, melez GMAPF için geliştirilen bu algoritma temel alınarak yeni hiyerarşik ve fırsatçı yöntemler geliştirilmiştir. Tez kapsamında geliştirilen tüm yöntemlerin, otonom depolama sistemleri bağlamında yapılan deneylerle etkinlikleri gösterilmiştir.

Özet (Çeviri)

Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, without colliding with any obstacles. Multi-agent pathfinding (MAPF) also aims to plan such routes for each agent such that no two agents collide with each other. MAPF is an intractable problem, because agents must avoid the collision with each other. We study a generalized version of MAPF (GMAPF) in the context of robotics (i.e., autonomous warehouses), where multiple robots must visit some locations (e.g., to collect some items) on the way to their destinations without colliding with any obstacles in the environment. In this thesis, we introduce a novel method to solve GMAPF problems using the expressive logic-based language of Answer Set Programming (ASP) and the efficient ASP solvers. Moreover, to ensure that the robots follow collision-free trajectories, we introduce an intelligent method for feasibility checks and their integration to our ASP-based approach to GMAPF. To further improve the scalability of our method to solve hybrid GMAPF problems, we introduce a hierarchical method to handle problem instances over large environments. Based on that, we introduce a greedy algorithm handle instances with large number of robots We experimentally evaluate our methods over randomly generated problem instances, to show the scalability of our hierarchical and greedy methods, and usefulness of ASP-based hybrid pathfinding.

Benzer Tezler

  1. Tez No

    342716

    Anlamsal web üzerinde çoklu etmen tabanlı öneri sistemi

    Multi-agent based recommendation system over semantic web

    ZEHRA GÜL ÇABUK

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. OĞUZ DİKENELLİ

  2. Tez No

    166672

    Lojistik sistemlerin yapay sinir ağları ile modellenmesi, gerçeklenmesi ve kontrolü

    Modeling, implementation and control of logistics systems using artificial neural networks

    MURAT ERMİŞ

    Doktora

    Türkçe

    Türkçe

    2005

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

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

    PROF.DR. FÜSUN ÜLENGİL

  3. Tez No

    382319

    ARIMA ve yapay sinir ağları (YSA) kullanılarak hibrit tahmin modeli geliştirilmesi

    Development of a hybrid forecasting model using ARIMA and artificial neural networks(ANN)

    AHMET ADİL ATEŞONĞUN

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    Endüstri ve Endüstri MühendisliğiBaşkent Üniversitesi

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

    YRD. DOÇ. DR. MEHMET GÜLŞEN

  4. Tez No

    656028

    Şebekeye bağlı hibrit yenilenebilir enerji sistemlerinin tasarımı ve optimizasyonu üzerine bir model önerisi ve uygulaması

    A model proposal for design and optimization of grid-connected hybrid renewable energy systems and its application

    OZAN ÇAPRAZ

    Doktora

    Türkçe

    Türkçe

    2020

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

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

    PROF. DR. AŞKINER GÜNGÖR

    PROF. DR. AYSUN SAĞBAŞ

  5. Tez No

    75786

    The Capacitaded lot sizing problem

    Başlık çevirisi yok

    Ş.İLKER BİRBİL

    Yüksek Lisans

    İngilizce

    İngilizce

    1997

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe Üniversitesi

    Sistem Mühendisliği Ana Bilim Dalı

    PROF. DR. LİNET ÖZDAMAR

Geri Dön