Table of Contents
1. Search in KUI Maze
You will program the A* algorithm in order to search through the given state space.
Task
Implement an A* algorithm that
- always finds the cheapest path to one of the goal states, if any path exists;
- if there is no path to any goal, the algorithm returns value
None; - during the search for the optimal path, the algorithm minimizes the number of explored states.
You should use the maze environment kuimaze2.SearchProblem.
For the algorithm to work correctly, you need to choose and implement a suitable heuristic function. The impact of selecting different heuristic functions is well explained at this webpage. The cost of transition between two neighbouring positions is always larger or equal to the Euclidean distance of these two positions, and it generally does not have to be the same for all pairs of positions.
How to
- Install the
kuimaze2package, if you have not done so yet. - Learn about the SearchProblem environment. (The
kuimaze2module containsexample_search.py. This file also serves as a tutorial how to work with the environment.) - Create the file
agent.pyaccording to the guidelines.
- Your solution must be compatible with the required version of Python. Otherwise it is possible that the automatic evaluation system will malfunction!
Agent class and its methods
In file agent.py, implement class Agent with the following methods:
| Method | input parameters | output parameters | note |
|---|---|---|---|
__init__ | environmnent: SearchProblem | none | Agent initialization. |
find_path | none | path | Returns the found path or None if no path exists. A path is a list of States, including the start state and the goal state. |
Tips
The following Python modules may be useful in implementing some parts of the A* algorithm: queue, heapq.
Submission
- The due date for submission is visible in the BRUTE.
- Upload a ZIP archive with the module
agent.pyand any other possible modules you created to BRUTE. All the files must be in the archive's root folder! The archive cannot contain any other folders! You should NOT submit any files contained in the downloaded kuimaze2 module.
Evaluation
See a more detailed info about evaluation.
Screenshots
This screenshot comes from a previous version of kuimaze. The current version produces slightly different images. Main difference: diagonal moves are not allowed now.
