G.O.A.P ( Goal Oriented Action Planning )

G.O.A.P ( Goal Oriented Action Planning ) 목적 ( 상태 ) 을 달성하기 위한 일련의 행동 ( 액션 ) 을 계획하는 Planner 입니다. 복잡한 FMS 없이 의사결정을 달성할 수 있어 확장하기 용이합니다.

 

G.O.A.P 에서 사용되는 용어는 아래와 같습니다.

Action : 상태를 변화하는 행위
Preconditions : 전제조건
Effects : 효과

 

G.O.A.P 의 Plan 이 수립되는 흐름은 아래와 같습니다.

Init State → ( conditon ) Action ( → effect ) → ( condition ) Action ... → Goal

 

계획 방식은 "backward chaning search" 를 사용하는데 과정은 아래와 같습니다.

• Add the goal to the outstanding facts list
• For each outstanding fact
  • Remove this outstanding fact
  • Find the actions that have the fact as an effect
  • If the precondition of the action is satisfied,
    • Add the action to the plan
    • Work backwards to add the now-supported action chain to the plan
  • Otherwise,
    • Add the preconditions of the action as outstanding facts

한글로 풀면 아래와 같습니다.

• 목표 ( Goal ) State 를 만족하는 Action ( effect ) 을 찾는다
• 만족한 Action 의 Precondition 을 만족하는 지 확인한다
• 만족하지 않다면, Precondition 을 만족하는 Action ( effect ) 를 찾는다
• 만족한 Action 을 찾을 때 까지 반복한다
• 복수 개의 Plan 이 검색되는 경우, 더 적은 cost 를 발생하는 plan 을 선택한다
  ( 모든 plan 을 검색한다. cost 를 찾는 방식은 다양하며 search algorithm 으로 A* 도 있다 )

작동 방식은 "Context Precondition" 을 사용합니다.

이는 상황에 따라 동작이 달라집니다 ( plan 이 항상 같지 않음 )
현재 State ( context ) 에 따라 결정되는 Action 이 달라지므로 다양성을 보장합니다
( Context 는 추상적인 개념임 )

 

가장 낮은 코스트의 경로를 찾는다

 

Appendix

• A*
  • A* search algorithm - Wikipedia
  • 모든 경로를 찾고 가장 적은 cost 의 plan 을 찾는 알고리즘 입니다.

Reference

• Microsoft Word - Examensarbete - Philip Bjarnolf - 0704535573.doc (diva-portal.org) - 11 page
• GOAP_draft_AIWisdom2_2003 (mit.edu)
• https://www.gameaipro.com/GameAIPro/GameAIPro_Chapter04_Behavior_Selection_Algorithms.pdf - 4.6