Davranış ağacı (yapay zeka, robotik ve kontrol) sayfasının kaynağını görüntüle

{{Öksüz|tarih=Eylül 2022}}
{{DISPLAYTITLE:Davranış ağacı (yapay zeka, robotik ve kontrol)}}
[[Dosya:BT_search_and_grasp.svg|küçükresim|sağ|upright=2.05|{{ortala|İki kollu bir robotun arama ve kavrama planını modelleyen davranış ağacı.}}]]

'''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.<ref name="Colledanchise TRO16">{{Akademik dergi kaynağı |soyadı1=Colledanchise |ad1=Michele |soyadı2=Ögren |ad2=Petter |yıl=2017 |başlık=How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees |dergi=IEEE Transactions on Robotics |cilt=33 |sayı=2 |sayfalar=372-389|doi=10.1109/TRO.2016.2633567 |s2cid=9518238 |url=http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-202922 }}</ref><ref name="Colledanchise BOOK17">{{Kitap kaynağı |soyadı1=Colledanchise |ad1=Michele |soyadı2=Ögren |ad2=Petter |yıl=2018 |arxiv=1709.00084 |başlık=Behavior Trees in Robotics and AI: An Introduction |yayıncı=CRC Press |doi=10.1201/9780429489105 |isbn=978-1-138-59373-2 |s2cid=27470659 }}</ref> Matematiksel olarak [[:en:Directed acyclic graph|yönlendirilmiş dönsüz grafikler]]dir.

== Arka plan ==

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.<ref name="Damian Isla">{{Web kaynağı | soyadı = Isla | ad = D. | tarih = 2005 | url = https://www.gamasutra.com/view/feature/130663/gdc_2005_proceeding_handling_.php | başlık = Handling complexity in the Halo 2 AI | iş = Game Developers Conference (Vol. 12) | arşivurl = https://web.archive.org/web/20120511035851/https://www.gamasutra.com/view/feature/130663/gdc_2005_proceeding_handling_.php | arşivtarihi = 11 Mayıs 2012}}</ref><ref name="Damian Isla2">{{Kitap kaynağı |soyadı=Isla |ad=D. |yıl=2008 |başlık=Halo 3-building a better battle |iş=Game Developers Conference 2008 }}</ref><ref name="agis2020">{{Akademik dergi kaynağı |soyadı1=Agis |ad1=Ramiro A. |soyadı2=Gottifredi |ad2=Sebastian |soyadı3=García |ad3=Alejandro J. |tarih=2020 |başlık=An event-driven behavior trees extension to facilitate non-player multi-agent coordination in video games |url=https://cs.uns.edu.ar/~ragis/Agis%20et%20al.%20(2020)%20-%20An%20event-driven%20behavior%20trees%20extension%20to%20facilitate%20non-player%20multi-agent%20coordination%20in%20video%20games.pdf |dergi=Expert Systems with Applications |cilt=155 |sayı=1 |sayfa=113457 |doi=10.1016/j.eswa.2020.113457 |erişimtarihi=23 Haziran 2021 |arşivurl=https://web.archive.org/web/20200726020620/https://cs.uns.edu.ar/~ragis/Agis%20et%20al.%20(2020)%20-%20An%20event-driven%20behavior%20trees%20extension%20to%20facilitate%20non-player%20multi-agent%20coordination%20in%20video%20games.pdf |arşivtarihi=26 Temmuz 2020 |ölüurl=hayır }}</ref><ref name="lim">{{Kitap kaynağı |soyadı1=Lim |ad1=C. U. |soyadı2=Baumgarten |ad2=R. |soyadı3=Colton |ad3=S. |yıl=2010 |bölümurl=http://ccg.doc.gold.ac.uk/wp-content/uploads/2016/10/lim_evogames10.pdf |bölüm=Evolving behaviour trees for the commercial game DEFCON |başlık=Applications of Evolutionary Computation |sayfalar=100-110|yayıncı=Springer |yer=Berlin |isbn=978-3-642-12238-5 |doi=10.1007/978-3-642-12239-2_11 }}</ref> 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.<ref name="ogren2">{{Kitap kaynağı |soyadı=Ögren |ad=Petter |bölümurl=https://www.csc.kth.se/~petter/Publications/ogren2012bt.pdf |bölüm=Increasing Modularity of UAV Control Systems using Computer Game Behavior Trees |başlık=AIAA Guidance, Navigation and Control Conference, Minneapolis, Minnesota |sayfalar=13-16|yıl=2012 }}</ref><ref name="colledanchise">{{dergi kaynağı |soyadı1=Colledanchise |ad1=Michele |soyadı2=Marzinotto |ad2=Alejandro |soyadı3=Ögren |ad3=Petter |url=https://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/ICRA14_cmo_final.pdf |başlık=Performance Analysis of Stochastic BTs |dergi=Robotics and Automation (ICRA), 2014 IEEE International Conference on |tarih=2014 |doi=10.1109/ICRA.2014.6907328 |s2cid=14719083 |erişimtarihi=23 Haziran 2021 |arşivurl=https://web.archive.org/web/20210302235032/https://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/ICRA14_cmo_final.pdf |arşivtarihi=2 Mart 2021 |ölüurl=hayır }}</ref><ref name="marzonotto">{{Kitap kaynağı |soyadı1=Marzinotto |ad1=Alejandro |soyadı2=Colledanchise |ad2=Michele |soyadı3=Smith |ad3=Christian |soyadı4=Ögren |ad4=Petter |bölümurl=https://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/2013_ICRA_mcko.pdf |bölüm=Towards a Unified BTs Framework for Robot Control |başlık=Robotics and Automation (ICRA), 2014 IEEE International Conference on |tarih=2014 }}</ref><ref name="Klocker">Klöckner, Andreas. "Interfacing BTs with the World Using Description Logic." In AIAA Guidance, Navigation and Control Conference, Boston, MA. 2013.</ref><ref name="Klocker2">{{Kitap kaynağı |soyadı=Klöckner |ad=Andreas |bölüm=Behavior Trees for UAV Mission Management |başlık=GI-Jahrestagung |sayfalar=57-68|yıl=2013 }}</ref><ref name="Bagnell">{{Kitap kaynağı |soyadı1=Bagnell |ad1=J. Andrew |ad2=Felipe |soyadı2=Cavalcanti |ad3=Lei |soyadı3=Cui |ad4=Thomas |soyadı4=Galluzzo |ad5=Martial |soyadı5=Hebert |ad6=Moslem |soyadı6=Kazemi |ad7=Matthew |soyadı7=Klingensmith |yazarlarıgöster=3 |bölümurl=https://espace.curtin.edu.au/bitstream/handle/20.500.11937/14608/193059_193059.pdf?sequence=2 |bölüm=An integrated system for autonomous robotics manipulation |başlık=Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on |sayfalar=2955-2962|yayıncı=IEEE |yıl=2012 |doi=10.1109/IROS.2012.6385888 |hdl=20.500.11937/14608 |isbn=978-1-4673-1736-8 |s2cid=419179 }}</ref> Davranış ağaçları artık Game AI ders kitaplarında<ref name="Millington">{{Kitap kaynağı|başlık=Artificial Intelligence for Games|url=https://archive.org/details/artificialintell0000mill|yayıncı=CRC Press|yıl=2009|isbn=978-0-12-374731-0|soyadı1=Millington|soyadı2=Funge}}</ref><ref name="Rabin">{{Kitap kaynağı|başlık=Game AI Pro|yayıncı=CRC Press|yıl=2014|isbn=978-1-4665-6596-8|ad=S.|soyadı=Rabin}}</ref> 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.<ref name="agis2020" /><ref name="champandard2012">{{Kitap kaynağı |ad1=Alex J. |soyadı1=Champandard |ad2=Philip |soyadı2=Dunstan |bölümurl=http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter06_The_Behavior_Tree_Starter_Kit.pdf |bölüm=The Behavior Tree Starter Kit |başlık=Game AI Pro: Collected Wisdom of Game AI Professionals |sayfalar=72-92|yıl=2012 }}</ref> 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 ==

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.<ref name="craft ai">{{Web kaynağı | yazar = craft ai | tarih = 2015 | url = http://www.craft.ai/blog/bt-101-behavior-trees-grammar-basics/ | başlık = BT 101 – Behavior Trees grammar basics | arşivurl = https://web.archive.org/web/20150626062043/http://www.craft.ai/blog/bt-101-behavior-trees-grammar-basics/ | arşivtarihi = 26 Haziran 2015}}</ref>

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ü ===

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 ====

[[Dosya:Fallback in Behavior tree.png|küçükresim|sağ|{{ortala|Şekil I. N görevin bir geri dönüş bileşiminin grafiksel gösterimi.}}]]

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ü ====

[[Dosya:Sequence composition in behaviour trees.png|küçükresim|sağ|{{ortala|Şekil II. N görevin bir dizi bileşiminin grafiksel gösterimi.}}]]
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ı ==

Davranış ağaçlarının analizine kontrol teorisi araçlarını uygulamak için, üçlü grup olarak tanımlanmaktadır.<ref name="colledanchise2">{{Kitap kaynağı |soyadı1=Colledanchise |ad1=Michele |soyadı2=Ögren |ad2=Petter |bölümurl=https://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/IROS14_CO.pdf |bölüm=How Behavior Trees Modularize Robustness and Safety in Hybrid Systems |başlık=In Intelligent Robots and Systems (IROS), 2014 IEEE/RSJ International Conference on |yayıncı=IEEE |yıl=2014 }}</ref>

<math>
 T_i=\{f_i,r_i, \Delta t\}, 
</math>

* <math> i\in \mathbb{N}</math> ağacın indeksidir.
* <math>f_i: \mathbb{R}^n \rightarrow  \mathbb{R}^n</math> adi fark denkleminin sağ tarafını temsil eden bir vektör alanıdır.
* <math>\Delta t</math> bir zaman adımıdır.
* <math>r_i: \mathbb{R}^n \rightarrow  \{R_i,S_i,F_i\}</math> iade durumudur.
* Çalışma <math>R_i</math>,
* Başarı <math>S_i</math>, 
* Başarısızlık <math>F_i</math> dır.

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

=== Davranış ağacı yürütme ===

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

<math>x_{k+t}(t_{k+1})=f_i( x_{k}(t_{k}))  </math>

<math>t_{k+1}=t_{k}+\Delta t </math>

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

=== Sıra kompozisyonu ===

İki karar ağacı  "<math>T_i</math> ve <math>T_j</math>" bir Sıra operatörü kullanılarak daha karmaşık bir davranış ağacı <math>T_0</math> olarak oluşturulabilir.

<math>T_0=\mbox{sıra}(T_i,T_j).</math>

Ardından dönüş durumu ve <math>T_0</math> ile ilişkili vektör alanı <math>f_0</math> aşağıdaki gibi tanımlanmaktadır:

<math>
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}
</math>

<math>
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}
</math>

== Ayrıca bakınız ==
* [[Karar ağacı]]
* [[Hibrit sistem]]
* [[Kapsama mimarisi]]

== Kaynakça ==
{{Kaynakça}}

== Dış bağlantılar ==
* {{Web kaynağı|url=https://wiki.ros.org/behavior_tree|başlık=ROS davranış ağacı kitaplığı|arşivurl=https://web.archive.org/web/20210624200543/https://wiki.ros.org/behavior_tree |arşivtarihi=24 Haziran 2021 }}
* {{Web kaynağı|url=https://docs.unrealengine.com/en-US/Engine/AI/BehaviorTrees/index.html|başlık=Unreal Engine 4 davranış ağacı belgeleri|arşivurl=https://web.archive.org/web/20201112000031/https://docs.unrealengine.com/en-US/Engine/AI/BehaviorTrees/index.html |arşivtarihi=12 Kasım 2020 }}
* {{Web kaynağı|url=https://outforafight.wordpress.com/2014/07/15/behaviour-behavior-trees-for-ai-dudes-part-1/|başlık=AI için davranış ağaçları: Nasıl çalışırlar?|arşivurl=https://web.archive.org/web/20190506153550/https://outforafight.wordpress.com/2014/07/15/behaviour-behavior-trees-for-ai-dudes-part-1/ |arşivtarihi=6 Mayıs 2019 }}
* {{Web kaynağı|url=https://www.pirobot.org/blog/0030/|başlık=Davranış Ağaçları: Robotunuz için Basit ama Güçlü Yapay Zeka|arşivurl=https://web.archive.org/web/20200225163905/http://www.pirobot.org/blog/0030/ |arşivtarihi=25 Şubat 2020 }}

{{Otorite kontrolü}}

[[Kategori:Otomat teorisi]]
[[Kategori:Hesaplama modelleri]]
[[Kategori:Sayısal elektronik]]
<!--[[Kategori:Robot control]]
[[Kategori:Automated planning and scheduling]]
[[Kategori:Visual programming]]-->