"A goal model for adaptive complex systems." International Journal of Computational Intelligence (2010)

A Goal Model for Adaptive Complex Systems

Scott A. DeLoach, Matthew Miller

---

1. Introduction

• 예전에는 software system 이 single domain 내에서 작은 문제를 해결했기 때문에, 디자인의 흐름은 곧 코드의 흐름이었고, 프로그래머는 알고리즘이 주어진 메모리와 processing 제약 내에서 알고리즘이 효율적으로 도는 것에 관심을 가졌다.
• 최근 사용자들은 시스템이 "intelligent" 해져서 시스템이 실행되는 중에 변화하는 환경과 문제에 적응하기를 기대한다. 
• 따라서 최근 개발자들은 여러 resource 로부터 얻은 information 을 사용해 문제를 해결하는 인간의 사고과정과 유사한 Software 개발을 시도하고 있다.
  
  

• Goal 은 변하는 환경과 조건 안에서 왜 특정 task 가 필요한지를 파악하고, 이것이 곧 System 구현의 핵심이다.
  
  

• 이 논문에서는, GMoDS(Goal Model for Dynamic Systems)를 제안한다. 
• 정의 : 시스템 레벨의 Goal을 파악하고 그 Goal 들을 design time과 runtime 에 활용해 시스템이 Dynamic한 문제와 환경에 적응하도록 하는 여러 Model 집합

• 세 가지 Model
• Goal Specification Model    : 디자이너의 의도를 파악한다.
• Runtime Model                : Specification Model 의 의미를 정의한다.
• Execution Model               : Instance Model 을 구현한다.
  
  

---

2. GMoDS Definition

1. Specification Model

• 세 가지 Main 요소

1. Goal             - 관찰가능한(observable), 원하는(desired) World state
2. Event            - 시스템 실행중에 발생하는 관찰가능한 현상(Phenomenon)
3. Parameter     - 달성하고자 하는 Goal 의 detail 이나 특정한 Event 의 발생에 대한 정보를 Agent 에 전달 

Agent가 Goal 을 추구하는 동안, 여러 Event 가 발생하고, 이러한 Event 는 시스템에 다른 Goal을 추가하거나 제거한다. 

시스템에 새로 추가된 Goal 은 생성을 유발한 event 로부터 parameter를 얻는다. 즉, Agent 는 Triggering Event 의 parameter 로부터 생성된 Goal의 parameter 에 기반하여 일을 수행하는 것. 

• Goal classes : Goal 간의 상호작용을 모델링 하기 위해 시스템 디자이너에 의해 설계된 것.
  Goal instances : 특정한 parameter 를 가지고 Goal Class 로부터 runtime에 생성된 것
  ( 하나의 Goal class 로부터 여러 개의 Goal instance 가 생성될 수 있다. )

• Upper level goal 은 Parent Goal
  Lower level sub-goals 를 Children Goal 이라고 한다.

• 자식이 없는 Goal 을 Leaf Goal 이라고 한다.

• Parent Goal 은 conjunctive <<and>> 나 disjunctive <<or> 를 가진다.

• Goal class는 runtime 에 Goal instance 를 생성하고, 각각의 Goal instance 는 서로 독립적이다. 
  
  

• Goal Triggers : 새로운 Goal instance 를 생성하거나 기존 Goal instance를 삭제하는 event 로 정의된다. 
• (e.g.) Goal instance g1 수행 중 발생하는 event e1에 의해 Goal instance g2 가 생성되는 것
• negative trigger : g1 수행 중 발생하는 event e1에 의해 g2가 삭제되는 것
• illegal : g4에서 g6을 생성하는 event e3에 대한 trigger는 illegal 인데, 만약 g4가 수행되는 중에 e1 보다 e3가 먼저 발생할 경우, g6이 생성되지만 부모 instance 인 g5가 아직 없기 때문이다.
• initial trigger e0 : root goal 을 포함해 초기 goal set을 추가하는 trigger.
  
  
• Goal Precedence : Goal 실행의 순서. 
• 같은 subtree 내에서만 적용된다. 아래 그림에서 g7(1)이 실행되기 위해서는 g6(1)이 achieve 되어야 하지만, g6(2) 와는 관계가 없다. 

• Restriction
  ① Precedence Cycle 은 존재하면 안된다.
  ② Trigger 와 Precede 가 섞인 Cycle 도 존재하면 안된다.
  ③ Ancestor 보다 Precede 할 수 없다. 

---

Formalization

 

위와 같은 방식으로 Goal Specification Tree를 Formalization 할 수 있다. 

앞서 언급했던 tree의 정의와 제약들을 Formalization 했을 경우, 아래와 같은 표로 정리된다.

---

2. Runtime Model

Runtime 에는 triggering event 에 의해 goal의 parameter 값이 제공되거나, 부모로부터 parameter 값이 상속되어 새로운 instance 를 생성한다. 

System 의 상태를 추적하기 위해, 4가지 predicate 를 사용하는데, 다음과 같다.

1. Achieved : goal 이 시스템에 의해 달성된 상태. Leaf일 경우, Agent 로부터 알게 되며, Parent goal은 children goal 의 달성여부에 의해 결정된다.
2. Obviated : goal 이 시스템에 더 이상 필요하지 않은 상태. 만약 부모 Goal G1에 두 개의 Subgoal G2, G3이 있고, <or> 로 연결되어 있을 때, G2 가 달성되면 G3는 obviated 상태가 된다. 
3. Preceded : 아직 달성되지 않은 preceding goal 이 있는 상태
4. Failed : 시스템이 해당 goal을 더 이상 절대로 달성할 수 없는 상태

3. Execution Model

Execution Model은 GMoDS를 goal 집합으로 정의하고 구현한다. 각각의 Goal은 위와 같이 6개의 부분집합으로 분류될 수 있으며, 각 분류에 대한 설명은 그림에 대부분 써 놓았다. 

이 때, 실제 Goal 이 수행되는 과정을 예시로 살펴보면, 가장 먼저 초기 initial event e0 에 의해 초기 goal들이 생성된다.

그 후, trigger e1 에 의해 g4로부터 g5 instance 가 생성되고, 이 예시에서는 parameter 가 각각 1, 2 인 instance 로 총 두 개의 g5 instance 가 생성되었다.

event e1 이후의 상태를 G instance tree 와 Execution Model Formulation 으로 나타내면 위와 같다. 그 위로 차츰 Leaf Goal 부터 Goal 이 달성되면서, 최종적으로 아래와 같은 Execution Model 이 되었을 때 시스템이 끝이 난다. 더 이상 active goal 과 triggered goal 이 없는 아래와 같은 상태에서 더 이상의 goal instance 가 생성되지 않으며, 모든 goal 이 achieved 나 obviated 에 속해 있기 때문에 전체 시스템 goal 인 g0가 achieved 된 것을 알 수 있다. 

---

원본 논문 파일

A goal model for adaptive complex systems.pdf

필기된 논문 파일

GMoDS_ijcitp_2010.pdf