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
- Tez No: 488367
- Danışmanlar: DOÇ. DR. ESRA ERDEM
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- Balancing mixed adversarial perturbations: Towards robust reinforcement learning
Karma çekişmeli bozulmaları dengeleme: Gürbüz pekiştirmeli öğrenmeye doğru
MUSTAFA ERDEM
Doktora
İngilizce
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE
- 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
2005
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. FÜSUN ÜLENGİL
- 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
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ DİKENELLİ
- Politika duyarlı text-to-SQL ajanının postgresql satır düzeyi güvenlik (RLS) ile uygulamalı değerlendirilmesi
Applied evaluation of the policy-sensitive text-to-SQL agent with postgresql row level security (RLS)
ALI ATIA ALI KOUNDI
Yüksek Lisans
Türkçe
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilişim Sistemleri Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL HAKKI CEDİMOĞLU
- Bir halı firmasında cağ değişim sürelerinin yapay sinir ağı yaklaşımı ile tahminlenmesi
Prediction of creel change delays in carpet production via artificial neural network approach
KÜBRA NUR MARAŞLIOĞLU
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. YUSUF KUVVETLİ