Distributed team formation for robot soccer
Robot futbolu için dağıtılmış takım formasyonu
- Tez No: 350540
- Danışmanlar: YRD. DOÇ. DR. SANEM SARIEL-TALAY
- 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: 2012
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Çoklu etmen sistemleri son yirmi yılda oldukça aktif bir araştırma alanı oluşturmuştur. Etmenler, belli hedefleri gerçekleştirmek amacıyla otonom kararlar alıp uygulayabilen bilgisayar sistemleri olarak tanımlanabilir. Etmenler hedeflerini gerçekleştirmek için bulundukları çevreden duyularıyla algıladıkları bilgileri göz önünde bulundurarak kararlar alıp bunları eyleme dönüştürürler. Akıllı etmenlerden oluşan çoklu etmen sistemleri robotların veya insanların bulunduğu çevreleri de kapsamasına rağmen, çoğunlukla yazılım etmenlerini barındıran benzetim ortamları için geliştirilmektedir. Çoklu etmen sistemlerinde etmenler karar verirken, bulundukları çevrenin yanısıra diğer etmenlerin davranışlarını da göz önünde bulundurmak zorundadır. Bazı hedeflerin gerçekleştirilebilmesi için diğer etmenlerle iletişim kurarak birlikte hareket edilmesi gerekmektedir. Çoklu etmen sistemlerindeki araştırmalar çoğunlukla birden fazla etmenle iletişim, çoklu etmen öğrenmesi, organizasyon, uzlaşma, dağıtılmış problem çözümü, hatalara karşı dayanıklılık, koordinasyon ve işbirliği gibi konularda tek etmenli sistemlerden daha iyi sonuçlar elde etmeye yoğunlaşmıştır.RoboCup yarışmaları çoklu etmen sistemleri için uygun sınama alanlarıdır. RoboCup organizasyonu 1997 yılında kurulmuştur ve çeşitli kategorilerde düzenlediği yarışmalarla yapay zeka konusundaki çalışmalara ilgiyi arttırmayı amaçlamaktadır. Her yıl düzenlenen RoboCup yarışmaları farklı boyutlarda robot futbolu, 2 boyutlu ve 3 boyutlu ortamlarda futbol benzetimi, robot kurtarma ortamları ve ev uygulamaları gibi çeşitli dallarda ligler içerir. RoboCup'ın temel hedefi 2050 yılında FIFA Dünya Kupası'nı kazanan futbol takımını yenebilecek tamamen otonom insansı robot takımını yaratabilmektir. Robot futbolu yarışmalarının bazıları çeşitli boyutlarda insansı robotlarla (Standart Platform Ligi, 3 boyutlu futbol benzetim ligi vb.) bazıları ise insansı olmayan ve daha hızlı hareket edebilen robotlarla (Orta boyutlu robot ligi, küçük boyutlu robot ligi vb.) yapılmaktadır. Bazı liglerde yarışan takımlar robotlarını kendi tasarlamaktadır. Bu tür liglerde takım stratejilerinden çok mekanik ve teknolojik özelliklerin kullanımı önemlidir. Standart Platform Ligi ve 3 boyutlu futbol benzetim ligi gibi liglerde ise tüm takımlar önceden belirlenmiş standart robotları kullanmak zorundadır. Bu yüzden bu tür liglerde birden fazla etmenin birlikte ve uyum içinde hareket etmesini sağlayacak stratejiler önem kazanmaktadır. Özellikle benzetim yarışmaları, gözlem, iletişim ve uzaktan yönetim kısıtları gibi sınırlamalara sahip karmaşık takım stratejilerini incelemek için oldukça uygundur. RoboCup 3 boyutlu futbol benzetim ligi yukarıda belirtilen kısıtlara sahip benzetimlere iyi bir örnektir ve 2011 yılı itibarıyla 14x21 m boyutlarında sahada 9x9 etmenli oyunlara ev sahipliği yapmıştır. Önümüzdeki yıllarda teknik gelişmelerle birlikte etmen sayılarının her takım için 11'e çıkarılması, saha boyutlarının gerçek futbol sahalarının boyutlarına genişletilmesi hedeflenmektedir. RoboCup 3 boyutlu simülasyon ligi, gerçek robotlar yerine bunların benzetimleriyle oluşturulan yazılımsal etmenleri kullandığı için araştırma maliyetleri açısından da ekonomik bir yapıya sahiptir. Bu yapı sayesinde RoboCup'ın 2050 yılı hedefini gerçekleştirme konusunda insan futboluna en yakın stratejilerin uygulanıp sınanabileceği yarışma ortamı RoboCup 3 boyutlu simülasyon ligidir.Gerçek futbol oyunlarında olduğu gibi, insansı futbol takımlarının ana hedefi rakip takıma karşı gol atmaktır. Verimli bir işbirliği sağlamak maçı kazanmak için anahtar faktördür. İşbirliği konusunda takım arkadaşına pas atmak veya sahaya gerektiğinde topun kontrolünü sağlamak üzere yayılmak gibi iki temel davranış vardır. İki davranış da etmenlerin istenen sonucu elde etmeleri için uygun konumlarda olmasını gerektirir. Bu konumlar genellikle oyundaki durumlara göre dinamik olarak değişen özel dizilişlerdir. Takımın genel performansı uyarlanabilir dizilişlere ve bunlara ait olan robotik etmenlerin konumlarına bağlıdır. İnsanların oynadığı futbol oyununun aksine, temeli oluşturan hareket modeline bağlılıktan dolayı insansı robot futbolunda genel dizilişler yoktur. Bu yüzden bir takımın hareketlilik kısıtları uygun takım stratejisini seçmede önemli bir rol oynamaktadır. Hızlı hareket edebilen robotlarla daha geniş alanlara yayılarak açık bir takım formasyonu uygulanabilir. Fakat insansı robotlar günümüz teknolojisindeki kısıtlamalardan dolayı çok hızlı hareket edememektedir. Yavaş hareket eden bir robot topa sahip olan takım arkadaşı topu kaybettiğinde uzak bir konumdaysa top kontrolünün rakibe geçmesine sebep olabilir. Aksi durumda topa sahip olan takım arkadaşına fazla yakın duran robot bu robotun hareket kabiliyetini düşürüp hata yapmasına sebep olabilir. Bu yüzden birbirlerinin hatalarını düzeltebilecek kadar yakın ve takım performansını düşürmeyecek şekilde konumlanmak önemlidir. Robotlar, konumlanma sırasında kendi takım arkadaşlarına dikkat ettiği gibi rakip takım oyuncularını da göz önünde bulundurmalıdır. Robotlar, hücum sırasında rakiplerden uzakta durmaya çalışarak rakip kaleye topu taşıma sırasında olası engellerden sakınmalıdır. Savunmada ise robotlar rakip robotlara olabilecek en yakın pozisyona gelmeli ve rakipleri engelleyerek top kontrolünün kendi takımına geçmesini sağlamalıdır. Takım formasyonu oluştururken söylenen tüm hususların dikkate alınması, futbolun temel amacı olan rakip takıma gol atma ve attığı gol sayısından az gol yiyerek oyunu kazanma konusunda takımın performansının en üst seviyeye yaklaşmasını sağlayacaktır.Bu tezin amacı, benzetim ortamında oynanan futbol oyununda rol ataması ve takım dizilişi olmak üzere iki önemli parçadan oluşan etkili takım stratejileri sunmaktır. Rol ataması ve takım dizilişi için farklı yöntemler geliştirilmiş ve bu alandaki geçmiş çalışmalarla beraber top konumu ve top kontrolü konusunda karşılaştırmalı testler yürütülmüştür. Etmenler saha içindeki rollerine göre (kaleci, savunma, orta saha, hücum) gruplara ayrılmış ve oyuncuların bulundukları gruptaki diğer etmenlerle uyumlu bir şekilde görevlerini yerine getirmeleri hedeflenmiştir. Takımda grup davranışları için savunma ve hücum şeklinde iki grup belirlenmiş ve etmenlerin kendi rollerine ait görevlerin yanında grubun davranışlarına da yardımcı olacak şekilde hareket etmeleri amaçlanmıştır. Etmenlerin gruplara ayrılması ile ilgili farklı yöntemler geliştirilmiş ve bu yöntemlerin sonuçları incelenmiştir. Bu yöntemler rollere atanmış robot sayılarının değişmediği durağan gruplama, çeşitli durumların önceden tanımlandığı ve bu durumlara göre rollerdeki robot sayılarının belirlendiği durum tabanlı gruplama ve Bayes öğrenme yöntemini temel alan olasılıksal gruplamayı içermektedir. Takımın saha içindeki konumlanması ve dizilişi için Voronoi diyagramlarını temel alan bir yapı geliştirilmiştir. Bu yapı ile tüm etmenler dağıtılmış bir şekilde kendi konumlarını hesaplamaktadır. Yöntemi kullanan her etmen ilk önce topa ve kendi konumuna göre bir çokgen oluşturmaktadır. Bu çokgen savunma grubundaki oyuncular için topla takımın kendi kalesi arasında rakibi durduracak şekilde, hücum oyuncuları içinse topun etrafında konumlanarak top kontrolünü sağlayacak şekilde oluşturulmaktadır. Daha sonraki aşamada etmen, saha içinde gördüğü takım arkadaşlarının konumlarını göz önünde bulundurarak Voronoi diyagramlarının kurallarına göre ilk oluşturduğu çokgeni değiştirmektedir. Bu değişim kendi çokgenini hesaplayan etmenlerle diğer etmenler arasında doğru parçaları çizilmesi, diğer etmenlerden bu çizgilere paralel çizgiler çekilmesi, paralel çizgiler çokgeni ikiye bölünüyorsa bu iki parçadan etmeni içerenin alınması gibi adımları içerir. Bu aşama sonucunda elde edilen çokgenin ağırlık merkezi etmenin gitmesi gereken hedefi belirlemektedir. Bu aşamalar çalışma zamanında sürekli güncellenerek dinamik bir formasyonun oluşması sağlanmaktadır. Uygulanan yöntem sayesinde etmenler bulundukları gruptaki diğer etmenlere, onların hareketlerini kısıtlamayacak şekilde olabildiğince yaklaşarak konumlanmaktadır. Takım formasyonu içinde rakip oyuncularla çarpışmaları engellemek amacıyla bazı engel sakınımı yöntemleri de uygulanmaktadır. Saha dizilişi ile amaçlanan topun etrafında etkin bir konumlanma ile top kontrolünü ele geçirmek ve top rakibin kontrolündeyken onları durdurabilecek konumlarda etmenler bulundurmaktır. Geliştirilen yöntemler belli bir yapı üzerinde birleştirilmiş ve RoboCup 3 boyutlu futbol benzetim ligi takımlarından beeStanbul'un yazılımına eklenmiştir. Yöntemlerin başarımı RoboCup 3 boyutlu futbol benzetim liginde yarışmakta olan bazı diğer takımların yazılımlarıyla yapılan maçlarla sınanmıştır. Başarım ölçütleri olarak topun takımlar tarafından kontrol edilme yüzdesi ve topun bulunduğu konumlar incelenmiştir. İlk ölçüt topun etrafında doğru konumlanmanın başarımını ölçerken ikinci ölçüt topun rakip sahaya taşınma yüzdesini incelemektedir. Bu yöntemlerle ilgili deneyler RoboCup 3 boyutlu futbol benzetim liginin yarışma ortamı Simspark'ta uygulanmıştır. Görsel arayüz olarak da RoboCup 3 boyutlu futbol benzetim liginde 2011'de kullanılmaya başlanan Roboviz programı kullanılmıştır.Bu tez kapsamında geliştirilen yöntemler temel olarak etmenlerin takım stratejisi konusunda ayrık kararlar vermesi ve işlem maliyetlerinin azami seviyede tutulmasını hedeflemektedir. Yöntemin iletişimde oluşabilecek sorunlara karşı dayanıklılığı da geliştirme sırasında dikkate alınmıştır. Rakiplerin saha içindeki dizilişleri, davranışları ve stratejilerine göre uyarlanabilir takım stratejileri geliştirmek de tez içindeki çalışmaların amaçlarından biridir. Bu hedeflere ulaşmada geliştirilen yöntemin başarımı çeşitli deneylerle sınanmıştır. Deneyler önerilen yöntemlerle literatürde mevcut bulunan yöntemler üzerinde karşılaştırmalı olarak yürütülmüştür. Önceki yöntemlerden bazıları denetçi kullanırken bazılarında etmenler bağımsız kararlar vermektedir. Denetçi kullanan yöntemler çoklu etmen sisteminin çevresiyle ilgili bilgileri alıp incelemekte ve bu bilgileri tüm etmenlere iletmektedir. Denetçi olmayan yöntemlerde ise etmenler, çevre ile ilgili kendi donanımlarıyla elde ettikleri ve diğer etmenlerden iletişim yoluyla aldıkları bilgileri kullanarak tamamen otonom karar vermek zorundadır. Sonuçlar rol ataması ve takım dizilişi için ayrık kararlar veren takım stratejilerinin önceki yöntemlere göre daha iyi çalıştığını göstermektedir.
Özet (Çeviri)
The field of multi-agent systems (MAS) has been an active research area for the last two decades. Multi-agent systems consist of intelligent agents and their environments. Although multi-agent systems can include environments with robots or humans, they mostly refer to software agents within the software simulations. Researches on MAS mostly focus on obtaining better results with multiple agents in communication, multi-agent learning, coordination and cooperation than single agents.RoboCup competitions are suitable testbeds for multi-agent systems. Annual RoboCup competitions consist of various leagues such as robotic soccer leagues in different sizes, soccer simulations in both 2D and 3D environments, robot rescue environments and at home leagues. Specifically, simulation competitions are suitable for analyzing complicated team strategies in the face of realistic constraints such as limitations on observability, communication and teleoperation. As of 2011, RoboCup 3D Soccer Simulation League (SSL) hosted 9x9 agent games on a 14x21 m field and is a good example of simulations with constraints mentioned above.Just like real soccer games, the main objective of a humanoid soccer team is scoring goals against an opponent team. Efficiency of cooperation is an important key factor to win a game. There are mainly two behaviors which involve cooperation issues, namely, passing the ball to a teammate or spreading out to the field of play to gain control of the ball whenever needed. Both behaviors require agents to be in appropriate positions to achieve the desired outcomes. These positions usually belong to special formations which may dynamically change their shapes for different situations during a game. The performance of the overall team is highly dependent on these adaptive formations and the corresponding positions of robotic agents. Contrary to human soccer games, there are not generic formations for humanoid soccer especially because these are also dependent on the underlying motion model. Therefore, the set of mobility constraints of a team plays an important role in the selection of an appropriate team strategy.The purpose of this thesis is to present efficient team strategies which consist of two important parts: role allocation and team formation of the agents in a simulated soccer game. Experiments are set in the RoboCup 3D SSL environment, Simspark. Different methods for role allocation and team formation are developed and compared with previous works in the area, in terms of ball possession and ball position.The methods developed in this thesis mainly aims distributed decisions to be made by the agents for the team strategy and to keep computational costs at minimum. Robustness of the method against the communication failures is another issue and it is also considered in the development. Experiments are set to analyze the developed methods and some earlier methods. Some of these earlier methods use supervisors while some of them make autonomous decisions. Results show that team strategies with distributed decisions for team formation and role allocation outperform the existing methods.
Benzer Tezler
- Hücresel imalat sistemlerinde maliyet ve sinir ağları tabanlı iki evreli bir kümelendirme yaklaşımı
Artificial neurat network x operation costs based twostage GT clusterning procedure
AFFAN NOMAK
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT DURMUŞOĞLU
- Doğalgaz boru hatlarının kaynağı ve tahribatsız muayenesi
Welding and non-destructive testing of naturalgas pipelines
MEHMET YILDIZ
- İşletmelerde yönetimsel etkililiğin oluşmasında bilgi teknolojilerinin rolü ve bir uygulama
Role of information technology in the formation of managerial effectiveness in business enterprises and an assessment application
İBRAHİM MEHDİ AKSU
- Seismic arrays for the imaging of alluvial deposits and monitoring engineering systems
Alüvyal çökellerin görüntülenmesi ve mühendislik sistemlerinin izlenmesi amacıyla kullanılan sismik dizilimler
ESRA AK
- İnşaat sektöründe ekip çalışması
Başlık çevirisi yok
TUĞBA GÖKÇEN
Yüksek Lisans
Türkçe
1998
Mimarlıkİstanbul Teknik ÜniversitesiBina Yapım Yönetimi Bilim Dalı
PROF. DR. FATMA HEYECAN GİRİTLİ
