[인공지능] Search

saerch를 하는 agent는 goal-based agent

주변 환경은 observable, static, discrete, deterministic하다고 가정하자.

problem solving agent

algorithm

goal-based agent의 한 종류인 problem-solving agent는 다음과 같이 정의된다.

function SIMPLE-PROBLEM-SOLVING-AGENT(percept)
    state = UPDATE_STATE(state, percept)
	if seq is empty
        goal = FORMULATE_GOAL(state)
        problem = FORMULATE_PROBLEM(state, goal)
        seq = SEARCH(problem)
    action = FIRST(seq)
    seq = REST(seq)
return action

problem solving agent는 먼저 현재 state와 percept한 걸 바탕으로 state를 갱신한다. 아직 search를 안해서 seq가 비어있으면, goal과 problem을 정의를 하고 search를 한다.

seq의 첫번째 element를 action으로 하고, sequence에는 나머지만 남긴다.

action을 리턴한다.

general step

1. goal formulation - goal을 정의한다.
2. problem formulation - 문제의 상황들을 정의한다.
3. search - goal에 도달하는 action들을 찾는다.
4. execute - action을 취한다.

problem formualation

problem solving agent의 일반적인 단계에 problem-formulation이 있었다. 문제에 관한 것들을 정의하는 과정이다. 구체적으로 정의하는 것은 다음과 같다.

• initial state
• actions
• transition model
• goal-test
• path cost

이때 initial state, actions, transition model들을 전부 묶어서 state space를 만든다.

state space 탐색

state와, action을 취하면 이동하는 state가 결국엔 state space를 구성한다. 이 state space를 잘 탐색하여 goal에 도달하는 것이 search의 목표이다.

tree search

먼저 state space를 tree처럼 생각해서 탐색하는 방법이 있다. tree이기에 중복되는 state를 허용한다.

function treeSearch(problem){
	fringe.insert(initialstate);
  
  	while(!fringe.empty){
    	node = fringe.pop();
      	if(goal(node)) return solution;
      
      	for(child in node.successors){
        	fringe.insert(child);
        }
    }
}

fringe에 initial state를 넣어준다.
그리고 계속 fringe에서 pop을 하고 goal test를 하고 successor state를 또 fringe에 넣어주면서 탐색을 한다.

graph search

graph search는 중복된 state를 허용하지 않는다. 따라서 이전에 방문한 노드들에 대한 visited역할을 하는 자료구조가 필요한데, 여기서는 closed list를 사용한다.

function graphSearch(problem){
	fringe.insert(initialState)
  	closed = {};
  
  	while(!fringe.empty()){
    	node = fringe.pop();
      	if(goal(node)) return solutionl
      	closed.insert(node);
      
      	for(child in node.successors){
        	if(child not in cloesd or fringe){
            	fringe.insert(child);
            }
        }
    }
}

uninformed search

uninformed search는 현재 state가 다른 state보다 좋은지 평가하지 않고 그냥 우직하게 탐색만 해가며 goal state를 찾는 과정이다.
bfs, uniform cost search, dfs, dls, ids, bidirection search 등이 여기에 속한다.

bfs

function bfs(problem){
	closed = {};
  	fringe.insert(intialState);
  
  	while(!fringe.empty()){
    	node = fringe.pop();
      	closed.insert(node);
      
      	for(child in node.successors){
          if(child not in fringe or cloesd){
              	if(goal(child)) return solution;
            	fringe.insert(child);
            }
        }
    }
}

• completeness : branch factor b가 finite하면 항상 답을 찾음
• time complexity : O(b^d)
• space complexity : O(b^d)
• optimality : step cost가 1로 일정하면. 그렇지 않으면 not optimal

bfs는 좋긴 한데 step cost가 uniform 할때만 사용할 수 있고, 메모리를 많이 잡아먹음

uniform cost search

bfs에서 step cost가 일정하지 않을 경우 사용하는 방법

function ucs(problem){
    closed={};
    fringe.insert(intialstate);
  
    while(!fringe.empty){
    	node = fringe.pop();
      	if(goal(node)) return solution;
      	closed.insert(node);
      
      	for(child in node.successors){
            if(child not in fringe or cloesd){
                fringe.insert(child);
            }
          else if(child.cost < fringe[child].cost){
              fringe.replace(child);
          }
        }
    }
}

• completeness : yes
• time complexity : O(b^(c*/e))
• space complexity : O(b^(c*/e))
• optimality : yes

dfs

• completeness : state space가 finite하면 yes
• time complexity : O(b^d)
• space complexity : O(bd)
• optimality : No. 여러 solution이 있을때 제일 먼저 발견한 게 답이 됨. (뒤의 solution이 cost가 더 작을 수도 있음)

dls

dfs에서 깊이를 l로 제한을 둬서 하는 방법

function dls(node, limit){
  cutoff_occured = false;
  
  if(goal(node)){
    return solution;
  }
  else if(limit == node.depth){
    return cutoff;
  }
  else{
    for(child in node.successors){
      res = dls(child, limit);
      
      if(res==cutoff){
        cutoff_occured = true;
      }
      else if(res!=failure){
        return solution;
      }
    }
  }
  if(cutoff_occured){
    return cutoff;
  }
  else{
    return failure;
  }
}

• completeness : 진짜 solution의 depth를 d라 할때 d<l이면 incomplete
• time complexity : O(b^l)
• space complexity : O(bl)
• optimality : no

ids

dls에서 limit을 0에서 답을 찾을때까지 1씩 증가시켜가는 방법.

• completeness : yes
• time complexity : O(b^d)
• space complexity : O(bd)
• optimality : step cost가 uniform하면 yes

bidirection search

start와 goal state에서 시작해서 둘이 만날때까지 search를 하는 방법. start에서 움직이는 건 쉽지만, goal state에서 뒤로 움직이는 건 어려움. 따라서 transition model의 inverse가 확실할때만 사용 가능.

• completeness : yes
• time complexity : O(b^(d/2))
• space complexity : O(b^(d/2))
• optimality : step cost가 uniform하면 optimal