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 finds the optimal path to the desired goal state. If there is no optimal path, the returned value should be None. You should use the maze environment kuimaze2.SearchProblem. For fulfilling the task, you need to select and implement a heuristic function. The impact of selecting different functions is well explained in link.

This task will teach you about:

• Time complexity
• Space complexity
• Resulting path quality

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.

The evaluation consists of two parts:

Algorithm quality:

• Tested on multiple mazes with various size and complexity.
• The solution shall run without errors.
• Is the path valid? (It shouldn't cross walls, go outside of the maze, and should be continuous on the 4-neighbourhood.)
• Is the path optimal?
• Is the algorithm efficient? Doesn't it explore more states than actually needed to find the optimal path?

Code quality:

• suitable comments or the code is so clear that it does not need comments
• reasonable length of methods
• the names of variables, functions, methods, etc. are meaningful and help in understanding and reading the code
• no repetitive code (no copy-paste in the same code)
• saving processing time and memory (i.e. no unnecessary nested loops)
• …

You can follow PEP8, although we do not check all PEP8 demands. Most of the IDEs (certainly PyCharm) point out mishaps with regards to PEP8. You can also read some other sources for inspiration about clean code (e.g., here) or about idiomatic python (e.g., medium, python.net).

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