[Artificial Intelligence] solve problem by searching, problem solving, 8-QUEENS, 8-PUZZLE, search state

 

problem solving

• 문제상황: current state와 goal state 사이에 gap이 있는 상황
• 문제해결: state에서 goal까지의 path = sequence of action을 찾는 것을 문제해결이라고 함
• 문제를 상태와 그들간의 연결선으로 이루어진 그래프 구조로 변환시킬 수 있으면 → 검색알고리즘 을 적용하여 해결할 수 있음
• 현재 state에서 goal state까지 가는 path = sequence of action

• 순서
  1. 문제 representation : problem 정의. 환경에 대한 모델을 정의
     1. search space 정의
     2. operator 정의 (given stae 에서 possible successor state로 가는), cost of transitions
  2. search strategy 적용 (tree 서치) (initial to goal state)
     1. 솔루션 : path from initial to goal state (효율적 방법, 경로 찾기). or a goal state (not initially known 최적화 문제와 연관)
        1. goal based 경우 BFS, DFS
        2. utility based 일 경우 A* 알고리즘 등

 

component of search problem

• 8-QUEEN 예제
  • States: all arrangements of 0 to 8 queens on the board.
  • IInitial (start) and goal (final) states
  • Actions: Add a queen to any empty square
  • Transition model: updated board
  • Goal test: 8 queens on the board with none attacked
• 8-puzzle
  • States: Location of each of the 8 tiles in the 3x3 grid
  • Initial state: Any state
  • Actions: Move Left, Right, Up or Down
  • Transition model: Given a state and an action, returns resulting state
  • Goal test: state matches the goal state?
  • Path cost: total moves, each move costs 1
• EX. 8-QUEENS, 8-PUZZLE

 

search tree

• node : 부모, 자식, 깊이, 경로비용 등을 포함한 데이터 구조, 서치 트리의 부분
  • cf) state : representation of a physical configuration (부모 자식 등의 정보는 없음)
  • search tree의 root= initial state
• edge (branch) : operator (action)
• expand: a function that given a node, ceates all children nodes
• state space: 모든 state의 집합, state과 operator을 정의한다면 state space를 만들 수 있음
• search space divided into three regions
  • Explored (a.k.a. Closed List, Visited Set)
  • Frontier (a.k.a. Open List, the Fringe)
  • Unexplored.
  • ex. 8퍼즐 문제
    • state: 3*3 퍼즐, operator : 빈칸 움직이는 상하좌우
    • 9! , 이를 다 찾아놓고 가는게 아님 → 각 state마다 현재의 state를 인식하고, 그 다음의 action을 판단 → action이 결국 goal state로 가게 해야함

• search state
  • search straegy 종류
    • random search: 답을 찾는 다는 것을 보장할 수 없음
    • uninformed search (여기까진 ai 아님)
      • BFS
      • DFS
      • depth-limited
      • iterative deepening depth first
      • bidirectional
    • informed search (여기서부터 ai)
      • Greedy best-first
      • a* (and many variations)
    • local search (goal을 모름 utility 사용)
      • Hill climbing
      • Simulated Annealing
      • Local beam Search
      • genetic search
    • Adversarial search
    • 강화학습
  • performance measure (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 (무한일 수도 있다.)
  • Reflex agents: use a mapping from states to actions.
  • Goal-based agents: problem solving agents or planning agents.