Davranış ağacı (yapay zeka, robotik ve kontrol)

Davranış ağacı, bilgisayar bilimi, robotik, kontrol sistemleri ve video oyunlarında kullanılan matematiksel bir plan yürütme modelidir. Sonlu bir dizi görev arasındaki geçişleri modüler bir şekilde tanımlamaktadır. Güçleri, basit görevlerin nasıl uygulanacağı konusunda endişelenmeden, basit görevlerden oluşan çok karmaşık görevler oluşturma yeteneklerinden gelmektedir. Davranış ağaçları, bir davranışın ana yapı taşının bir durumdan ziyade bir görev olması arasındaki temel farkla, hiyerarşik durum makinelerine bazı benzerlikler sunmaktadır. İnsan anlayışının kolaylığı, davranış ağaçlarını daha az hataya açık hale getirmiştir. Davranış ağaçlarının diğer birkaç kontrol mimarisini genelleştirdiği gösterilmiştir.^[1]^[2] Matematiksel olarak yönlendirilmiş dönsüz grafiklerdir.

Arka plan[değiştir | kaynağı değiştir]

Davranış ağaçları, bilgisayar oyunu endüstrisinden, oyuncu olmayan karakterlerin (NPC'ler) davranışını modellemek için güçlü bir araç olarak ortaya çıkmaktadır.^[3]^[4]^[5]^[6] Halo, Bioshock ve Spore gibi yüksek profilli video oyunlarında yaygın olarak kullanılmıştır. Son çalışmalar, davranış ağaçlarını İHA, karmaşık robotlar, robotik manipülasyon ve çoklu robot sistemleri için çok görevli bir kontrol çerçevesi olarak önermektedir.^[7]^[8]^[9]^[10]^[11]^[12] Davranış ağaçları artık Game AI ders kitaplarında^[13]^[14] ve Unity (oyun motoru) ve Unreal Engine gibi genel oyun ortamlarında ele alınacak olgunluğa ulaşmıştır.

Davranış ağaçları, geliştirme paradigmaları için popüler hale gelmiştir. Sadece NPC'nin eylemlerini programlayarak ve ardından yaprak düğümleri eylemler olan ve iç düğümleri NPC'nin karar vermesini belirleyen bir ağaç yapısı (genellikle sürükle ve bırak yoluyla) tasarlayarak karmaşık bir davranış yaratabilmektedir. Davranış ağaçları görsel olarak sezgiseldir ve tasarlaması, test etmesi ve hata ayıklaması kolaydır. Diğer davranış oluşturma yöntemlerinden daha fazla modülerlik, ölçeklenebilirlik ve yeniden kullanılabilirlik sağlamaktadır.

Yıllar boyunca, davranış ağaçlarının çeşitli uygulamaları, olay güdümlü davranış ağaçlarına dönüşene kadar endüstrinin taleplerini karşılamak için hem verimlilik hem de yetenekler açısından gelişmeye devam etmiştir.^[5]^[15] Olay güdümlü davranış ağaçları, ağacın dahili olarak yürütmesini nasıl idare ettiğini değiştirerek ve olaylara tepki verebilen ve çalışan düğümleri iptal edebilen yeni bir düğüm türü sunarak klasik davranış ağaçlarının bazı ölçeklenebilirlik sorunlarını çözmüştür. Günümüzde, olay güdümlü davranış ağacı kavramı bir standarttır ve basitlik için hala "davranış ağaçları" olarak adlandırılsalar da, uygulamaların çoğunda kullanılmaktadır.

Anahtar kavramlar[değiştir | kaynağı değiştir]

Bir davranış ağacı, düğümlerin kök, kontrol akış düğümleri veya yürütme düğümleri (görevler) olarak sınıflandırıldığı yönlendirilmiş bir ağaç olarak grafiksel şekilde temsil edilmektedir. Her bir bağlı düğüm çifti için giden düğüme ebeveyn, gelen düğüme alt düğüm denmektedir. Kökün ebeveyni ve tam olarak bir çocuğu(alt dalı) yoktur. Kontrol akış düğümlerinin bir ebeveyni ve en az bir çocuğu vardır. Yürütme düğümlerinin bir ebeveyni ve çocuğu yoktur. Grafiksel olarak, bir kontrol akış düğümünün çocukları, soldan sağa doğru sıralanarak onun altına yerleştirilmektedir.^[16]

Bir davranış ağacının yürütülmesi, çocuğuna belirli bir sıklıkta işaretler gönderen kökten başlamaktadır. Bir onay işareti, bir çocuğun yürütülmesine izin veren etkinleştirici bir sinyaldir. Davranış ağacında bir düğümün yürütülmesine izin verildiğinde, yürütmesi henüz bitmemişse çalışıyor, hedefine ulaşmışsa başarılı, aksi takdirde başarısızsa üst öğeye bir durum döndürmektedir.

Kontrol akışı düğümü[değiştir | kaynağı değiştir]

Oluşturulduğu alt görevleri kontrol etmek için bir kontrol akış düğümü kullanılmaktadır. Bir kontrol akış düğümü, bir seçici (geri dönüş) düğümü veya bir dizi düğümü olabilmektedir. Alt görevlerinin her birini sırayla yürütmektedirler. Bir alt görev tamamlandığında ve durumunu döndürdüğünde (başarılı veya başarısız), kontrol akış düğümü bir sonraki alt görevi yürütüp yürütmemeye karar vermektedir.

Seçici (yedek) düğüm[değiştir | kaynağı değiştir]

Geri dönüş düğümleri, başarısız olmayan ilk çocuğu bulmak ve yürütmek için kullanılmaktadır. Bir geri dönüş düğümü, çocuklarından biri başarılı veya çalışır durumda olduğunda, başarı veya çalışıyor durum koduyla hemen geri dönmektedir. Çocuklar önem sırasına göre soldan sağa doğru işaretlenmektedir.

Kodda, bir geri dönüş kompozisyonunun algoritması şöyledir:

1 for i from 1 to n do (for i'den birer 1'er n'ye kadar do)
2     çocuk_durumu ← İşaret(çocuk(i))
3     if çocuk_durumu= çalışma
4         return çalışma
5     else if çocuk_durumu= başarı
6         return başarı
7 end
8 return başarısızlık

Sıra düğümü[değiştir | kaynağı değiştir]

Dizi düğümleri, henüz başarılı olmayan ilk çocuğu bulmak ve yürütmek için kullanılmaktadır. Bir dizi düğümü, alt öğelerinden biri başarısız veya çalışır durumda olduğunda (bkz. Şekil II ve aşağıdaki kod) durum koduyla hemen geri dönmektedir. Çocuklar sırayla soldan sağa doğru işaretlenmektedir.

Kodda, bir dizi bileşimi için algoritma şöyledir:

1 for i from 1 to n do (for i'den birer 1'er n'ye kadar do)
2     çocuk_durumu ← İşaret(çocuk(i))
3     if çocuk_durumu= çalışma
4         return çalışma
5     else if çocuk_durumu= başarı
6         return başarı
7 end
8 return başarısızlık

Matematiksel durum uzayı tanımı[değiştir | kaynağı değiştir]

Davranış ağaçlarının analizine kontrol teorisi araçlarını uygulamak için, üçlü grup olarak tanımlanmaktadır.^[17]

$T_{i}=\{f_{i},r_{i},\Delta t\},$

$i\in \mathbb {N}$ ağacın indeksidir.
$f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}$ adi fark denkleminin sağ tarafını temsil eden bir vektör alanıdır.
$\Delta t$ bir zaman adımıdır.
$r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}$ iade durumudur.
Çalışma $R_{i}$ ,
Başarı $S_{i}$ ,
Başarısızlık $F_{i}$ dır.

Not: Görev, ebeveyni ve çocuğu olmayan dejenere bir davranış ağacıdır.

Davranış ağacı yürütme[değiştir | kaynağı değiştir]

Bir davranış ağacının yürütülmesi, aşağıdaki standart adi fark denklemleriyle tanımlanmaktadır:

$x_{k+t}(t_{k+1})=f_{i}(x_{k}(t_{k}))$

$t_{k+1}=t_{k}+\Delta t$

$k\in \mathbb {N}$ ayrık zamanı temsil etmektedir.
$x\in \mathbb {R} ^{n}$ davranış ağacı tarafından modellenen sistemin durum uzayıdır.

Sıra kompozisyonu[değiştir | kaynağı değiştir]

İki karar ağacı " $T_{i}$ ve $T_{j}$ " bir Sıra operatörü kullanılarak daha karmaşık bir davranış ağacı $T_{0}$ olarak oluşturulabilir.

$T_{0}={\mbox{sıra}}(T_{i},T_{j}).$

Ardından dönüş durumu ve $T_{0}$ ile ilişkili vektör alanı $f_{0}$ aşağıdaki gibi tanımlanmaktadır:

$r_{0}(x_{k})={\begin{cases}r_{j}(x_{k})&{\text{ eğer }}x_{k}\in {\mathcal {S}}_{1}\\r_{i}(x_{k})&{\text{ aksi takdirde }}.\end{cases}}$

$f_{0}(x_{k})={\begin{cases}f_{j}(x_{k})&{\text{ eğer }}x_{k}\in {\mathcal {S}}_{1}\\f_{i}(x_{k})&{\text{ aksi takdirde }}.\end{cases}}$

Ayrıca bakınız[değiştir | kaynağı değiştir]

Kaynakça[değiştir | kaynağı değiştir]

^ Colledanchise, Michele; Ögren, Petter (2017). "How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees". IEEE Transactions on Robotics. 33 (2): 372-389. doi:10.1109/TRO.2016.2633567.
^ Colledanchise, Michele; Ögren, Petter (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press. arXiv:1709.00084 $2. doi:10.1201/9780429489105. ISBN 978-1-138-59373-2.
^ Isla, D. (2005). "Handling complexity in the Halo 2 AI". Game Developers Conference (Vol. 12). 11 Mayıs 2012 tarihinde kaynağından arşivlendi.
^ Isla, D. (2008). Halo 3-building a better battle. Game Developers Conference 2008.
^ ^a ^b Agis, Ramiro A.; Gottifredi, Sebastian; García, Alejandro J. (2020). "An event-driven behavior trees extension to facilitate non-player multi-agent coordination in video games" (PDF). Expert Systems with Applications. 155 (1): 113457. doi:10.1016/j.eswa.2020.113457. 26 Temmuz 2020 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 23 Haziran 2021.
^ Lim, C. U.; Baumgarten, R.; Colton, S. (2010). "Evolving behaviour trees for the commercial game DEFCON" (PDF). Applications of Evolutionary Computation. Berlin: Springer. ss. 100-110. doi:10.1007/978-3-642-12239-2_11. ISBN 978-3-642-12238-5.
^ Ögren, Petter (2012). "Increasing Modularity of UAV Control Systems using Computer Game Behavior Trees" (PDF). AIAA Guidance, Navigation and Control Conference, Minneapolis, Minnesota. ss. 13-16.
^ Colledanchise, Michele; Marzinotto, Alejandro; Ögren, Petter (2014). "Performance Analysis of Stochastic BTs" (PDF). Robotics and Automation (ICRA), 2014 IEEE International Conference on. doi:10.1109/ICRA.2014.6907328. 2 Mart 2021 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 23 Haziran 2021.
^ Marzinotto, Alejandro; Colledanchise, Michele; Smith, Christian; Ögren, Petter (2014). "Towards a Unified BTs Framework for Robot Control" (PDF). Robotics and Automation (ICRA), 2014 IEEE International Conference on.
^ Klöckner, Andreas. "Interfacing BTs with the World Using Description Logic." In AIAA Guidance, Navigation and Control Conference, Boston, MA. 2013.
^ Klöckner, Andreas (2013). "Behavior Trees for UAV Mission Management". GI-Jahrestagung. ss. 57-68.
^ Bagnell, J. Andrew; Cavalcanti, Felipe; Cui, Lei; Galluzzo, Thomas; Hebert, Martial; Kazemi, Moslem; Klingensmith, Matthew (2012). "An integrated system for autonomous robotics manipulation" (PDF). Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on. IEEE. ss. 2955-2962. doi:10.1109/IROS.2012.6385888. hdl:20.500.11937/14608. ISBN 978-1-4673-1736-8.
^ Millington; Funge (2009). Artificial Intelligence for Games. CRC Press. ISBN 978-0-12-374731-0.
^ Rabin, S. (2014). Game AI Pro. CRC Press. ISBN 978-1-4665-6596-8.
^ Champandard, Alex J.; Dunstan, Philip (2012). "The Behavior Tree Starter Kit" (PDF). Game AI Pro: Collected Wisdom of Game AI Professionals. ss. 72-92.
^ craft ai (2015). "BT 101 – Behavior Trees grammar basics". 26 Haziran 2015 tarihinde kaynağından arşivlendi.
^ Colledanchise, Michele; Ögren, Petter (2014). "How Behavior Trees Modularize Robustness and Safety in Hybrid Systems" (PDF). In Intelligent Robots and Systems (IROS), 2014 IEEE/RSJ International Conference on. IEEE.

Dış bağlantılar[değiştir | kaynağı değiştir]

"ROS davranış ağacı kitaplığı". 24 Haziran 2021 tarihinde kaynağından arşivlendi.
"Unreal Engine 4 davranış ağacı belgeleri". 12 Kasım 2020 tarihinde kaynağından arşivlendi.
"AI için davranış ağaçları: Nasıl çalışırlar?". 6 Mayıs 2019 tarihinde kaynağından arşivlendi.
"Davranış Ağaçları: Robotunuz için Basit ama Güçlü Yapay Zeka". 25 Şubat 2020 tarihinde kaynağından arşivlendi.

[Colledanchise_TRO16-1] Colledanchise, Michele; Ögren, Petter (2017). "How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees". IEEE Transactions on Robotics. 33 (2): 372-389. doi:10.1109/TRO.2016.2633567.

[Colledanchise_BOOK17-2] Colledanchise, Michele; Ögren, Petter (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press. arXiv:1709.00084 $2. doi:10.1201/9780429489105. ISBN 978-1-138-59373-2.

[Damian_Isla-3] Isla, D. (2005). "Handling complexity in the Halo 2 AI". Game Developers Conference (Vol. 12). 11 Mayıs 2012 tarihinde kaynağından arşivlendi.

[Damian_Isla2-4] Isla, D. (2008). Halo 3-building a better battle. Game Developers Conference 2008.

[agis2020-5] Agis, Ramiro A.; Gottifredi, Sebastian; García, Alejandro J. (2020). "An event-driven behavior trees extension to facilitate non-player multi-agent coordination in video games" (PDF). Expert Systems with Applications. 155 (1): 113457. doi:10.1016/j.eswa.2020.113457. 26 Temmuz 2020 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 23 Haziran 2021.

[lim-6] Lim, C. U.; Baumgarten, R.; Colton, S. (2010). "Evolving behaviour trees for the commercial game DEFCON" (PDF). Applications of Evolutionary Computation. Berlin: Springer. ss. 100-110. doi:10.1007/978-3-642-12239-2_11. ISBN 978-3-642-12238-5.

[ogren2-7] Ögren, Petter (2012). "Increasing Modularity of UAV Control Systems using Computer Game Behavior Trees" (PDF). AIAA Guidance, Navigation and Control Conference, Minneapolis, Minnesota. ss. 13-16.

[colledanchise-8] Colledanchise, Michele; Marzinotto, Alejandro; Ögren, Petter (2014). "Performance Analysis of Stochastic BTs" (PDF). Robotics and Automation (ICRA), 2014 IEEE International Conference on. doi:10.1109/ICRA.2014.6907328. 2 Mart 2021 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 23 Haziran 2021.

[marzonotto-9] Marzinotto, Alejandro; Colledanchise, Michele; Smith, Christian; Ögren, Petter (2014). "Towards a Unified BTs Framework for Robot Control" (PDF). Robotics and Automation (ICRA), 2014 IEEE International Conference on.

[Klocker-10] Klöckner, Andreas. "Interfacing BTs with the World Using Description Logic." In AIAA Guidance, Navigation and Control Conference, Boston, MA. 2013.

[Klocker2-11] Klöckner, Andreas (2013). "Behavior Trees for UAV Mission Management". GI-Jahrestagung. ss. 57-68.

[Bagnell-12] Bagnell, J. Andrew; Cavalcanti, Felipe; Cui, Lei; Galluzzo, Thomas; Hebert, Martial; Kazemi, Moslem; Klingensmith, Matthew (2012). "An integrated system for autonomous robotics manipulation" (PDF). Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on. IEEE. ss. 2955-2962. doi:10.1109/IROS.2012.6385888. hdl:20.500.11937/14608. ISBN 978-1-4673-1736-8.

[Millington-13] Millington; Funge (2009). Artificial Intelligence for Games. CRC Press. ISBN 978-0-12-374731-0.

[Rabin-14] Rabin, S. (2014). Game AI Pro. CRC Press. ISBN 978-1-4665-6596-8.

[champandard2012-15] Champandard, Alex J.; Dunstan, Philip (2012). "The Behavior Tree Starter Kit" (PDF). Game AI Pro: Collected Wisdom of Game AI Professionals. ss. 72-92.

[craft_ai-16] raft ai (2015). "BT 101 – Behavior Trees grammar basics". 26 Haziran 2015 tarihinde kaynağından arşivlendi.

[colledanchise2-17] Colledanchise, Michele; Ögren, Petter (2014). "How Behavior Trees Modularize Robustness and Safety in Hybrid Systems" (PDF). In Intelligent Robots and Systems (IROS), 2014 IEEE/RSJ International Conference on. IEEE.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]