1. Search in KUI Maze

You will program the A* algorithm in order to search through the given state space.

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.

1. Install the kuimaze2 package, if you have not done so yet.
2. Learn about the SearchProblem environment. (The kuimaze2 module contains example_search.py. This file also serves as a tutorial how to work with the environment.)
3. Create the file agent.py according to the guidelines.

In file agent.py, implement class Agent with the following methods:

The following Python modules may be useful in implementing some parts of the A* algorithm: queue, heapq.

• The due date for submission is visible in the BRUTE.
• Upload a ZIP archive with the module agent.py and 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.

See a more detailed info about evaluation.

This screenshot comes from a previous version of kuimaze. The current version produces slightly different images. Main difference: diagonal moves are not allowed now.