[인공지능 : AI, Artificial Intelligence] Lecture 3 : Inteligent Agent 2부

Lecture 3

Intelligent Agent 복습

• 목적 purspose가 있고, 분명하다.
• 그 목적을 달성하기 위해 효율적인 방법 acting(판단, 의사결정)을 한다.
• rational intelligent agent
  • 목적을 달성하기 위해 utility를 maximize하는 방향으로 acting을 하는 것
  • 효율적으로

3.1 Problem Solving Agent(by Search)

Problem Solving이란

• 현재 state에서 goal state까지 가는 path = sequence of action이라고 할 수 있다.
• problem solving 문제는 그러면 utiliy based agent 가 아니라 goal based agent 에만 해당된다고 봐야되나요?

문제란 무엇인가???

• AI의 세가지 방법론 : 학습 추론 문제해결 중 문제해결의 한 요소
• what should be와 what 이 다르다면 그것이 문제
  • current state와 goal state 사이에 gap이 있는 상황
• state에서 goal까지의 path = sequence of action을 찾는 것을 문제해결이라고 한다.
  • 이는 모델 내에 설정해둔 function에 의하여 정해진다.

이건 3,4,5장에서 배운다

• agent는 전체 트리를 아는 것이 아니라, 각 state에서 무엇을 할 지 아는 것이다.
• 예시)
• 문제 해결(problem solving)은 현재 상태에서 목표상태까지 효율적으로 찾아가는 순차적인 과정/순서

How to solve a problem by searching

즉, search problem은 다음과 같이 공식화 할 수 있다.

문제라는 것은 어떤 종류가 해당하는 것인가? 즉, 정의가 어떻게 되는 것인가?

• Tree or Graph 구조로 변형하는 것이 대부분이다. 즉, Tree 구조에 Search 알고리즘을 적용하는 것인데,
  • 이것이 Goal 기반일 수도 (BFS, DFS)
  • Utility 기반일 수도 있다. (Goal의 위치를 추정하는 A* 알고리즘 등)

Goal based Agent

• 모든 goal 기반 알고리즘은 모두 model 기반 알고리즘이다.
  • 여기서 model은 tree이다.
  • 이 tree의 전부를 알지는 않지만, 그 구조를 알고 있고, 그동안 action에 의한 agent가 거쳐온 path도 알기 때문에 알고리즘이 각 모델에 잘 호환이 된다.
  • 어떤 식으로 확장해나갈 것인가?를 알면 tree에 대한 완전한 이해도를 만들지 않아도 만든 것과 같다.

예시) 8 puzzle

8 puzzle 문제를 살펴보자

• 1 ~ 8까지의 수를 움직여서 순서대로 되도록 만드는 게임이다.
• 왼쪽은 state, 오른쪽은 Goal
• 이문제 자체가 problem

• 빈칸에 들어갈수 있는 숫자를 Tree 구조로 바꾸면

• Tree 구조로 바꾸면 Search 알고리즘을 사용해서 Goal까지 갈 수 있다. 이 때, 각 Tree의 구조물은 다음과 같은 의미를 지닌다.
  • node : status을 의미
  • edge : action을 의미
• 여기서 모든 state의 집합을 state space라고 한다.
• path = initial state에서 goal state까지 operator를 따라 가는 경로
• 그렇게 해서 효율적인 path을 찾는 것을 solving이라고 한다.

예시) 8퍼즐에서 그런데 sequence of action에서 state가 몇개나 될까???

• 9!이다.
• 이를 다 찾아놓고 가는게 아니다
• 각 state마다 현재의 state를 인식하고, 그 다음의 action을 판단한다. action이 결국 goal state로 가게 해야한다.

operator를 blank 칸을 옮기는 것으로 정의하는 것이 간단하다.

사진 아래부분이 Search Tree

problemn solving as search는 다음 두 단계로 이루어진다.

1. probelm representation : problem 정의. 환경에 대한 모델을 정의
2. Search : search 알고리즘 적용. agent function을 결정하는 일

• 여기서 action을 결정하는 f의 issue
  • 최단 거리인가?
  • 시간 복잡도
  • 함수 f를 반복했을 때 goal까지 간다는 것을 보장해야한다.

---

agent 관점의 performance는 다음과 같다.

• 답을 찾아야되고
• 빨리 찾아야
• 답이 여러개면 가장 좋은 것을찾아야한다
• utility를 maximize하는가?

---

예시) 10자리 수의 영문 숫자 조합 중, 특정한 한 문자를 찾는다고 하자.

• 알파벳과 숫자가 각각 24, 10개 있다.
• 즉, 34^10 중 하나의 경우를 파악한다고 하자
• 그럼 각각의 조합을 traverse해가면서 goal state와 같은 것인지 탐색할 것이다.

aaaaa.....

aaaaaaa....b
aaaaaaa....c
.
.
.
aaaabcd....f

---

문제를 표현하는 방법

search를 염두에 두고 search-space로 표현하거나,
재귀적 축소 방식으로 sequence of action을 찾아내거나

state-space representation

• state-space
• initial state
• goal state(test)
• action(operation) : 다음 어떤 state로 옮겨갈지 정하는 함수를 의미
• transition model
• 상태공간에서 초기 상태에서 목표상태에 도달할 수 있는 일련의 연산자를 찾으면 그것이 문제의 해이다

다른 저자의 정의

예시) 배 문제

Search를 위한 model을 정의한다.

총 state는 2^5 가지가 있다. 물론 가능하지 않은 state도 있다. 예를들면 Boat만 2번 오른쪽에 있는 경우...

다음은 정의 가능한 operator를 정의한다.

이제 agent는 operator를 통해서 어떤 state로 갈지 선택하는 것

---

State Space : Grpahs vs Search Tree

• Graph로 표현하더라도 Tree 구조로 변환할 수 있다.
• search tree는 각 node가 전체 path를 지정하는 것이 된다.
• 어떤 쪽이든 자유롭게 사용한다. 그리고 어떤 쪽이든 그 크기가 작아지도록 설계한다.

에시) Tic Tac Toe

예시) Drug design

Path가 아니라 Goal을 찾는 경우

여기서는 아미노산의 seq를 찾아야하는데, 총 가지수는 20^8개 이다...

이번에는 path를 찾는 것이 아니라, utilituy가 주어지고 특정값을 넘도록해서 유사 goal을 찾는 것이다.

• 이런 경우, state, initial, goal, operator, cost of transition, serch tree는 어떻게 설정하나???
• 그리고 path를 찾는 것인가? solution인가?
• 5장 Local Search에서 다룰 것이다.

Search Methods

• representation된 problems를 search 방법으로 해결할 것이다.
  • Problem 은 states 와 operators 로 표현이 된다. (이 상태에서는 “구조화”된 statespace 만들어졌다) => 그런 후, search algorithm 을 사용하여 그 problem 을
    solve 한다.

Goal based Agent의 Search 방법은 크게 5가지로 구분된다.

• random search
• blind search : uninformed search. Brute-Force라고도 하고, 그냥 다 뒤져보는 것을 의미한다.
• heuristic search : 인간의 지식을 이용해서 조금 더 효율적으로 접근한다. utility 값을 사용
• henetic search : informed search. Local Search. Goal 찾을 때
• reinforcement learning : Policy를 찾는 것. 곧 path를 찾게 되는 효과가 있다

앞으로는 informed, uninformed search에 대해서 알아볼 것이고, 다음시간에 알아볼 것이다.

Assignment

1. 다음 문제에 대하여 문제 저의 혹은 문제 표현을 해보자.
2. 각각에 대하여 state, state space의 크기(즉, 모든 가능한 state의 수), actions(혹은 operators)를 정의하여 보시오.

• 그림 3.4의 8-puzzle

state : 각 숫자 칸과 blank 칸이 배치되어있는 상황을 state로 정의한다.
state space의 크기 : 9! = 362,880
actions : blank칸이 상하좌우로 이동하는 것을 action이라고 정의한다.
이를 일종의 집합으로 표현하자. 첫 원소는 blank 칸의 위치이고, 그 이후의 원소는 blank칸의 이동 방향이다.

{1 : right, down}
{2 : left, right, down}
{3 : left, down}
{4 : right, up, down}
{5 : left, right, up, down}
{6 : left, up, down}
{7 : right, up}
{8 : left, right, up}
{9 : left, up}

• 그림 3.5의 8-queen

8개의 queen이 서로 공격하지 못하도록 배치해야한다.

state : 위쪽의 row부터 차례로 queen을 배치한 보드판 상황을 state로 본다. 이때, 어차피 같은 row에는 두 개의 queen이 올라올 수 없으므로, 각각의 row를 개별로 본다.
state space의 크기 : 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40,320로 볼 수 있으나, 허용되지 않는 배치도 존재할 수 있으므로 이것보다 적을 것이다.
actions : 위쪽의 row부터 순서대로, 각각의 row에 대해서 서로 공격하지 못하는 위치에 queen을 놓는 것을 action이라고 본다.

• 3x3 보드에서의 틱택토 게임

가장 먼저 3개로 한줄을 완성하는 플레이어가 승리하는 게임이다.

state : 각 플레이어가 순서대로 O X를 두는 보드 상황을 state로 정의한다.
state space의 크기 : O와 X가 번갈아가면서 둔다고 하면 다음과 같다. 단, 이 경우는 시작하는 기호가 O인 경우로 고정한다.
9 + 98 + 987 + 9876 + 98765 + 987654 + 9876543 + 98765432 + 987654321 = 986409
actions : 하나의 위치를 정해서 차례에 맞게 빈칸에 O 혹은 X를 넣는 것을 action으로 정의한다.

• 5x5 보드에서의 오목 게임 (대략의 범위를 구해도 상관 없음)

가장 먼저 5개로 한 줄을 완성하는 플레이어가 승리하는 게임이다. 즉, 틱택토의 확장버전

state : 각 플레이어가 서로 하나씩 black과 white를 둔 보드의 상황을 state로 정의한다.
state space의 크기 : 아래의 python code를 통해서 대략적인 경우의 수를 구하였다.

sum = 0
temp = 1

for i in range(25, 0, -1):
    for j in range(25, i-1, -1):
        temp *= j
    sum += temp
    temp = 1

print(sum)

그 결과 42,163,840,398,198,058,854,693,625를 얻을 수 있었다.
actions : 하나의 위치를 정해서 차례에 맞게 빈칸에 black 혹은 white를 넣는 것을 action으로 정의한다.

노트의 나머지 내용

Tree Search Algorithm

Blind Search

BFS는 왼쪽부터 오른쪽으로 탐색을 실시한다.
즉, 탐색 순서가 b-c-d-e-f-g-h-...

DFS는 맨 마지막 child node까지 탐색한다.
a-b-g-l-m-h

Heuristic Search

BFS와 DFS의 틀을 기반으로, 다음 search할 node를 arbitary node가 아닌 heuristic value를 기준으로 고른다.

Search strategies

order of expansion으로 그 strategy가 결정된다.

strategy는 다음과 같은 평가기준이 있다.

• completeness : 항상 solution을 찾는가
• time complexity : number of nodes expanded
• space complexity : maximum number of nodes in memory
• optimality : least cost solution인가?

Time & Space Complexity는 다음과 같이 측정된다.

• b : maximum branching factor of the search tree
• d : depth of the least-cost solution
• m : maximum depth of the state space (무한일 수도 있다.)

Uninformed search strategy 종류

Uninformed strategy는 해당 문제의 정의에서 나오는 information까지만 사용한다.

• Breath-first Search
• Depth-first Search
• Uniform-Cost Search
• Depth-first Search
• Depth-limited Search
• Iterative deepening Search

각 strategy의 비교

아래는 참고용

• Depth-limited
  • depth first search 중 탐색할 수 있는 depth의 크기에 limit이 있는 search이다.
  • optimal하지 않다.
  • time/space complexity는 각각 O(b^d) and O(bd)
• Iterative deepening
  • BFS와 DFS의 혼종.
  • best depth limit은 모든 depth limit을 다 시도해보아야 찾을 수 잇다.
  • space complexity는 O(bd)
  • Optimal하다.
• Bi-directional search
  • initial state와 goal state에서 동시에 초기화. 둘이 언젠간 만난다고 생각
  • complete
  • optimal
  • time and space efficiencies are exponential, O(b^(d/2)).

아래는 Depth-Limited Tree Search

다음은 Iterative deepening search

Goal Based Agents

• Reflex agents : use a mapping from states to actions.
• Goal-based agents : problem solving agents or planning agents.

• Agent는 Goal을 향해 work
• future state에 대한 action의 영향을 고려
• solution을 향한 search로 formalize한다.

Problem Solving as Search

1. Define the problem
   • Goal
   • Problem
2. Solving the problem as 2 stage process
   • Search : exploration of several possibilities
   • Execute the solution found

• Initial state : the state in which the agent starts
• States : All states reachable from the initial state by any sequence of actions (State space)
• Actions : possible action availabel to agent. Action(s) returns the set of actions that can be executed in state s (=Action space)
• Transition model : Description of what each action deos Results(s, a)
• Goal Test : determines if a given state is a goal state
• Path Test : Function that assigns a numeric cost to a path with respect to performance measure

Components of a Search Problem

• State space 𝑆: in this case, an edge-weighted graph
• Initial (start) and goal (final) states: 𝑥𝐼 and 𝑥𝐺
  • There can be more than one start/goal state: solve one side of a Rubik’s cube
• Action: in this case, moving from one state to a nearby state
• Transition model: tuples (𝑠1, 𝑎, 𝑠2) that are valid
  • Sometimes written as 𝑇(𝑠1, 𝑎) = 𝑠2
  • There are usually costs/rewards associated with a transition, 𝑅(𝑠1, 𝑎)
• Solution: valid transitions connecting 𝑥_𝐼 and 𝑥𝐺
  • Optimal solution: solution with lowest
  • cost (e.g., length of the path)

다음은 문제를 Tree가 아니라 Graph로 보았을 때의 model 정의

• State space : a physical configuration(구성)
• Search space : an abstract configuration represented by a search tree or graph of possible solutions.
• Search tree: models the sequence of actions
  • Root: initial state
  • Branches: actions
  • Nodes: results from actions. A node has: parent, children, depth, path cost, associated state in the state space.
• Expand: A function that given a node, creates all children nodes

The search space is divided into three regions:

1. Explored (a.k.a. Closed List, Visited Set)
2. Frontier (a.k.a. Open List, the Fringe)
3. Unexplored.

Search는 node를 3에서 2로, 1로 옮기는 것이다.
그리고 Strategy는 어떤 순서로 그 node를 옮기고, 또한 Expansion을 할지 결정한다.

즉, Search는 다음 구성 요소로 이루어져 있다.

• Open List
• Expansion
• Exploration Strategy

각각의 Search 방법에서 Open List에 대해서 다음과 같이 행동한다.

Breadth-first search (BFS)

• Always add new nodes at the end of the queue

Depth-first search (DFS)

• Always add new nodes in the front of the queue

Uniform-cost (Dijkstra’s)

• Always keep the node with the best cost in the front of the queue

A*

• Similar to uniform-cost, but also uses a guess of distance to goal