개 념 계획과 문제풀이의 기본개념 문제풀이(Problem Solving) 계획(Planning)

Presentation on theme: "개 념 계획과 문제풀이의 기본개념 문제풀이(Problem Solving) 계획(Planning)"— Presentation transcript:

1 개 념 계획과 문제풀이의 기본개념 문제풀이(Problem Solving) 계획(Planning)
특정의 목표를 달성하기 위해 취해야 할 행동들을 순서대로 나열하는 과정  탐색에 의한 문제풀이 광역적 의미(모든 인공지능 문제) 계획(Planning) 행동 순서의 표현 막연한 단계  상세한 것을 결정  계층 구조 계획의 완성 : 문제풀이 연산자들의 나열 문제 풀이 : 광역적인 의미에서 보면 모든 인공지능 프로그램들이 문제풀이 시스템이라고 할 수 있다 계획 - 일반적으로 계획이라고 하는 것은 행동을 취하기 전에 행동들의 순서를 결정하는 것 추상 하루일과 오전계획 점심계획 저녁계획 출근 기사보기 점심식사 신문보기 서류작업 퇴근 상세 은행 돈 기름 운전 휴게실 빵 신문 컴퓨터

2 계획의 종류 비계층적(nonhierarchical) 계획 계층적(hierarchical) 계획
계층의 두 가지 의미(부목표와 계획의 세분화): 세분화 단계가 없음 각 목표들을 달성하기 위한 일련의 문제풀이 행동들을 나열하여 계획을 형성하는 것 현상태에 목표상태로 단순 진행(STRIPS) 단점 중요한 행동들과 단순히 세부적이기만 한 행동들을 구별하지 않음 세부적인 계획을 많이 가지는 계획을 형성하는 데는 많은 경비가 소요 애매한 단계들을 가지는 계획의 경우 문제풀이 연산자들을 결정하기가 어려움 단점 보완을 위해 계층적 계획 기법 이용 계층적(hierarchical) 계획 대략적 계획을 세운 후, 대략적인 부분들의 세부 부계획을 만듬 최종적으로 세부적인 문제풀이 연산자들을 완전하게 나열 추상 공간(abstraction space) 높은 위치: 추상적, 중요한 부목표, 중요치 않은 세부사항이 없음 낮은 위치: 세부적인 문제풀이 연산자들이 나열 ABSTRIPS, NOAH, MOLGEN 계획으로 얻을 수 있는 잇점으로는 탐색 노력의 절감, 목표 충돌의 해결, 오류수정의 기초 제공 등이 있을 수 있습니다.

3 탐색 및 부목표의 상호작용 탐색 부목표의 상호작용
특정의 목표 달성 또는 문제풀이 행동들의 순서를 결정하기 위해서 가능한 많은 순서들 중에서 어떤 것을 선택할 것인가를 결정하기 위해서 사용 부목표의 상호작용 어떤 문제를 해결하기 위해서 두 가지 이상의 목표들을 모두 만족시켜야 할 때 발생(한 부목표의 만족은 다른 부목표의 달성을 방해함) '사다리를 칠하라‘ 선행조건 : '페인트를 구하라' - 탐색 문제 해결 연산자들의 조합의 수가 연산자들의 수에 지수적으로 비례하여 증가히기 때문에 일반적으로 조합적 폭발로 일컬어 진다. - 부목표 각각의 목표들의 달성시켜야 할 순서가 대개 문제 내에서 정해지는 것이 아니기 대문에 이 문제는 해답을 찾는 데 치명적일 수 있습니다. 사다리를 칠하라, 지붕을 칠하라 선행조건을 고려하여 계획의 선후를 결정할 수 있는 계획시스템이 더 지능적이다 Choice Point '붓을 구하라' '지붕을 칠하라' 선행조건 : '페인트를 구하라' '붓을 구하라' '사다리를 구하라'

4 탐색 및 부목표의 상호 작용 탐색 문제는 부목표의 상호 작용 문제와 밀접하게 관련 HACKER, INTERPLAN
둘 이상의 부목표에서 특정 순서로는 목표를 달성할 수 없다는 것을 발견하게 되면 실패한 선택점에서 부터 역추적을 진행해야 한다. 탐색량에 영향을 미침 HACKER, INTERPLAN 부목표들이 서로 독립적이라는 선형 가정을 휴리스틱으로 이용 연산자들의 모든 순서들을 성공적으로 조사한다는 것이 어려움 NOAH, MOLGEN NOAH : 문제풀이 연산자들의 선행 조건들을 고려하여 부분 순서를 형성 MOLGEN : 제약 조건들이 이용될 수 있을 때까지 연산자들의 순서를 정하지 않는다. - 사다리를 칠하라를 먼저 달성되도록 결정하면 지붕을 칠하라라는 목표를 달성할 수 없다는 것을 발견하게 된다.

5 비계층적 계획과 계층적 계획의 비교 STRIPS와 ABSTRIPS의 비교
STRIPS(STanford Research Institute Problem Solver) 가정 문제풀이 시스템 : 문제에 대한 해결 과정을 탐색하는 가운데 문제풀이 연산자를 적용함으로써 만들어지는 상태들을 조사하는 프로그램 시작 상태 : 문제풀이 시스템에 의해 첫번째로 검사되어지는 상태 목표 상태 : 문제풀이가 성공적으로 종료 되었을 경우 그 마지막 상태 STRIPS 문제 풀이 시스템 유효한 문제풀이 연산자와 객체들의 집합을 가진다 실행시 문제 공간의 상태 변화를 수반한다.

6 STRIPS 예) 한 잔의 커피를 마시는 문제 연산자 객체
“주방에 가서 커피가 끓여져 있다면, 그 커피를 적당히 잔에 따른다. 만일 커피가 끓여져 있지 않다면, 커피를 만들거나 아니면 사러 가야 할 것이다. 커피를 직접 끓이고 싶지만, 원두나 인스턴트 커피가 없다면, 커피를 사러 판매점에 가야 한다. 만일 돈이 없다면 먼저 은행에 들러야 한다.” 연산자 물을 끓인다 x를 따른다 x를 구입한다 커피를 만든다 x에 간다 돈을 출금한다 객체 끓는 물 주방 원두커피 판매점 원두커피 끓인 커피 판매점 은행 돈 주방에 가서 커피가 끓여져 있다면 , 그 커피를 잔에 따른다. 만일 커피가 끓여져 있지 않다면, 커피를 만들거나 사러 가야 한다. 커피를 직접 끓이고 싶지만 원두나 인스턴트 커피가 없다면 커피를 사러 판매점에 가야 한다. 만일 돈이 없다면, 먼저 은행에 들러야 한다. 이와 관련된 연산자와 객체

7 STRIPS Effect List 연산자 선행조건 효과(Effect) 커피를 부어라 끓인 커피가 있다. 문제해결
커피를 부어라 끓인 커피가 있다. 문제해결 커피를 만들어라 원두가 있다 끓인 커피를 가진다 분쇄기가 있다 끓고 있는 물이 있다 주방 안이다 무언가를 구입하라 판매점에 있다 무언가를 가진다 돈이 있다 어떤 곳에 가라 그 장소가 존재한다 어떤 곳에 있다 그 곳 외에는 없다 돈을 출금하라 은행에 있다 돈을 가진다 물을 끓여라 주방 안이다 끓는 물을 가진다

8 STRIPS 시작 상태 목표 상태 시작 상태와 목표 상태
문제 해결: 목적-수단 방법(means-ends analysis) 이용 현재 상태와 목표 상태 비교  차이 조사  차이를 줄일 수 있는 문제풀이 연산자를 찾음  목표 상태에 도달할 때 까지 반복 예) 차이를 줄이는 연산자 ‘커피를 만들어라’ ‘무언가를 구입하라’ 시작 상태 끓인 커피가 없다 주방 안이다 분쇄기가 있다 돈이 있다 끓인 물이 있다 목표 상태 끓인 커피를 가진다 주방 안이다 분쇄기가 있다 돈이 있다 끓인 물이 있다 차이 (Difference) 둘 중 하나를 선택하여 문제풀이 시작

9 STRIPS ‘커피를 만들어라’를 선택한 경우 (커피를 부어라) 선행조건: 끓인 커피가 있다 OR (커피를 만들어라)
주방 안이다, 분쇄기가 있다 돈이 있다, 끓인 물이 있다 (목표상태) OR (커피를 만들어라) 선행조건: 원두가 있다, ... (끓인 커피를 구입하라) 선행조건: ... 끓인 커피가 없다. 주방에 있다 원두가 있다, 분쇄기가 있다 돈이 있다, 끓인 물이 있다 (원두를 구입하라) 선행조건: 판매점에 있다, ... (주방에 가라) 선행조건: 주방이 있다 끓인 커피가 없다. 원두판매점에 있다. 분쇄기가 있다 돈이 있다, 끓인 물이 있다 (판매점에 가라) 선행조건: 판매점이 존재한다 끓인 커피가 없다. 주방 안이다, 분쇄기가 있다 돈이 있다, 끓인 물이 있다 (시작 상태) 문제 공간 안에서 참(true) 상태 변이

10 STRIPS 탐색과 역추적 ‘분쇄기가 없다.’, ‘분쇄기 판매점이 없다.’, ‘돈이 없다.’로 시작상태 변경 (커피를 부어라)
선행조건: 끓인 커피가 있다 OR (커피를 만들어라) 선행조건: 원두가 있다, 분쇄기가 있다, ... (끓인 커피를 구입하라) 선행조건: ... (원두를 구입하라) 선행조건: 돈이 있다, 판매점에 있다, ... (분쇄기를 구입하라) 선행조건: 돈이있다, 분쇄기 판매점에 있다 (돈을 출금하라) 선행조건: 은행에 있다 (판매점에 가라) 선행조건: 판매점이 존재한다 참 (판매점에 가라) 선행조건: 판매점이 존재한다 (은행에 가라) 선행조건: 은행이 존재한다 참 거짓 참

11 ABSTRIPS ABSTRIPS(Abstraction STRIPS) 추상 공간의 계층구조 하에서 계획을 형성한다
초기 명세에 주어지는 모든 객체와 연산자들은 추상 공간에 포함 선행조건은 임계(criticality)라 부르는 계층으로 할당 선행조건의 중요도에 따라 계층별 구분 임계의 할당 순서 1. 사람이 중요성을 직관적으로 판단해서 선행조건의 부분순서를 형성 2. ABSTRIPS에서 임계를 더욱 정확하게 조정하기 위해 임계조정 알고리즘을 적용 부분 순서(partial ordering) 선행조건 직관적 임계 장소가 존재한다 3 어떤 것이 있다 2 어딘가에 있다 1

12 ABSTRIPS ABSTRIPS의 임계 조정 방법 선행조건 임계
어떠한 연산자에 의해서도 변화 될 수 없는 참값을 가지는 모든 선행 조건들은 가장 높은 임계 할당 선행 조건의 각각을 이루기 위한 단기 계획이 발견될 경우 부분 순서에서 기술되는 것과 같은 임계 할당 단기 계획이 발견되지 않을 경우 부분 순서에서 가장 높은 임계보다 더 높은 임계 할당 선행조건 임계 원두 판매점이 존재한다 끓인 커피 판매점이 존재한다 은행이 존재한다 분쇄기가 있다 24 원두, 끓는 물, 돈이 있다 끓인 커피 판매점, 원두 판매점, 은행에 있다 1

13 ABSTRIPS의 탐색과정 계층 5: 계층 4: 계층 3: 계층 2: 계층 1:
OR 계층 5: (커피를 만들어라) 선행조건: 임계5의 선행조건 없음 분쇄기가 있다(4) (끓인 커피를 구입하라) 선행조건: 임계5의 선행조건 없음 임계4의 선행조건 없음 임계3의 선행조건 없음 선행조건: 돈이 있다, 커피 판매점에 있다 원두…, 끍는물…, 돈…(2) (분쇄기를 구입하라) 선행조건: 분쇄기 상점에 있다, 계층 4: 돈…(2) (분쇄기 상점에 가라) 선행조건: 분쇄기 판매점이 존재한다 실패: 계층5로 되돌아 감 계층 3: 계층 2: (돈을 출금하라) 선행조건: 은행에 있다 (판매점에 가라) 계층 1: STRIPS 보다 더욱 적은 탐색과 역추적으로 문제 해결 최종 목표를 만족시키기 위한 중요한 선행 조건이 만족 될 수 없다는 점을 빨리 검출할 수 있다 (은행에 가라)

14 비계층적 계획 계획을 위한 비계층적인 접근은 단일 추상 단계에서 연산자들의 순서를 형성
대표적인 비계층적 계획 시스템: HACKER 서로 독립적이지 않은 결합적인 부목표들로 형성되는 어려운 문제를 비계층적으로 해결 부목표들 사이의 간섭에 의한 불완전한 계획을 형성시켜 놓고 다음 단계에서 불완전한 계획 내의 연산자들을 재순서화하여 계획을 수정 예) 봄맞이 대청소 : 먼지 쓸기, 마루 닦기, 유리창 닦기, 양탄자 털기 임의의 순서대로 작업이 진행될 경우 먼지를 쓸어 내지 않고 마루를 닦는 것 양탄자를 먼저 털지 않고 마루를 닦는 것 → 보호 목표(protected goal)의 파괴(violation)를 초래 마루 닦기가 끝난 후에는 마루가 마를 때까지 사람이 마루를 지나가는 것과 다른 목적을 위해 마루를 사용하는 것을 불허 → 어떤 목표의 달성은 다른 목표들의 달성을 방해

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

16 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)))) A B  B C A C

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

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

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

20 목표 및 연산 상 태 목표 및 연산 상 태 C C 1. A B 1. A B 2. C A B 2. C A B B A 3. C A
목표 및 연산 상 태 목표 및 연산 상 태 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가 보호목표 파괴 발견 → 역행

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

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

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

24 블록 문제를 위한 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))))

25 NOAH에서 “상태”의 개념 NOAH에서 “상태”의 개념 자신의 참값이 결코 변하지 않는 몇몇 지식이 세상 모델내에서 표현됨
문제풀이가 시작되었을 때 가지는 주위 상황의 상태를 포함 세상의 변화된 상태는 추가 리스트 또는 상태를 변화시키는 연산자의 삭제 리스트에 추가된 명제에 의해 표현됨 Table Of Multiple Effects(TOME) 네트 내의 각 단계에서 상황 변화들을 요약 목표들간의 상호작용에 관련된 검사를 하기 위해서 사용 계획 내에서 하나 이상의 행동에 의해서 단일 명제의 값이 바뀔 경우, 행동들간의 상호간섭의 가능성 존재

26 비평 (Critics) 비평 (Critics) NOAH에서의 계획 상호간섭에 관한 검사를 하기 위해 사용 비평의 종류
충돌-해결(RESOLVE-CONFLICTS) 비평 중복-선결조건-제거(ELIMINATE-REDUNDANT-PRECONDITIONS) 비평 현존-객체-사용(USE-EXISTING-OBJECTS) 비평 NOAH에서의 계획 절차적 네트의 현재 최하위 단계에서 반복적 실행 초기에, 노드는 목표 NOAH를 위해 구축 노드를 SOUP 프로시저를 사용해 확장 상호작용에 관한 검사 현 단계의 노드들이 다른 단계로의 확장이 시도되기 전에 상호작용에 관한 검사 시행

27 Achieve (AND (ON A B) (ON B C))
예) 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)

28 그림 7.8 참조를 위해 번호가 지정된 노드들에 관한 비평 전의 단계
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 참조를 위해 번호가 지정된 노드들에 관한 비평 전의 단계

29 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

30 (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) 그림 7.10 모든 비평 후의 단계 3

31 (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

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