CS470 Intro. to Artificial Intelligence Spring 2021
Homework 1
Date assigned: 12 Mar 2021
Submit your homework to your TA via email by the due date. Late submissions
will not be accepted. The homework must be written in English. Write the
homework number, your name and student ID number on the top of the front
page.
1 Introduction
In this assignment, you will implement informed and uninformed search algorithm.
2 Multi-Agent Pac-Man
In this assignment, we referred to Multi-Agent Pac-Man project
(http://stanford.edu/~cpiech/cs221/homework/prog/pacman/pacman.html) from
Stanford University. Don't forget to use Python 3.6 when scripting your code.
3 Project Instruction
3.1 Breadth-first-search
Breadth first search is a search algorithm that traverses tree like data structure
exploring the neighbor nodes first. Sequence of exploring tree is explained in picture
below.
Figure 1: Sequence of exploring tree with BFS.
Breadth-first-search can be implemented with a queue. By putting neighbor
nodes of current node into a queue and exploring next node with queue sequence, we
can explore the neighbor nodes first.
3.2 A* algorithm
A star algorithm is kind of Breadth-first-search algorithm that uses heuristic function
to find shortest path efficiently. Unlike Breadth-first-search algorithm, A* first
explores the nodes which have high evaluation function value. Evaluation function is
sum of cost of the path from the start node to node n, and estimated cost which is
needed to reach to goal from node n (heuristic).
f(n) = g(n) + h(n)
3.3 What to do
You should implement BFS and A* algorithm in order to get Pac-man to the goal.
Pac-man can move in four directions which are 'North', 'South', 'East', and 'West'
('Stop' is not considered). Legal actions that Pac-man can take depend on Pac-man's
situation. For example, if East and South side of Pac-man is blocked by wall,
legal-actions are 'North' and 'west'. So, considering legal-action as a node, visit
unexplored area in BFS order and reach to the goal. In case of A*, you are required to
implement A* algorithm only (no need to visit unexplored point with Pac-man).
Figure 2: Example Tree of legal actions of Pac-man
While exploring tree with BFS, please visit neighbor node in East, West, South,
North order and print the sequence of x, y coordinate that Pac-man first visit in
result.txt file. Starting location of Pac-man is considered to be (0, 0).
3.4 What to Submit
Please submit searchAgents.py file only. Any late submissions will not be accepted.
3.5 How to Run the Code
To try out the Pac-man, run pacman.py from the command line. This agent will just
stop at every action. If you implement search agent, the agent will move appropriately
to search food.
python pacman.py
To activate the BFSAgent, use -p BFSAgent:
python pacman.py -p BFSAgent
To activate the AstarAgent, use -p AstarAgent:
python pacman.py -p AstarAgent
To run Pac-man with no graphic, use –q
python pacman.py -p AstarAgent –q