3. Solving Problems by Searching
Problem-solving agent : 인공지능을 이용하여서 문제를 푼다.
입력부터 출력까지 이어지는 그리고 중간에 있는 알고리즘을 이용하여서 문제를 푼다.
AI를 이용한 문제 해결도 사실상 알고리즘을 이용한 문제 해결방법 그래도 여기에서 말하는 Solving Problems라는 말은 AI와 관련된 환경
Problem Solving Agent라는 것은 문제를 푸는 여러가지 방법을 찾아낸다는 것을 의미한다.
예를 들어 경로를 탐색한다고 하더라도 A에서 B지점으로 가는 방법을 일일히 적어놓는 것이 아닌 AI가 해당 경로를 찾아내는 것을 생각해 볼 수도 있다.
AI적 문제해결에 있어서는 문제를 어떻게 접근할 지에 대한 생각이 필요하다.
3.1 Problem-Solving Agents
Goal : 우리가 찾고자 하는 결론
Goal Formulation : 결론을 찾아내는 과정을 알고리즘화 하는 과정
Problem Formulationm : 결론에 도달하
3.1.1 Well-defined problems and solutions
예를 들어 그림 3.2에서는 로마의 도시별로 연결시키어 두었다.
한 문제는 5가지의 구성요소로 정의 될 수 있다.
-
Initial State : AI 문제 해결을 위한 초기화 과정
-
Actions : agent가 할 수 있는 action들
-
Transition Model : agent가 수행하는 action들에 대한 설명들로
1) Result(s,a) : s의 상황에서 a의 행동
2) successor : 주어진 상황에서 핻ㅇ동을 통해 도달할 수 있는 상태
Result(In(Arad),Go(Zerind)) = In(Zerind)
현재는 Single Agent만이 Transition이 될 수 있음 => 추후에 동시에 여러개의 Agent를 이용할 수도 있음 이를 제네틱(Genetic) 알고리즘(=유전 알고리즘)이라고 함
이때의 successor은 Zerind, Timisoara, Sibiu 등등으로 나뉘어 질 수 있음
-
Goal Test
A에서 B로 이동하면서 자신이 원하는 결과가 나왔는지를 매번 확인해주는 Goal Test가 필요하다. -
Path Cost
이동하면서 발생하는 비용에 대한 문제, 성능 측정 문제
Step Cost : c(s,a,s')를 가장 작은 경로의 비용 (a는 행동 s는 시작지 s'은 도착지)
Path Cost = Sigma(Step Cost[i]) from 0 to N
매 문제마다 이 5가지 방법을 통해 정의를 하고 사용
Optimal Solution : 최적의 해결책은 목표를 이루되 가장 적은 비용이 드는 방법을 말함
3.1.2 Formulating Problems
3.2 Example Problems
이미지와 같이 진공청소기가 쓰래기를 처리하는 방법에 대해서 다루고 있다.
3.2.1 Toy Problems(시험)
여기에 적힌 것과 같이 6가지를 정확하게 묘사하는 문제가 나올 수 있기 떄문에 여기에 나오는 예시를 가지고 6가지의 Problem-Solving Algorithms을 떠올려보자
- Stats : agent location and dirt locations
- Initial State : 초기화 단계
- Actions : 기계가 행동할 수 있는 행동들
- Transition model : 행동의 끝에는 원하는 결과물이 존재한다.
- Goal test : 행동의 결과 우리가 원하는 결과를 얻었는지를 확인한다.
- Path cost : 행동을 함에 있어서 소모되는 자원
3.2.2 Real-World Problems
시험에 나오지 않는 부분
3.3 Searching for Solutions
solution을 위한 탐색
초기 상태 공간 = search tree 에서부터 branches(action)가 생기어 나가 다양한 해결 방법을 찾아낼 수 있음.
대표적인 기초가 되는 알고리즘이 BFS, DFS임
주어진 state 노드에서 뻗어나갈 수 있는 대상들을 다 frontier에 집어넣고 모든 frontier을 모아서 open list에 집어 넣음. 하지만 open list에 있는 모든 해결책이 좋은 결과를 가져오는 것이 아니기 때문에 이중에서도 가장 좋은 해결책을 골라내야 함, 그것을 어떻게 선택하느냐에 따라서 search algorithm과 search strategy가 달라지게 됨.
그래서 problem solving 하는데 있어서 가장 중요한 것이 바로 open list와 explored set(closed list) 개념이 비 AI 알고리즘하고 대비되는 파트이기 때문에 뒤에서는 어떻게 이를 적용하는지가 나올 예정
