You will program the A* algorithm in order to search through the given state space.
Program an A* algorithm that finds the optimal path to the desired end state. If there is no optimal path, the returned value should be None
. You should use the maze environment kuimaze.InfEasyMaze
. 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:
agent.py
according to the guidelines.
pip3 install gym numpy sudo apt-get install python3-pil.imagetk
For mac and windows users, the python3-pil.imagetk won't work. You need to use the following command instead:
pip3 install pillow
All the methods and functions in kuimaze_search.zip are documented in the subfolder /kuimaze_doc/
or available at this link.
The ZIP file contains the file easy_example.py
. This file serves as a tutorial to the environment as seen on this code snippet with the basic functions:
import kuimaze # package import MAP = 'maps/normal/normal9.bmp' env = kuimaze.InfEasyMaze(map_image=MAP) # create the environment observation = self.environment.reset() # returns start_pos, goal_pos positions_with_costs = env.expand(position) # returns [(pos, cost)] list
Implement your agent in the file agent.py
as the class BaseAgent
.
The final agent must have the following methods:
Method | input parameters | output parameters | note |
---|---|---|---|
__init__ | environmnent | none | Agent initialization. |
find_path | none | path | Generates the path. The method returns a list of coordinates for the path. It must start with the starting position and end at the goal position [(x1, y1), (x2, y2), … ]. If there is no path, it should return None . |
The evaluation splits into two:
Evaluation | min | max | note |
---|---|---|---|
Algorithm quality | 0 | 5 | Evaluation given by the automatic evaluation system. |
Code quality | 0 | 2 | Comments, code structure, cleanliness, proper naming… |
Algorithm quality:
Code quality:
The date for submission is visible in the Upload system.
* Upload a ZIP archive with the module agent.py
and any other possible modules you created to the Upload system. All the files must to be in the archive's root folder! The archive cannot contain any other folders!