행동 트리(인공지능, 로봇 및 제어)

행동 트리는 컴퓨터 과학, 로봇 공학, 제어 시스템, 비디오 게임에 사용되는 계획 실행의 수학적 모델이다. 그들은 모듈형 방식으로 유한한 일련의 작업들 사이의 전환을 설명한다. 이들의 강점은 단순 업무가 어떻게 이행되는지 걱정하지 않고 단순 업무로 구성된 매우 복잡한 업무를 만들 수 있는 능력에서 나온다. 행동 트리는 어떤 행동의 주요 구성 요소가 상태라기보다는 과제라는 핵심적인 차이점을 가진 계층적 상태 기계와 어느 정도 유사성을 나타낸다. 인간의 손쉬운 이해는 행동 트리를 오류 발생 가능성이 적고 게임 개발자 커뮤니티에서 매우 인기가 있다. 행동 트리는 몇 가지 다른 제어 아키텍처를 일반화하는 것으로 나타났다.^[1][2] 수학적으로, 그것들은 순환 그래프에 지시된다.

배경

행동 트리는 비플레이어 캐릭터(NPC)의 행동을 모델링하는 강력한 도구로서 컴퓨터 게임 산업에서 유래한다.^[3][4][5][6] 그들은 헤일로, 바이오쇼크, 스포어 같은 유명 비디오 게임에 널리 사용되어 왔다. 최근 작품들은 행동 트리를 UAV, 복잡한 로봇, 로봇 조작, 다중 로봇 시스템을 위한 다중 임무 제어 프레임워크로 제안하고 있다.^{[7][8][9][10][11][12]} 행동 트리는 이제 유니티(게임 엔진)와 언리얼 엔진(아래 링크 참조)과 같은 일반적인 게임 환경뿐만 아니라 ^[13][14]게임 AI 교과서에서 다루어야 할 성숙기에 도달했다.

행동 트리는 NPC의 행동을 프로그래밍하기만 하면 복잡한 행동을 만들 수 있고, 그 다음에는 (대개 드래그 앤 드롭을 통해) 나뭇잎 노드가 작용이고 내부 노드가 NPC의 의사결정을 결정하는 트리 구조를 설계할 수 있다는 개발 패러다임으로 유명해졌다. 행동 트리는 시각적으로 직관적이고 디자인, 테스트, 디버그가 용이하며, 다른 행동 창조 방법보다 모듈성, 확장성, 재사용성을 더 많이 제공한다.

수년에 걸쳐 다양한 행동 나무의 구현은 사건 중심 행동 나무로 진화하기 전까지 산업의 요구를 충족시키기 위한 효율성과 능력 모두에서 계속 향상되었다.^[15][5] 이벤트 중심 행동 트리는 트리가 내부적으로 실행을 처리하는 방식을 변경하고, 이벤트에 반응하고 실행 노드를 중단할 수 있는 새로운 유형의 노드를 도입함으로써 고전적 행동 트리의 일부 확장성 문제를 해결했다. 오늘날에는 단순성을 위해 여전히 '행동수'라고 불리고 있음에도 불구하고 사건 주도 행동수라는 개념이 표준이고 대부분의 구현에 사용되고 있다.

주요개념

동작 트리는 노드가 루트, 제어 흐름 노드 또는 실행 노드(태스크)로 분류되는 방향 트리로 그래픽으로 표현된다. 연결된 각 노드 쌍에 대해 나가는 노드를 상위 노드라고 하고 들어오는 노드를 하위 노드라고 한다. 루트는 부모가 없고 정확히 하나의 자식을 가지며, 제어 흐름 노드는 하나의 부모와 적어도 하나의 자식을 가지며, 실행 노드는 하나의 부모를 가지며 자식이 없다. 그래픽으로, 제어 흐름 노드의 아이들은 왼쪽에서 오른쪽으로 정렬된 그 아래에 배치된다.^[16]

동작 트리의 실행은 특정 주파수의 틱을 자식에게 보내는 루트부터 시작한다. 체크 표시는 어린이를 실행할 수 있는 활성화 신호다. 동작 트리에서 노드 실행이 허용되는 경우, 실행이 아직 완료되지 않은 경우 실행 중인 상태, 목표를 달성한 경우 성공 또는 그렇지 않은 경우 실패를 부모에게 반환한다.

제어 흐름 노드

제어 흐름 노드는 구성되는 하위 작업을 제어하는 데 사용된다. 제어 흐름 노드는 선택기(낙하) 노드 또는 시퀀스 노드일 수 있다. 그들은 각각의 하위 작업을 차례대로 운영한다. 하위 작업이 완료되어 상태(성공 또는 실패)를 반환하면 제어 흐름 노드가 다음 하위 작업 실행 여부를 결정한다.

선택기(하강) 노드

폴백 노드는 실패하지 않는 첫 번째 아동을 찾아 실행하는 데 사용된다. 폴백 노드는 자식 중 하나가 성공 또는 실행을 반환할 때 성공 또는 실행 상태 코드를 가지고 즉시 반환된다(아래 그림 I 및 유사 코드 참조). 아이들은 중요한 순서대로 왼쪽에서 오른쪽으로 간지럽혀진다.

유사 코드에서 예비 구성의 알고리즘은 다음과 같다.

1부터 n까지 i에 대해 2 do 2 childstatus ← if chick(i) 3 if childstatus = running 4 running 5 if childstatus = success = success 6 return success 7 end 8 return 실패 

시퀀스 노드

시퀀스 노드는 아직 성공하지 못한 첫 번째 아동을 찾아 실행하는 데 사용된다. 시퀀스 노드는 자식 중 하나가 실패 또는 실행을 반환할 때 고장 또는 실행 상태 코드를 사용하여 즉시 반환된다(아래 그림 II 및 유사 코드 참조). 아이들은 왼쪽에서 오른쪽으로 차례차례 체크되어 있다.

유사 코드에서 시퀀스 구성에 대한 알고리즘은 다음과 같다.

1 ~ n의 i에 대해 1 ~ 2 do 2 childstatus ← if chick(i) 3 if childstatus = running 4 returning 5 if childstatus = failure = return fails 7 end 8 return 성공 

수학적 상태 공간 정의

동작 나무의 분석에 제어 이론 도구를 적용하기 위해서는 3투플로 정의할 수 있다.^[17]

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

where ${\displaystyle i\in \mathbb {N} }$ is the index of the tree, ${\displaystyle f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}$ is a vector field representing the right hand side of an ordinary difference equation, ${\displaystyle \Delta t}$ is a time step and ${\displaystyle r_i:{\mathbb{R}}^{}}$${\displaystyle r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}}$ is the return status, that can be equal to either Running ${\displaystyle R_{i}}$, Success ${\displaystyle S_{i}}$, or Failure ${\displaystyle F_{i}}$.

참고: 업무는 부모도 자식도 없는 타락한 행동 나무다.

동작 트리 실행

동작 트리의 실행은 다음과 같은 표준 일반 차이 방정식으로 설명된다.

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

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

여기서 $k{\displaystyle \in }$ ${\displaystyle N\mathbb{}}$ ${\$는) 이산 시간을 나타내며$$, x ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\$은(는) 동작 트리에 의해 모델링된 시스템의 상태 공간이다$$.

시퀀스 구성

두 개의 동작 트리 ${\displaystyle {Ti}_{}}$ ${\$와 ${\displaystyle T_{}}$ j ${\$는 시퀀스 연산자를 사용하여$$ 더욱 복잡한 동작 트리 ${\displaystyle {T\mathrm{}}_{}}$ 0${\$로 구성할 수 있다$$.

${\displaystyle T_{0}={\mbox{sequence}}(T_{i},)T_{j}).}$

${\displaystyle {그런\mathrm{}}_{}}$ 다음 return status $r{\displaystyle {}_{}}$ ${\$과($와{\displaystyle {}_{}}$)$$T 0{\$displaystyle$T_{$0}$과(와) 관련된 벡터 필드 f 0 ${\displaystyle$ $f_{0$$}$을 다음과 같이 정의한다$$(${\displaystyle S_{\mathrm{}}}$ 1 ${\$ {\{$S}}_{1$^{[definition needed]}

${\displaystyle r_{0}(x_{k})={\begin{case}r_{j}(x_{k})&{\text{{{}}인 경우 {}x_{k}\mathcal {S}\}\r_{i}(x_{k})&\text{}.\end{case}}}$

${\displaystyle f_{0}(x_{k})={\begin}f_{j}(x_{k})&{\text{{{}}인 경우 {}x_{k}\mathcal {S}\}\f_{i}(x_{k})&\text{}.\end{case}}}$

참고 항목

• 결정 트리
• 하이브리드 시스템
• 서브섬션 아키텍처

참조

외부 링크

• ROS 동작 트리 라이브러리
• 언리얼 엔진 4 동작 트리 설명서
• AI를 위한 행동 나무: 작동 방식
• 동작 트리: 로봇을 위한 간단하면서도 강력한 AI