[인공지능] 3. Solving problems by searching - 1

1. Problem-Solving Agents

  1) Problem Formulation

  - Problem은 initial state, actions, transition model, goal test, path cost로 정의된다.

  - Problem formulation은 goal이 주어진 상황에서, 무슨 action 과 states를 고려할 것인지 결정하는 과정을 말한다.

  - Problem의 solution은 initial state가 goal state로 가게 만드는 action들의 sequence이다.

  - goal에 다다르기 위한 sequence of actions을 찾아나가는 과정이 search이다.

  - solution이 찾아지면 action이 수행되도록 추천된다. 이것이 바로 execution이다. 

 

   * State Space  : initial state에서부터 어떤 action squence를 통해 도달할 수 있는 모든 states들의 집합

   * path : sequence of actions에 의해 연결된 states들의 sequence

  2). Abstraction (추상화)

     : representation에서 detail을 제거해나가는 과정이 abstraction이다. Abstraction은 우리가 어떤 abstract solution을 더 detailed 한 환경에서 solution으로 확장시킬 수 있다면 valid하다. Abstraction은 원래의 문제보다 solution에 있는 각각의 actions들을 수행하는 것이 더 쉬울 경우에 유용하다. 따라서 더 좋은 abstraction을 하기 위해서는, validity를 유지하고 abstract action이 수행하기 쉽도록 유지하면서도 가능한 많은 detail을 제거해야 한다. 

 

 

2. Example Problems

3. Searching for Solutions

  1) Search Tree  

    - Solution은 action sequence의 형태로 나타남. 그래서 search 알고리즘은 여러가지 가능한 action sequences들을 고려하여 작동한다. 

    - 모든 가능한 action sequence는 initial state에 시작하는데, search tree에서는 그게 바로 root!! 

    - branches는 각각 action이고 nodes는 state space에 속하는 state에 해당한다. 

 

  2) Search Strategy and Performance Evaluation

     i. Search Strategy

       - First-in first-out (FIFO)

       - Last-in first-out (LIFO)

       - Highest priority first

 

     ii. Performance evaluation

       - Completeness

       - Optimality

       - Time complexity

       - Space complexity