Artificial Intelligence Solving Problems by Searching Objective: The goal of this programming assignment is to implement and compare three search algorithms - Depth-First Search (DFS), Breadth-First Search (BFS), and A* algorithm – in solving a specific problem. This assignment will provide understanding and implementing different search strategies using Python and evaluating their performance. Problem Statement: Consider a 2D grid representing a maze. The objective is to find the optimal path from the starting point (S) to the goal point (G) using the specified search algorithms. The maze consists of open cells (.) representing valid paths and obstacles (X) representing blocked areas. Maze Representation: ● Example Maze: S '.' represents an open cell. 'X' represents an obstacle. 'S' represents the starting point. 'G' represents the goal point. Tasks: 1. Maze Generation: G O Implement a function to generate a random maze with a size of 10 X 10 and density of obstacles using Python. O The maze should have a defined starting point (S) and a goal point (G). O 2. Depth-First Search (DFS): Each run of the algorithms should produce a different maze configuration in terms of starting point, goal point and obstacle location. However, in each run, all 3 algorithms should use the same maze. Maze configuration changes from run to run but remains same within each run of three algorithms. o O Implement the Depth-First Search algorithm in Python to find a path from the starting point to the goal point. O Visualize the explored paths and the final solution. 3. Breadth-First Search (BFS): O Implement the Breadth-First Search algorithm in Python to find a path from the starting point to the goal point. O Visualize the explored paths and the final solution. 4. A* Algorithm: 5. Performance Evaluation: ● Implement the A* algorithm in Python with an appropriate heuristic function to find an optimal path from the starting point to the goal point. Visualize the explored paths and the final solution. O 7. Report: O O Compare the performance of DFS, BFS, and A* algorithm in terms of: Solution Path Length Number of Nodes Expanded Time Execution 6. Visualization: ■ Implement a visualization tool in Python to display the maze, explored paths, and the final solution for each algorithm. The visualization should be interactive and highlight the progress of the search. Write a report documenting your Python implementation, including: Overview of the problem and maze generation. Description of each implemented algorithm. Results of the performance evaluation. Visualizations and observations. ■ ■ Note: the exact behavior of each run depends on the algorithm's determinism, the characteristics of the maze, and any random or heuristic elements involved. It's essential to consider these factors when interpreting and analyzing the results of multiple runs on the same size of the maze. You can gain valuable insights by investigating the reasons behind different paths and variations in algorithm behavior. In your report, provide a clear and concise summary in the following format. Summary of Algorithm Performance (10 Runs) Depth-First Search (DFS) Failures: [Number of failures out of 10 runs] ● Breadth-First Search (BFS) ● ● ● A* Algorithm Successes: [Number of successes out of 10 runs] Average Solution Path Length: [Average length of successful runs] Average Nodes Expanded: [Average number of nodes expanded in successful runs] Average Execution Time: [Average execution time in seconds for successful runs] ● Note: Provide additional details on each failure, such as the specific run number and any observations or insights gained from analyzing failures. Failures: [Number of failures out of 10 runs] Successes: [Number of successes out of 10 runs] Average Solution Path Length: [Average length of successful runs] Average Nodes Expanded: [Average number of nodes expanded in successful runs] Average Execution Time: [Average execution time in seconds for successful runs] Submission Guidelines: ● Failures: [Number of failures out of 10 runs] Successes: [Number of successes out of 10 runs] Average Solution Path Length: [Average length of successful runs] Average Nodes Expanded: [Average number of nodes expanded in successful runs] Average Execution Time: [Average execution time in seconds for successful runs] ● Grading Criteria: ● Submit the Python source code in zip format along with any necessary instructions for running the program. Include a README file with details on how to install dependencies, compile, and execute the Python code. Submit the report in a pdf or word format. Grading Rubric: Correctness and functionality of the implemented algorithms in Python. Quality of visualization and interactivity in Python. Accuracy and completeness of the performance evaluation. Clarity and organization of the report. 1. Maze Generation (10 points): [2 points]: Implementation of a function to generate a random maze in Python. [2 points]: Maze includes a starting point (S), a goal point (G), open cells (.), and obstacles (X). [2 points]: Maze generation allows customization of size and obstacle density. [2 points]: Starting point (S) and goal point (G) are correctly placed. • generation is efficient and produces varied mazes. 2. Depth-First Search (DFS) Implementation (15 points): ● 3. Breadth-First Search (BFS) Implementation (15 points): ● ● 4. A* Algorithm Implementation (15 points): ● ● [5 points]: Correct implementation of DFS algorithm in Python. [5 points]: DFS finds a valid path from starting point to goal point. [3 points]: Visualization of explored paths during DFS. [2 points]: Visualization of the final solution path using DFS. 5. Performance Evaluation (20 points): [8 points]: Accurate comparison of DFS, BFS, and A* in terms of solution path length. [8 points]: Accurate comparison of DFS, BFS, and A* in terms of the number of nodes expanded. [4 points]: Discussion of time complexity for each algorithm. 6. Visualization Quality (15 points): ● [5 points]: Correct implementation of BFS algorithm in Python. [5 points]: BFS finds a valid path from starting point to goal point. [3 points]: Visualization of explored paths during BFS. [2 points]: Visualization of the final solution path using BFS. ● [2 points]: Maze ● [5 points]: Correct implementation of A* algorithm in Python. [5 points]: A* finds an optimal path from starting point to goal point. [3 points]: Visualization of explored paths during A*. [2 points]: Visualization of the final optimal solution path using A*. 7. Report (25 points): [5 points]: Clear and interactive visualization tool implementation in Python. [5 points]: Visualization accurately reflects the progress of the search algorithms. [5 points]: Visualization enhances understanding of the maze exploration process. [5 points]: Overview of the problem and maze generation in Python. [5 points]: Description of each implemented algorithm in Python. [5 points]: Results of the performance evaluation in Python. [5 points]: Visualizations and observations presented in a clear and organized manner. [5 points]: Overall quality, coherence, and professionalism of the report. To record the performance of each algorithm, run each algorithm 10 times each with a difference maze configuration. Record the performance of each run of the algorithm using the following table: 10x10 Maze Performance Table (10 Runs) 1 2 10 Average 1 2 10 2 : Total Points: 100 Run Algorithm Solution Path Length [nodes] [nodes] 10 Average Average BFS 1 Note: DFS [length] DFS [length] DFS DFS BFS [length] BFS [length] BFS : [length] [avg_length] A* A* [length] A* [length] A* [length] [nodes] [nodes] [avg_length] [nodes] [nodes] [length] [avg_length] Nodes Expanded [time] Pass [time] Fail [nodes] [avg_nodes] [time] Pass [time] Fail [nodes] [avg_nodes] [time] Pass [time] Fail [nodes] [avg_nodes] Execution Time Status [time] [avg_time] [time] [avg_time] [time] [avg_time] Pass Pass Pass Replace [length], [nodes], [time], [avg_length], [avg_nodes], and [avg_time] with actual values obtained during each run and their averages. In the "Execution Time" column, use the actual execution time values for each run.