====== 01 Intro and Search I ======

===== Learning outcomes =====
After this lab session, a student
  * knows where to ask for help when stuck (lab sessions, [[https://cw.felk.cvut.cz/forum/forum-1945.html|BE5B33KUI forum]], email teachers);
  * understands the assessment scheme of the course;
  * understands the rules for plagiarism and AI usage;
  * understands the first quiz assignment;
  * can install Python and the ''kuimaze2'' environment;
  * understands the specification of the first mandatory task ''03-search'';
  * knows how to use the interface of ''kuimaze2.SearchProblem'' environment;
  * is able to submit a solution to BRUTE.

===== Program =====
  * [[https://cw.fel.cvut.cz/b252/courses/be5b33kui/start#grading|Grading and requirements]]
  * Read [[https://cw.fel.cvut.cz/wiki/help/common/plagiarism_cheating|plagiarism rules]] and [[courses:be5b33kui:ai|AI tools rules]]
  * Read about [[https://cyber.felk.cvut.cz/study/computer-labs/|computer labs]] how to set-up initial password, access home directory, links to other university services, ...
  * How to [[https://cw.fel.cvut.cz/b252/courses/be5b33kui/tutorials/python_installation|install Python]] on your computer if you do not have it yet
===== Bonus Quiz: Optimal plane travel plan =====
  * Find and justify the optimal travel plan of a plane
  * Submit your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]] **lab01quiz** (deadline in BRUTE)
  * Format: text file, photo of your solution on paper, pdf - what is convenient for you
  * Solution will be discussed on the next lab
  * 0.5 points
  * Solve and upload the right version according to the first character of your family name:
    * family name starting from A to L:  {{ :courses:be5b33kui:labs:weekly:plane_a_2025.pdf |version A}}
    * family name starting from M to Z:  {{ :courses:be5b33kui:labs:weekly:plane_b_2025.pdf |version B}}.

> {{page>courses:be5b33kui:internal:quizzes#Plane flight plan&nodate}}


===== Getting to know the KUIMaze environment =====
   * [[courses:be5b33kui:semtasks:kuimaze:00_install|Install kuimaze2 environment]]. 
   * See the "[[courses:be5b33kui:semtasks:01_search:start#howto|How To]]" section of [[courses:be5b33kui:semtasks:01_search:start|Search in KUI Maze]].
   * Create a ''SearchProblem'' environment, i.e. an instance of the class ''kuimaze2.SearchProblem'', with the map given by the image ''maps/easy_intro/easy_intro_1.png'':
<code python>
>>> from kuimaze2 import SearchProblem
>>> from kuimaze2.map_image import map_from_image
>>> map_path = 'maps/easy_intro/easy_intro_1.png'
>>> env = SearchProblem(map_from_image(map_path), graphics=True)</code>
  * Render the maze map with the ''render()'' method:
<code>
>>> env.render()
</code>
You should see the following image:
{{ :courses:b3b33kui:cviceni:program_po_tydnech:easy_intro_1.png?200 |}}
**Keep the image window open for now, don't close it!**
  * Try to use various methods the environment provides:
<code>
>>> start = env.get_start()
>>> start
State(r=0, c=1)
>>> env.get_goals()   # Notice the different return type, this returns a list of possible goals
[State(r=2, c=4)]
>>> actions = env.get_actions(start)
>>> actions
[<Action.UP: 0>, <Action.RIGHT: 1>, <Action.DOWN: 2>, <Action.LEFT: 3>]
>>> new_state = env.get_transition_result(start, actions[1])
>>> new_state
(State(r=0, c=2), 1)
>>> texts = {State(0,0): "S", State(0,1): "1"}
>>> env.render(texts = texts)
>>> env.render(texts = texts, current_state=State(0,0), next_states=[State(1,0)])
</code>
  * Try calling ''env.render()'' again. Has the image changed in any way?
  * Examine ''example_search.py'' and try to understand what is going on in it.
  * Try to construct the path from the start to the destination manually and modify the method ''Agent.find_path()'' so that it returns your hard-coded path.
  * Try submitting your agent to [[https://cw.felk.cvut.cz/brute/|BRUTE]] in task ''01-easy-search'', see below.

===== Optional training assignment: 01-easy_search =====
  * Although some of you might be impatient to jump to the implementation of the A* algorithm, try finding your way through a maze using a simpler algorithm, e.g., BFS or UCS, and test it on a smaller problem, easier for you to follow step-by-step and debug. This way you can verify you handle the environment in the right way. 
  * Try different search strategies. If you write your code in a general enough way, virtually the same code will stay in place for the A* algorithm (the first mandatory assignment). 
  * Try the task submission interface of [[https://cw.felk.cvut.cz/brute|BRUTE]]. Submit your ''agent.py'' module to task ''01-easy_search''. Observe the feedback you get from the evaluation script.
  * In this training task, you should get some points for finding valid path, some points for finding an optimal path; there are also deductions for exploring more states than needed. BEWARE: What is sufficient for this toy task does not have to be sufficient for the first mandatory task! The requirements are somewhat higher there!





===== Mandatory Assignment 1: Searching in a Maze =====
  * In the [[courses:be5b33kui:semtasks:01_search:start|1st mandatory assignment]], your task is to implement the A* algorithm that will be introduced in the second lecture. If you can do the previous "Easy Search" assignment fast enough and if you are used to Python, you can start working on the first mandatory assignment.
  * Do not forget that the cost of transition form one state to another does not have to be the same for all state pairs.

===== Other =====
  * [[http://tristanpenman.com/demos/n-puzzle/|visualisation]] of different search algorithms demonstrated on the n-1 puzzle problem

===== Homework =====
  * Submit the ''lab01quiz''.
  * Make the ''kuimaze2'' environment work in your Python installation.
  * Finish ''01-easy_search'' task (non-mandatory).
  * Start working on ''03-search'' task.