CS440/ECE448 Fall 2019 Assignment 1: Search Due date: Monday September 16th, 11:59pm

In this assignment, you will build general-purpose search algorithms and apply them to solving puzzles. In Part 1, you will be in charge of a "Pacman"-like agent that needs to find a path through maze to eat a dot or "food pellet." In Part 2 you will need to find a single path that goes through all the dots in the maze.

Programming language

This MP will be written in Python. If you've never used Python before, you should start getting used to it. A good place to start is the Python Tutorial (also available in hardcopy form). You should install version 3.6 or 3.7 on your computer, as well as the pygame graphics package.

Your code may import extra modules, but only ones that are part of the standard python library . Unless otherwise specified in the instructions for a specific MP, the only external library available during our grading process will be pygame. For example: in mp1, numpy is not allowed

Contents

• Part 1: Basic Pathfinding
• Part 2: Search with multiple dots
• Hints for Part 2
• Extra Credit
• Provided Code Skeleton
• Deliverables

Implement the state representation, transition model, and goal test needed for solving the problem in the general case of multiple dots. For the state representation, besides your current position in the maze, is there anything else you need to keep track of? For the goal test, keep in mind that in the case of multiple dots, the Pacman does not necessarily have a unique ending position. Next, implement a unified top-level search routine that can work with all of the following search strategies, as covered in class and/or the textbook:

• Depth-first search
• Breadth-first search
• A* search

To check for correctness, you can run each of the three search strategies on the following inputs:

• Medium maze
• Big maze
• Open maze

The provided code will generate a pretty picture of your solution.

Part 2: Search with multiple dots

• Tiny search
• Small search
• Medium search

You should be able to handle the tiny search using uninformed BFS. In fact, it is a good idea to try that first for debugging purposes, to make sure your representation works with multiple dots. However, to successfully handle all the inputs, it is crucial to use A* and come up with a good heuristic. For full credit, your heuristic should be admissible and should permit you to find the solution for the medium search in a reasonable amount of time.

It's ok for A* to call itself as a subrouine. But your top-level function must be A*. This will ensure that your code always returns a path with minimum length. If you have some other clever way to approach the multiple-dot problem, implement that as extra credit.

Hints for Part 2

Extra Credit

Sometimes, even with A* and a good heuristic, finding the optimal path through all the dots is hard. In these cases, we'd still like to find a reasonably good path, quickly. Write a suboptimal search algorithm that will do a good job on this big maze. Your algorithm could either be A* with a non-admissible heuristic, or something different altogether. Note that the extra credit will be capped to 10% of what the assignment is worth.

Specifically, your extra credit function must solve this maze in less than 6 minutes (when we test it on gradescope). Assuming that it finishes in that amount of time, grading will be based only on the length of your returned path.

Provided Code Skeleton

We have provided ( tar file or zip file) all the code to get you started on your MP, which means you will only have to write the search functions. You should only modify search.py. Use the provided API functions (e.g. getNeighbors) and do not modify code in files other than search.py. Otherwise the autograder may be unable to run your code and/or may decide that your outputs (especially for depth-first search) are incorrect.

maze.py

• getStart() :- Returns a tuple of the starting position, (row, col)
• getObjectives() :- Returns a list of tuples that correspond to the dot positions, [(row1, col1), (row2, col2)]
• isValidMove(row, col) :- Returns the boolean True if the (row, col) position is valid. Returns False otherwise.
• getNeighbors(row, col) :- Given a position, returns the list of tuples that correspond to valid neighbor positions. This will return at most 4 neighbors, but may return less.

search.py

There are 4 methods to implement in this file, namely bfs(maze), dfs(maze), astar(maze), and astar_multi(maze). The method astar_multi is for part 2 of the assignment, and the other methods are for part 1. There is also one optional method extra(maze) which you will use if you decide to do the extra credit. Each of these functions takes in a maze instance, and should return the path taken (as a list of tuples). The path should include both the starting state and the ending state. The maze instance provided will already be instantiated, and the above methods will be accessible.

To understand how to run the MP, read the provided README.md or run python3 mp1.py -h into your terminal. The following command will display a maze and let you create a path manually using the arrow keys.

python3 mp1.py --human maze.txt

The following command will run your astar search method on the maze.

python3 mp1.py --method astar maze.txt

You can also save your output picture as a file in tga format. If your favorite document formatter doesn't handle tga, tools such as gimp can convert it to other formats (e.g. jpg).

Tips

• Check that you are using python 3. Running our code (especially the display code) under python 2 may cause mysterious errors.
  
  
• You can (and should) create additional test mazes to make sure your code is working properly and/or help you debug problems. Similarly, we can (and likely will) run your code on mazes not shown here.
  
  
• In your implementation, make sure you get all the bookkeeping right. This includes handling of repeated states (in particular, what happens when you find a better path to a state already on the frontier) and saving the optimal solution path.
  
  
• Pay attention to tie-breaking. If you have multiple nodes on the frontier with the same minimum value of the evaluation function, the speed of your search and the quality of the solution may depend on which one you select for expansion.
  
  
• Implement all strategies using a similar approach and coding style. In particular, while DFS can be implemented very compactly using recursion, you must store the frontier in an explicit stack, queue or priority queue (depending on the search algorithm) for this assignment. Among other things, limits on recursion depth can be (depending on your installation) much lower than the number of objects that you can pack into an explicit stack.
  
  
• You will be graded primarily on the correctness of your solution. Your code must run in a generally reasonable amount of time, but you do not need to do significant optimization. For example, we don't care whether your priority queue or repeated state detection uses brute-force search, as long as you end up expanding exactly the correct number of nodes (except for small differences caused by differences among tie-breaking strategies) and find the optimal solution. So, feel free to use "dumb" data structures as long as it makes your life easier and still enables you to find the solutions to all the inputs in a reasonable amount of time.