Behavior Tree :: Subsumption Architecture, Teleo-Reactive, Decision Trees

Behavior Tree의 디자인 형식에 대해 알아보기 전에 behavior 과 관련 된 로봇 프로그래밍 아키텍쳐에 대해서 알아보도록 하자. 참고한 논문과 책에서는 크게 3가지(Subsumption Architecture, Teleo-Reactive, Decision Trees)를 다루고 있다. 이들을 이제부터 SA, TR, DT라고 부르기로 하자.

 

Subsumption Architecture

SA는 용어 그대로 계층적인 구조의 아키텍쳐이다. 발표 된 논문에 나온 예시를 사용하면서 설명해보자. 아주 간단한 로봇이 있다. 이 로봇의 SA 최하위 계층에는 음파 탐지기를 이용해 장애물을 탐지하고 장애물을 피하는 작업이 있다 (Obstacle Avoidance). 그 위 계층에는 무작위로 로봇을 움직이게 하는 작업이 있다. 무작위로 움직이는 목적은 벡터 덧셈을 통해 장애물을 피하는 계층을 포섭(Subsumption)하게 된다. 가장 최상위 계층에는 로봇이 특정 장소를 찾도록 하는데, 중간 계층은 무시되도 최하위 계층인 장애물 회피 계층과는 연관되어 움직이게 된다. 결국 최하위 계층이 가장 우선시 되는 형태로 다른 계층들도 로봇을 작동시키게 된다. 로봇 뿐만 아니라 real time AI에도 사용됐다고 한다.

​

SA은 매우 쉽게 개발할 수 있고, 모듈화도 가능하며 계층 구조도 가지고 있지만 단점도 명확히 존재한다.

시스템 자체의 크기를 키우는 게 어렵다. 매우 복잡하고 다양한 행동들이 있을 경우 시스템을 구축하는 데 어려움이 있고, 구조적으로 한계가 있기 때문에 각 계층의 컨트롤러를 추가하거나 옮기기가 매우 어렵다.

BT로 SA 구조를 표현할 수 있다. Fallback node를 이용해서 SA구조를 직관적으로 BT형태로 매핑할 수 있다. 계층 구조 형태로 진행되던 SA를 Fallback ( Selector, Priority)노드를 이용하여 특정 Controller를 실행하고, 나머지는 실행하지 않는 형태로 구성하면 된다.

Teleo-Reactive programs

Teleo-Reactive programs, 이하 TR은 에이전트가 목적을 달성하는 방향으로 액션을 취하는 방식을 말한다. TR program은 지속적으로 주변 환경을 관찰하고 그에 반응하여 행동을 취하며 목적을 달성하게 하는 프로그램이다. 주변 환경과 취할 액션 간의 조합의 집합으로 이루어져 있고 이는 목적을 달성하기 위해 진행 된다. 주변 환경을 계속 확인하기 때문에 문제가 생길 경우 특정 하위 작업들을 중단하기도 한다.

​

TR의 장점은 반응이 좋은 실행성이다. 주변 환경을 계속 확인하기 때문에 반응성이 당연히 좋다. 또한 작은 문제에는 조건-액션 형태를 직관적으로 만들 수 있다. 다만, 단점은 SA와 동일하게 한가지 기능을 지우거나 추가하기가 매우 어렵고, Saferty나 Failer 테스트를 하기 위해서는 모든 액션마다 테스트를 해줘야 한다.

How Behavior Trees generalize the Teleo-Reactive paradigm and And-Or-Trees

TR의 연속적으로 환경을 확인하고 그게 맞는 조건 - 액션을 하게 하기 위해서 BT에서는 Fallback 노드를 사용하고, 그 밑에 조건 - 액션을 넣는다. 이를 통해서 기본 TR을 BT 형태로 손쉽게 바꿀 수 있다.

Decision Trees

의사 결정 트리로 불리는 DT다. 의사 결정을 내리는 데 사용 되는 단서를 if-then으로 엮어 트리를 만드는 형태이다. 쉽게 말해서 특정 행동에 따른 패턴을 규칙의 조합으로 바꾸는 것을 말한다. 마지막 leaf node는 결정, 결말, 액션등을 표현하게 되고 lead가 아닌 node인 intermediate node의 경우 행동의 예측을 나타내게 된다.

​

DT를 BT로 바꾸는 작업을 단순히 행동에 대한 예측 node를 조건으로 만들고 leaf들을 running 되도록 하면 된다. 결정 노드의 경우는 모두 작은 형태의 BT로 바꾸면 된다. DT의 단점은 action에 대한 정보 흐름이 없다는 것인데, BT의 leaft들을 running을 반환하는 형태로 만들면서 정보 흐름을 만들게 된다. (running을 return 한다는 부분이 잘 이해가 되진 않는다)

​

이번글에서는 간단하게 SA, TR, DT를 알아봤다. 다음 글에서는 BT에 대해서 조금 더 자세히 알아보도록 하자.

​

​

​

참고자료

​

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=devdeepblue&logNo=220289804924

https://www.youtube.com/watch?v=hAPcwKrmRHE

https://www.youtube.com/watch?v=YWyXNpTx_aI

https://www.behaviortree.dev/docs/nodes-library/fallbacknode/

https://teleoreactiveprograms.net/

https://www.semanticscholar.org/paper/How-Behavior-Trees-generalize-the-Teleo-Reactive-Colledanchise-%C3%96gren/dca653b30b05116a9ba2725a6c2e13333c4f7907