[인공지능] Ch12 Search

 

Agent

• 인공지능에서 agent란 독자적으로 행동하는 하나하나의 주체를 의미한다.
• decision-maker == AI model
• 어떤 조치를 취할 것인지 결정하는 구성 요소

1) Reflex Agents

agent의 종류의 첫 번째로 Reflex Agent가 있다.

이 agent는 현재 인식(및 기억력)에 따라 작업을 선택한다.

위 그림을 보자. 

로봇(agent)은 사과만을 보고 사과에 닿기 위해 점프를 하지만 그 이후에 떨어질 것은 예측하지 못하고 있다.

즉, 향후 행동의 결과를 고려하지 않는다.

 

2) Planning Agents

두 번째 종류로는 Planning Agents가 있다.

이 agent는 "만약에"를 물으며 행동의 (가설화된)결과에 따라 결정한다.

위 로봇은 처음에 보았던 로봇과는 반대로 도구를 이용하고 있다.

점프를 하면 떨어진다는 결과를 예상하고 다른 결정을 한 것이다.

 

이 agent는 행동에 대해 세상이 어떻게 진화하는지에 관한 모델을 가지고 있어야 한다.

즉, 세상이 어떻게 될지를 고려하는 것이다. 

Optimal planning vs. Complete planning

- 최적의 계획은 언제나 가장 좋은 해결책을 가지고 있지만, 시간이 많이 걸린다는 단점이 있다.

- 완벽한 계획은 최고의 해결책은 아닐지라도 우선 가까운 것을 고르지 때문에 시간이 적게 걸린다.

 

Planning vs. Replanning

- 계획은 미래 행동을 모두 만들어서 목적을 달성하는 것이다.

- 재계획은 제한된 행동만을 가지고 제한된 결정을 한다.

 

Search Problems

Search Problems란 agent가 어떤 선택이 좋은 결과로 이끄는지 탐색하는 것을 의미한다.

 

search problem은 다음과 같이 구성된다.

• 상태 (state space): 필요한 state만 골라서 가능한 모든 상황을 모아둔 것
• 성공 함수 (successor function): state에 따라 함수가 변하는 것
• 시작 상태, 목표 상태 (start state, goal state): 이 함수의 시작과 끝

 

State Space Graphs

state space graph는 search problem을 수학적 표현으로 나타낸 것이다.

상태 공간 그래프에서 각 상태는 한 번만 발생한다.

메모리에 이 전체 그래프를 구축하는 경우는 거의 없지만(노드들이 많아서) 유용한 아이디어이긴하다.

 

Search Trees

search tree는 계획을 트리 구조로 나타낸 것이다.

시작 상태는 루트 노드이다.

자식 노드는 successors에 해당한다.

이도 마찬가지로 대부분의 problem에서 실제로 전체 트리를 만들 수는 없다.

 

Search Algorithm Properties

Search 알고리즘에서 분석하는 4가지 지표는 다음과 같다.

- Complete: 해가 존재하는 경우 반드시 해를 찾을 수 있는지

- Optimal: 최저 비용의 경로를 찾을 수 있는지

- Time complexity: 해를 찾는데 걸리는 시간

- Space complexity: 검색에 필요한 메모리 공간

 

위 그림에서 b는 분기 요인, m은 최대 깊이를 의미한다.

전체 트리 노드의 수는 다음과 같다.
1 + 𝑏 + 𝑏^2 + … . 𝑏^𝑚 = 𝑂(𝑏𝑚)

 

1) Depth-First Search(DFS) Properties

우리가 알고 있는 그 DFS가 맞다. 깊이를 우선으로 탐색하는 전략이다.

 

✅DFS는 어떤 노드를 확장하는가?
-  트리의 일부 left prefix.
- 전체 트리를 처리할 수 있다.
- 𝑚이 유한하면 𝑂(𝑏^𝑚)에 시간이 걸린다. (1+𝑏+𝑏^2+⋯+𝑏^𝑚=𝑂(𝑏^𝑚))

✅finge(현재 선택 가능한 노드의 컬렉션)는 얼마나 많은 공간을 차지하는가?
- 뿌리를 내릴 수 있는 길에는 형제자매만 있으므로 𝑂(𝑏𝑚) (𝑏+(𝑏−1)+(𝑏−1)+⋯+(𝑏−1)=𝑂(𝑏𝑚))

✅해가 존재하는가?
- 𝑚는 무한할 수 있으므로 사이클을 방지해야 한다. 무한하지 않은 경우에만 해가 존재한다.

 

✅최적해를 찾을 수 있는가?
- 아니다. 깊이나 비용에 관계없이 "left most"해를 찾는다.

 

2) Breadth-First Search(BFS) Properties

BFS는 너비를 우선으로 탐색하는 전략이다.

 

✅BFS는 어떤 노드를 확장하는가?
- 가장 얕은 솔루션 위의 모든 노드 처리
- 가장 얕은 솔루션의 깊이를 𝑠로 한다.
- 검색하는 데에는 𝑂(𝑏𝑠)시간이 걸린다.

✅fringe는 얼마나 많은 공간을 차지하는가?
• 대략 마지막 단계가 있으므로 𝑂(𝑏^𝑠)

✅해가 존재하는가?
• 해가 존재한다면 𝑠은 유한해야 하므로 존재한다.

✅최적해를 찾을 수 있는가?

- 모든 경로의 비용이 동일하다면 찾을 수 있다.

 

다음은 DFS와 BFS를 한번에 비교한 사진이다.

 

3) Iterative Deepening

DFS의 공간에 대한 이점과 BFS의 시간에 대한 이점을 적절히 섞은 것이다.

 

예시)

Run a DFS with depth limit 1. If no solution…
Run a DFS with depth limit 2. If no solution…
Run a DFS with depth limit 3. …..

 

낭비적으로 중복되는 것이 아닌지 의문을 품을 순 있지만, 일반적으로 대부분의 작업은 검색된 최저 수준에서 이루어지기 때문에 그리 나쁘지 않다고 한다.

 

4)Uniform Cost Search (UCS) Properties

낮은 비용의 경로를 우선으로 탐색하는 전략이다.

 

✅해가 존재하는가?

- 최선의 솔루션에 유한한 비용이 있고 최소 arc 비용 양수라고 가정하면 그렇다.

✅최적해를 찾을 수 있는가?

- 그렇다.

 

• UCS의 장점은 complete하고 optimal 하다는 것이다.
• 단점은, 목표에 대한 정보가 없기 때문에 탐색이 효율적이지 않다는 것이다.