CS 404, Spring 2024 Artificial Intelligence Assignment 1: Solving Color-Maze Puzzle using A* Search Due Sunday, 17 March, 11:30pm Color-Maze puzzle is a single-agent grid-game played on a rectangular board that includes a maze. Initially, the agent is located on a single maze cell. The agent can move in four cardinal directions: up, down, right or left. Once a direction is chosen, the agent moves in that direction until it reaches a wall at once, and colors all the cells it travels over. Once a cell is colored, its color does not change. The goal is to color all the cells of the maze by moving the agent over them, while minimizing the total distance traveled by the agent. This game is available at: https://www.mathplayground.com/logic_color_maze. Please implement in Python an A* search algorithm to solve the following version of the Color-Maze puzzle. Input is a rectangular game board with a single agent, represented as a grid where each grid cell is uniquely marked with 0, X or S: • O denotes the cells that are empty and that need to be colored, • X denotes the cells occupied by the walls, and • S denotes the cell occupied by the agent. For instance, in Figure 1 (right) describes the game board depicted in Figure 1 (left). OOOKOS 0 0 0 X 0 0 Χ 0 0 0 X X X ○ × × × ×0 ○ × × × ×O ○ × × × 0 0 X X X 0 0 X 0 X 0 X 0 X X X 0 0 0 Figure 1: An example puzzle (left) and its representation in the given format (right). Output is an alternating sequence of states and moves, that illustrates how the agent colors all the cells such that the total distance traveled by the agent is minimized. For instance, Figure 2 (resp. Figure 3) shows step by step how the agent can color the cells of a given maze, where the total distance traveled by the agent is 6 (resp. 5). In both solutions, the agent takes the same number of moves but the total distance traveled by the agent is smaller in Figure 3. Therefore, the sequence of states and actions illustrated in Figure 3 should be returned as the output. CS 404, Spring 2024 Artificial Intelligence 111 Figure 2: The agent moves right, down, and then up, and travels 6 units of distance in total. What to do The assignment consists of four parts: Figure 3: The agent moves right, up, and then down, and travels 5 units of distance in total. 1. (20 points) Model the Color-Maze puzzle as a search problem: Specify the states, suc- cessor state function, initial state, goal test, and step cost function.¹ 2. (20 points, provided that part 1 is completed) Extend your search model for Color-Maze to apply A* search:¹ (a) Find an inadmissible heuristic function h₁ and illustrate with an example that h₁ is not admissible. (b) Find an admissible heuristic function h₂ and prove that h₂ is admissible. (c) Discuss whether h₂ is monotone or not. 3. (20 points, provided that part 2 is completed) Implement in Python the A* search algo- rithm studied in class, 2 to solve the Color-Maze puzzle. Make sure that your implemen- tation displays the solution (i.e., an alternating sequence of states and actions) as well as the total distance travelled. 4. (40 points, provided that part 3 is completed) (a) Define 3 difficulty levels (e.g., easy, normal, difficult) for a Color-Maze puzzle instance, and prepare a benchmark set of at least 15 Color-Maze puzzle instances of 3 difficulty levels (i.e., 5 easy, 5 normal, 5 difficult instances), on a game board of size 12 x 12.³ (b) Evaluate your A* implementations experimentally over these benchmark instances, and summarize the results of your experiments in a table that shows, for each puzzle instance, the number of cells in the maze, the difficulty level, the total distance traveled by the agent, with heuristic h₁ vs. h2, the total number of expanded nodes, with heuristic h₁ vs. h2, the CPU time and the memory consumption, with heuristic h₁ vs. h2. (c) Discuss the results presented in the table: - What do you observe about the scalability of the A* search algorithm? How does the time and memory consumption increase as the input size increases? Are these observations surprising or expected, considering the asymptotic time and space complexity of the algorithm? Please explain. How does the A* search algorithm explore the search space, with h₁ vs. with h₂? Are these observations surprising or expected, considering the ad- missibility/monotonicity features of the functions? Please explain. ¹Reminder: The step cost function and the heuristic function return positive numbers > € > 0, at every non-goal state. 2 Attention: Some A* implementations available online are incorrect or incomplete. Make sure that your own implementations match the algorithms taught in class. 3 Attention: In the demos, you are expected to show one example for each difficulty level. 2 CS 404, Spring 2024 Submit Artificial Intelligence • A pdf copy of a description of 4 · your formulations of the Color-Maze puzzle (i.e., search model and heuristic func- tions), and experimental evaluation of your A* search implementation on the Color-Maze in- stances (i.e., table and discussion). A zip file containing the following: - Your Python code for the algorithm, with comments describing your solution. Several test boards you created for the 4'th part of the assignment, and the corre- sponding solutions found by your implementations. In each one of the deliverables above, please include your name and student id. Demos If your submitted implementation runs correctly and you can demonstrate it with your test instances successfully (without any bugs), then you will be invited to make a demo of your implementations. The 3'rd and the 4'th parts of the assignment will be graded at the demos.5 The demos are planned for the week following the deadline and will be scheduled later on. Collaboration You are allowed to work with another classmate. In that case, each team should submit one report in pdf, and one zip file at SUCourse+. Both team members should be present at the demos, if the team would like to make a demo of their implementation. 4Suggestion: You can use Overleaf for editing in LATEX: https://www.overleaf.com/. 5 Attention: If your implementation does not run correctly with any of your instances, you will not be invited to the demos and thus no credit will be given to the 3'rd and the 4'th parts. 3