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:
kuimaze2
package, if you have not done so yet.
kuimaze2
module contains example_search.py
. This file also serves as a tutorial how to work with the environment.)
agent.py
according to the guidelines.
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 State s, including the start state and the goal state. |
The following Python modules may be useful in implementing some parts of the A* algorithm: queue, heapq.
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:
Subject of evaluation | Eval. type | Points | note |
---|---|---|---|
Algorithm quality | Automatic evaluation | 0-5 | Does the solution work correctly? |
Code quality | Manual evaluation | 0-2 | Is the solution implementation clear? |
Algorithm quality:
Code quality:
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).