Search Problems

본 강의는 UC Berkeley의 AI 강의를 참고하여 진행됩니다.

Pacman을 예시로 사용하여 Search Problems의 3가지 구성요소를 살펴보자. (pac coin CPR좀..)

• A State space

State space는 각 상황을 나타내는 state의 집합이다.

state는 x,y에 위치한 food의 on, ff의 상태이다.

위 이미지에서 간략하게 state space를 계산한다면 3 X 3 크기에 food가 on, off로 나뉘므로 으로 볼 수 있다.

물론 더 들어가서 팩맨의 위치, 팩맨의 방향까지 고려할 수 있지만 용어 및 개념파악을 위한 것이므로 더 자세히 들어가지는 말자.

• A successor function(with actions, costs)

왼쪽 현재 state에서 "N",1.0이 실행되면 우상단의 이미지와 같이 팩맨이 North 방향으로 cost 1 만큼 이동한다.

• A start state and a goal test

start state(시작점)와 goal test(골지점)이 존재한다.

시작점에서 종료지점까지로 변환되는 행동(계획)의 시퀀스를 솔루션이라 부른다.

이제 3가지 구성요소를 살펴보았으니 실습을 통해 감을 익혀보자.

States, Actions, Successor, Goal test 구하기

---

Problem	길찾기	모든 점 먹기
States	(x,y) location	{(x,y), dot booleans}
Actions	NSEW	NSEW
Successor	update location only	Update location and possibly a dot boolean
Goal test	(x,y)=END	dots all false

같은 상황에서 골지점에 따라 state, successor가 달라질 수 있는 것이 포인트!

State Space Size 구하기

---

Map size: 5 * 6

Agent facing: 4 [NSEW]

Food Count: 30 [Map size]

Agent Positions: 120 [Map size * Agent facing]

Ghost positions: 12

World states: [Agent Positions * 2^Food count * Ghost positions^2 * Agent facing]

States for pathing: 120

States for eat-all-dots: 120*2^30