ROS2 - Behavior Tree

📜 주제

Behavior Tree에 대해서 알아보자

💡 기존 FSM의 문제

로봇은 주변 상황에 대해 빠르고 효율적으로 인지하고 상태를 바꿔야 한다. 만약 사람이나 장애물이 나타나게된다면 로봇은 방향을 바꾸거나 멈추거나 조치를 취해야 한다.
FSM은 태스크 스위칭 구조로 많은 세월동안 사용되왔다. 하지만 FSM은 reactivity와 modularity에 대해서 trade off가 발생했다.
또한 FSM은 one-way control transfer다. FSM에서 많이 사용하는 Goto 상태문은 one-way control transfer로 불리는 예제중 하나다. 프로그램이 다른 코드의 프로그램으로 점프하면서 실행하는 방법으로 원시적이면서 프로그램의 이해를 망치는 요인 중 하나가되고 상태가 복잡해질수록 상태또한 복잡해지고 코드 또한 복잡해지게 된다. BT는 two-way control transfers로써 트리의 내부 노드에 의해 통제되므로 BT를 쓰는것이 더욱 효율적으로 상태를 관리할 수 있다.

✏️ Behavior Tree란?

1) BT 컨셉
BT는 internal 노드가 제어 흐름 노드이며 leaf 노드는 실행 노드를 가지는 directed rooted tree이다. 기존 트리에서 사용하는 parent와 child 개념또한 적용시킬 수 있다.
root 노드는 부모가 없는 유일한 노드이며 다른 노드들은 하나의 부모가 있고 제어 흐름 노드는 하나 이상의 child를 가진다.

BT는 루트노드부터 시작해 자식노드를 하나씩 순회하면서 execution을 실행할건지 말건지 signal을 보내는데 이를 tick이라하며 초당 몇번을 tick할껀지 정해준다. 노드는 tick을 받으면 실행하고 tick을 받지 않으면 실행하지 않는다. child는 실행 즉시 running상태를 부모에게 보내며 작업이 성공하면 success를 보내고 작업이 실패하면 failure 상태를 보낸다.

2) 제어 흐름 노드와 실행 노드
제어 흐름 노드는 sequence, fallback, parallel, decorator로 크게 4가지로 나뉜다.
실행 노드는 action과 condition으로 크게 2가지로 나뉜다.

Sequence노드는 자식들의 왼쪽부터 tick을 보내는데 자식이 failure 또는 running을 보내면 그대로 자신의 부모에게 failure 또는 running을 보낸다. 즉, 왼쪽부터 차례대로 tick을 보내는데 success가 발생하면 다음 child로 진행되고 만약 failure나 running을 반환하면 더이상 다른 자식에게 tick을 보내지 않고 자신의 부모로 그에 해당하는 값을 보낸다는 것이다. 모든 자식이 success라면 부모에게 success를 보내게 된다.

Fallback 노드는 자식들의 왼쪽부터 tick을 보내는데 자식이 Success 또는 Running을 보내면 그대로 자신의 부모에게 success 또는 running을 보낸다. 즉, 왼쪽부터 차례대로 tick을 보내는데 failure가 발생하면 다음 child로 진행되고 만약 success나 running을 반환하면 더이상 다른 자식에게 tick을 보내지 않고 자신의 부모로 그에 해당하는 값을 보낸다는 것이다. 모든 자식이 failure라면 부모에게 failure를 보내게 된다.

Parallel 노드는 모든 자식에게 tick을 보낸다. 그리고 M개의 자식들이 Success를 보내면 Success가 되고 N-M+1개의 자식들이 failure를 보내면 failure가 된다. 여기서 N은 자식들의 개수이고 M은 문턱값이 된다. 만약 M <= N이라면 running상태가 된다.

Action 노드는 명령을 실행한다. 예를 들어 목표지점으로 이동이라거나 도킹이라거나 자동문 열기 등 특정 행동을 뜻한다. 이 노드는 명령이 성공했을때 Success를 보내고 명령이 실패하면 failure를 보낸다. 명령이 실행중이라면 running을 보내게 된다.

Condition 노드는 현재 상태를 확인하고 Success 또는 Failure를 보내게된다. 이 때 주의할 점은 running상태가 없다는 것이다. 적절히 어떤 변수나 로봇의 상태를 체크하는 방법으로 사용가능할 것 같다.

Decorator 노드는 하나의 자식과 함께하는 제어 흐름 노드이다. 데코레이터 노드는 자식 노드가 응답하는 것에 대해서 특정 규칙같은걸 추가해줄 수 있다. 예를 들어 자식 노드가 N번 실패할 때 Failure를 반환한다던가 자식 노드가 T초안에 Success를 반환 안한다던가 사용자 입맛에 맞는 제어흐름노드를 만들 수 있다.

BT의 예로는 다음과 같다.

🤔 정리 및 참고 문서

여기까지가 내가 읽은 책의 16페이지 내용이다.
총 챕터 3까지 정리하고 읽을 것이며 다음에는 팩맨을 예를 들어 BT를 구성해볼 것이다.

Book: Behavior Trees in Robotics and AI.
Author: Michele Colledanchise and Petter Ogren from Cornell University
Url: https://arxiv.org/abs/1709.00084v4