[인공지능] 4주차: 탐색

Problem-Solving Agents

 

입력: Percept(Sensing의 결과물)

low-level의 sensing data와는 다르다.

 

if $seq$ is empty

행동의 sequence(행동의 계획)이 없다면

 

$goal$ = Formulate-Goal($state$)

Agent가 현재 상황에 맞게 스스로 세운 목표

목표도 여러 수준이 있으며, 높은 수준의 목표는 보통 인간이 준다.

Goal을 달성하기 위한 Subgoal을 세우는 건 가능

그래서 스스로 목표를 세웠다고 보기 어려운 경우가 많다는 게 일반적인 의견

 

$problem$ = Formulate-problem($state$, $goal$)

목표를 문제화함 = 현재 상태와 Goal 상태가 다르다는 가정

지금 문제가 없다면 Goal이 달성된 상태라 할 게 없음

Goal: 도달하고 싶은 미래의 상태

현재부터 Goal까지 가야 한다

현재 상태부터 Goal까지 가기 위해서는 환경을 바꿔야 함: Action

Action의 sequence를 만들어야 함: 내가 할 수 있는 행동에는 어떤 것이 있는가?

-> 묵시적으로 Action model이 쓰인다.

 

seq <- Search($problem$)

목표까지 도달할 수 있는 행동의 sequence

 

$action$ <- First($seq$)

지금 수행할 행동 = 시퀀스의 첫 번째

 

seq <- Rest($seq$)

seq 에 나머지 sequence

별 일 없으면 앞으로도 이렇게 수행하겠다는 행동의 sequence를 내부에 저장

Ex) 상황이 동적이라면?

 

return $action$

지금 수행할 행동 반환

 

Agent로서는 이 방법으로 접근할 수 있지만 다양한 이유(동적 상황 등)에 의해 goal에 도달하지 못 할 수 있다.

-> 전역적으로 행동을 결정하는 것이 더 올바른 방법

 

내부적으로 탐색(Search)은 향후의 action의 sequence (= plan)을 짜는 데에 쓰인다.

 

Ex) Romania에 여행을 가서 현재 Arad에 있고, 내일 출국을 위해 빠르게 Bucharest에 도착해야 한다

ⓐ states: 특정 도시에 있는 것

State space: 가능한 모든 상태의 집합

Goal space: 도달하고 싶은 상태의 집합

state로 표현돼야 탐색할 수 있다.

ⓑ actions(≒ state transitions): 도시를 옮기는 것

ⓒ initial state: Arad에 있음

ⓓ goal condition: Bucharest에 있는 것

ⓔ solution: 경로(Sequence of cities)

 

 

Ex) Vacuum world

각 Node가 각 State를 나타냄 - 상태 전이도

ⓐ State(≠Percepts): $Robot location$, 현재 방의 상태($Clean/dirty$)

물론 방이 더러운지 깨끗한지 알아내는 것은 고도의 sensing이 필요하나 여기서는 바로 sense할 수 있다 가정

Partially observable: 방 $A$에 있으면서 방 $B$의 상태까지 아는 것은 불가능

ⓑ Action: $Left$, $Right$, $Suck$

위의 그림은 Agent 동작(L, R, S)에 따라 어느 상태에서 어느 상태로 변하는지 나타낸 것

ⓒ Initial state: 8 state(State 조합의모든 경우의 수는 8개임)

ⓓ Goal state: 사실 목표 상태가 될 수 있는 건 두 개 뿐 (A에 있으면서 둘 다 깨끗한 거, B에 있으면서 둘 다 깨끗한 거)

 

 

 

Ex) 8-puzzle

 

 

state: 9!(location of tiles)

actions: move blank $left$, $right$, $up$, $down$

Initial state: 주어짐

Goal contidion: 주어짐

* 최적의 solution은 NP-hard

 

 

 

Tree

Arad에 있을 때 할 수 있는 행동은(갈 수 있는 도시는) 세 곳 뿐이다.

그리고 그 다음 도시에서 갈 수 있는 도시는 ...

-> Tree 형태를 띠게 된다.

 

Arad가 목표가 아니므로 새로운 상태를 만든다(Expanding state)

 

Strategy(탐색 전략 = 탐색 방법): 후보가 여러 개면 어느 노드를 먼저 확장할 것인가

= 어느 노드를 먼저 탐색할 것인가

 

loop의 핵심:

모든 노드에 대해 그 노드가 Goal인지 검사한다

Goal이 아닌 말단 노드를 부모로 해서 그 말단 노드에서 갈 수 있는 자식 노드를 expand한다.

 

Root 노드 설정 후 목표인지 검사

 

탐색 전략 평가

완전성(Completion): 해가 있다면 무조건 해를 찾아냄을 보장한다.

최적성(Optimality): 최적의 해를 찾는다.

시간 복잡도(Time complexity)

공간 복잡도(Space complexity)

 

 

Search strategies

Uninformed search

가장 기본적인 탐색

 

 

Breadth-First Search

Root에서 가까운 것부터 expand

모든 노드마다 거의 같은 시간이 필요함

모든 노드에 대해 목표인지 검사 후 목표면 확장하는 작업이 필요

 

Complete: Y

Time: $1+b+b^2+b^3+ \cdots + b^d = O(b^{d+1})$ ($b$: 가지 수 = subnode 수 = 2, $d$: 차수)

Space: $O(b^{d+1})$ (메모리에 모든 노드가 유지된다)

Optimal: Y

원래는 $O(b^d)$인데 깊이 $d$의 모든 노드는 목표 탐지전에 확장되므로 결국 깊이 $(d+1)$의 노드까지 확장된다.

 

 

 

Uniform Cost search

비용이 가장 적은 노드를 먼저 확장한다.

너비우선 탐색
BFS에서는 비용을 안 따짐

근데 이거랑 BFS랑 거의 똑같음

 

Complete: Y

Time: $O(b^{\lceil \frac{C*}{\epsilon} \rceil})$

Space: $O(b^{\lceil \frac{C*}{\epsilon} \rceil})$

Optimal: Y

$C*$: 최적 해의 비용

$\epsilon$:: 모든 동작의 최소 비용

 

Depth-First Search

Root에서 먼 것부터 expand

왼쪽을 먼저 확장한다.

 

Complete: N (Infinite-depth space)

Time: $O(b^m)$

Space: $O(bm)$ (Linear space)

Optimal: N

 -> 깊이 제한을 준다.

 

 

Depth-Limited Search

어떤 깊이 제한 $l$를 설정해 그 밑으로는 안 내려가는 Depth-First search

-> 깊이를 어떻게 제한할 것인가?

Depth limit 설정의 어려움

 

 

Iterative Deepening Search

반복적으로 깊이를 더 깊게 판다

너비 우선과 깊이 우선을 섞은 거 = 너비 우선은 최적성과 완전성을 보장한다 + 깊이 우선은 공간 복잡도가 작다

요약하면 깊이 제한을 늘려가며 (목표를 찾을 때까지) 반복적으로 깊이 우선 탐색을 여러 번 하는 것

 

① 깊이 우선 탐색

② 각 노드가 목표인지 검사한 후 깊이 제한에 도달하면 목표가 아니어도 expanding은 안 함

③ 목표를 찾지 못 하면 깊이 제한 확장

 

탐색 완료된 노드는 메모리에서 바로바로 제거됨 -> 공간복잡도 낮음

 

Complete: Y

Time: $O(b^d)$

Space: $O(bd)$

Optimal: Y

 

 

Repeated States

같은 상태로 여러 군데에서 도달

-> 목표 상태로 도달하는 경로는 여러 개일 수도 있다.

 

 

Graph Search

fringe: 확장가능한 노드

closed: 확장한 적 있는 노드의 집합

if Goal-Test[problem](State[node]): 목표 상태에 도달했으면 solution을 return 한다.

if State[node] is not in $closed$ then: 확장한 적 없는 노드면

add State[node] to closed: closed에 추가하고

fringe <- InsertAll(expand(node, problem, fringe): 선택된 노드를 확장 후 새로운 자식 노드를 후보 집합인 fringe에 넣음