====== State space search ======
You will program the [[https://en.wikipedia.org/wiki/A*_search_algorithm|A* algorithm]] in order to search through the given [[https://en.wikipedia.org/wiki/State_space_search|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 =====
- Create the file ''agent.py'' according to the guidelines.
- Use the testing environment supplied in the ZIP {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}} file for testing before submission.
- Extract the ZIP file in the folder with your project.
- 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 {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}} are documented in the subfolder ''/kuimaze_doc/'' or available at this [[https://cw.felk.cvut.cz/cmp/courses/be5b33kui/kuimaze_doc/index.html|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:
- 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 | 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 [[https://cw.felk.cvut.cz/upload/|Upload system]].
* Upload a ZIP archive with the module ''agent.py'' and any other possible modules you created to the [[https://cw.felk.cvut.cz/upload/|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:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:normal9.png|}}