계획과 문제 풀이 (Planning and Problem Solving) (Lecture Note #19) 인공지능 이복주 단국대학교 컴퓨터공학과

Outline 개념 계획의 종류 탐색 및 부목표의 상호작용 비계층적 계획, 계층적 계획 STRIPS ABSTRIPS HACKER Goal Regression 계층적 계획

HACKER HACKER 기술 습득(skill acquisition)의 모델로 개발 기술은 절차(procedure)로 정의되며, 각 절차들은 기술 영역 내에서의 특정 문제를 해결 어떤 기술에서 특정 문제 해결 절차가 포함되어 있지 않다면 이 문제를 위한 새로운 절차가 설계되어야 함 기본적으로는 새로운 문제의 부 목표들을 달성하는 수단으로 기존의 절차들을 이용하여 문제를 해결 새로운 절차들은 버그(bug)를 가진 것으로 간주 대표적인 버그: 상호 간섭하는 결합적인 부 목표 특정의 기술 영역 내에서는 많은 절차들에서 버그들이 공통으로 출현 HACKER는 이러한 버그들 처리 가능 → 디버깅

HACKER (2) HACKER의 문제 풀이용 라이브러리 해답 라이브러리 지식 라이브러리 프로그래밍 기법 라이브러리 문제 풀이 절차들을 포함 지식 라이브러리 문제 영역에 대한 사실들을 소유 프로그래밍 기법 라이브러리 해답 라이브러리에서 문제풀이에 대한 적절한 절차를 제공할 수 없을 때 사용할 수 있는 방법들을 제공 예) 목표 : MAKE (ON B C) 해답 라이브러리에서 절차 찾음 → 실패하면 프로그램 기법 라이브러리를 이용, 새로 구성 (TO (MAKE (ON X Y)) (PUTON (X Y))) 적용불가 → 버그 (PREREQUISITE-MISSING) → 지식 라이브러리에 의뢰 → 사실탐색 (FACT (PREREQUISITE (PUTON (X Y) (PLACE-FOR X Y)))) : 적용불가 ↓ (FACT (PREREQUISITE (EXPRESSION (CLEARTOP OBJECT)) (HAVE ( ) (MOVES EXPRESSION OBJECT)))) 달성되어야 할 선행 요건: (CLEARTOP B) A B  B C A C (PLACE-FOR X Y): X를 Y위에 놓기 위해 공간이 있어야 함. 여기서는 만족. 그래서 적용 불가 … (CLEARTOP OBJECT) … 물체를 움직이는 데 필요한 선행조건: 윗 부분이 비워져 있어야 함

HACKER (3) HACKER가 해결하지 못하는 문제 ((ACHIEVE (ON B C)) (ACHIEVE (ON A B))) 각 부목표의 달성은 상대방의 부목표의 달성을 방해(보호 파괴) (ON B C)  (ON A B) 또는 (ON A B)  (ON B C) 둘 다 실패 대안: 보호 파괴를 허용 → 나중에 파괴된 목표를 다시 달성 : 최적이 아닌 계획 C 위에 B를 올린다 → 보호 파괴 허용 → 다시 C 위의 B 제거 다시 A 위의 C 제거 C 위에 B, B 위에 A를 올려 목표 달성 A C B  A B C

목표 역행 (Goal Regression) 시스템 HACKER의 경우 보호 파괴가 발생할 경우 역추적을 수행 → 여러 개의 목표들의 순서를 바꾸어서 목표들을 달성하기 위한 계획을 재형성 결합적인 목표들이 많이 있고 또한 대부분의 부목표들이 상호 간섭을 가진다면 매우 비효율적 목표들의 순서를 바꾸어 다시 계획을 형성하기 때문에 어떤 목표들에 대해서는 한 번 달성된 목표를 또 다시 달성시키는 작업을 진행  특정의 부목표를 위한 해답을 중복으로 달성시키는 비효율적인 작업 대안 결합적인 부목표들 중에서 한 순간에 하나의 부목표만을 대상으로 하여 계획을 형성 이 과정에서 이미 달성된 목표들과의 간섭이 발생하는지를 항상 검사 간섭이 일어나는 경우에는 그 목표를 다른 위치로 이동 목표들 사이에서의 간섭을 다루기 위해 목표 역행의 개념도입

목표 역행 시스템 목표 역행 이미 달성된 목표들은 후속되는 연산들에 의해서 파괴되지 않는다는 것을 보장하기 위한 방법 제공 기본적인 계획 알고리즘 결합적인 부목표들 중에서 가장 첫번째 부목표를 먼저 달성시킴 계획의 끝부분에서부터 이미 달성된 것들을 파괴하지 않는 곳까지 나머지 부목표들을 역행하면서 계획을 확장시켜 나감 장점 계획의 형성이 구축적(constructive) 즉, 계획의 형성이 연산 하나 하나의 추가로 이루어짐 HACKER와 같은 시스템에 비해서 부목표의 반복적인 달성을 피함으로써 탐색에 드는 경비를 매우 많이 감소 시킴 단점 각 연산의 삽입 위치 결정의 어려움

목표 역행 시스템 목표 및 연산 상 태 목표 및 연산 상 태 C C 1. A B 1. A B 2. C A B 2. C A B 목표 및 연산 상 태 목표 및 연산 상 태 C C 1. A B 1. A B (Clear A) (Clear A) 역행 2. C A B 2. C A B (Put B on C) (Put A on B) B A ACHIEVE (ON B C) 3. C A 3. C B ACHIEVE (ON A B) (Put A on B) (Clear B) A (Put B on C) 실패 ACHIEVE (ON B C) B ACHIEVE (ON A B) 4. C 두번째 목표 (ON B C)를 끝에 붙인다. → B위에 A가 보호목표 파괴 발견 → 역행

계층적 계획 계층적 계획 NOAH (Nets of Action Hierarchies)는 계획들을 위해 이전의 문제풀이 시스템보다 더 풍부한 구조를 가지는 절차적 네트라 불리는 표현 방법 사용 절차적 네트는 이전의 연구들과는 달리, 문제풀이에 관련된 절차적 지식과 선언적 지식 모두를 표현 절차적 지식은 목표들의 문장을 부목표들로 확장하고, 어떤 한 상태로부터 다른 상태로 변형하는 연산자들의 행동을 시뮬레이트하는 함수들을 포함 선언적 지식은 이들 함수들의 실행에 따른 효과들을 표현

계층적 계획 NOAH에서의 문제풀이 부목표 상호작용 이전의 계획 시스템과 NOAH 비교 절차적 네트를 확장함으로써 달성 본래의 목표보다 더 상세한 목표들의 노드를 계속 추가 문제의 본래 목표는 더욱 상세한 목표들의 여러 단계로 대치 간단한 문제풀이 연산자들에 의해서 즉시 달성될 수 있는 목표들의 단계로 대치 부목표 상호작용 결합적 목표를 달성하기 위해 임의의 순서를 따를 경우 발생 두 가지 피해 나가는 방법 타당한 이유가 있기 전까지는 부목표들의 순서를 정하지 않음 지속적인 계획 확장과 문제 발생 이전에 올바르게 수정 이전의 계획 시스템과 NOAH 비교 Over-constraint (임의의 순서 가져야) vs. under-constraint (필요한 경우 제외하고 순서를 정하지 않음) NOAH: constructive

절차적 네트의 구조 절차적 네트의 구조 계획을 표현하는 데 있어서 여러 개의 단계 포함 각 단계는 부분적으로 순서가 정해진 연속된 노드들로 구성 목표들은 동시에 달성될 수 있다고 가정 단일 목표 노드를 추상화의 다양한 단계에서 계층으로 구성된 계획으로 확장 추상적인 연산자들을 더욱 상세한 연산자들로 확장하는 절차 사용 예) 추상적 연산자: (MAKE COFFEE) 확장된 연산자들: (BOIL WATER), (GRIND COFFEE), (PUT COFFEE IN FILTER), (POUR WATER THROUGH)

비평 (Critics) 비평 (Critics) NOAH에서의 계획 상호간섭에 관한 검사를 하기 위해 사용 비평의 종류 충돌-해결 (RESOLVE-CONFLICTS) 비평: 충돌목표 재 순서화 (HACKER의 디버깅 절차와 비슷) 중복-선결조건-제거 (ELIMINATE-REDUNDANT-PRECONDITIONS) 비평: 실제로는 한번의 실행을 필요로 하는 데 두 번 나타나는 연산자 제거 현존-객체-사용 (USE-EXISTING-OBJECTS) 비평: 변수에 어떤 값을 할당할 것인가 선택 범용 비평, Domain specific 비평 NOAH에서의 계획 절차적 네트의 현재 최하위 단계에서 반복적 실행 초기에, 노드는 목표 NOAH를 위해 구축 상호작용에 관한 검사 현 단계의 노드들이 다른 단계로의 확장이 시도되기 전에 상호작용에 관한 검사 시행

Achieve (AND (ON A B) (ON B C)) NOAH - 예 A 예) C B  A B C (ON C A) (CLEARTOP B) (CLEARTOP C) (AND (ON A B) (ON B C)) 단계 1: Achieve (AND (ON A B) (ON B C)) Achieve (ON A B) s j 단계 2: Achieve (ON B C)

그림 7.8 참조를 위해 번호가 지정된 노드들에 관한 비평 전의 단계 NOAH - 예 1 (CLEAR A) 3 s j Put A on B (CLEAR B) 2 s j 4 (CLEAR B) 6 s j Put B on C 5 (CLEAR C) 그림 7.8 참조를 위해 번호가 지정된 노드들에 관한 비평 전의 단계

NOAH - 예 1 (CLEAR A) 3 s j Put A on B (CLEAR B) 2 s 4 (CLEAR B) 6 s j Put B on C 5 (CLEAR C) 그림 7.9 충돌-해결 비평 후의 단계 3

NOAH - 예 (CLEAR A)의 확장 (CLEAR C) Put C on Object 1 s j Put A on B 4 (CLEAR B) 6 s j Put B on C 5 (CLEAR C) (CLEAR A)를 하기 위해서는 현재 A 위에 C가 있기 때문에 (CLEAR C)를 하고 C를 아무 곳이나 내려놓아야 함 그림 7.10 모든 비평 후의 단계 3

NOAH - 예 (CLEAR C) Put C on Object 1 s j Put A on B 4 (CLEAR B) 6 s j Put B on C (CLEAR C) 5 그림 7.11 비평 전의 단계 4 (CLEAR C) Put C on Object 1 s 4 (CLEAR B) 6 s j Put B on C Put A on B (CLEAR C) 5 그림 7.12 해결-충돌 비평 후의 단계 4

NOAH - 예 (CLEAR C) Put C on Object 1 s j Put B on C Put A on B (CLEAR B) 그림 7.13 단계 4, 최종 계획

Summary 개념 계획의 종류 탐색 및 부목표의 상호작용 비계층적 계획, 계층적 계획 STRIPS ABSTRIPS HACKER Goal Regression 계층적 계획

블록 문제를 위한 SOUP 코드 문제 풀이를 위한 SOUP 함수 사용 (QLISP 확장) (PUTON (QLAMBDA (ON X Y) (PAND (PGOAL (Clear X) (CLEARTOP X) APPLY (CLEAR)) (PGOAL (Clear Y) (CLEARTOP Y) (PGOAL (Put X on top of Y) (ON X Y) APPLY NIL) (PDENY (CLEARTOP Y)))) NOAH에서 “상태”의 개념: 자신의 참 값이 결코 변하지 않는 몇몇 지식이 세상 모델 (world model) 내에서 표현됨: 문제풀이가 시작되었을 때 가지는 주위 상황의 상태를 포함 세상의 변화된 상태는 추가 리스트 또는 상태를 변화시키는 연산자의 삭제 리스트에 추가된 명제에 의해 표현됨 Table Of Multiple Effects (TOME): 네트 내의 각 단계에서 상황 변화들을 요약 목표들간의 상호작용에 관련된 검사를 하기 위해서 사용 계획 내에서 하나 이상의 행동에 의해서 단일 명제의 값이 바뀔 경우, 행동들간의 상호간섭의 가능성 존재