Search (1st assignment)

You will program the A* algorithm in order to search through the given state space.

Task

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.

Learning outcomes

This task will teach you about:

Time complexity
Space complexity
Resulting path quality

How to

Create the file agent.py according to the guidelines.
Use the testing environment supplied in the ZIP kuimaze_search.zip file for testing before submission.
1. Extract the ZIP file in the folder with your project.
2. You need to have the following python3 packages AI-gym, numpy and pillow for proper use of the scripts. You can get these packages by running this command from your terminal:

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

The code must be compatible with Python 3. Otherwise it is possible that the automatic evaluation system will malfunction!

All the methods and functions in kuimaze_search.zip are documented in the subfolder /kuimaze_doc/ or available at this link.

Agent class and its methods

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`.

Evaluation

The evaluation splits into two:

Minimal solution that returns a correct path. If there is no path, it returns an empty set.
Manual evaluation of the code and its form (clean code).

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:

tested on multiple mazes with various size and complexity
is the path valid? - does not cross walls and is continuous on the 8-neighbourhood
is the path optimal?

Code quality:

suitable comments or the code is so clear that it does not need comments
reasonable length of methods
variables and functions are properly named and this naming helps understanding and reading the code
no repetitive code (copy-paste in the same code)
saving processing time and memory (i.e. no unnecessary nested loops)
…

Submission

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!

Screenshots

Possible final screenshot:

Table of Contents