====== 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:
<code bash>
pip3 install gym numpy
sudo apt-get install python3-pil.imagetk
</code>

<WRAP important round>
   * The code must be compatible with **Python 3**. Otherwise it is possible that the automatic evaluation system will malfunction!
</WRAP>

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:
<code python>
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
</code>

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|}}