CS170 Artificial Intelligence, UCR, Winter 2024
1 Introduction
Explore the world of search algorithms in a grid-based environment. In this project, you will implement different search strategies to navigate from a starting cell to a target cell, while encountering obstacles and open paths.
This hands-on exercise aims to deepen your understanding of the fundamental search algorithms frequently employed in Artificial Intelligence. This project also involves determining the shortest path based on the search algorithm you use for exploring the route.
2 Code Structure
You’ll be given a code template containing the SearchAlgorithms class. Your task is to fill in the methods corresponding to each search algorithm and ensure they return both the status of the target’s discovery and the final state of the grid:
• uniform search(): Implement the Uniform Search algorithm.
• dfs(): Implement the DepthFirst Search algorithm.
• bfs(): Implement the BreadthFirst Search algorithm.
• best first(): Implement the Best First Search algorithm, based on a heuristic you design or choose. Use the Manhattan distance as the heuristic.
1
• a star(): Implement the A Search algorithm, combining both cost and heuristic (Manhattan distance).
• agreedy(): Implement the Greedy Search algorithm, focusing solely on the heuristic (Manhattan distance).
For algorithms that use a priority queue, utilize the heapq module from
Python’s standard library to manage the queue efficiently. The grid is represented as a list of lists, containing:
• s: Starting position.
• t: Target or goal position.
• 0: Empty cells that you can traverse.
• -1: Walls or obstacles that you cannot traverse.
As you traverse the grid, mark the order of cells you visit by replacing the 0s with consecutive numbers. The starting and target positions, represented by s and t, should remain unchanged.
3 Requirements
• Follow the provided class and method names precisely. This ensures compatibility with the autograder on Gradescope.
• The function signatures or class names must not be altered.
• Use the Manhattan distance as the heuristic for the Best First, A*, and Greedy algorithms.
• Utilize the heapq module for implementing priority queues in applicable algorithms.
• Each search algorithm function must return a tuple containing two elements: a numeric indicator and the final state of the grid. The numeric indicator should be 1 if the target is found, and -1 if it is not found. The final state of the grid should display the marked cells according to the path found by the search algorithm. For instance, if the target is found, the function could return (1, grid), where 1 represents the successful search and grid represents the final state of the board.
• When adding to your queue or stack, follow this order: Right, Down, Left, Up, or the reverse. The order can be reversed as well.
1 Introduction
Explore the world of search algorithms in a grid-based environment. In this project, you will implement different search strategies to navigate from a starting cell to a target cell, while encountering obstacles and open paths.
This hands-on exercise aims to deepen your understanding of the fundamental search algorithms frequently employed in Artificial Intelligence. This project also involves determining the shortest path based on the search algorithm you use for exploring the route.
2 Code Structure
You’ll be given a code template containing the SearchAlgorithms class. Your task is to fill in the methods corresponding to each search algorithm and ensure they return both the status of the target’s discovery and the final state of the grid:
• uniform search(): Implement the Uniform Search algorithm.
• dfs(): Implement the DepthFirst Search algorithm.
• bfs(): Implement the BreadthFirst Search algorithm.
• best first(): Implement the Best First Search algorithm, based on a heuristic you design or choose. Use the Manhattan distance as the heuristic.
1
• a star(): Implement the A Search algorithm, combining both cost and heuristic (Manhattan distance).
• agreedy(): Implement the Greedy Search algorithm, focusing solely on the heuristic (Manhattan distance).
For algorithms that use a priority queue, utilize the heapq module from
Python’s standard library to manage the queue efficiently. The grid is represented as a list of lists, containing:
• s: Starting position.
• t: Target or goal position.
• 0: Empty cells that you can traverse.
• -1: Walls or obstacles that you cannot traverse.
As you traverse the grid, mark the order of cells you visit by replacing the 0s with consecutive numbers. The starting and target positions, represented by s and t, should remain unchanged.
3 Requirements
• Follow the provided class and method names precisely. This ensures compatibility with the autograder on Gradescope.
• The function signatures or class names must not be altered.
• Use the Manhattan distance as the heuristic for the Best First, A*, and Greedy algorithms.
• Utilize the heapq module for implementing priority queues in applicable algorithms.
• Each search algorithm function must return a tuple containing two elements: a numeric indicator and the final state of the grid. The numeric indicator should be 1 if the target is found, and -1 if it is not found. The final state of the grid should display the marked cells according to the path found by the search algorithm. For instance, if the target is found, the function could return (1, grid), where 1 represents the successful search and grid represents the final state of the board.
• When adding to your queue or stack, follow this order: Right, Down, Left, Up, or the reverse. The order can be reversed as well.