Greedy Best-First Search

Evaluation Func & Heuristic Func

1. Evaluation func f(n)
   1. node n의 estimated cost
2. Heuristic func h(n)
   1. node n에서 goal state로 가는 가장 저렴한 비용의 추정치
   2. root-finding problem에서 각 도시별 직선거리 함수

Greedy Best-First Search

1. 정의: best-first search의 일종 → h(n) value가 가장 적은 노드를 확장
   1. table을 유지하는 경우 그래프 (중복을 고려)
   2. 없애는 경우 tree search (중복을 고려하지 않음)
2. 성능 평가
   1. Completeness → 사이클 발생
      1. Not complete: tree-like search
      2. complete: graph search
   2. Not cost-optimal
   3. Time Complexity: O(b^m)
   4. Space Complexity: O(b^m)

A* Search

1. 정의: f(n) = g(n) + h(n)을 evaluation function으로 이용
   1. g(n): n까지 오는 데 비용
   2. h(n): n부터 goal까지 가는 데 추정되는 비용
2. Admissible Heuristic Function
   1. goal에 도달하기 위한 비용을 절대 overestimate하지 않음
   2. h(n) <= h*(n) : h(n)은 실제 값
   3. admissible heuristic function을 이용한다면 A* search는 cost-optimal하다.
3. Consistent Heuristic Function
   1. consistent: 모든 노드 n과 a라는 행동으로 생성된 자식 n’이 있을 때
   2. h(n) <= c(n,a,n') + h(n') 성립
   3. consistent heuristic function을 이용한다면 A* search는 cost-optimal하다 → 모든 consistent heuristic은 admissible하다.
4. Search contours
   1. A*는 가장 적은 f-cost를 가진 frontier 노드를 확장하므로 등고선이 커지면서 cost가 점점 커지는 형태이다.
   2. 좋은 휴리스틱을 가졌다면, 등고선은 점점 goal state에 가까워질 것이며 최적 경로에 가까워질수록 더 좁아질 것이다.
5. Optimally Efficient → C* : optimal cost
   1. surely expanded: f(n)<C*
   2. depends: f(n)=C*
   3. never expended: f(n) > C*
6. Weighted A* Search
   1. 정의: C와 WC*사이의 cost를 가지는 해답을 찾는 것
   2. f(n)=g(n)+W*h(n)
   3. Suboptimal search techniques
      1. bounded suboptimal search: 실제 optimal cost의 1/2배 ..
      2. bounded-cost search: 실제 cost는 모르고 얼마 안에 도달하는 경로 찾기
      3. unbounded-cost search
      4. beam search: 메모리는 적게 유지 → 가장 좋은 score인 것만 유지하고 나머지는 가지치기
7. 성능 평가
   1. Complete
   2. Cost-optimal
   3. Time-complexity <= O(b^d)
   4. Space complexity <= O(b^d)

Iterative-Deepening A* Search

1. 정의 (IDA*)
   1. iterative deepening search + A* Search
   2. 이전 반복에서 cutoff를 초과하였던, f-cost가 가장 작은 임의의 노드를 cutoff → 기준보다 크지 않았다면 계속 내려감
2. 특징
   1. f-cost가 모두 정수일 때 잘 작동
   2. f-cost가 모두 다른 노드일 때, 반복 숫자가 결국 state수와 같아질 수 있다.

Recursive Best-First Search

1. 정의 (RBFS)
   1. recursive depth-first search + best-first search
   2. f-limit을 현재 노드가 초과한다면 다시 감아 내려가서 alternative path로 이동
2. 진행 과정
   1. 일단 처음 limit = 무한대
   2. 다음 경로 중 가장 작은 cost인 쪽을 선택, limit은 두 번째로 가장 작은 값으로 변경
   3. 내려가서 limit과 cost의 값을 비교 → cost가 limit보다 크면 해당 cost를 limit으로 변경하고, limit과 같은 cost를 가졌던 node를 확인
3. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(bd)
      • 지나치게 적은 메모리 사용 → 계속 같은 state를 반복하여 탐색

Simplified Memory-Bounded A* Search

1. 정의
   1. A* search를 메모리가 꽉 찰 때까지 진행
   2. 메모리가 꽉 찼다면 f-cost가 가장 큰 worst leaf node를 버림
   3. 잊어버린 노드의 값을 다시 부모에게 전달
2. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(b^d)

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})