• 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note1을 정리하였음을 밝힙니다.
• 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다.

Summary

• 탐색 문제(search problem)은 state space, successor function, start state, goal test로 구성된다. 탐색 문제는 BFS, DFS, UCS의 uninformed search와 Greedy Search, A* Search의 informed search를 통해 풀 수 있다.

Search problem

1. Agent

탐색 문제에서 에이전트(agent)는 주어진 환경에서 목적 상태까지 최고/최적의 해결책을 주는 일련의 행동을 수행해야 한다.
이때 세계의 현재 상태만을 기준으로 행동하는 모델과 미래 상황까지 예측해 행동하는 모델이 있다. 후자 planning agent는 전자 reflex agent의 성능보다 대개 뛰어나다. 이때 이 에이전트는 주어진 상황에서 최고의 가능한 움직임을 결정한다는 점에서 '지능적'이다.

에이전트가 택하는 일련의 행동이 탐색 문제에서 우리가 얻어내야 할 해결책(solution)임을 기억하자. 이때 해결책을 선택하는 기준이 informed인가, uninformed인가에 따라 선택하는 알고리즘 역시 달라진다.

2. State Spaces and Search problem

탐색 문제는 다음 네 가지 요소로 이루어져 있다.

1. state space: 모든 가능한 상태들의 집합
2. successor function: 현재 상태를 기반으로 다음 상태 및 비용을 연산하는 함수
3. start state: 초기 상태
4. goal test: 주어진 상태가 목적지인지 확인하는 함수

탐색 문제는 start state에서 시작해 successor function을 통해 자신의 state를 반복적으로 확장해가며 goal test를 하는 모델이다. 이때 goal test로 이어지는 경로를 어떻게 구할지를 plan이라 하며, 사전에 결정한 strategy에 따라 그 순서가 달라진다.
이때 주어진 문제와 문제를 해결하기 위한 조건에 따라 정보가 달라질 수 있다.

1. Pathing: 좌푯값, 동서남북 이동, 좌표 갱신 successor, 현재 좌표가 목적지인지 확인
2. Eat-All-Dots: 좌푯값과 dot의 유무, 동서남북 이동, 좌표 및 dot 갱신, 모든 dot이 다 false인지 확인

이때 1번 경로 찾기 문제는 2번 모든 점을 다 먹는 문제보다 더 적은 정보만을 필요로 한다.

"어떤 종류"의 문제를 푸는 지에 따라서 필요한 변수 설정 자체가 달라진다. 물론 해당 문제를 풀기에 유용한 알고리즘 역시 달라진다. 후술할 내용이지만, 속도인지, 비용인지, agent의 수가 몇 명인지 등에 따라 탐색 알고리즘으로 사용할지 택해야 한다.

3. State Space Size

팩맨 게임 문제를 푸는 데 써야 하는 연산량 또한 state 정보와 관련된다. 가령 다음과 같은 문제가 주어진다.

1. 팩맨 좌표: 팩맨 한 명, 120개의 위치
2. 팩맨 방향: 동서남북
3. 고스트 좌표: 고스트 두 명, 12개의 위치
4. 음식(점) 구성요소: 30개, 두 가지 상태(먹힘/먹히지 않음) 존재

따라서 전체 가능한 state space size는 $120*4*12^2*2^{30}$.

4. State Space Graphs and Search Trees

상태 공간 그래프는 상태를 의미하는 노드 및 successor를 의미하는 방향 간선으로 구성된다. 이 간선에 successor function을 수행하는 데 드는 비용이 weight로 구성된다. 일반적으로 상태 공간 그래프는 메모리 상 전체 그래프를 담기에는 크기가 매우 크다. 상태 공간 그래프에서 각 노드는 정확히 '한 개'의 state로 표현된다.

탐색 트리는 특정 state가 몇 번 나타나는지에 대한 제약 조건이 없다. 즉 "여러 번" 같은 노드가 나타날 수 있다. 탐색 트리의 노드는 state 그 자체만이 아니라, start state에서 특정 state까지 경로에 위치하는 state를 의미하기 때문이다. 다시 말해, 경로 상 동일한 노드는 여러 번 나타날 수 있다. 따라서 특정 state에 이르기까지 다양한 경로가 탐색 트리에서 나타날 수 있다. 따라서 상태 공간 그래프보다 사이즈가 더 크다.

이때 탐색 문제를 해결려면 어떻게 효율적으로 연산해야 할까? succeessor function을 사용해야 한다. 현재 수행 중인 state만을 저장해 새로운 다음 state만 얻어내면 되기 때문이다. 따라서 특정 경로를 저장하고 있는 탐색 트리를 통해 탐색 문제의 solution을 풀 수 있다. 탐색 트리는 goal state에 도달할 때까지 특정 노드의 successor로 노드를 반복적으로 대체, 즉 '경로'를 구한다.