SOLVING PROBLEMS BY SEARCHING
- 올바른 길을 가려면 당연히 즉각적으로 행동을 취하지 않고 agent는 계획을 세워야 한다. 목표에 도달기 위한 길을 구성하는 행동을 하는 형태를 problem-solving agents라고 하고 그것을 수행하는 프로세스를 search라고 한다.
- problem-solving agents가 atomic representation(원자적 표현)을 사용하는데, 그것은 world의 상태들을 전체로 취급하며 문제해결 알고리즘에 대해 구조적으로 안에 포함되지 않는다. 즉, 내부적으로 활동하지 않고 전체적인 것을 파악한다.
*atomic representation(원자적 표현) : 한 구역에서 다른 구역으로 이동한다. 그렇게 world를 구분시켜 준다.
- 우리는 agent가 목표에서 얼마나 멀리 있는지 추정하는 informed 알고리즘과 추정치를 사용할 수 없는 정보에 uninformed 알고리즘 사이에서 뭐가 뭔지 구분할 것이다. (정보가 있으면 더 효율적이다.)
- 빅오의 개념을 사용한다.
Problem-Solving Agents
- 만약 agent가 추가적인 정보, 만약 환경이 unknown이면, agent는 행동 중 하나를 무작위로 하는 것이 최선이 될지도 모른다. 여기서는 우리의 agent는 항상 정보에 접근할 수 있다고 가정하고 진행한다. 그러기 위해서는 4가지 단계가 있다.
(1) Goal formulation: agent가 goal로 가야 하는 환경. 즉, goal이 생김
(2) Problem formulation: goal이 주어진 상황에서, 무슨 action과 states를 고려할 것인지 결정하는 과정을 말한다.
(3) Search: 목표를 도달할 때까지 작동한다. 그렇게 goal을 찾은 방법을 solution이라고 한다. 수많은 시뮬레이션으로 goal에 도달했겠지만 결국은 찾거나 solution이 없거나가 결과로 나온다.
(4) Execution: agent는 solution에서 action들을 한 번씩 작동한다. (action1 -> action2, action2->action3)
Search problems
기본 용어들
agent: 환경을 인식하고 행동하는 개체
state: agent와 그 환경이 구성되어 있는 상태
initial state: agent가 처음 행동할 기본 state
actions: state에서 행동할 수 있는 선택
Actions(𝒔) returns the set of actions that can be executed in state 𝒔
transition model: 어떠한 state에서 어떠한 것도 가능하게 하는 action을 실행하는 결과가 나타나는 state에서의 설명
Result(𝒔, 𝒂) returns the state resulting from performing action a in state 𝒔
state space: 어떠한 action에 의해 initial state에서부터 갈 수 있는 모든 state의 세트
Goal Test: 주어진 state가 goal state인지 결정하는 방법
Path Test: 지정된 경로와 관련된 숫자적인 비용
solution: 초기 state부터 목표 state까지 향하는 행동들의 나열
optimal solution: solutions 중 가장 낮은 path cost를 가지는 solution
node: 아래의 내용을 가지는 데이터 구조이다.
- state
- parent(이 노드에서 발생된 노드의 부모)
- action(노드를 갖기 위해 parent에게 적용된 action)
- path cost(initial state에서 노드까지 가는 비용)
Approach: (73~82p)
- inital state를 포함하는 frontier에서 시작한다. (1)
- 반복한다:
만약 frontier가 비어있으면, solution은 없다.
node를 frontier에서 제거한다. (2) (4)
node가 goal state를 포함하고 있으면, solution을 반환다. (4)
node를 확장한다, frontier에 결과가 나온 노드들을 추가한다. (3)
순서: (1)->(2)->(3)->(4) // if goal= solution. else return (2)
문제가 생긴다면: 갔던 곳을 또 가는 비효율적인 action이 발생하면 무한 루프가 생긴다.
Revised Approach: (85~99p)
-스택을 사용한다.(후입선출)
ㅎ- inital state를 포함하는 frontier에서 시작한다.
- 비어있는 explored set를 설정하고 간다.
- 반복한다:
만약 frontier가 비어있으면, solution은 없다.
node를 frontier에서 제거한다. ---->node를 explored set로 옮긴다. (stack사용) (2) (4)
node가 goal state를 포함하고 있으면, solution을 반환다. (4)
node를 확장한다, frontier에 결과가 나온 노드들을 추가한다. (3)
순서: (1)->(2)->(3)->(4) // if goal= solution. else return (2)
uninformed search: 정보가 없는 상태의 서치 방법
아래는 uninformed search의 종류들이다.
Depth-First Search (DFS):
-가장 깊은 노드를 frontier에 항상 포함시킨다.
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
Breadth-First Search (BFS): (105~115)
-인접한 노드를 frontier에 항강 포함시킨다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
-큐(queue)를 사용한다. (선입선출)
- inital state를 포함하는 frontier에서 시작한다.
- 비어있는 explored set를 설정하고 간다.
- 반복한다:
만약 frontier가 비어있으면, solution은 없다.
node를 frontier에서 제거한다. ---->node를 explored set로 옮긴다. (queue사용) (2) (4)
node가 goal state를 포함하고 있으면, solution을 반환다. (4)
node를 확장한다, frontier에 결과가 나온 노드들을 추가한다. (3)
순서: (1)->(2)->(3)->(4) // if goal= solution. else return (2)
informed search: 정보가 있는 상태로 더 효율적으로 solution 찾기 가능한 방법
아래는 informed search의 종류들이다.
greedy best-first search: 가장 goal에 가까운 node를 expand한다. 휴리스틱 함수를 이용해 node를 evaluate 한다. (h(n))
-직선 거리를 재서 가장 가까운 node로 다가간다.
A* search: evaluate function으로 현재 node까지의 cost를 구하는 g(n)과 현재 노드에서 goal 까지의 cost를 구하는 h(n) 두개를 합친 f(n) = g(n) + h(n) 을 사용한다. g(n)은 실제 측정값이니까 주어지고, h(n)은 cost의 최솟값을 추정한 값이다.
f(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다. 일반적으로 가장 작은 f(n)을 찾기 위해 queue가 사용된다.
optimal if
- ℎ(𝑛) is Admissible: goal까지 도달하는데 드는 cost를 예상한 값은 실제 cost를 절대 넘지 않는다.
- ℎ(𝑛) is consistent: 모든 node n과 n의 모든 자손 노드 n'가 있을 때, n에서부터 goal까지의 예상되는 cost (n에서 n'까지 가는 cost + n'에서부터 goal까지의 cost)보다 크지 않은 경우
앞선 node보다 cost가 작아질 수 없음.
- 즉, (나중에 찾은 solution의 true cost) > (처음에 찾은 solution의 true cost) 가 항상 만족한다.
Adversarial Search(137~159)
- competitive multiagent environment, 즉 서로 경쟁적인 두 agent가 있는 상황을 다룬다. 이는 game으로 잘 알려져 있는 adversarial search problem을 말한다.
game은 다음과 같은 요소들로 이루어져 있다.
- S0 : The initial state. 게임이 어떤 상황에서 시작되는지
- Player(s) : 각 state에서 어느 player가 움직일 차례인지 알려줌
- Actions(s) : 각 state에서 취할 수 있는 move들의 집합을 return
- Result(s, a) : 어떤 state s에서 action a를 했을 때 result. transition model.
- TerminalTest(s) : 게임이 끝났거나 한명이 졌을 때 true를 반환. 게임이 끝났는지 안 끝났는지를 판별. (게임이 종료된 그 state를 terminal state라고 부름)
- Utility(s, p) : state s에서 player p에게 얼마나 유리한지를 정의하는 utility function( = objective function or payoff function)
-max(x) 가 최대화된 점수를 목표로 한다.
-min(o)가 최소화된 점수를 목표로 한다.
Minimax
Minimax Value : game tree에서 optimal stategy는 minimax value를 통해 결정된다. 각 node의 minimax value는 각 player가 처음부터 끝까지 optimal하게 게임을 play했다고 가정했을 때의 utility이다. 선택권이 주어졌을 때, 나는 나에게 value가 maximum이 되는 state를 선호할 것이고, 상대방은 나의 value가 minmum되는 state를 선호할 것이다.
MiniMax(s) = Utility(s) if TerminalTest(s)
max MiniMax(Result(s,a)) if Player(s) = MAX( 이건 내 차례일 때 )
min MiniMax(Result(s,a)) if Player(s) = MIN( 상대 차례일 때 )
즉 내 차례일 때는 action을 취했을 때의 utility 값이 maximum하게 선택할 것이고
상대 차례일 때는 action을 위했을 때의 utility 값이 minimum하게 선택할 것이다.
Max-Value는 MinValue중에 최댓값, Min-Value는 MaxValue중에 최솟값이라고 생각하면 된다. 제일 먼저는 MAX turn이니까 Min-value 중 max 값을 return한다. 아래서 부터는 계속 반복이다.
Alpha-Beta Pruning
minimax 와 똑같이 작동하지만, final decision에 어차피 속하지 못할 branch들은 처음부터 가지치기를 해준다.
만약 tree에 node n이 있다고 하자. 만약 player가 n보다 윗 쪽에서 더 좋은 선택지 m을 가지고 있었다면, n은 실제 play에서 선택될 일이 없을 것이다. 이럴 경우 우리는 n이 속한 노드들을 더이상 조사해보지 않고 prune할 수 있다. 어차피 저기서 제일 best한 경우를 선택해봤자 n이기 때문에!
Depth-Limited Minimax
깊이 제한 미니맥스는 종료 상태에 도달하지 않고 정지하기 전에 미리 정의된 횟수의 움직임만을 고려한다. 그러나 가상의 게임이 종료되지 않았기 때문에 이것은 각 액션에 대해 정확한 값을 얻을 수 없다.
이 문제를 해결하기 위해 깊이 제한 미니맥스는 주어진 상태에서 게임의 기대 효용을 추정하거나, 다시 말해 상태에 값을 할당하는 평가 함수에 의존한다. 이러한 값은 올바른 액션을 결정하는 데 사용될 수 있으며, 평가 함수가 좋을수록 이에 의존하는 미니맥스 알고리즘이 더 잘 수행된다.
Evaluation functions
game-playing program의 수행 능력은 evaluation function의 퀄리티에 영향을 받는다.
(1) evaluation function을 사용할 때, 실제 utility function에서의 terminal states의 순서와 달라지면 안된다.
(2) nonterminal state에서, evaluation function은 실제로 이길 확률과 강하게 연관되어 있어야 한다.
(3) 계산이 지나치게 오래 걸리면 안된다.
* Features
: 대부분의 evaluation function은 각 state의 features를 통해 state가 얼마나 좋은지를 계산한다. 이 때 feature는 state의 '상태'라고 보면 된다. Feature를 사용하여 states의 카테고리를 분류하거나 같은 class들을 정의할 수 있다. 같은 feature를 갖는 states끼리 묶은 것이 카테고리이다.
-> state가 어떤 상태(=feature)에 있고 이때 이 상태가 어떤 상태인지 분석해서 얼마나 유리한지 값 반환하는게 evaluation function
'인공지능 > 인공지능개론' 카테고리의 다른 글
| [AI] Optimization (4-3) (1) | 2024.06.11 |
|---|---|
| [AI] Optimization (4-2) (0) | 2024.06.05 |
| [AI] Optimization (4-1) (1) | 2024.06.05 |
| [AI] Uncertainty(3-1) (0) | 2024.04.24 |
| [AI] Knowledge (2) (1) | 2024.04.20 |
