AI Problem-solving agent와 Search 알고리즘

Problem-solving Agents

• Atomic state 표현법 사용

• Solution = Sequence of actions

• 정답을 결정할 때 미래의 percept에 대해서는 고려하지 않습니다.

• 검색 알고리즘이 정답을 찾을 때 사용됩니다.

 

검색 알고리즘 종류

• Informed search : 문제 정의 외의 추가적인 정보를 가진 채 검색하는 알고리즘

• Uninformed search : 문제 정의 외의 정보는 없이 검색하는 알고리즘

 

From romania to home : 루마니아에서 집까지 찾아가는 문제

문제 정의

Goal : world state의 set : Agent의 위치 state를 기록한 정보

가정 : 지도를 갖고 있음 (= informed search)

Action : 도시간의 이동

문제 : Route finding : 경로 탐색

Task environment

• Fully observable : 지도와 거리가 모두 주어짐

• Discrete : 도시간의 이동 단위로 시간이 쪼개어짐

• Known : Agent가 world 에 대해 알고 있음

• Deterministic : state와 action 이 주어졌을 때 다음 state가 100% 확정적임

Solution : 고정된 액션의 연속(Fixed sequence of actions)

Formulate -> search -> execute

 

Simple problem-solving agent program

function SIMPLE-PERBLEM-SOLVING-AGENT(percept) returns an action
  persistent: seq, an action sequence, initially empty
  state, some description of the current world state
  goal, a goal, initially null
  problem, a problem formulation

  state <- UPDATE-STATE(state, percept)
  if seq is empty then // seq = solution list
    goal <- FORMULTAE-GOAL(state)         // goal 의 정의
    problem <- FORMULATE-PROBLEM(state, goal) // problem 의 정의
    seq <- SEARCH(problem) // 답을 찾아라
    if seq = failure then return null // 답을 찾지 못했으면 아무 행동도 하지 마라고 리턴
  action <- FIRST(seq) // 답에 해당하는 action을 취하라
  seq <- REST(seq)
  return action

 

문제정의의 5대 요소

• Initial state

• Actions

• Transition model  :  RESULT(state, action) = state`

• Goal test : Goal 의 집합

• Path cost : Goal 을 위한 비용

• performance measure

• Step cost(state, action, state`) : State가 Action을 취함으로서 발생하는 비용

Vacuum-cleaner 문제 정의

 

Initial state : 위 8개의 상태 중 하나

Actions : Left, Right, Suck

Goal test : 모든 방이 깨끗한지 확인

Path cost : 매 step 마다 코스트를 1로 취급

 

8-puzzle problem

Initial state : 

Actions : Move blank Left, right, up, down

Transition Model

Goal test

Path cost : 매 step 마다 코스트를 1로 취급

 

8 Queen problem

8 * 8 크기의 체스판에 8개의 퀸을 서로 잡을 수 없는 위치에 놓는 문제

State

• Incremental formulation : 빈 판에 Queen 을 하나씩 배치

• Complete-state formation : 퀸을 8개 배치한 후 이동시키기

N-Queen 문제는 cost 에는 관심이 없고 답을 찾기만 하면 된다.

 

Incremental formulation

• Initial state : No queens on the board

• Actions : 빈 공간에 퀸을 놓기

• Transition model

• Goal test : 8개의 퀸이 보드에 있고, 서로 공격할 수 없는 위치에 놓여있음을 확인

 

Leftmost empty column 부터 채워나가는 formulation 이 더 효율적임

Leftmost와 Complete-state formulation 에 대해 생각해보자

 

Infinite state space problem

• State : 양수 전체

• Initial state : 4

• Actions : Factorial, Square root, floor(크지 않은 최대 양수)

• Transition model

• Goal test : 주어진 수를 만들 것. 아래 예제에서의 주어진 수는 5