Here we have a vacuum cleaning agent that can sense the environment and perform actions to move around and vacuum clean dirty squares. We assume a 5 by 5 grid world known to the agent. The environment is fully observable: the percepts give complete information about the Dirty/Clean status of every square and the agent’s location. The environment is deterministic: A clean square remains clean and a dirty square remains dirty unless the agent cleans it up. The actions available for the agent are: Left, Right, Up, Down, Suck. Each action takes place in one time step. The actions and percepts are perfectly reliable. Each of the actions will incur a cost of 1. At the end of each time step, each remaining dirty square will incur a cost of 2. The agent’s performance is measured by the total cost received from start state to reaching a state with all squares being “Clean”. As usual, a rational agent should maximize its performance score and thus minimize the total cost.
Assume the agent is in square (x, y) at time t, and the square was “dirty” at time t1. Suppose the agent performs the “Suck” action at time t, then square (x, y) will NOT incur cost due to dirtiness at step t (because at the end of this time step, square (x, y) is already clean).
Formulate the vacuum cleaning problem as a search problem. In this sub-problem, you would define the states, actions, the successor function, and the goal test. You can assume the initial state has the top 5 squares all dirty, and the agent is located at the bottom left square. You can index each square in the 5×5 grid world by (x, y) with the bottom left square = (1, 1) and the top right square = (5, 5).
How do you represent a state? Hint: A state S should specify two things:
(a) The dirty/clean status for all 25 squares, AND
(b) the current location (x, y) of the agent.
Dirty/Clean Status: 11111 (top 5 squares dirty), 0000000000 (bottom 20 squares clean)
State S = (Dirty/Clean Status for Each Square, Agent’s Location (x, y))
Write (or adapt from open-source implementation) a Python program to implement the A* algorithm (tree search) for the vacuum cleaning agent’s problem (defined in Question 5 of Homework 2). Your agent should utilize the admissible heuristic function h1(n) defined in your answer to Q(5.3) in Homework 2 (or a corrected h1(n) in case your h1(n) answer to Q(5.3) was not correct). Run the program for the 5 by 5 grid world with the top 5 squares dirty, and the agent located in the lower left corner square (coordinate (1, 1)) as the initial state. Print out the sequence of actions in the optimal path returned by the program. In addition, print out the f(n) values for every node n on the optimal solution path (including the node for the initial state and the node for the final goal state). Print out the number of nodes expanded by the algorithm using h1(n).
Part (B) (25%)
Run your A* algorithm for the same problem, using the alternative heuristic function h2(n) defined in your answer to Question (5,4) in Homework 2 (or a corrected h2(n) in case your h2(n) answer to Q(5.4) was not correct). Print out the sequence of actions in the optimal path returned by the program. In addition, print out the f(n) values for every node n on the optimal solution path (including the node for the initial state and the node for the final goal state). Print out the number of nodes expanded by the algorithm using h2(n).
Program documentation (5%)
Please provide reasonable documentation to your program to make it easy for understanding. If you are submitting multiple files, please zip them and then submit ONE .zip file. If you are submitting a Jupyter notebook, please use the first cell to include your name and indicate any packages (other than aima-python master – which I assume by default) that would be needed to run your notebook. If you are submitting a Python program instead of a Jupyter notebook, you should either include in your submission a ‘readme’ file or use comments at the beginning of your Python file to indicate your name and any packages needed to run your program (same as the Jupyter notebook case). Try to name your submission with YOUR NAME (for example: Chen_Astar.ipynb or Chen_Astar.py or Chen_Astar.zip) to make identification of your submission easier. Use of comments is strongly encouraged to help better understanding of your program logic.
All Study Co-Pilots are evaluated by Gotit Pro as an expert in their subject area.