State space search

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.

Learning outcomes

This task will teach you about:

  • Time complexity
  • Space complexity
  • Resulting path quality

How to

  1. Create the file agent.py according to the guidelines.
  2. 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

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

Evaluation

The evaluation splits into two:

  1. Minimal solution that returns a correct path. If there is no path, it returns an empty set.
  2. Manual evaluation of the code and its form (clean code).
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:

  • tested on multiple mazes with various size and complexity
  • is the path valid? - does not cross walls and is continuous on the 4-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:

courses/be5b33kui/labs/search/start.txt · Last modified: 2018/03/29 09:48 by svarnpet