AI 1: Lab Assignment 1
Lab Assignment代写 This is an individual assignment and consists of a Python coding element and a report. However, you are allowed to…
Agents and Search
Instructions Lab Assignment代写
- This is an individual assignment and consists of a Python coding element and a report.
- However, you are allowed to collaborate on the Python element of the assignment, provided that:
- you collaborate with at most 2 other students (so groups of maximum 3 collaborators);
- you clearly indicate, at the top of both the report and the code, the names and s-numbers of the students with whom you collaborated.
-
you write your report independently.
If you fail to disclose your collaborators, or your collaboration involves also the report element of the assignment, your submission will be treated as an instance of plagiarism (see the Nestor pages of the course for information about how the Board of Examiners treats cases of plagiarism during this online teaching period).
- Answer all questions and formulate your answers concisely and clearly.
- Remember it is not allowed to use code not developed by yourself. Doing so constitutes plagiarism. If you use external sources (videos, websites, discussion fora, etc.) to develop your code make sure to clearly refer to them in your report and in your code. Failing to disclose these sources constitutes again an instance of plagiarism.
- Reports need to be written in LATEX. A template is available on Nestor. The text should be authored by yourself and yourself only.
- Comply with the deadline provided on Nestor. Deadlines are strict (penalties apply for late submissions, see below).
- Comply with the instructions on how to submit your assignment fifiles. These involve submitting all source codes in such a way that they can be easily tested by us. Such instructions will be available on a dedicated submission section on Nestor.
Assessment
The grade of this lab assignment will counts for 25% of your fifinal grade. We subtract 2n−1 grade points for a submission that is between n − 1 and n days late (n ≥ 1).
Questions? Get in touch with us! You can do so during labs, tutorials, using the discussion boards on Nestor or the helpdesk email ai1rug1920@gmail.com. Make sure you read the instructions to contact the helpdesk that are provided on Nestor. Only emails sent according to the instructions will be replied to.
Figure 1: Maze
[26 pts] Theory assignment
[10 pts] PEAS descriptions
Study the material on PEAS descriptions from the book.
Questions:
- a) Write a PEAS-description for the following agents:
- A reversi/othello computer (see http://en.wikipedia.org/wiki/Reversi)
- A robotic lawn mower (see http://en.wikipedia.org/wiki/Robotic_lawn_mower).
- b) Characterize each domain as fully observable / partially observable, deterministic / stochastic, episodic / sequential, static / dynamic, discrete / continuous and single agent / multi-agent.
[16 pts] Maze Lab Assignment代写
Given is a simple maze environment (see Figure 1 above). An agent in this environment can choose from 4 actions: move one step north, east, south, or west. Here is the problem defifinition:
States: The squares of the maze.
Actions: Step in direction N=north, E=east, S=south, or W=west.
Goal Test: Is the agent in the yellow colored square (square 15)?
Path cost: Each step has cost 1.
Initial state: The agent is in the red square (square 1).
Furthermore, the agent is provided with a collision detector that indicates whether it has just collided against a wall. If the agent hits a wall, then it knows that the corresponding direction is blocked and it will try the next direction from the set of possible actions. The agent always tries actions in the order [N, E, S, W].
First we try to solve the maze using the following open list 1 version of depth fifirst search (DFS). The pseudo code for this implementation is given below.
For example, the actions of the algorithm in the search for a DFS path from square 5 to square 10 (i.e. we call MazeDFS(maze, 5, 10)) is N, N, E, S.
Questions:
a) Why is it not possible to use mazeDFS() to fifind a path from the red square to the yellow square? Where does it go wrong?
b) How should the (pseudo-)code be modifified such that it is guaranteed to always fifind a solution (if one exists)?
c) In which order are the states visited by the modifified algorithm for the call mazeDFS(maze, 1, 15)?
d) In which order are states visited by the modifified algorithm for the call mazeDFS(maze, 1, 15) if we change the order of actions into [N,S,W,E]?
e) If we replace the stack in the original algorithm by a FIFO queue, then the algorithm is suddenly turned into (the open list version of) breadth fifirst search (BFS). Will this algorithm always fifind a solution (if one exists)? Explain your answer.
f) In which order are states visited by the open list BFS algorithm for the call mazeDFS(maze, 1, 15)? Only give the fifirst ten steps!
g) Can we reduce the number of visited states of the BFS algorithm? If yes, how should the program be modifified?
h) Would you use (a variation of) DFS or (a variation of) BFS for path searching in large mazes? Explain your answer.
[64 pts] Programming assignment – 3D maze Lab Assignment代写
In this fifirst programming assignment we consider a three-dimensional maze problem. On Nestor, you can fifind the fifile maze.zip. After extracting it, you will fifind a directory maze with fifiles in it. Go into this directory. You can fifind the following fifiles in the directory:
*.maze: These fifiles are simple textfifiles with information about the maze :
– Coordinates (x, y, z) denote cells in the maze, with X, Y and Z in the directions as pictured
in fifigure 2. The top left cell on flfloor 0 has coordinate (0,0,0).
Figure 2: Coordinate system in the maze
– The current position is indicated by the capital letter X. The letter G in cell (1,1,0) in default.maze denotes the goal cell.
– If you run the code, the maze will also be printed with the coordinates at the bottom of each cell.
– Connections between rooms are indicated by spaces. Thus, it is possible to go from (0,3,1) to (1,3,1), but it is not possible to go from (0,2,1) to (1,2,1).
– If a room has a staircase going up, then this is indicated by the letter U (Up). The letter D (Down) denotes a staircase going down.
– All connections between rooms are symmetric: if (x, y, z) has a staircase going up, then (x, y, z +1) has a staircase going down.
– So, in the maze it is possible to go up from (1,3,0) to (1,3,1), and vice versa.
– Note that oblique moves (moves along a diagonal) are not allowed. The cost for going up is 3, for going down is 2 and sideways is 1.
maze.py: This fifile defifines the Room and Maze class. It shouldn’t be necessary to change these fifiles. Look over the available methods for the Room class, as they may be useful – Room.get connections() in particular. Use that function to provide you with the order in which to visit neighboring states.
state.py: State is a class to keep track of the current path and cost. Feel free to add things if needed. Lab Assignment代写
maze solver.py: File where the functions for the search algorithms are. The open list version of DFS and BFS is already implemented.
main.py: File to read arguments from command line or start solver with default options
fringe.py: Fringe is a wrapper around the queue library of python in order to track some statistic. This can be used to see how many states were added to the queue and how maney states where visited.
You can run it with: python3 main.py [BFS|DFS] [mazefile]. When the program fifinds a solution it will print the fringe statistics and the path. It will also print the maze the path displayed in it and the cost in the upper left corner of a cell.
Questions:
a) Try to run default.maze with the depth fifirst search algorithm (python3 main.py DFS). Will it fifind a solution? If not, why not?
b) Try to run BFS.maze with the breadth fifirst search algorithm. Will it fifind a solution? If not, why not?
4c) Fix (if needed) the BFS and DFS algorithms so that they will fifind a solution in the mentioned cases.
d) Implement the uniform cost search algorithm (make sure that you can call it with python3 main.py UCS).
e) Implement the greedy search algorithm (make sure that you can call it with: python3 main.py GREEDY greedy astar.maze).
f) Implement the A* search algorithm (make sure that you can call it with: python3 main.py ASTAR greedy astar.maze).
g) Why are the paths that the A* and the greedy search algorithm have found difffferent? Lab Assignment代写
h) Implement the iterative deepening search algorithm (make sure that you can call it with: python3 main.py IDS). Note: recursion can be useful here, but is not needed. If you decide to use recursion, make sure that you print the path and cost.
i) Build a table consisting of one row for each algorithm, where you give the sequence of actions taken by each algorithm in sequence.maze (by means of example, ENESENUWWNNDS is the sequence of actions taken by BFS in the default.maze maze).
