기초 인공지능 Assignment01 - Maze Game BFS와 A* Algorithm을 활용한 최단 경로 찾기

1. Requirements

python 버전 3.6 이상, pygame library

1. 문제 설명

[그림 01] AI_assignment01 디렉토리 구성

[그림 01]과 같이 과제 디렉토리 안에는 게임 난이도를 나타내는 stage1,stage2,stage3 폴더가 있다. 그리고 각 난이도별 맵 크기가 다른 3개의 txt파일이 존재한다. 코드를 다운 받은 뒤, pygame을 정상적으로 설치하고 터미널 상에서 코드를 실행하면 [그림 02]와 같은 실행 화면이 나타난다. (코드 실행 방법은 README.md 참조)

[그림 02] 난이도별 초기 실행 화면 모습

파란 사각형은 출발지점이며, 초록색 원이 목표지점을 나타낸다. stage1은 목표지점이 한 개가 있고, stage2는 각 모서리마다 목표지점이 한 개씩 존재하며, 총 네 개의 지점을 반드시 지나가야 한다. 그리 고 stage3는 목표지점이 여러 곳이 존재하며, 모든 지점을 통과해야 한다.

이번 과제에서는 python 언어로 BFS와 A* algorithm을 구현해 최단 경로를 탐색하는 것이 목표이다. 파일에는 search.py, maze.py, agent.py, maze_game.py 4가지 python 파일이 존재하며, 작성해야 할 파일은 search.py이다.

[각 stage별 구현해야 하는 점]

• Stage 1

Stage 1은 BFS와 A* algorithm을 각각 이용해 최단 경로를 탐색한다. A* algorithm의 경우에는, Heuristic Function으로 Manhattan Distance를 사용한다. BFS와 A* algorithm은 동일한 경로의 길 이를 출력해야 한다. 그리고 A* algorithm은 BFS보다 적은 수의 search states를 출력해야 한다.

• Stage 2

Stage 2는 A* algorithm을 이용해 최단 경로를 탐색한다. 단 Stage 2에서는 Heuristic Function은 사 용자가 정의해야 한다. 또한 stage2/small.txt, stage2/medium.txt, stage2/big.txt 실행시간 모두 2초

를 넘지 않아야 한다.

• Stage 3

Stage 3 역시 A* algorithm을 이용해 최단 경로를 탐색한다. Stage 3에서도 Heuristic Function은 사 용자가 정의한다. 단, 3단계에서는 Minimum Spanning Tree(MST) 알고리즘을 활용한 Heuristic Function을 정의해야 한다. Minimum Spanning Tree(MST) 구현 방법은 Kruskal Algorithm, Prim Algoritim 2가지 방법이 있으며, 2가지 방법 중 하나를 선택하면 된다.

1. 보고서

보고서 분량 제한은 없으나, 반드시 다음과 같은 내용이 포함되어야 한다.

1. 사용한 라이브러리와 각 알고리즘마다 구현한 방법에 대한 간단한 설명

1. 각 stage별로 출력되는 경로 그림과, 터미널 상에서의 path length와 search states, execute time

출력 캡처 화면 ([그림 03] 참고)

[그림 03] 출력화면 캡처 예시

즉 다음과 같은 출력화면이 포함되어야 한다.

1. bfs method로 실행한 stage1의 small.txt,medium.txt,big.txt 경로 그림과 출력 캡처 화면

1. astar method로 실행한 stage1의 small.txt,medium.txt,big.txt 경로 그림과 출력 캡처 화면

1. astar_four_circles method로 실행한 stage2의 small.txt,medium.txt,big.txt 경로 그림과 출력 캡 처 화면

1. astar_many_circles method로 실행한 stage3의 small.txt,medium.txt,big.txt 경로 그림과 출력 캡처 화면

1. Stage2와 Stage3에서 직접 정의한 Heuristic Function에 대한 설명

1. 주의사항

라이브러리는 자유롭게 사용 가능. execute time을 제외한 코드 실행시 출력 화면과 보고서에 첨부된 화면 캡처 내용이 동일해야 한다. copy check 적발시 0점 처리.

1. 제출

search.py 파일과 AI01_보고서_학번.pdf 두가지 파일을 압축해 AI01_학번_이름.zip으로 사이버 캠퍼스 에 업로드한다.