Yönlendirme Davranışları, Takip etme ve Kaçma
Steering Behaviours, Seek and Flee
Yönlendirme davranışları, otonom ajanların çevreyle etkileşim içinde gerçekçi ve dinamik hareketler sergilemesini sağlayan bir simülasyon tekniğidir. Bu davranışlar, bir ajanın çevresindeki diğer nesneleri algılaması ve bu nesnelere göre uygun kuvvet ve yön belirlemesi üzerine kuruludur. Örneğin, bir ajan bir hedefe ulaşmaya çalışırken engellerden kaçınabilir, diğer ajanlarla uyum içinde hareket edebilir ya da bir grup içindeki konumunu koruyabilir. Bu bölümde, yönlendirme davranışlarının temel prensiplerini ve oyun geliştirme ya da simülasyon projelerinde nasıl kullanılabileceğini detaylı bir şekilde inceleyeceğiz. Bu sürecleri kurgularken 2 boyutlu uzayda vektörler konusunu sık sık ele alacağız. 2 boyutlu vektörleri anlattığım sayfaya aşağıdaki linkden ulaşabilirsiniz.
2 Boyutlu Uzayda Vektörler
Graflar, düğümler ve bu düğümler arasındaki bağlantıların oluşturduğu ağ yapılarıdır. Graf temelli yol bulma algoritmaları birbiri ile bağlantıları düğümleri kullanır. Bu düğümler arasındaki bağlantıların yönleri ve ağırlıkları (hareket bedeli) vardır. Bu özellikler düğümler arasındaki hareketin yönünü ve bedelini belirler. Bu yöntemi kafes(grid) sistemlerinde de kullanabiliriz. Aslında kafesler de bir çeşit graflardır.
Bir ajanın A noktasından B noktasına ulaşması için gereken hız, ivme ve pozisyonları yönlendirme davranışları ile hesaplarız. Ajan, bir noktadan uzaklaşmak, belirli bir yolu takip etmek ya da bir objeyle çarpışmaktan kaçınmak gibi görevleri bu davranışlar sayesinde yerine getirebilir. Dahası, farklı davranışları birleştirerek daha karmaşık senaryolar oluşturabiliriz. Örneğin, ajan bir yolu takip ederken aynı anda çevresindeki objelere grup haline hareketini bu yöntem sayesinde kurgulayabiliriz. Bu tür birleşik davranışlar, ajanın daha gerçekçi ve esnek hareketler sergilemesini sağlar.
Ajan özellikleri
Öncelikle otonom ajan kavramını biraz daha detaylı ele almamız gerekiyor. Daha önce de belirttiğimiz gibi, yönlendirme davranışları ajanın hareketlerini ivme temelinde şekillendirir. İvme sayesinde hız, hız sayesinde ise konum değişikliği elde ederiz. Bunları en basit hali ile kullanabilmek için ajanın aşağıdaki özelliklere sahip olması gerekmektedir.
- Maksimum lineer ivme:Bu değer ajanın kendi içinde hesaplanan veya sabit olarak verilen değerdir. Yönlendirme davranışında lineer hıza maksimum ne kadar ivme uygulanabileceğini söyler. Skaler sayıdır.$$\overrightarrow{Al_{max}}\left(x,y\right)$$
- Maksimum lineer ivme:Bu değer ajanın kendi içinde hesaplanan veya sabit olarak verilen değerdir. Yönlendirme davranışında dönme hızının maksimum ne kadar ivme ile yapılabileceğini söyler.$$Aq_{max}$$
- Maksimum lineer hız:Bu değer ajanın ulaşabileceği maksimum hızdır. Skaler sayıdır.$$\overrightarrow{Vl_{max}}\left(x,y\right)$$
- Maksimum açısal hız:Bu değer ajanın ulaşabileceği maksimum açısal hızdır. Skaler sayıdır.$$Vq_{max}$$
- Lineer ivme:Bu değeri yönlendirme davranışı hesaplar ve bizim hareketimizin ana kaynağıdır. Vektörel sayıdır, yönü vardır. Algoritmamızın çıktısıdır.$$\overrightarrow{Al}\left(x,y\right)$$
- Açısal ivme:Bu değeri yönlendirme davranışı hesaplar ve bizim hareketimizin ana kaynağıdır. Skaler sayıdır(2 boyutlu uzay için). Algoritmamızın çıktısıdır.$$Aq$$
- Lineer Hız:Bu değer ajanımızın mevcut hızıdır. Her karede lineer ivme eklenerek değiştirilir. Vektörel sayıdır, yönü vardır.$$\overrightarrow{Vl}\left(x,y\right)$$
- Açısal Hız:Bu değer ajanımızın mevcut açısal hızıdır. Her karede açısal ivme eklenerek değiştirilir. Skaler sayıdır(2 boyutlu uzay için).$$Vq$$
- Pozisyon:Adındanda anlaşılacağı üzere ajanımızın mevcut pozisyonunun değeridir. Vektöreldir.$$\overrightarrow{P}\left(x,y\right)$$
- Oryantasyon:Ajanımızın baktığı yöndür. Skaler sayıdır(2 boyutlu uzay için).$$Q$$
Konum Hız İvme ilişkisi
Öncelikle bilimsel tanımlamalar başlayalım. Pozisyon objemizin uzayda bulunduğu yeri göstermektek için kullandığımız vektördür. Hız ise bu konumun zamana göre değişimidir. Konum hız ilişkisini aşağıdaki denklemlerle gösteririz.
$$\overrightarrow{V(t)}=\frac{dx}{dt}$$
$$\overrightarrow{X_c} = \overrightarrow{X_p} + \int_{t_0}^{t_1}{\overrightarrow{V(t)}dt}$$
Yönlendirme davranışında hesaplama ivmeden konuma doğru yapılır. Yukarıdaki konum integralini çözmeliyiz. Biz bu integrali Euler Yöntemi ile kolayca çözebiliriz.
Euler Yöntemi
$$f(x)=\frac{dy}{dx}$$
$$y_0: Başlangıç konumu$$
Bu kısım yazacağımız algoritmanın matematiksel açıklamasıdır. İsterseniz bu kısımı atlayarak Euler yöntemi uygulamasına geçebilirsiniz. Euler yöntemi, bir başlangıç değer problemi için diferansiyel denklemlerin yaklaşık çözümlerini bulmak amacıyla kullanılan temel bir nümerik yöntemdir. Bu yöntemde, çözümün eğrisini küçük adımlarla (h) yaklaşık olarak takip ederiz. Diferansiyel denklemin sağ tarafındaki türev, bir noktadaki eğimi temsil eder. Euler yöntemi, bu eğimi kullanarak, y'nin bir sonraki değerini tahmin eder. Bu işlemler iteratif olarak bizi istenen x değerine yaklaştırır.
1. Adım büyüklüğü belirlenir. Positif olmak zorundadır. Ne kadar küçük olursa o kadar gerçekçi sonuç elde ederiz.
$$h_1$$
2. Adım anında değişim hesaplanır.
$$f_1 = \frac{dy}{dx}$$
3. Değişim ile adım çarpılarak mevcut konuma eklenir.
$$y_1 = y_0 . f_1$$
4. İlk adıma geri dönülür. İstenen x'e gelene kadar döngü devam eder.
Yukarıdaki adımlarla nümerik olarak integrali çözebiliriz. Biz bu yöntemi son adımı değiştirerek kullanacağız
Euler Yöntemin uygulanması
Biz yukarıda bahsettiğim Euler yönteminin adımlarını kullanarak konumu hesaplayacağız. Bu adımları denklemimize uygun olacak bir biçimde tekrar yazalım.
1. Adım büyüklüğümüz önceki adım ile şimdiki adım arasındaki zaman farkıdır. Önceki adım zamanımız yoksa(ilk adımımızsa) sıfır veya çok küçük bir değer verebiliriz.
$$h_1 = \Delta t = t_1 - t_1$$
2. Biz o andaki hızı bildiğimiz için direkt hızı kullanabiliriz.
$$f_1 = \overrightarrow{V}$$
3. Hız ile zaman farkını çarpılarak mevcut konuma eklenir.
$$\overrightarrow{X} = \overrightarrow{V} . \Delta t$$
4. İlk adıma geri dönülür. Program durana kadar devam eder.
Euler yöntemini başlangıçta uygulaması zor gözükse bile problemimize kolayca uygulayabildik. Sürekli değişen hız ve ivme değerlerine göre posizyonumuzu gerçek zamanlı bir şekilde hesaplayabiliriz. Aynı ilişkiyi ivme ile hız arasında da tanımlarız. İvme tamamen algoritmanın hesaplaması ile belirlenir. Yukarıdaki yöntemi kullanarak ivmeden mevcut hızı hesaplarız. Yine yukarıdaki yöntemi kullanarak mevcut hızdan da mevcut konumu elde ederiz.
Yönlendirme algoritmalarının temel prensibi
Yönlendirme algoritmasının ana prensibi ajanımızın mevcut hızının, olması istenen hıza ivme ile getirilmesidir. Takip davranışı bakarak daha iyi anlayabiliriz. Aşağıdaki örnekte ajanımızın hedefine doğru bir istenen hız mevcuttur. İvmemizde sürekli bir şekilde mevcut hızımızı istenen hıza yaklaştırır.
Euler yöntemi ve yönlendirme algoritmalarının temelinin koda dökümü
Bu aşağıdaki gibi euler yöntemini koda aktarabilir, yönlendirme algoritmalarımız için bir temel yapı oluşturabiliriz.
Takip Etme Davranışı
Seek Behaviour
Takip etme (seek) davranışında, ajanın bir hedefe ulaşması amaçlanır. Bu davranış, hedefe doğru bir yön belirleyerek başlar. İlk olarak, ajandan hedefe doğru bir doğrultu vektörü oluşturulur. Bu vektör, ajanın istenen hızının yönünü ifade eder. Daha sonra, bu doğrultu vektörünün büyüklüğü ajanın maksimum hızına eşitlenir ve böylece istenen hız vektörü elde edilir.
Ardından, ajanın mevcut hız vektörü, istenen hız vektöründen çıkarılarak ivmelenme doğrultusu belirlenir. Bu doğrultu vektörünün büyüklüğü, ajanın maksimum lineer ivmesine ayarlanır. Sonuç olarak, ajan bu ivmeyi kullanarak hedefe doğru hareket eder. Bu anlatılanı matematiksel ifadeye dökelim.
Öncelikle değişkenleri tanımlayıp ne anlama geldiğiniz yazalım.
Ajanın karakter özellikleri
Ajanın maksiumum ivmesi:
$$V_{max}$$
Ajanın maksiumum ivmesi:
$$A_{max}$$
Ajanın uzaysal özellikleri
Ajanın başlangıç konumu:
$$P_i = (P_{ix}, P_{iy})$$
Ajanın başlangıç hızı:
$$V_i = (V_{ix}, V_{iy})$$
Hesaplanan ivme:
$$A = (A_{x}, A_{y})$$
Takip etme davranışı özellikleri
Takip etme davranışının hedefi:
$$P_t = (P_{tx}, P_{ty})$$
İvmeyi hesaplamak için uygulanan işlemler
Tanımladığımız özellikleri kullanarak takip davranışı sonucunda oluşacak ivmeyi hesaplayalım.
İstenen hızın doğrultusu hesaplarız.
$$V_{ed} = P_t - P_i$$
İstenen hızı hesaplarız:
$$len(V_{ed}) = \sqrt{V_{edx}^2 + V_{edy}^2}$$
$$V_e = V_{ed} * \frac{V_{max}}{len(V_{ed})}$$
İvmemizin doğrultusu hesaplarız:
$$A_{ed} = V_e - V_i$$
İvmemizi hesaplarız:
$$len(A_{d}) = \sqrt{A_{dx}^2 + A_{dy}^2}$$
$$A = V_{d} * \frac{A_{max}}{len(A_{d})}$$
Yukarıdaki vektörel işlemler(uzunluğu bulma, birim vektör elde etme gibi) için kütüphane kullanabiliriz ya da kendimizde kodunu yazabiliriz.
Bu işlemlerin sonucunda aşağıdaki gibi bir hareket elde ederiz.
Maksimum hızı:
60
Maksimum ivmesi:
40
Yukarıdaki similasyonda bir ajan ve onun bir hedefi bulunmakta. Fakat hedef sabit olmak zorunda değil. Ajanda gördüğünüz Mevcut hız, Hedeflenen hız ve İvme ok işaretleri ile gösterilmekte. Ajanlar sadece statik hedefi takip etmek zorunda değildir. Ajan ajanı takip edebilir.
1. ajanın
Maksimum hızı:
40
Maksimum ivmesi:
20
2. ajanın
Maksimum hızı:
40
Maksimum ivmesi:
20
3. ajanın
Maksimum hızı:
40
Maksimum ivmesi:
20
Bu örnekte 3 ajan herbiri diğerini takip etmektedir.
Animasyonda da görüldüğü üzere çok karmaşık hareketleri yönlendirme davranışları algoritmaları ile simule edebilmekteyiz. Örneklerde de anlaşılacağı üzere takip etme davranışına sahip ajan hedefine yaklaşıp durmaz. İlk örnekte ajan son olarak salınma hareketi eder. İkinci örnekte de tamamen kaotik bir durum söz konusudur. Ajanın hedefe varıp durması için daha farklı bir yönlendirme davranışı kullanmamız gerekir. Bu davranışı sonraki yazılarımda anlatacağım.
Kaçma Davranışı
Flee Behaviour
Kaçma (flee) davranışı, ajanın belirli bir noktadan uzaklaşmasını sağlamak için kullanılır. Kaçılan nokta sabit, hareketli veya başka bir ajana bağlı olabilir. Çalışma prensibi, takip etme (seek) davranışına oldukça benzerdir, ancak burada amaç hedefe yaklaşmak değil, ondan uzaklaşmaktır.
Bu davranışta, istenen hızın doğrultusunu belirlerken, tehlike kaynağının konumundan ajanın mevcut pozisyonu çıkarılır. Bu işlem, takip davranışında elde edilen doğrultunun tam tersini verir. Sonuç olarak, ajan tehlikeden uzaklaşacak şekilde bir hareket oluşturur.
Maksimum hızı:
8
Maksimum ivmesi:
4
Aşağıdaki örnekteki uzayda da, takip etme davranışına sahip ajan ve kaçma davranışına sahip ajan beraber bulunmaktadır.
Takip eden ajanın
Maksimum hızı:
9
Maksimum ivmesi:
3
Kaçan ajanın
Maksimum hızı:
10
Maksimum ivmesi:
4
Kaçma davranışında ajanın belirli bir uzaklığa geldikten sonra kaçmasını sonlandırmak isteyebiliriz. Sonuçta güvenli uzaklığa geldikten sonra ajanımızın tehditten kaçması anlamsız olabilir. Bunu şekilde çözebiliriz. Ben kaçma davranışımıza durma uzaklığı tanımlayarak çözümünü göstereceğim.
Maksimum hızı:
25
Maksimum ivmesi:
45
Durma uzaklığı:
20
Kaçma davranışımıza bir durma uzaklığı tanımladığımızda tehditle ajanımızın arasındaki uzaklık ölçülür. Eğer tehdit durma uzaklığından daha yakınsa ajanımız tehditten kaçar. Eğer durma uzaklığından daha uzaksa hedeflenen hız 0 vektörüne eşitlenir. Böylece ajanımız yavaşça durur.
Kaçma davranışının aşağıdaki gibi kodlayabiliriz.
Kapanış
Yönlendirme davranışlarına bu iki davranışla başlamak uygundur. Sonraki yazımda bu yönlendirme davranışlarını baz alan davranışlara gireceğim.
linkedin
github