2022. 4. 1. 16:09ㆍMajor`/인공지능
Problem-Solving Agents
1. 어떤 Agent든 "Sensor"를 통해서 인식하는 정보들이 존재할 것이다 :: Percept
2. Percept 정보와 State(직전 상태) 정보를 결합(Update-State)함으로써 새로운 State를 정의한다
※ Sequence(Sequence Of Action)가 없다면?
Sequence가 없다는 의미는 현재 "계획"이 없다는 의미이다
>> 따라서 계획을 먼저 수립해야 한다
1) 현재 State로부터 먼저 Goal을 정한다
- Goal은 1) Agent가 스스로 정할 수 있고, 2) 외부에서 Agent에게 정해줄 수 있다
2) 현재 State & Goal을 통해서 Problem을 formulate한다 (탐색 대상이 될 수 있는 Problem으로 만들기)
- State와 Goal이 다르다면 Problem을 해결하기 위해서 노력할 것이다
- State와 Goal이 동일하다면 Problem은 정의되었지만 해결할 필요는 없다 (이미 Goal에 도달했기 때문에)
3) Problem에 대한 Solution이 도출될 때까지 "탐색"을 수행한다
- "탐색"을 진행하면 결국 Sequence Of Action(계획)이 도출된다
3. Sequence 중에서 "첫번째 Sequence"를 return하고 그것이 바로 "지금 당장 Agent가 수행해야 할 Action"이다
- 아직 수행하지 않은 Sequence를 차례대로 수행해야 Goal에 도달한다
- 차례대로 return되는 Sequence가 Agent가 수행해야 할 Action들이 된다
4. 3)에서 return되지 않은 나머지 Sequence들을 전체적 Sequence로 Update한다
탐색에서 필수적인 요소
1. Initial state
문제를 해결함에 있어서 초기 상태
2. Possible actions
현재 상태로부터 가능한 행동들
- 어떤 상태에서 다른 상태로 이동하기 위한 행동
>> 결국 1, 2는 문제에 따라 어느정도 차이가 존재하기 때문에 "추상화"를 해서 State & Action이라고 정의한다
3. Goal Test
현재 상태가 목표에 도달했는지 판단하는 테스트
4. Path Cost
어떤 상태에서 다른 상태로 가는 경로의 비용
"Solution : a sequence of actions leading from the initial state to a goal state"
상태 공간 탐색 문제 : State Space Search Problem
Example 1) Romania Traveling
## Formulate The Problem ##
initial state : "Arad"
Goal : "Bucharest"
State : 현재 여행객이 어느 도시에 존재하는가 (여러개의 도시들 중에서 하나)
Percept : "Arad"에서 여행객이 인식할 수 있는 환경 → "Zerind" / "Timisoara" / "Sibiu"
Action : Percept & States를 통해서 생성된 Sequence에서 최종적으로 선택된 행동
>> Solution : "Arad" → "Bucharest"까지 가기 위한 "sequence of actions"
그러면 Agent는 "Search"을 통해서 (state, Action)이 계속 변경될 것이다
Agent는 합리적인 판단에 의해서 목적지로 가는 탐색을 Solution이 도출될 때까지 수행해야 한다
▶ 상태 전이도
Agent가 어떠한 Action을 취했을 경우 그에 따라 가능한 상태의 경우의 수
결국 계속해서 탐색이 진행되가면서 Tree의 형태를 띄고 있는것을 볼 수 있다
물론 Graph의 형태로 표기할 수도 있다
- Tree는 Cycle이 존재하지 않고, Graph는 Cycle이 존재할 수 있다
Example 2) 8-Puzzle
## Formulate The Problem ##
State : 1 ~ 8 타일들이 현재 어디에 있는가 (Location of Tiles)
Action : (빈칸 기준) Left / Right / Up / Down
- 빈칸의 위치에 따라 Action의 개수가 달라질 수 있다 (2 ~ 4)
Goal test : Goal state (given)
Path cost : 1 per move
다만 8-puzzle은 현재 state에 대한 상태 전이도의 경우의 수가 굉장히 많기 때문에 Action이 가능한 상태만 펼쳐서 탐색하는 것이 좋다
Tree Search
현재 state로부터 가능한 Action들을 펼침(Expanding)으로써 탐색하는 방법
- 펼치다는 뜻은 한 노드로부터 다른 노드들을 expanding한다는 의미이다 :: Expanding States
당연히 Goal이 도출될 때까지 탐색은 진행되고 모든 State에서 Goal test를 진행한다
Node vs State
Node는 자료구조이다.
Search Tree를 구성하고, Node내부에는 State/Parent Node/Action/Path Cost/Depth 등의 정보가 기입되어 있다
State는 Node 하나하나에 저장되어 있는 "현재 상태를 나타내는 정보"이다
탐색 전략
탐색 전략이란, 확장 순서를 어떻게 결정할지에 대한 것이다
탐색 방향
→ 전향 탐색 (Forward Search) : start ~> goal
→ 후향 탐색 (Backward Search) : goal ~> start
→ 양방향 탐색 (Bidirectional Search) : start ~> goal / goal ~> start
탐색 전략 평가
1. 완전성 (Completeness)
"does it always find a solution if one exists?"
해당 전략을 따라서 진행하면 "반드시 Solution이 찾아지는가?"
2. 시간복잡도 (Time Complexity) & 공간 복잡도 (Space Complexity)
빅-오로 표기해준다 (upper bound)
- b : 트리의 가짓수 (얼마나 expand 되었는가)
- d : 최소 비용의 depth
- m : 제일 깊은 깊이 (maybe ∞)
3. 최적성 (Optimality)
"does it always find a least-cost solution?"
해당 문제에 대한 탐색의 Goal이 반드시 존재하고, 한번에 Goal을 탐색했을 경우
>> 최소 비용 Solution
탐색 방법
Uninformed Search
탐색에 필수적인 4가지 요소 (state/action/goal test/path cost)외의 부가적 정보가 없는 탐색 방법
- Breadth-First Search : BFS
- Uniform/Least/Lowest Cost Search
- Depth-First Search : DFS
- Depth-Limited Search
- Iterative Deepening Search
Informed Search = Heuristic Search
탐색에 필수적인 4가지 요소 (state/action/goal test/path cost)외의 부가적 지식(Heuristic)이 존재하고 부가적 지식(Heuristic)을 활용해서 최적의 Solution을 도출하는 탐색 방법
- Best-First Search
- A* Search
- Iterative Deepening A* (IDA*) Search
Uniformed Search
BFS
기본적인 너비 우선 탐색
보통 Queue로 구현한다
| <BFS> | 만족? 불만족? | 이유 |
| 완전성 | O | BFS는 depth별로 전부 탐색을 하기 때문에 완전성은 보장이 된다 만약 탐색이 불가능하다는 의미는 어차피 풀 수 없는 문제이다 |
| 최적성 | O | 동일한 Path Cost를 가진 Level 별 Node끼리 하나의 그룹으로써 그룹별 탐색을 수행하기 때문에 최적성은 보장된다 |
| 시간 복잡도 | O(bd+1) | |
| 공간 복잡도 | O(bd+1) | |
"BFS is complete but expensive"
Uniform/Least/Lowest Cost Search
확장되지 않은 여러 노드 중에서 "최소 비용 노드"부터 확장을 하는 탐색 방법
- 물론 여기서 current state로부터 expanding이 가능한 node들을 대상으로 한다
주로 Priority Queue로 구현한다
>> 확장 순서는 최소 비용을 고려해서 "A - B - C - E - G - D - F"순으로 확장된다
| <UCS> | 만족? 불만족? | 이유 |
| 완전성 | O | Goal에는 당연히 도달할 수 있다 |
| 최적성 | O | "최소 비용"을 기준으로 expanding하기 때문에 최적성 또한 보장된다 |
| 시간 복잡도 | O(bcelling(c*/e)) | |
| 공간 복잡도 | O(bcelling(c*/e)) | |
DFS
기본적인 깊이 우선 탐색
보통 Recursion이나 Stack으로 구현한다
| <DFS> | 만족? 불만족? | 이유 |
| 완전성 | X | 만약 어떤 depth를 선택했는데 무한히 길다고 가정하면 절대로 goal에 도달할 수 없기 때문에 완전성은 보장되지 않는다 |
| 최적성 | X | Solution이 존재한다해도 여러 곳을 경유해서 갈 수 있으므로 최적성은 보장이 되지 않는다 |
| 시간 복잡도 | O(bm) | |
| 공간 복잡도 | O(bm) | |
"DFS is cheap but incomplete"
Iterative Deepening Search
깊이 별로 제한을 두어서 DFS를 하는 방식이다 :: Depth Limit Search
정해진 깊이 내에서는 계속해서 DFS를 한다
| <IDS> | 만족? 불만족? | 이유 |
| 완전성 | O | Goal에는 당연히 도달할 수 있다 |
| 최적성 | O | 깊이별로 계속 DFS를 돌리는 방식은 결국 최적성을 보장할 수 밖에 없다 |
| 시간 복잡도 | O(bd) | |
| 공간 복잡도 | O(bd) | |
Repeated States
하나의 Node로부터 다른 Action(다른 Branch)을 취했는데 각각의 다른 Action에 대해서 동일한 Node가 Expanding 되는 현상
결국 이렇게 Expanding되면 Search를 할 때 다른 Path여도 동일한 state가 계속 반복되는 것으로 볼 수 있다
closed : Expanding이 완료된 Node들의 집합
fringe : 아직 Expanding 되지 않은 Node들중에서 현재 Expanding 가능한 Node들의 집합
node : fringe로부터 선택된 Expanding 대상 Node
1) if 만약 node가 Goal-Test를 통과했다면
해당 node를 Solution으로써 return
>> 결국 Solution Sequence가 있는데 해당 Sequence의 마지막에 node를 insert
2) else if 만약 node가 closed Set가 없다면
해당 node를 closed Set에 추가시켜주고 해당 node로부터 새로운 fringe Set을 생성해준다
3) else : 만약 node가 closed Set에 존재한다면
해당 node는 closed Set에 이미 있고 여기까지 도달했다는 것은 해당 Node로부터 새로운 chile node 후보들을 정의하지 않겠다는 것이다
