Provided Code Skeleton
We have provided the code skeleton
zip file
including all the code and example mazes to get you started, 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
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),
astar(maze), astar_corner(maze), and astar_multi(maze). The method astar_corner is for part 2, astar_multi
is for part 3, 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 & Notes
- 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.
The final evaluation mazes will be different from the shown examples.
- 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. You must store the frontier in an explicit queue or priority queue (depending on the search algorithm).
-
You will be graded primarily on the correctness of your solution. The evaluation on executation time will include all the process of precomputing and path searching.
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.
- After fininsing all the parts, you may find the final implmentation can be general enough for all the parts in the assignment, but we still expect to have fewer execuation time for simpler tasks. (i.e. no unnecessary pre-computing). Note that for part 2, all the solutions should not exceed 2 seconds.
Deliverables
This MP will be submitted via gradescope.
Please upload only search.py to gradescope.
After submission, gradescope will run preliminary tests to determine whether or
not your submission appears valid. These preliminary tests are worth 0 points,
and are for your information only. Passing all of these preliminary tests
does not guarantee that your implementations are correct.