[인공지능] 6-2 계획수립

고전적 계획 수립

상태공간 계획수립 : 초기 상태에서 목표 상태로의 경로 탐색

• 초기 상태를 목표 상태로 변화 시키는 일련의 연산자 찾기
• 노드(node) : 세계의 상태
• 에지(edge) : 상태 전이를 일으키는 행동
• 행동 = 바로 적용할 수 있는 기본 행동
  • 연산자(operator) = 기본 행동
• 전향 탐색
  • 초기 상태에서 시작
  • 적용가능한 연산자를 목표 상태에 도달할 때까지 적용
  • 너비우선 탐색(Breadth-first search)
  • 깊이우선 탐색(Depth-first search)
  • 휴리스틱 탐색 : A* 알고리즘
• 후향 탐색
  • 목표 상태에서 시작
  • 해당 상태를 만들어내는 행동선택을 시작 상태에 도달할 때까지 반복
• STRIPS 알고리즘
  • 후향 탐색 방법
  • 목표 상태가 만족되지 않으면, 목표 상태를 effect로 만들 수 있는 연산자를 선택하여 연산자의 매개변수를 설정하고 precondition이 만족되는지 확인
  • precondition 중에 만족되지 않는 것이 있으면, 그것을 effect로 하여 위 과정 반복
  • 모든 precondition들이 만족되면 사용된 매개변수 설정된 연산자들을 역순으로 나열하여 계획생성
• GraphPlan 알고리즘
  • 기존 계획공간 계획수립에 비해 매우 빠른 속도
  • 명제 단계와 행동 단계가 번갈아가며 구성

명제 단계 0

• 초기상태에 주어지는 각 리터럴을 노드로 표현

행동 단계 1

• 명제 단계 0의 명제들에 대해서 적용될 수 있는 각 행동을 노드로 표현
• 명제 단계 0에 나타나는 Precondition의 리터럴 노드와 연결
• 명제 단계 2에 나타나는 Effect의 리터럴 노드와 연결

명제 단계 2

• 행동 단계 1의 행동의 Effects 부분에 나타나는 리터럴들과 명제 단계 0의 리터럴들에 대응하는 노드 생성
• 명제 단계 0의 모든 노드를 명제 단계 2에 유지

행동 단계 3와 명제 단계 4를 동일한 방법으로 반복

행동 단계와 명제 단계 확장

 

계획수립 그래프의 확장

• 상호배제 링크
  • 행동 단계와 명제 단계 한 쌍의 추가시, 동시에 실행되거나 만족될 수 없는 동일 단계의 노드들 사이 연결
• 행동 단계의 상호배제
  • 상충되는 결과 도출 : 한 행동의 effect가 다른 행동의 effect가 만드는 명제를 제거하는 경우
  • 간섭 : 한 행동이 다른 행동의 precondition에서 사용되는 명제를 제거하는 경우
  • 경쟁관계 사전조건 : 두 행동이 직전 단계에서 상호배제관계에 있는 명제들을 precondition에서 사용하는 경우
• 명제 단계의 상호배제
  • 상충되는 지지 : 대응되는 두 명제를 만들어내는 이전 단계의 모든 행동이 서로 상호배제 관계에 있는 경우

계획공간 계획수립

• 계획공간 : 모든 가능한 (부분)계획의 집합
• 노드 : 부분계획
• 엣지 : 부분계획을 변환하는 연산자

계층적 계획수립

• 특정 영역의 문제해결을 위한 작업 방법에 대한 지식을 여러 추상화 수준의 계층적인 구조로 기술
• 추상적인 계획에서 시작하여 점점 구체적인 계획으로 구성
• HTN 알고리즘