서문
최근 F/TPS 게임에서 AI 팀의 개별 AI 행위 조직화는 가장 중요한 이슈중 하나이다.
예를 들어, 하프라이프에서 기억에 남는 장면으로 회자되는 것 중 하나는 주인공과 해병대간 총격전이다.
적 해병대원들은 싱글 캠페인 중 엄호하고, 측면으로 돌아가거나 엄폐하는 행동들을 했다.
비록 총격전이 벌어진 곳에서 시나리오의 특수한 상황에 맞게 하드코딩 되었으나,
NPC간 조직화된 행동의 임팩트를 충분히 보여줬었다.
이러한 성공에도 불구하고, 팀 조직화는 많은 노력을 필요로 한다.
지금껏은 대부분 상당히 정교하고 복잡한 FSM으로 제작되어 왔지만,
최근에는 Goal-Oriented Action Planning (GOAP)이 새로운 패러다임으로 제시되고 있다.
GOAP는 캐릭터가 "무엇을" "어떻게" 해야하는지 결정할 수 있는 의사결정의 요구에 의해 생겨났다.
FSM에 비해, GOAP로 작성된 AI는 대처한 상황에서의 대안(alternative solution)을 찾아낼 수 있고,
개발 단계에서는 미쳐 생각하지 못했던 문제들을 독립적으로 해결할 수 있다.
이제부터 team-based strategy를 작성하기 위해, GOAP를 HTN으로 확장시켜보려고 한다.
Goal-Oriented Action Planning (GOAP)
GOAP는 캐릭터가 수행할 수 있는 행동을 나타낸다.
게임 내 주어진 상황에 의거하여, 어떤 행동들을 할건지 그리고 행동들의 적절한 순서를 결정한다. (ie. 계획)
이러한 양상은 AI 행동 패턴의 모듈화된 개발을 가능하게 해준다.
행동과 결과의 상호 관계를 FSM을 작성할 때 명시적으로 지정하기 보다, 런타임에 결정되도록 한다.
위 그림은 FSM with GOAP를 간단한 예로 대조한 그림이다.
FSM은 캐릭터가 취할 수 있는 2개의 상태 : Fight, Patrol를 지정한다.
몬스터가 보이면 캐릭터는 "Fight" 상태로 바뀐다.
전투가 종료되면 몬스터는 없고(killed or fled), 캐릭터는 패트롤을 계속한다.
GOAP에서의 행동들은 STRIPS 표현을 사용한다.
STRIPS에서 행동들은 operators라 불리는 제네릭 스키마타의 인스턴스들이다.
Operator는 preconditions와 effects를 가진다.
Preconditions는 operator가 수행되기 위해 반드시 유효해야 하는 조건들이다.
Effects는 operator를 적용한 결과로 현재 상황이 어떻게 변하는 지를 나타낸다.
위 그림 역시 FSM에서의 2개의 행동(state)를 정의하고 있는 2개의 operator와
operators들을 적용시키고 난 후의 있을 법한 결과들을 보여주고 있다.
일반적으로 FSM에서의 상태는 GOAP에서 operator로 구현될 수 있다.
비록 지나치게 단순화되었지만, 위 그림은 GOAP에서의 동적이고 자연스러운 AI 행위의 생성을 보여준다.
AI들은 가능한 모든 행동들을 사용할 필요가 없고, 행동들의 순서는 미리 정의되어 있지 않다.
이것이 FSM을 작성할 때 발생할 수 있는 모든 상황을 예측하는 어려움을 줄여준다.
Hierachical Task Network Planning
우리가 하려는 복수 AI의 조직화(coordinating)는 hierachical task network(이하 HTN) planning이다.
HTN planning은 STRIPS planning의 레벨 보다는 high-level task 레벨에서의 또다른 형식의 planning 기법이다.
HTN planning은 high-level task들을, 모든 task가 하나의 행동(action)으로 쪼개질 때까지, 더 단순한 하나의 task로 분해한다.
HTN planning은 STRIPS planning에 비해 두 가지 주요 장점을 가진다.
1) STRIPS planning에 비해 훨씬 더 상황이나 문제에 대해 표현할 수 있는 능력이 뛰어나다.
: HTN planning으로는 표현할 수 있는 문제가 STRIPS planning으로는 표현할 수 없음을 의미.
2) 몇몇 리포트에 의하면, 전략적인 지식을 자연스럽게 구현할 수 있다고 한다.
: 그래서, 지금은 STRIPS plan representation 방식에 의거한 GOAP가
: HTN representation을 채택하는 데 크게 이익이 있을 거라고 기대할 수 있다.
HTN planning에서의 main knowledge artifact는 methods라 불린다.
Method 단위에서 compound task를 어떻게 달성하는지를 구현한다.
Method는 다음 세 가지 요소로 구성된다.
1) 달성해야 할 Task, head라 불린다.
2) Method가 실행되기 위해 반드시 충족되어야 하는 preconditions set
3) Head를 달성하기 위해 필요한 sub-tasks
Second knowledge artifact는 operators이다.
HTN planning에서의 operator은 STRIPS planning에서의 그것과 동일한 목적을 가진다.
즉, 다시 말해 operator는 action(행동) scheme을 나타낸다.
그러나, HTN plannaing의 operators는 달성하기 위한 primitive tasks와 operator가 적용되었을 때의 결과를 나타내는 effects로 구성된다.
실행이 되어야 하는지 여부에 대한 조건 판단은 methods에서 결정되기 때문에, precondition은 operator에 포함되지 않는다.
STRIPS와 HTN planning의 결정적인 차이는 다음과 같다.
STRIPS : 의사 결정 과정이 행동(action) 레벨에서 발생함.
HTN : 의사 결정 과정이 task(행동을 포함) 레벨에서 발생함.
이것이 HTN을 이용하여 GOAP 프레임워크를 확장하려는 정확한 이유이다.
게임 AI의 측면에서 볼 때, 위 STRIPS/HTN의 결정적 차이점은
HTN planning은 직접적으로 어떤 행동을 실행할지를 결정하기 보다,
어떤 전략을 선택하고 어떻게 달성하기 위한 결정에 초점을 맞추고 있음을 의미한다.
STRIPS representation으로도 전략을 구현할 수 있으나, task간 상호 관계의 조합으로 HTN이 훨씬 더 자연스럽다.
Encoding Strategies in HTNs
이제 HTN을 이용해서 전략을 수립하는 과정을 한 번 해보기로 하자.
점령전(Domination Game)을 위해 HTN을 이용하여 전략을 세우는 것으로 가정한다.
우선 점령전에서 이기기 위한 Win-domination (Team, DomPoints) task를 위해 몇몇 method를 만들어야 한다.
여기에서 Team은 소속되어야 할 bot들을 포함하고 있고, DomPoints는 맵상의 점령 포인트에 대한 정보이다.
여기에서는 두 가지 methods에 대해 얘기할텐데, 우선 Controll All Points method에 대해 알아보자.
Method는 적어도 세마리 이상의 bot player가 필요하다.
점령포인트를 획득하고 점령포인트 간 패트롤을 실시할 2마리의 봇을 Team(1)에 배정하고,
남은 bot은 Team(2)에 배정되어, 적을 찾아서 사살하는 임무를 할당 받는다.
위 내용을 정리하여 아래와 같이 기술할 수 있다.
Method : Cotroll All Points
Task : Win-domination (Team, DomPoints)
Preconditions:
1. Team(Team)
2. numberMembers(Team, n)
3. n>=3
4. Team(1) <= selectMembers(2, Team)
5. Team(2) <= remaining(Team, Team(1))
Subtasks:
1. Capture Domination Points(Team(1), DomPoints)
2. Patrol(Team(1), DomPoints)
3. !SeekAndDestroy(Team(2))
Subtasks #3의 ! 마크는 primitive task 임을 나타내며, 이것은 operator에 의해 실행될 수 있음을 의미한다.
두번째 method는 Control Half Plus One Points 이다.
이 메써드는 적어도 하나 이상의 점령 포인트를 획득한 뒤 이것들을 patrol 하는 것을 목적으로 한다.
Controlling a Team of Bots with HTN planning
Win-domination task를 위한 계획을 생성하기 위해, SHOP planning 방식을 써본다 (SHOP 정리할 것)
SHOP은 Maryland 대학에서 개발한 domain-independent HTN planning 방식이다.
(Simple Hierachical Ordered Planning)
위 그림은 Controll All Points의 결과 plan을 도식화 한 것이다.
인-게임에는 3개의 점령포인트와 세 마리의 봇 플레이어가 팀에 소속되어 있다.
첫 두마리는 점령포인트와 그 점령포인트간 패트롤에 배정되었고, 세번째 봇은 적을 찾아서 사살하는 임무에 배정되었다.
HTN에서 result plan은 모든 leaf(primitive task)의 연속적인 집합이다.
Capture Domination Points task는 세 개의 primitive task로 나뉘어지며, Patrol task는 두 개의 primitive task로 나뉘어진다.
그래서 최종 plan은 여섯개의 primitive tasks들의 조합으로 실행될 것이다.
SHOP은 total order planner이다 : 따라서, primitive tasks들은 생성된 곳에서 순차적으로 수행되려고 할 것이다.
이제 각 bot player들이 주어진 tasks들을 수행할 차례이다.
Plan execution 알고리즘은 각 bot에게 일련의 task를 순차적으로 배정한다.
위 그림을 예로 들면,
bot1은 dom1 획득을 배정받고,
bot2는 dom2 획득을,
bot3는 적을 찾아 사살하기 임무를 동시에 배정받는다.
그리고 복수의 임무를 배정받은 bot들은 배정받은 task를 순차적으로 수행한다.
즉, bot1은 dom1 획득이 끝나야 dom3에 대해 획득을 시도할 것이고,
마찬가지로 bot2는 dom2를 획득한 후에 패트롤을 시작한다.
일단 plan이 실행되기 시작하면, 시스템은 Win-domination task로부터 나누어지는
method들의 precondition들을 꾸준히 체크해야 한다.
만약 미리 정해놓은 threshold보다 precondition들의 무효성이 커지면 새로운 plan이 생성되고 실행되어야 한다.
다시 말해, 충분히 많은 조건들이 게임 내 환경의 변화를 충족시킬 수 있을 때에만 plan은 변경되어야 한다.