Drzewo zachowań (sztuczna inteligencja, robotyka i kontrola) - Behavior tree (artificial intelligence, robotics and control)

Drzewo zachowanie jest model matematyczny z planem realizacji stosowanego w informatyce , robotyce , systemów sterowania i gier wideo . Opisują przełączanie między skończonym zbiorem zadań w sposób modułowy. Ich siła tkwi w umiejętności tworzenia bardzo złożonych zadań złożonych z prostych zadań, bez martwienia się o to, jak te proste zadania są realizowane. Drzewa zachowań wykazują pewne podobieństwa do hierarchicznych maszyn stanów, z tą kluczową różnicą, że głównym elementem konstrukcyjnym zachowania jest zadanie, a nie stan. Łatwość zrozumienia przez ludzi sprawia, że ​​drzewa zachowań są mniej podatne na błędy i bardzo popularne w społeczności twórców gier. Wykazano, że drzewa zachowań uogólniają kilka innych architektur sterowania. Matematycznie są to skierowane grafy acykliczne .

Drzewo zachowań modelujące plan poszukiwania i chwytania dwurękiego robota.

Tło

Drzewa zachowań wywodzą się z branży gier komputerowych jako potężne narzędzie do modelowania zachowania postaci niezależnych (NPC). Były szeroko stosowane w głośnych grach wideo, takich jak Halo , Bioshock i Spore . Ostatnie prace proponują drzewa zachowań jako ramy kontroli wielu misji dla UAV , złożonych robotów, manipulacji robotami i systemów wielorobotowych. Drzewa zachowań osiągnęły już dojrzałość, którą można znaleźć w podręcznikach Game AI, a także w ogólnych środowiskach gier, takich jak Unity (silnik gry) i Unreal Engine (patrz linki poniżej).

Drzewa zachowań stały się popularne ze względu na swój paradygmat rozwoju: możliwość tworzenia złożonego zachowania jedynie poprzez programowanie działań NPC, a następnie projektowanie struktury drzewa (zwykle poprzez przeciąganie i upuszczanie ), której węzły liści są działaniami i których węzły wewnętrzne determinują podejmowanie decyzji przez NPC. Drzewa zachowań są wizualnie intuicyjne i łatwe w projektowaniu, testowaniu i debugowaniu oraz zapewniają większą modułowość, skalowalność i możliwość ponownego użycia niż inne metody tworzenia zachowań.

Z biegiem lat różnorodne implementacje drzew zachowań poprawiały się zarówno pod względem wydajności, jak i możliwości w celu zaspokojenia wymagań branży, aż przekształciły się w drzewa zachowań oparte na zdarzeniach . Drzewa zachowań sterowane zdarzeniami rozwiązały niektóre problemy ze skalowalnością klasycznych drzew zachowań, zmieniając sposób, w jaki drzewo obsługuje wewnętrznie ich wykonywanie, oraz wprowadzając nowy typ węzła, który może reagować na zdarzenia i przerywać uruchomione węzły. W dzisiejszych czasach koncepcja drzewa zachowań sterowanego zdarzeniami jest standardem i jest używana w większości implementacji, mimo że dla uproszczenia nadal nazywa się je „drzewami zachowań”.

Kluczowe idee

Drzewo zachowań jest graficznie reprezentowane jako drzewo ukierunkowane, w którym węzły są klasyfikowane jako główne, węzły przepływu sterowania lub węzły wykonania (zadania). Dla każdej pary połączonych węzłów węzeł wychodzący nazywa się rodzicem, a węzeł przychodzący nazywa się dzieckiem. Korzeń nie ma rodziców i dokładnie jednego dziecka, węzły przepływu sterowania mają jednego rodzica i co najmniej jedno dziecko, a węzły wykonania mają jednego rodzica i nie mają dzieci. Graficznie, dzieci węzła przepływu sterowania są umieszczone poniżej niego, uporządkowane od lewej do prawej.

Wykonanie drzewa zachowań zaczyna się od korzenia, który wysyła do swojego dziecka tiki z określoną częstotliwością. Tik jest sygnałem umożliwiającym egzekucję dziecka. Gdy wykonanie węzła w drzewie zachowań jest dozwolone, zwraca on rodzicowi status uruchomiony, jeśli jego wykonanie jeszcze się nie zakończyło, sukces, jeśli osiągnął swój cel, lub niepowodzenie w przeciwnym razie.

Węzeł przepływu sterowania

Węzeł przepływu sterowania służy do sterowania podzadaniami, z których się składa. Węzeł przepływu sterowania może być węzłem selektora (zastępczego) lub węzłem sekwencji. Wykonują kolejno każde ze swoich podzadań. Gdy podzadanie zostanie zakończone i zwróci swój status (powodzenie lub niepowodzenie), węzeł przepływu sterowania decyduje, czy wykonać następne podzadanie, czy nie.

Węzeł selektora (zastępczy)

Rysunek I. Graficzna reprezentacja awaryjnej kompozycji N zadań.

Węzły rezerwowe są używane do znalezienia i wykonania pierwszego dziecka, które nie zawodzi. Węzeł awaryjny zwróci natychmiast kod statusu powodzenia lub uruchomienia, gdy jedno z jego dzieci zwróci sukces lub działa (patrz rysunek I i pseudokod poniżej). Dzieci są zaznaczone w kolejności ważności, od lewej do prawej.

W pseudokodzie algorytm dla kompozycji zastępczej to:

1 for i from 1 to n do
2     childstatus ← Tick(child(i))
3     if childstatus = running
4         return running
5     else if childstatus = success
6         return success
7 end
8 return failure

Węzeł sekwencji

Rysunek II. Graficzna reprezentacja kompozycji sekwencji N zadań.

Węzły sekwencji służą do znalezienia i wykonania pierwszego dziecka, które jeszcze się nie powiodło. Węzeł sekwencji zwróci natychmiast kod stanu niepowodzenia lub uruchomienia, gdy jedno z jego dzieci zwróci błąd lub działa (patrz Rysunek II i pseudokod poniżej). Dzieci są zaznaczone w kolejności od lewej do prawej.

W pseudokodzie algorytm kompozycji sekwencji to:

1 for i from 1 to n do
2     childstatus ← Tick(child(i))
3     if childstatus = running
4         return running
5     else if childstatus = failure
6         return failure
7 end
8 return success

Matematyczna definicja przestrzeni stanów

W celu zastosowania narzędzi teorii sterowania do analizy drzew behawioralnych można je zdefiniować jako trzykrotne.

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

gdzie jest indeksem drzewa, jest polem wektorowym reprezentującym prawą stronę zwykłego równania różnicowego, jest krokiem czasowym i statusem zwracanym, który może być równy Running , Success lub Failure . ${\ Displaystyle i \ w \ mathbb {N}}$${\ Displaystyle f_ {i}: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R} ^ {n}}$${\ Displaystyle \ Delta t}$${\ Displaystyle R_ {i}: \ mathbb {R} ^ {n} \ rightarrow \ {R_ {i}, S_ {i}, F_ {i} \}}$${\displaystyle R_{i}}$${\displaystyle S_{i}}$${\ Displaystyle F_ {i}}$

Uwaga : zadanie jest zdegenerowanym drzewem zachowań bez rodzica i dziecka.

Wykonanie drzewa zachowań

Wykonanie drzewa zachowań jest opisane następującymi standardowymi równaniami różnicowymi zwyczajnymi:

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

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

gdzie reprezentuje czas dyskretny i jest przestrzenią stanów systemu modelowaną przez drzewo zachowań. ${\ Displaystyle k \ w \ mathbb {N}}$${\ Displaystyle x \ w \ mathbb {R} ^ {n}}$

Kompozycja sekwencji

Dwa drzewa zachowań i można je skomponować w bardziej złożone drzewo zachowań za pomocą operatora Sequence. ${\displaystyle T_{i}}$${\displaystyle T_{j}}$${\displaystyle T_{0}}$

${\ Displaystyle T_ {0}= {\ mbox {sekwencja}} (T_ {i}, T_ {j}).}$

Następnie status powrotu i związane z nim pole wektorowe są definiowane (dla ) w następujący sposób: ${\displaystyle r_{0}}$${\displaystyle f_{0}}$${\displaystyle T_{0}}$${\displaystyle {\mathcal {S}}_{1}}$

${\ Displaystyle r_ {0} (x_ {k}) = {\ zacząć {przypadki} r_ {j} (x_ {k}) i {\ tekst {jeśli}} x_ {k} \ w {\ mathcal {S} }_{1}\\r_{i}(x_{k})&{\text{ inaczej }}.\end{przypadki}}}$

${\ Displaystyle f_ {0} (x_ {k}) = {\ zacząć {przypadki} f_ {j} (x_ {k}) i {\ tekst {jeśli}} x_ {k} \ w {\ mathcal {S} }_{1}\\f_{i}(x_{k})&{\text{ inaczej }}.\end{przypadki}}}$

Zobacz też

• Drzewo decyzyjne
• System hybrydowy
• Architektura subsumpcji

Bibliografia

Zewnętrzne linki

• Biblioteka drzewa zachowań ROS
• Dokumentacja drzewa zachowania Unreal Engine 4
• Drzewa zachowań dla AI: jak działają
• Drzewa zachowań: prosta, ale potężna sztuczna inteligencja dla twojego robota