An approach to multi-agent pursuit evasion games using reinforcement learning

Güvenlik başta olmak üzere yaşamın birçok alanında uygulamalarını gördüğümüz kaçma-kovalama problemleri, her dönem için popüler bir araştırma konusu olmuştur. Özellikle son on yılda, süreç içerisine öğrenmenin de katılmasıyla ajanlar akıllı ajanlar halini almış ve bir haritaya gereksinim duymaksızın çevreleri hakkında topladıkları bilgileri kendi faydaları için kullanmaya başlamışlardır. Bu yönelim, problem çözümüne farklı disiplinlerden yeni bakış açıları kazandırmayı başarmış ve konuya olan ilginin tekrar yoğunlaşmasını sağlamıştır. Takviyeli öğrenme, kaçma-kovalama problemlerinin çözümünde kullanılan ve ajanların çevre ile etkileşiminden faydalanan bir yöntemdir. Bu yöntemle ajanlar, karmaşık algılayıcılar ve haritalar kullanmadan çevrelerinden aldıkları geribildirimler (ödüller ve cezalar) ile davranışlarını optimize ederler. Yapılan çalışmalarda, bir kaçan ajan, bir kovalayan ajan içeren senaryolar için başarılı deneyler gerçekleştirilmişse de, birden fazla kovalayan ajan bulunan takip senaryoları için yeterli sayıda araştırma bulunmamaktadır. Bu tezde, çok ajanlı kaçma-kovalama problemlerinde takviyeli öğrenme yaklaşımı araştırılmış ve buna yönelik olarak deneyler sunulmuştur. Problemin çözümüne ilişkin benimsenen yöntemde ajanlar Watkins’in Q(λ) öğrenmesi metodunu kullanmaktadırlar. Q-öğrenmesi, uyguladığı politikadan bağımsız, optimal olarak aksiyon-değer tablosunu güncelleyen bir Geçici Farklar Kontrolü algoritmasıdır. Bizim çalışmalarımızda kullanılan Watkins’in Q(λ) yöntemi ise Q-öğrenmesinin uygunluk izleri mekanizmasıyla genişletilmiş bir hali olup, ajanın uygulayacağı keşif niteliğindeki ilk hamleye kadar takip eden tecrübeleri kullanmaktadır. Çalışmamızda kovalayan ajanlar takımı için eşzamanlı öğrenme yaklaşımı uygulanmıştır. Bu yaklaşımda, aynı takımdaki ajanların her biri kendi aksiyon-değer tablosuna sahiptir ve takım arkadaşlarından bağımsız olarak bilgi uzayını günceller. Çalışmamızda, bahsi geçen yöntemler kullanılarak, bir kaçma kovalama problemi simülasyonu düzenlenmiş ve yapılan deneylerde elde edilen sonuçlar paylaşılmıştır.The game of pursuit-evasion, which is encountered frequently in applications of security, has always been a popular research subject in the field of robotics. Especially in the last two decades, when computer scientists gave rise to learning, the agents turned into intelligent agents and they started to use the information about their enviroment for their own purposes, without using the help of a map. This tendecy drew considerable amount of attention and opened the area to newcomers from several different disciplines.Reinforcement learning, which takes the advantage of an agent’s interaction with the environment, is a method widely used in pursuit-evasion domain. With the help of this method, agents use the feedbacks (rewards and punishments) taken from the environment to optimize their behaviour, without using complex sensors and maps. Although there are successful examples of the one-pursuer one-evader scenario, there is not enough research on multi-agent pursuit-evasion problems in literature. In this master’s thesis, a research is conducted on multi-agent pursuit-evasion problem using reinforcement learning and the experimental results are submitted. The intelligent agents use Watkins’ Q(λ)-learning algorithm for the solution of the problem. Q-learning is an off-policy temporal difference control algorithm. The method we used on the other hand, Watkins’ Q(λ) learning algorithm, is a unified version of Q-learning and eligibility traces. It uses backup information until the first occurence of an exploration. In our work, concurrent learning is adapted for the learning of the pursuit team. In this approach, each member of the team has got its own action-value function and updates its information space independently