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
.
This task will teach you about:
agent.py
according to the guidelines.
pip3 install gym numpy sudo apt-get install python3-pil.imagetk
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 SearchAgent
.
The final agent must have the following methods:
Method | input parameters | output parameters | note |
---|---|---|---|
__init__ | environmnent | none | Agent initialization. |
heuristic_function | position , goal | value | Method returns the value of an admissible heuristic function from the state position to the final state goal . |
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 positions. If there is no path, it should return None . |
The evaluation splits into two:
Evaluation | min | max | note |
---|---|---|---|
Algorithm quality | 0 | 4 | Evaluation given by the automatic evaluation system. |
Code quality | 0 | 4 | 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!