联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2021-03-31 11:36

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


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp