[Search_6] Corners Problem: Heuristic (1)

※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 1: Search"를 해결하는 과정을 정리한 글입니다.

 

Corners Problem: Heuristic

이번 문제는 A* 탐색에서 구현한 코드가 필요하기 때문에, 이번 문제를 풀기 전에 A* 탐색 문제를 먼저 수행하여야 합니다.

 

cornerHerustic의 CornersProblem을 위해 단순하지 않으면서 일관적인 휴리스틱을 구현하십시오.

- python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

 

python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5 실행 시 시작되는 게임 화면

python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5 실행 시 출력 화면

 

위의 AStarCornersAgent는 아래의 명령어의 단축 명령어이다.

- python pacman.py -l mediumCorners -p SearchAgent -a fn=aStarSearch, prob=CornersProblem, heuristic=cornersHeuristic

 

python pacman.py -l mediumCorners -p SearchAgent -a fn=aStarSearch, prob=CornersProblem, heuristic=cornersHeuristic 실행 시 시작되는 게임 화면

python pacman.py -l mediumCorners -p SearchAgent -a fn=aStarSearch, prob=CornersProblem, heuristic=cornersHeuristic 실행 시 출력 화면

 

휴리스틱은 탐색 상태를 가지고 가장 가까운 목표지점까지의 비용의 추정치를 반환하는 함수임을 기억해야 합니다. 가장 효과적인 휴리스틱은 실제 목표지점까지의 비용과 가까운 값을 반환하는 것입니다. 허용성을 가지기 위해서는 휴리스틱 값이 반드시 실제로 가장 가까운 목표지점까지의 최단 경로의 비용보다 작아야 합니다. 일관성을 가지기 위해서는 비용이 c인 작업을 수행할 때 휴리스틱이 c만큼 떨어질 수 있다는 것을 알고 있어야 합니다.

 

허용성만 가지고는 경로 탐색에서 정확성을 보장하기에는 충분하지 않기 때문에 강력한 일관성이 필요할 것입니다. 하지만 허용 가능한 휴리스틱은 대부분 일관적이고, 특히 문제 완화를 위한 휴리스틱은 더욱 그렇습니다. 따라서 허용 가능한 휴리스틱을 브레인스토밍 하는 것부터 시작하는 것이 가장 좋을 것입니다. 잘 동작하는 허용 가능한 휴리스틱을 만들었다면 일관성도 체크할 수 있을 것입니다. 일관성을 보장하는 유일한 방법은 증명하는 것입니다. 하지만 확장한 노드의 다음 노드가 f-value 값이 같거나 높다면 가끔 모순이 발생할 수 있습니다. 또한, 만약 균일 비용 탐색 (Uniform Cost Search, UCS)와 A* 탐색 알고리즘을 수행하였는데 서로 다른 길이의 길을 반환하였다면 구현된 휴리스틱이 일관적이지 않은 것입니다. 이번 문제는 까다로울 것입니다.

 

단순한 휴리스틱은 어느 곳에서나 0을 반환하고 실제 완성 비용을 계산하는 휴리스틱입니다. 어느 곳에서나 0을 반환한다는 것은 동작 시간을 줄이지 못한다는 것을 의미하고, 결국 autograder를 작동하였을 때 최종 비용을 계산하는 도중에 시간이 초과될 것입니다. 휴리스틱의 계산 시간을 줄이는 것은 중요하지만 이번 과제에서 autograder는 오직 노드의 개수를 체크하는 것만 수행할 것입니다.

 

최종적으로 구현된 휴리스틱은 어느 위치에서 작동하더라도 단순하지 않고 나쁘지 않고 일관된 휴리스틱일 것입니다. 휴리스틱이 반드시 모든 goal state에서는 0을 반환하고 절대로 음수 값을 반환하지 않게 만드십시오. 휴리스틱에 따라 확장된 노드가 얼마나 되느냐에 따라 아래와 같은 점수를 받을 것입니다.

 

확장된 노드에 따른 점수 표

 

만약 구현된 휴리스틱이 일관적이지 않을 경우 점수를 받지 못하니 조심하십시오.