[인공지능 : AI, Artificial Intelligence] Lecture 5 : Search 2부

Lecture 5

지난 이야기..

들른 곳이 closed 나머지가 open list에 있는 것. agent로 보는 관점에서 보자.

• 어떤 순간에 주어진 환경에서 나의 action을 결정하는 과정을 살펴보고 있었다.

• 환경은 open, closed list이다. 모델은 tree로 구성되어있고, agent는 goal test를 해서 goal인지 확인한다.

• 이번에는 어떤 Information을 가지고 있을 때, goal에 더 가까운 쪽으로 선택을 하는 방법이 Informed Search이다.

• Local Search의 경우, Goal을 모른다. 대신 Utility를 사용한다.

여러 다른 탐색 전략을 비교하는 기준

• completeness : 답 찾는 거 보장?
• optimality : 답이 최적해 보장?
• time complexity : heuristic, MC carlo, 강화학습...

Informed Search

uninformed search, informed search, local search 차례로 기술이 발전했다.
여기서 USC의 경우 정보라기 보단 지나온 기록이기 때문에, Informed라고 보지 않는다.

위 그림에서 systemic search strategy가 tree를 만든다는 의미이다.

completeness를 보장하는지가 매우 중요하다.

A* Algorithm

A*의 경우 속도와 completeness 모두 보장한다.

UCS는 기록을 사용하는 거지 추정에 사용가능한 정보를 사용하는 것이 아니다.
이와 비교해서 heuristic search는 일종의 경험적 지식과 힌트를 사용하는 것이다.

예를 들어서 틱택토에서 heuristic 값을 number of winning lines로 두면 다음과 같다.
이런 방식으로 state의 개수를 줄이는 건 heuristic search가 맞다.

A*는 open list는 유지하므로 completeness는 보장한다.
추후에 보장된다는 증명을 살펴 볼 것.

Heuristic Search는 goal에 도달하면 다른 경로는 생각 안하고 Search를 멈춘다.
Best first search의 범주에 포함된다.

f = g + h를 사용한다.

Greedy Algorithm은 h만을 사용하고, BFS는 g만을 사용한다.

참고 : 여러가지 Search 방법론에 대한 정리

• Breath-first

• Depth-first

• Best-first = open list에 있는 것 중에서 가장 좋은 것을 선택하는 것이다. 지나온 것을 버리지 않는다. 다시 봐야할 후보로 놓는다.

  • cost가 모두 동일하다면 그 Best first는 Breath first와 같아진다

• Greedy Search = 현재 state에서 가장 좋은 것을 선택해서 action하는 것을 의미한다. 지나간 것은 버린다. 과거의 state로 돌아갈 수 없다.

• Local search : 일단 좋은 쪽으로 가면 goal이 있지 않을까? 하는 느낌으로

---

Heuristic을 사용해서 문제에 접근하자.
Heuristic이 없다면, MC 혹은 Reinforcement를 사용한다.

Heuristic Search 예시

• greedy best-first search : best-first search이긴한데, 추정치만 쓰겠다는 의미이다. 추정치만 쓰기에 compltetness를 보장 못한다.
• A* search : cost g값과 추정치 h*를 합한 f를 사용해서 다음 action을 정한다.
• IDA*

다음은 A*의 전체적인 그림이다.
추정치를 이용해서 단번에 Goal에 근접한 state로 넘어간다.

다음은 틱택토에 대한 예시이다.
뒤집으면 같은 결과 나온 것을 이용해서 space의 크기를 줄인다.

또 틱택토에 대한 예시이ㅏㄷ.
각 위치에 따른 h값은 이길 가능성에 대한 추정값으로 둘 수 있다.

미국의 각 지역별 거리에 따른 경로를 표시한 그래프이다.
직선거리를 heuristic 값으로 둘 수 있다.

체스의 경우

• 내가 가진 말의 개수와 상대가 가진 말의 개수의 차이
• 각 말의 중요도 및 가치를 수치로 환산
• 각 말의 위치의 중요도를 수치로 환산

Heuristic Search가 통하지 않는 경우

바둑의 경우

• space가 250^180 정도...
• 체스와 달리 heuristic이 없다
• Deep Reinforcement Learning
  • 기본적인 탐색구조
  • MC
  • Reinforcement Learning

UCS, greedy, A* 모두 best first search를 하면된다.
단지 f인지 g인지 cost인지의 차이.
각각 분류해보라.

---

이후는 강의노트 기반이다.

Search as a problem solving technique

Goal based agent를 생각해보자.
이 agent는 search problem을 다음의 방식으로 formulate할 수 있다.

• providing a description of the current problem state,

• providing a description of its own actions that can transform one problem state into another one,

• providing a description of the goal state where a desired goal holds.

• solution은 다음과 같이 구성되어 있다.

  • path from current state to the goal state
  • path cost function이 각 path마다 지정된다.
  • 서로 다른 해답은 path cost function의 평균을 비교해서 우열을 가릴 수 있다.

다음 두 종류의 Search method가 있다.

• Uninformed search (no problem-specific information is available to direct the search). We shall use the Missionaries and Cannibals (M&C) problem to illustrate uninformed search.
• Informed search (there is a problem-specific information helping the agent through the search process). We shall use the 5-puzzle problem (a downsized version of the 8-puzzle problem) to illustrate informed search.

Informed Search

domain knowledge를 사용한다.

• Use a heuristic function that estimates how close a state is to the goal
  • heuristic function : drastically limits search for solutions in large problem spaces
  • Heuristic은 Optimal을 보장하지 않는다.
  • Heuristic은 completeness를 보장하지 않는다.
  • 그저 괜찮은 수준의 solution을 괜찮은 수준의 time 내로 구하는 것에 목적이 있다.
• A heuristic does NOT have to be perfect!

다음은 Informed Search의 예시이다.

1. Greedy best-first search
2. A* search
3. IDA*

Ways to use heuristic information

• To decide which node to expand next
• In expanding a node, to decide which successor(s) to generate
• To decide which nodes to prune from the search space (어떤 node 제거할 지)

Ordered or best-first search

• use an evaluation function f* to estimate the promise of a node
• compute f* for each node and select node with minimal value to examine next - goal is to reduce the number of nodes examined
• effectiveness depends on f*
• f*(n) = g(n) + h*(n)

• 이전까지의 탐색방법은 출발점에서 현재 상태까지의 거리가 가장 짧은 쪽으로 path 가 진행되어 왔다
• 이제는 현재 상태에서 목적 상태까지의 남은 거리를 “추정”하여 가장 좋은 쪽으로 path 를 선택하는 것을 고려하기로 한다.
• 출발점에서 현재 상태까지의 거리 -> g(n)
• 현재상태에서 목표점까지의 추정 거리 -> h(n)*
• 그 구조는 다음과 같다.

Greedy Algorithm (Best-First Greedy)

• Greedy-best-search 는 h 값만 가지고 찾는 것
• Initial state 에서 부터 시작해서 진행하면서 지금 현재 상태에서 갈 수 있는 것 중에서 제일 좋은 곳으로 선택.
• A common case: Best-first takes you straight to the (wrong) goal
• Worst-case: like a badly-guided DFS

• Evaluation function h(n) = cost from n to closest goal (heuristic)
• Greedy search expands the node that appears to be closest to goal

function Greedy-Best First-Search(initialState, goalTest)
  return Success or Failure /* Cost f(n) = h*(n) */

  frontier = Heap.new(initialState)
  explored = Set.new()

  while not frontier.isEmpty():
    state = frontier.deleteMin()
    explored.add(state)

    if goalState(state):
      return Success(state)

    for neighbor in state.neighbors():
      if neighbor not in frontier or explored:
        frontier.insert(neighbor)
      else if neighbor in frontier:
        frontier.decreaseKey(neighbor)
  return Failure

단순히 글로 나타내면 순서는 다음과 같다.

1. current state = initial state
2. expand current state
3. evaluate offspring state s with heuristic h(s)(estimates cost of path from s to goal)
4. $current state = argmin_s(h(s))$, $s \in offspring(current state)$
5. current state != goal state -> go to step 2

• Complete : No, stuck in loop. Complete only in finite space and repeated loop check
• Time : O(b^m). good heuristic give dramatic improvement
• Space : O(b^m). Keeps all node in memory
• Optimal : No

A* Search

• a combination of the best-first greedy search and uniform-cost search
  • 즉, Cost function만 다르고 메커니즘은 UCS를 따른다.
• Minimize the total estimated solution cost
• Combines:
  • g(n): cost to reach node n
  • h(n): cost to get from n to the goal
  • f(n) = g(n) + h(n)
    • f(n) is the estimated cost of the cheapest solution through n
  • 출발 상태에서 현재 상태까지의 경로비용과 현재상태에서 목적 상태까지의 추정 경로 비용을 모두 고려한다.
  • 여기서 h(n)은 goal 으로 빠르게 인도하는 역할(forward cost)을 하고, g(n)은 shortest path 를 유지하는 역할(backward cost)을 한다.
  • 또한 h(n)은 heuristic 을 함수로 변환한 것이며 search space 를 줄여서 효율적으로 탐색하도록 유도한다.
• We assume here that f(n) never decreases
• A* search is both optimal and complete.
• any time a shorter path between the start node and any node is found, A* must update cost of paths going through that node.
  • so implementation is hard

function Greedy-Best First-Search(initialState, goalTest)
  return Success or Failure /* Cost f(n) = g(n) + h*(n) */

  frontier = Heap.new(initialState)
  explored = Set.new()

  while not frontier.isEmpty():
    state = frontier.deleteMin()
    explored.add(state)

    if goalState(state):
      return Success(state)

    for neighbor in state.neighbors():
      if neighbor not in frontier or explored:
        frontier.insert(neighbor)
      else if neighbor in frontier:
        frontier.decreaseKey(neighbor)
  return Failure

예시로 8 puzzle을 Heuristic Search로 푼다고 하자.

계산 방법 예시

Optimality of heuristic search

이런 질문을 할 수 있다.
h*가 h 보다 항상 작은가? 즉, 최단거리를 보장하는가?
근데 나도 모른다.

• 만약 h*=h 이면 perfect search. Optimal number of nodes evaluated. (minimum cost path can be found!)
• 만약 h*=0 이면 reduces to blind uniform cost algorithm (minimum cost path can be found!)
• 만약, h*가 h 도 아니고 0도 아니면, can minimum cost path be found?
  • 만약 h*<=h 이면 최소 비용 경로 탐색을 보장한다. => admissibility conditions (completeness와 optimality를 보장)

Admissibility

• 만약 두 개의 알고리즘 A1 & A2 가 있어서 각각 다른 heuristic h1과 h2*을 사용하고 h1>h2* 이라면,
  • A1 is more informed than A2,
  • and A1 will never expand a node that A2 will not.
• A good heuristic must be admissible
• An admissible heuristic never overestimates the cost to reach the goal, that is it is optimistic
• A heuristic h is admissible if

$$
∀ node n, h(n) ≤ h∗(n)
$$
where h∗ is true cost to reach the goal from n.

• $h_{SLD}$ (used as a heuristic in the map example) is admissible because it is by definition the shortest distance between two points.