인공지능30

• 

  Sensorless Problems, The Belief-State Search Problem Searching with Partial Observations - agent 의 percept 는 현재 위치한 state 를 정확히 알지 못한다. 가능한 state 가 둘 이상 존재할 수 있다. - Belief states : 내가 어떤 state 에 있는지 정확히 알 순 없지만 가능한 state 에 있을 것이라고 생각 (후보군) Searching with No Observation - percept 가 없는 경우이다. - sensor 가 없고 그에 순응하는 문제들이다. (sensor 의 비용이 크기 때문에) - 예) 컨테이너 벨트에서 물품의 방향을 고치기 위해 카메라가 존재할 수 있다. 카메라로 방향을 파악하는데, 카메라가 비싸니깐 몇번의 action 으로 고정된 방향을 가리치도록 대체할 수 있다. .. 인공지능 2021. 11. 20.

• 

  Partially Observable and/or Nondeterministic Worlds, AND-OR Search Trees, The Slippery Vaccum World Partially Observable and/or Nondeterministic Worlds - fully observable, deterministic 한 문제들에서 percept 은 새로운 정보를 제공하지 않았다. - partially observable 하다면, 가능한 state 들 중 agent 가 어떤 state 에 있는지 percept 가 좁혀줄 수 있다. - nondeterministic 하다면, 가능한 결과가 실제로 일어난 것을 percept 가 알려준다. -> percept 들이 미리 정해져있지 않다. 따라서 어떤 percept 가 들어오냐에 따라 agent 가 action 을 다르게 해야 한다. solution 은 action sequence 가 아니라 contingency plan 이.. 인공지능 2021. 11. 19.

• 

  Simulated Annealing, Local Beam Search, Stochastic Beam Search, Genetic Algorithms - Hill-climbing search 는 landscape 에 따라 Incomplete 하다. -> greedy - Random walk 는 더 좋은 곳이 아니라 무작위로 이동을 한다. 그러나 landscape 를 거의 무한으로 이동해야 solution 을 찾을 수 있으므로 매우 비효율적이다. - Annealing 은 금속을 뜨겁게 가열한 다음에 천천히 식히는 과정을 말한다. 이는 금속을 부드럽게 하기 위해 사용된다. Simulated Annealing t = 1부터 무한까지 반복문을 도는데, T next가 더 좋은 경우), next 로 이동한다. 그러나 next 가 current 보다 좋지 않은 경우, 확률적으로 next 로 이동한다. 확률은 e^(델타E / T) 가 되는데, 초반에 T가 클 때에는.. 인공지능 2021. 11. 8.

• 

  hill-climbing search, Random-Restart Hill-Climbing Search The 8-queens problem - Complete state formulation (먼저 퀸을 다 배치한 후 이동한다) -> Local Search 에서 사용 - 8(어떤 퀸을 움직일지) x 7(그 퀸이 움직일 수 있는 칸) = 56 successors 가 존재할 수 있다. - Heuristic cost function h : 퀸들 중에서 공격할 수 있는 쌍의 개수 h = 0 일때 goal state 이다. h = 8x7 / 2 는 h의 최댓값이 될 것이다. 칸에 적혀있는 숫자는 퀸을 그 칸으로 이동했을 때 h의 값이 된다. The hill-climbing search algorithm problem 을 input 으로 받고 state(local maximum) 를 return 하는 함수이다. 노.. 인공지능 2021. 11. 8.

• 

  Local Search, Hill-Climbing Search In this Chapter - 이전까지는, fully observable, deterministic, known 한 문제들을 다루었다. - 그리고 solution 은 action 의 연속으로 이루어졌다. 이번 chapter 에서 배울 것은 다음과 같다. - Local Search initial state 부터 경로를 탐색하는 것이 아니라, 현재 states 를 평가하고 수정하는 것이다. 즉, 과정이 존재하는 것이 아니라 현재 state 만 존재한다. path cost 가 아니라, goal state 를 찾는 것이 중요하다. - Nondeterministic and partially observable worlds Nondeterministic 이란 action 을 취했을 때 다음 state 가 하나로 .. 인공지능 2021. 10. 18.

• 

  Admissible Heuristics from Subproblems, Pattern Databases Admissible Heuristics from Subproblems - 8-puzzle 문제의 subproblem 이다. - 1~8까지 모두 고려하는 게 아니라, 1~4까지만 고려하면 되는 문제로 원래 문제의 subproblem 이다. - 기존의 h1, h2 는 계산이 쉬웠다. 그러나 Subproblem 은 그에 비해 바로 찾는 것이 어렵다. - Subproblem 의 optimal solution 비용은 항상 original problem 보다 작으므로, admissible heuristic 하다. Pattern Databases - 모든 가능한 subproblem 의 state 에 대한 cost 를 저장해두는 방식이다. Goal state 에서부터 무작위로 start 하여, 만나는 node들의 co.. 인공지능 2021. 10. 18.

• 

  A* Search for N-puzzle Problem, Relaxed Problem The 8-Puzzle Problem - 8-퍼즐을 푸는데 평균적으로 22 step 이 걸리며, branching factor 은 평균 3이다. tree search 의 경우 3^22 개의 노드를 방문할 것이다 -> 3.1 x 10^10 node 에 달하는 큰 수 graph search 의 경우 1700000개의 노드를 방문할 것이며, 15-puzzle 의 경우 10^13 에 달할 것이다 A* Serach for the n-Puzzle Problem - 두 개의 Admissible heuristics 을 사용할 수 있다. - 즉, 절대 goal 까지 가는데 걸리는 step 을 넘지 않는 heuristic 함수를 필요로 한다. h1 : 잘못 위치된 타일의 수 h2 : 잘못 위치된 타일과 goal 위치와의 .. 인공지능 2021. 10. 18.

• 

  Informed search, Greedy Best-first Search, A* Search Informed Search - 지금까지의 Uninforemd 와는 달리, 문제 정의 이외의 정보를 더 활용하여 효율적으로 검색을 하는 방법이다. - Best-First Search : 트리 내 evaluation function f(n) 에 의해 cost가 가장 적은 노드를 판별하여 먼저 탐색한다. f(n) 은 heuristic function h(n) 을 포함하고 있다. h(n) 이란 n에서부터 goal 까지의 최소 비용을 예측하는 함수이다 예를 들어, Romania 문제에서 원래는 도시간의 비용이 지도에 주어졌지만, h(n)을 사용한다면 도시 n에서부터 goal 까지의 직선거리를 사용할 수 있다. (직선거리 = straight line distance -> SLD) Greedy Best-First .. 인공지능 2021. 10. 17.

• 

  Iterative Deepening Depth-First Search, Bidirectional Search Iterative Deepening Depth-First Search - Depth limit 를 점진적으로 늘려가나는 DLS 방식으로, goal state 를 찾을 때까지 반복해나간다. - Space complexity : Depth-first search 와 같이 O(bd) 이다. - Completeness & Optimal : Yes, Breadth-first search 처럼 branching factor b가 유한하다면 complete 하고, path cost 화 depth 가 비례하다면 optimal 하다. - 예시 - Goal 을 찾을 때까지 depth limit 를 늘려가는 과정이다. Efficiency of IDS - 같은 노드가 여러번 생성되어 성능이 좋지 않을 것으로 보이지만, 대부분.. 인공지능 2021. 10. 17.

• 

  Depth-First Search, Depth-Limited Search Depth-First Search - 항상 가장 깊은 노드부터 expand 하는 기법이다. - Graph search 의 frontier 를 LIFO 로 구현한 방식이다. Performance of Depth-First Search - Completeness : Graph search version : Yes, 단 state space 가 유한한 크기일 때 Tree search version : No, 방문했던 노드를 재방문 가능하므로 cycle 이 생길 수 있다. -> graph 버전은 explored set 으로 노드의 중복을 막고, tree 버전은 루프가 생길 수 있다. - Optimality : No, 항상 최적은 아니다. 최적의 답보다 더 깊이 있는 노드를 먼저 찾을 수 있기 때문 - Time .. 인공지능 2021. 10. 17.

• 

  Uniformed Search, BFS, UCS Uninformed Search -문제의 정의 외에는 다른 정보가 주어지지 않는 검색 알고리즘이다. - blind search 라고 불리기도 한다. - 이 알고리즘은 현재 상태에서 목표 상태까지의 path cost 를 모른다. - 따라서 오직 다음 후임자(successor) 를 expand 하고, 목표 상태인지 목표 상태가 아닌지를 구분만이 가능하다. - 후임자(successor) 들을 expand한 순서는 매우 중요한 key 가 될 것이다. - Uninformed Search 종류 Breadth-First Search (너비 우선 탐색) Uniform-Cost Search (일정량 탐색) Depth-First Search (깊이 우선 탐색) Depth-Limited Search (깊이 제한 탐색) It.. 인공지능 2021. 10. 17.

• 

  Search Tree, Tree search, Graph search A Search Tree - 문제를 형식화 한 뒤, 문제를 풀어야 한다. - 이때, solution 은 하나의 action sequence인데, 이 동작열을 찾기 위해 검색 알고리즘을 사용한다. - 검색 알고리즘은 가능한 여러 sequence 들을 살펴본다. - Initial state -> root - actions -> branches - states -> nodes Tree Search - initial state을 현재 state 로 설정한다. - Iterate 현재 state 가 Goal 인가? 그렇다면, 지금까지 찾은 solution (action sequence) 를 리턴 아니라면 가능한 action 들을 고려한 뒤 EXPAND 액션 선택 선택한 action 으로 파생된 state 를 현재 .. 인공지능 2021. 10. 17.