Behavior Tree :: FSM과 BT의 차이점

BT는 Mobile robot에는 꽤 많이 사용되고 있는 것 같다. BT Navigator가 최근에 업데이트 되고 있는 걸 볼 수 있다.

이런 동향을 조금 더 파악하고, 로봇 팔과 모바일 로봇 팔에서 적용해볼 수 있는 가능성에 대해 회사에서 이야기했다.

이야기를 하다보니 FSM과 BT에 대해 조금 더 깊은 이해가 필요할 것 같아서 정리해보려 한다.

BT란?

 

출처 :  Behavior Trees in Robotics and AI: An Introduction

아마도 BT를 가장 잘 아는 사람들은 게임 업계 개발자분들 일것이다. BT는 자율적인 에이전트(agent)가 다른 일(Task)들을 바꾸는 방법을 구조화 하는 것을 말한다. 간단한 Pick and Place 구조를 위 그림에서 확인할 수 있다. BT의 가장 중요한 장점은 modular와 reactive이다.

​

BT의 초기 발명은 게임에 존재하는 NPC들의 모듈성을 높이기 위해서였다. 모듈성을 높인다는 것은 코드의 재사용성을 높인다는 뜻이고 함수의 디자인을 최적화하며 테스트 효율을 높인다는 뜻이 된다. BT의 가장 큰 장점이라면 각각의 개별적인 행동들이 다른 형태의 상위 행동을 위한 행동에서 다시 사용될 수 있다는 것이다(재사용성, 모듈화의 장점)

​

추가적으로 BT를 구성한다는 것은 비전문가가 특정 행동을 할 수 있도록 프로그래밍을 할 수 있다는 것이다. 최근 ChatGPT를 이용한 Prompt 기반 행동 실행 또한 다양한 행동 API를 이용한 BT를 구성한다고 볼 수도 있겠다.

 

FSMs의 문제는?

 

그렇다면 고전적으로 사용하던 Finite state machines의 문제점을 뭐였을까?

자율 에이전트는 변화에 대한 빠르고 효율적으로 변화할 수 있는 능력과 모듈성이 필요하다. 예를 들어 우리는 로봇이 자율주행 도중 계획 된 경로에 사람 혹은 물체가 들어올 경우 빠르게 변화했으면 싶어한다(reactive). 또한 특정 행동에 사용 됐던 행동을 재사용해서 다른 행동도 쉽게 만들기를 원한다. 매번 다양한 행동에 대한 코드를 작성할 수는 없는 노릇이기 때문이다(modular). 거기에 새로운 기능을 만들었을 때 오롯이 그 기능한 테스트하기를 원한다(test efficent).

​

이런 관점에서 FSMs가 한계가 있었는데 이는 초기 프로그래밍 언어에서 사용된 전형적인 Goto-statement 때문이다. Goto-statement는 "단방향 제어 전달(one-way control transfers)" 방식을 말한다. state로 가다, 즉 특정 state에서 다른 state로 이동하여 계속 실행된다는 뜻이다. 그것도 단방향으로만. 최근 프로그래밍의 경우에는 "양방향 제어 전달(two-way control transfers)"을 사용한다. 이는 특정 프로그램에서 실행되어 특정 부분의 코드로 넘어간 후 실행한 후 다시 원래 코드 부분으로 돌아와 계속 실행되는 것을 말한다.

​

FSMs의 경우 one-way control transfer 형태로서, 시스템 혹은 에이전트가 반응하기 위해서는 state 간에 너무 많은 이동이 있어야하고, 이는 너무 많은 one-way control transfer이 많아진다는 것이다. 만약 하나의 state가 빠지게 되면 모든 state의 연결성이 변경되어야 한다는 치명적인 단점이 있다. 또한 당연하게도 하나의 state가 추가 되면 다양한 state에서도 추가 된 state로 이동하는 one-way control transfer를 모두 만들어줘야 한다. (엄청만 복잡도의 증가) 이런 문제점을 해결하기 위해 새롭게 나온 것이 HFSMs(Hierachical Finite State Machines)이다.

HFSMs과 문제점

 

출처 :  Behavior Trees in Robotics and AI: An Introduction

HFSMs(Hierachical Finite State Machines)은 State Charts라고도 불린다. FSMs의 단점을 보안하여 나온 방법론이다. HFSMs에서는 하나의 state가 하나 이상의 state를 포함할 수 있게 된다. 2개 이상을 포함하는 state를 suprestate라고 하는데, 일반적으로 state간의 전이는 superstate간의 전이가 된다. 즉 superstate간의 전이만 생각하면 된다는 뜻이다.

당연하게도 장점은 모듈성이 좋아지고 substate가 superstate를 상속할 수 있게 되는 Behavior inheritance라는 장점이 생긴다. 단점의 경우로는 아직도 유지보수의 관점에서는 해야할 일이 많고, 계층 구조적인 방식을 도입했지만 이 계층 또한 개발자가 하나씩 구조를 짜줘야한다. 구조가 추가 됨으로서 좋아진 건 맞지만 state가 늘어나면 복잡도가 증가하는 건 마찬가지다.

HFSMs,  출처 :  Behavior Trees in Robotics and AI: An Introduction

 

BT ,  출처 :  Behavior Trees in Robotics and AI: An Introduction

동일한 Behavior에서 HFSMs의 경우 각 전이에 대한 명제 (참, 거짓)을 정의해줄 필요가 있다. 또한 HFSMs의 경우 계층적 구조를 명시적으로 설정해줘야 하지만 BT의 subtree의 경우 각각이 하나의 모듈이 되는 형태가 된다. BT와 반대로 HFSMs의 경우 sub-HFSMs가 있긴 하지만 그 안에서도 다수의 전이를 관리해줄 필요가 있기 때문에 유지보수가 좋지 않다.

 

BT의 단점은?

 

BT의 장점은 모듈성과 계층적 정리, 코드 재사용성, 반응성, 가독성 등이 있다 그렇다면 단점은 무엇일까?

BT 엔진을 사용하기가 처음에는 어렵고 (다만, 한번 해두면 쉽게 재사용할 수 있다) 모든 조건을 확인해야하는 경우에는 리소스가 많이 들어갈 수 있다. 또한 FSM과 다른 방식으로 접근하여 디자인을 해야해서 처음에는 어려움이 있을 수 있다. 마지막으로는 덜 성숙된 분야라 사용할 수 있는 소프트웨어가 한정적이다.

​

단점들의 자세한 내용은 2탄에서 정리하면서, 디자인 원칙에 대해서 이야기해보도록 하겠다.

​

​

​

참고자료

https://arxiv.org/abs/1709.00084

https://www.ri.cmu.edu/pub_files/2012/10/IROS12_1059_FI.pdf

https://github.com/ros-planning/navigation2/tree/main/nav2_bt_navigator