来源:名城汉中    时间:2021-04-01 09:15


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


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

( 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


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 file only. Any late submissions will not be accepted.

3.5 How to Run the Code

To try out the Pac-man, run 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.


To activate the BFSAgent, use -p BFSAgent:

 python -p BFSAgent

To activate the AstarAgent, use -p AstarAgent:

 python -p AstarAgent

To run Pac-man with no graphic, use –q

 python -p AstarAgent –q 

请加QQ:99515681 或邮箱   WX:codehelp