1. Please note the modification of the grid-world configuration (now it is 3 by 3), and the initial state setting (ONLY the top 3 squares are dirty, and the agent location is in the center of the grid-world) from the distributed hard-copy.

Part (A)

In Python, write (or adapt from open-source implementation) a computer program to implement the A* algorithm for the vacuum cleaning agents problem for an optimal sequence of actions. Run the program for the 3 by 3 grid world with top 3 squares dirty, and agent in the center square (second row and second column) as the initial state. Print out the sequence of actions and the associated sequence of states in one optimal path returned by the program. Also print out the optimal paths cost.

Part (B)

Run your A* algorithm for the same problem, using the alternative heuristic function h. Again, print out the sequence of actions and the associated sequence of states in one optimal path returned by the program. Also print out the optimal paths cost.

Moreover, print out the number of nodes generated by using h₂ and by using h in your program runs.