Chapter 2. Uninformed Search

Example Problems

1. Robotic Vacuum Cleaner
2. 8-Puzzle
3. 8-queens
4. Route-finding problem

Solving Problems by Searching

용어 정의

1. Problem formulation: 어떤 고려할 state, action을 결정할지 정하는 프로세스 → 목표는 주어져 있음
2. 문제는 state space, initial state, goal state, action, transition model, action cost function으로 구성
3. action의 연속은 path를 구성
4. solution: initial state→goal state로 가는 path
5. optimal solution: path cost가 가장 적은 해답
6. search: 목표에 도달할 수 있는 행동의 연속을 찾는 것
7. execution phase에서 행동을 한 번에 한 개씩 찾아낼 수 있다.

Abstraction

1. 정의: 표현에 필요 없는 디테일은 감추는 것
   1. Useful abstraction
   2. Valid abstraction
   3. level of abstraction

State space

1. 정의: 환경이 처할 수 있는 가능한 state의 집합
2. 그래프로 표현: vertices → state, edges → actions
3. solution

Search Tree

1. Node expansion: Node generation, parent / child / successor node
2. reached state: 해당 state에 맞는 노드가 생성된 상태
3. frontier: unexpanded node의 집합
4. redundent path and cycle 신경쓰면 → graph search, 아니면 → tree-like search

탐색 전략 및 성능 평가

1. 탐색 전략
   1. FIFO
   2. LIFO
   3. Highest priority first
2. 성능 평가
   1. completeness
   2. cost optimality
   3. time complexity
   4. space complexity

Task Environment의 특징

• Task environment: 성능평가, 환경, actuator, sensor
• fully observable, partially observable, unobservable ⇒ sensor
• deterministic, nondeterministic, stochastic ⇒ transition model
• discrete, continuous ⇒ state, action, sensor, time
• known, unknown ⇒ laws of physics
• single, multiagent ⇒ agent
• episodic, sequential ⇒ dependency
• static, dynamic, semi-dynamic ⇒ state and action
• fully observable, deterministic, known environment → solution = fixed sequence of actions

Uninformed Searches

Breadth-First Search

1. 정의: 루트 노드가 가장 먼저 확장되고, 루트 노드의 자식이 확장되고, 그 다음 그들의 자식이 확장되고… 하는 식
2. 수도코드 특징
   • IsGoal 함수: frontier에 FIFO queue를 사용
   • reached: 노드가 생성되면 reached list에 저장
3. 성능 평가
   1. Complete: 유한한 branching factor, 유한/무한 state space
   2. Cost optimal하지 않음
   3. time complexity: O(b^d) → b: branching factor, d: 가장 얕은 해
   4. space complexity: O(b^d)
   5. 답이 있으면 무조건 찾을 수 있다.

Uniform-Cost Search

1. 정의: 가장 적은 path cost g(n)을 가진 노드 n으로 확장
2. 수도코드 특징
   • reached: lookup table → key problem.Initial & value node
   • child.PathCost < reached[s].PathCost : 방문은 이미 한 상태에서 비교만
   • late goal test
3. 성능 평가
   1. Complete: 모든 cost가 양수라는 조건이 있어야 함
   2. Cost-Optimal
   3. Time complexity: O(b^{1+\lfloor{C/\epsilon}\rfloor})
   4. Space complexity: O(b^{1+\lfloor{C/\epsilon}\rfloor}) → C*: optimal solution의 cost
4. 하나만 선택하려면 time보다는 space를 줄이는 것이 필요

Depth-First Search

1. 정의: Frontier에 있는 가장 깊은 노드를 확장
   • backing search: 단 1개의 successor만이 생성됨 → 부분적으로 확장된 노드는 다음 번에 확장될 노드에 대해서 기억
   • 새로운 메모리를 할당하는 것보다 현재 상태 설명을 직접 변경함으로써 successor 생성 → backtrack이 가능하게 하기 위해서는 되돌리는 것이 가능해야 함
2. 성능 평가
   1. Completeness
      • not complete: infinite state space, tree-like search
      • complete: finite, graph
   2. Not cost-optimal
   3. Time complexity: $O(b^m)$ → m: 트리의 최대 깊이
   4. Space complexity
      1. O(b^m): graph search → backtracking 정보를 유지해야 하므로
      2. O(bm): tree-like search → 트리 서치를 하면 complete해지지 않으므로
      3. O(m): backtracking search

Depth-Limited Search

1. 정의: depth limit l이 정해져 있음 → 깊이 l인 노드의 경우는 successor가 없는 것처럼 취급
2. 수도코드 특징
   1. result ← cutoff
3. 성능 평가
   1. Not complete
   2. Not cost-optimal
   3. time complexity: $O(b^l)$ → l: depth limit
   4. space complexity: $O(bl)$ → 방문한 노드 리스트를 유지하지 않으므로

Iterative Deepening Search

1. 정의: depth-limited search + increasing limits
2. 성능 평가
   1. Complete
   2. Not cost-optimal
   3. Time complexity: O(b^d)
   4. Space complexity: O(bd) → 메모리 절약
3. 특징
   1. depth first search와 breadth first search의 장점을 모두 포함
   2. hybrid approach로 이용 가능
   3. state space가 메모리 크기보다 크고 depth가 알려지지 않았을 때 이용
   4. Iterative lengthening search: cost가 모두 동일한 것이 아니라면 cost가 커지는 방식으로 deepening

Bidirectional Search

1. 정의: 2개의 frontier로 확장 → 1개는 initial state, 1개는 goal state → 중간에서 만나기를 기원
2. 수도코드 특징
   1. solution 선택 시 어떤 방향이 가장 비용이 적을지 판단하여 그것을 선택함
   2. proceed 함수: 상대방의 reached state 정보를 받아서 실행
3. 성능 평가
   1. Complete
   2. Not cost-optimal
   3. time complexity: O(b^{d/2})
   4. space complexity: O(b^{d/2})