[인공지능 2주차] Search

Sep 10(Tue)

Agent의 종류

이전 장에서 AI는 Agent라고 말했는데 Agent가 문제를 해결할 때는 크게 2가지 방법이 있다. 첫째는 현재 상황만을 인지하고 미래의 결과는 생각하지 않는, greedy한 친구가 있는데 얘를 Reflex Agent라 한다. 문제를 해결하기 위해 즉시 행동한다(act immediately).

greedy한 agent이기 때문에 눈앞에 보이는 가장 가까운 목표들을 맹목적으로 쫓아가므로 rational(목표를 최대한 달성)하다고 말할 수 있다. 다만 현재 환경에 영향을 많이 받는 모델이다.

반대로 행동에 따른 결과를 고려하여 행동(ask “what if”)하는 숙고하는 친구도 있는데, 얘를 Planning Agent라고 한다. 미래를 생각하여 움직이는 agent인 것인데, 좀 더 자세히 나눌 수 있다.

최적값을 찾아 계획하는 Optimal한 planning이 있고, 답이 있으면 하나라도 찾기 위해 계획하는 Complete한 planning이 있다. 또 모든 케이스의 미래를 고려하는 planning이 있고, 기존의 계획을 토대로 계속 재설계하는 Replanning이 있다.

이 planning agent는 reflex agent보다는 낫지만 여전히 항상 최선인지(optimal)는 판단하기 어렵다. 또한 완전 탐색(complete planning)의 경우 계산하는데에 시간이 많이 걸린다. 그러나 각 시점마다 계획을 바꾸는 replanning에 비해서는 더 높은 성능(score)을 보인다.

이제 이 planning agent를 기반으로 탐색 문제를 살펴보자

탐색 문제(Search Problem)

탐색 문제를 해결하기 위해서는 3가지를 정의해야 하는데, 상태 공간(state space), 다음수 함수(successor function; 일종의 수열?), 시작 상태와 목표 상태(start state & goal state)가 있어야한다.

여기서 successor function은 행동의 제약과 각 행동에 따른 비용(cost)을 갖고 있으면 좋다. 우리가 찾는 solution은 이 시작 상태를 출발해 목표 상태까지 (되도록이면 최소 비용으로) 도달하는 것이 된다.

탐색 문제는 일종의 모델이다. 세상의 문제는 복잡하기에 완벽하게 해결할 수는 없지만, 상황을 포착하고 요약한다면 더 그럴듯한 해결책을 떠올릴 수 있지 않을까?하는 데에서 모델로 여길 수 있다.

상태 공간 그래프(State Space Graphs)

그런데 시작 상태와 목표 상태 중간에도 다양한 상태가 있을 수 있다. 그러나 이들 모두를 고려할 필요는 없다. 우리가 원타는 탐색 상태(search state)는 필요한 몇몇 요소들만을 가지고 세계를 축약한 모델만을 생각하면 된다. 다음과 같이 팩맨의 상태 공간을 생각해보자.

가로 10칸, 세로 12칸의 좌표에 점이 가로 5칸, 세로 6칸에 걸쳐서 존재한다. 오른쪽 열의 귀신 두 마리는 세로의 칸수 12칸 내에서 이동할 수 있고, 팩맨은 동서남북으로 이동이 가능하다.

이때 모든 상태는 어떻게 될까? 팩맨이 있을 수 있는 위치 120곳과 30개의 점의 유무(2^30), 유령 2마리의 위치(12^2), 팩맨이 바라보는 방향(4)을 모두 곱하면 74조 개만큼의 state가 존재한다. 너무나 방대하고, 이를 저장할 용량도 마땅치 않다.

그러나 필요한 디테일에만 집중해보자. 팩맨이 있을 수 있는 위치는 120곳이므로 모든 점을 먹는 경우의 수는 120*2^30정도가 될 것이다. 이것도 정말 많이 줄은 것이다. 중요한 점은, abstraction을 통해 가짓수를 remove할 수 있다는 것이다.

여기서 착안한 방법이 상태 공간 그래프(State Space Graphs)이다. 각각의 상태를 노드로, 각 행동을 화살표로 표현하는데, 목표 상태를 포함한 모든 상태는 딱 한 번씩만 발생한다. (탐색 트리와의 차이점) 하지만 상태 공간 그래프로 아무리 문제 상황을 축약하더라도, 여전히 저장하기에는 크기가 크다는 문제가 있다.

탐색 트리(Search Trees)

이와 대조되는 방법이 탐색 트리(Search Tree)이다. 이 탐색 트리는 루트 노드인 start state에서 점차 leaf node로 내려가며 goal state를 찾아 나선다. 이 경우 왔던 상태로 돌아가는 재귀적인 상황도 발생하기도 하고, goal state를 찾았다해도 그 과정이 모두 다를 수도 있다. 그리고 대부분의 경우, 모든 케이스를 아우르는 트리를 만들어낼 수 없다.(재귀가 가능하기 때문)

상태 공간 그래프(SSG)와 탐색 트리(ST)를 비교하자면, SSG가 그나마 용량이 작긴 하지만, 그마저도 크다. 또한 SSG는 크기가 유한하지만, ST에서는 재귀로 인해 크기가 무한할 수 있다.

Uninformed Search Methods

이제 본격적으로 탐색 알고리즘을 다룰 건데, 먼저 정보가 없는 경우의 탐색(Uninformed Search)을 살펴보겠다. 여기서 uninformed하다는 것은 목적지까지의 거리, 목적지와 관련한 상태 정보 등이 없이 현재 상태만을 관측하여 행동하는 것을 말한다. Blind Search라고도 한다. 자세한 내용은 이 블로그를 한 번 봐보자.

상술한 search tree에서의 탐색은 최대한 적은 leaf를 거치는, 즉 최소 경로일 경우가 좋다(혹은 최소 비용). 이때 fringe(가장자리; frontier:첨단)를 기점으로 탐색을 진행한다는 점을 기억하자.

우리는 전략에 따라 fringe로부터 다음 leaf node들을 탐색할 것이고, 더 탐색할 수 있는 노드가 남지 않는다면 실패를, 남아있다면 나머지 노드를 서치 트리로 넘기고, 목표에 도착한다면 대응하는 solution을 return할 것이다. 이게 General Tree Search이다.

알고리즘을 자세히 보면, 그래프의 모양과 시작 노드 s, 목표 노드에 해당하는지를 한단하는 함수 goal(n)이 파라미터로 들어온다. 우리가 탐색할 frontier는 초깃값으로 시작 노드 s를 갖는다. 이때 frontier의 자료구조는 뒤에 나올 BFS, DFS, 혹은 그 이상의 것에 따라 달라진다.

이제 frontier에서 원소 하나를 비복원 추출(select and remove)하고, 그 경로의 맨 마지막 원소(fringe의 원소)를 goal()과 넣어 bool 값을 얻는다. true라면 해당 경로 (n0,…,nk)를 리턴하고, 그렇지 않다면 해당 fringe의 leaf node들을 경로에 추가하여 frontier에 추가한다. 이렇게 하여 while문이 다 돌았을 때 if절이 통과되면 성공한 경로를 리턴하여 마무리하고, 반복문이 다 돌았음에도 답을 못찾았다면 no solution을 리턴한다.

탐색 알고리즘의 특성

이러한 탐색은 4가지 특성을 갖는다. 첫째, 완전한가?(Complete) 존재하는 솔루션을 하나라도 찾을 수 있으면 완전하다.

둘째, 최적인가?(Optimal) 최소 경로 혹은 최소 비용으로 원하는 goal state에 도달할 수 있는지에 대한 여부이다.

셋째, 시간 복잡도는 어떠한가?(Time Complexity) 너무 시간이 오래 걸리는 알고리즘은 적절치 않다.

넷째, 공간 복잡도는 어떠한가?(Space Complexity) 경로를 찾는 과정에서 저장해야하는 노드들의 개수가 너무 많다면, 그것 또한 적절하지 않다.

여기서 복잡도를 계산할 수 있는데, root node로부터 모든 노드들로 갈라질 때 가지의 수를 b라 하고, 최대 깊이를 m이라 하자. root node는 1개, 그 아래 층은 b개, 그 아래는 b^2, b^3.. 까지해서 b^m개의 노드까지 가므로 일반적인 탐색 알고리즘에서 시간 복잡도와 공간 복잡도는 모두 O(b^m)이다.

Sep 12(Thu)

DFS와 BFS

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 이미 잘 알고 있으니 특기할 점만 표로 정리하자.

DFS: deepest node first	BFS: shallowest node first
Fringe is a LIFO stack	Fringe is a FIFO queue
if m is finite, takes time O(b^m). 모든 노드를 돈다면 저만큼 걸린다	if the shallowest solution be in depth s, it takes time O(b^s). 가장 얕은 층에 위치한 솔루션의 깊이 s까지 도달한다. 유한하다.
fringe takes space O(bm). 스택은 저만큼만 있어도 충분하다	fringe takes space O(b^s). 큐에 s층의 모든 노드가 다 들어갈 수 있어야 한다.
Not Complete. 무한 굴레에 빠질 수 있다	Is Complete! s층에서 반드시 유한한 솔루션을 찾는다
Not Optimal. 항상 왼쪽/오른쪽부터 차례대로 살펴보게 된다.	Not Optimal. 가장 얕은 솔루션은 찾지만, 그게 최적일지는 모른다. 최소비용 또한 아닐 수 있다.

Iterative Deepening Search

이제 상기한 DFS와 BFS의 특징을 조합해 더 나은 Uninformed Search Methods를 찾아보자.

DFS는 BFS에 비해 공간 복잡도가, BFS는 DFS에 비해 시간 복잡도가 더 좋았다. 이 둘의 장점만을 취할 수 있는 알고리즘은 없을까? 그것이 반복적 깊이심화 탐색(Iterative Deepening Search)이다.

IDS는 매번 더 깊은 곳까지를 한계 깊이(depth limit)로 정하고 그곳까지 DFS를 실행한다. 여기서 중요한 점은 매번 기존에 탐색한 지점을 중복 탐색한다는 것이 차이다. IDS는 BFS와 닮았으나 BFS는 중복 탐색이 없었다. 그러나 IDS는 중복 탐색을 포함하여 DFS를 실시한다.

당연히 방문하는 노드는 기하급수적으로 증가한다(# of nodes grows exponentially). 계산을 해보면 DFS보단 적지만 BFS보단 조금 더 많은 노드를 다닌다. 그러나 거시적인 관점에선 IDS나 BFS나 방문 노드의 큰 비율 차이는 없다. 이렇게 방문 노드의 수, 즉 공간 복잡도를 희생함으로써 얻는 장점이 무엇이길래?

BFS의 시간 복잡도 O(b^s)와 DFS의 공간 복잡도보다도 나은 O(bs)를 가져간다. 완전 탐색도 가능하다. 다만 optimal한지에 대해선 여지가 있는데 탐색할 때마다의 비용이 1이었다면 optimal하고 그게 아니라면 최적이 아닐 수 있다.

Uniform Cost Search

자 다시 BFS로 돌아와보자. BFS는 가장 얕은 답을 찾아내기에 행동의 수로는 최소(shortest path in terms of number of actions)라고 볼 수 있다. 그러나 최소 비용은 아니다. 최소 비용은 뭘로 찾을 수 있을까? 이제 살펴볼 것은 그 유명한 다익스트라 알고리즘의 일반화 버전인 균일 비용 탐색(Uniform Cost Search)이다.

가장 저렴한(cheapest) 노드를 찾아 나서는 UCS는 우선순위 큐를 활용한다. DFS랑 유사한 방식이지만 항상 최적의 답을 낸다. 여기서 Uniform이라 함은, 우선순위 큐에서 디큐(dequeue)하는 과정의 cost들이 점차 다 균일한 값으로 모여지기 때문에 붙여졌다.

여기서 시간복잡도는 조금 계산하기가 어려운데, 발견한 solution까지의 비용이 C*이고 각 화살표의 최소 탐색 비용이 epsilon이라면, 유효 깊이(effective depth)는 C star / epsilon이 된다.

따라서 시간 복잡도는 \(O(b^{C*/\epsilon})\)이고 공간 복잡도 또한 \(O(b^{C*/\epsilon})\)이다. DFS의 시간 복잡도와 공간 복잡도가 같은 것에서 비롯된 것이다.

UCS는 완전 탐색이 가능하며, 최적 탐색이기도 하다. 따라서 앞서 다룬 탐색 알고리즘의 특성 4가지를 모두 최적으로 만족한다. 그러나 여전히 UCS도 Uninformed Search이기 때문에 어디로 가는 것이 좋은 방향(direction)인지와 goal의 위치(location information)를 알지 못한다. 탐색하는 과정에서 빙빙 헤메면서 goal을 이곳저곳 찾게 된다. 이것까지 해결하면 정말 좋을 듯 하다!

Uninformed Search끼리의 비교

외우려하지 말고 이해해보자. 셤에 직접적으로 출제하진 않으시고 참고용으로 주실 듯

Informed Search(=Heuristic Search)

다음과 같이 팬케이크를 하노이탑과 비슷하게 가장 넓은 장부터 바닥에 놓이도록 하는 문제를 봐보자. 그냥 무작정 넘기다보면 답을 찾을 수 있을까? 뒤집을 때마다 뒤집는 장 수만큼 비용이 든다면 어느 장부터 뒤집어야 할까? 불가능한 state나 무한한 state도 나올까? 이 문제를 어떻게 해결하면 좋을까?

직관적이게, 가장 큰 장부터 바닥으로 가도록 뒤집으면 된다. 총 n장이 있다면 최대 n번만에 문제를 해결할 수 있다. 이때 ‘가장 큰 장부터’라는 정보가 있었다. 그렇다, 우리는 아직 goal에 대한 정보를 얻지 못하는 uninformed한 상황만 다뤘었다. 이제부터는 목표까지 얼마나 걸리는지에 대한 정보가 있는 Informed(Heuristic) Search를 다뤄보자.

탐색 휴리스틱(search hueristic)은 내가 목표로부터 얼마나 가까운지에 대한 정보이다. 대각선이 불가한 맨하탄 거리(Manhattan distance)나 대각선이 가능한 유클리드 거리(Euclidean distance)를 채택하자. 이때 거리는 벽을 통과하여 측정하므로 거리가 짧다고 해서 진짜 가까운 게 아닐 수 있다.

다음과 같이 Arad에서 Bucharest까지 가는 경로를 생각해보자. 휴리스틱을 갖고 greedy하게 판단한 경로는 노란색으로, 비용은 450이 든다. 그런데? 최적의 경로는 조금 더 경유지가 많은 파란색으로, 418의 비용이 든다. 즉 아무리 휴리스틱이 있어도 greedy할 경우 잘못 갈 수 있으므로 optimal하다고 할 수는 없다.

또한 greedy한 heuristic search의 경우 복잡도가 모두 지수꼴로 나오고, 완전하지도, 최적이지도 않다. 그렇다면 어떻게 해야 하는가? 다음 수업에서 계속..

출처: 인공지능(COSE361) ㅇㅅㅅ 교수님