Search
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.
None
kuimaze.InfEasyMaze
This task will teach you about:
agent.py
# On Linux pip3 install --user gym numpy sudo apt-get install python3-pil.imagetk # On Mac with Homebrew package manager pip3 install gym numpy pip3 install Pillow brew install python-tk # On Windows pip3 install gym numpy pip3 install Pillow
All the methods and functions in kuimaze_search.zip are documented in the subfolder /kuimaze_doc/ or available at this link.
/kuimaze_doc/
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:
easy_example.py
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 Agent, inheriting from the class kuimaze.BaseAgent.
Agent
kuimaze.BaseAgent
The final agent must have the following methods:
__init__
environmnent
find_path
The evaluation splits into two:
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).
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!
Possible final screenshot: