Problem-solving agent, search algorithm

Problem-Solving Agents

- Atomic 표현법을 사용한다.

- task environments : 문제의 solution 은 Sequence of actions 이다.

- 즉, 미래의 percept 에 대해서는 고려하지 않는다.

- 검색 알고리즘이 solution 을 찾을 때 사용된다.

 

- search algorithm 종류 

• Uninformed search : 문제에 대한 정의 외에 정보는 X
• Informed search : 문제에 대한 정의 + 추가적인 정보를 가짐

- From Romania to Home : 루마니아에서 집까지 찾아가는 문제

 

 

Goal Formulation

- Goal : 이 세상의 일부 상태의 집합 

- 지도를 가지고 있다고 가정하자 (=informed search) 

• action : 도시간의 이동
• Route finding : 경로탐색

- Task environment

• Observable -> fully, 지도와 거리가 모두 주어짐
• Discrete -> 도시간의 이동 단위가 쪼개어져있음, 연속X
• known -> agent 가 world 에 대해 알고 있음
• deterministic -> state 와 action 이 주어졌을 때 다음 state 가 확정적임

- Solution : 고정된 action 의 연속

- Formulate -> search -> execute

 

 

Formulate, Search, Execute

- Simple problem-solving agent program

input 으로 percept 를 받는다.

이전 상태와 percept 정보를 바탕으로 현재 상태를 update 한다. -> Update-state(state, percept)

seq (동작열) 이 비어있는 경우에는, 목표를 세워준다. ->Formulate-Goal(state)

목표를 문제화한다. -> Formulate-problem(state, goal)

목표까지 도달할 수 있는 행동의 sequence 를 찾는다.-> Search(problem)

sequence 의 첫 번째 값이 지금 수행할 action 이 된다. -> First(seq)

seq를 나머지 sequence 로 대입한다. -> Rest(seq)

그리고 현재 수행할 행동을 반환한다. -> return action

 

 

Define a Problem

문제정의의 요소이다.

- State 

- Initial state : 시작(첫 번째) 도시

- Actions : 도시간 이동

- Transition model : Result(s, a) = s'

- Goal test : A set , Goal 의 집합

- Path cost :

• Goal 까지의 비용 = goal까지의 모든 step cost 를 다 더할 때
• step 비용 - state 가 action 을 취함으로서 발생하는 비용)

 

The Vacuum-Cleaner Agent Problem

- States : 현재 방의 상태 (Clean/Dirty), 아래 그림 처럼 8개의 가능한 State 가 존재한다.

- Initial State : 위 8개의 상태 중 하나

- Actions : Left, Right, Suck

- Transition model : 위 상태에서 어떠한 action 을 취해서 다른 state 로 이동하는 것

- Goal Test : 모든 방이 깨끗한지 확인한다 -> goal state 가 될 수 있는 건 맨 아래 두개의 state

- Path cost : 매 step 바다 1의 비용이 든다.

 

 

8-Puzzle Problem

- states : 8! (빈칸은 자동 결정)

- Initial state : 주어짐

- Actions : move the blank -> Left, Right, Up, Down (모든 상황에서 네 가지 동작이 다 가능한 것은 아님)

- Transition model : 어떤  blank 에 action 을 취하면 blank 의 위치가 어떻게 되는지

- Goal test : 주어짐

- Path cost : 각 step 마다 1의 비용이 듬

 

 

8-Queens Problem

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

-States : 

• Incremental formulation : 빈 판에 Queen 을 하나씩 배치하는것
• Complete-state formulation : 퀸을 8개 다 배치 후 위치를 이동시키는것

- Path cost : 관심X , Goal 을 찾는게 문제다

- Initial State : 퀸이 하나도 없음(Incremental 일때)

- Actions : 퀸을 빈 공간에 놓는것

- Transition model

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

 

-More efficient formulation

: 왼쪽의 빈 열부터 채워나가는 게 효율적이다. (한 column 에 한명의 퀸만 있을 수 있음)

 

 

 

A Toy Problem with Infinite State Space

- 무한한 공간의 문제

 

- States : 양수 전체

- Initial state : 4

- Actions : 팩토리얼, 제곱근, 바닥함수(크지 않은 최대 양수)

- Transition model

- Goal test : 주어진 수를 만들어야 함 -> 5

 

->주어진 공간이 없어 무한하게 만들 수 있다.

 

 

More Real-World Problems

- Airline travel-planning

- Traveling salesperson problem (NP-hard)

- VLSI layout (반도체칩 component 배치)

- Robot navigation (연속된 공간)

- Automatic assembly sequencing (단백질 설계)