01 Intro and Search I

We log on, discuss the rules, answer first questions, create first simple Python program.

Read about computer labs how to set-up initial password, access home directory, links to other university services, …

Reading about Python and programming essentials from the Programming Essentials course. Tutorials help with setting Python, discuss how to upload homework correctly, and add some class examples and some most frequent Python modules.

After solving the logging issues we will go into Objective Python. We will look into the environment you'll use to implement and deliver the algorithms you'll meet in the course. Python is well on-line documented/discussed, in case of problems, the internet is your friend. However, be careful to read about the plagiarism rules concerning your assignments uploads.

• Calculate the optimal travel plan of a plane
• submit your solution to BRUTE lab01quiz by February 20, midnight
• 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
• Students with their family name starting from A to K (included) have to solve and upload subject A , while students with family name from L to Z have to solve and upload subject B.

In the State Space Search environment, find the cheapest path. Keep in mind that the cost of changing positions is not necessarily the same everywhere.

• Install kuimaze2 environment.
• See the “How To” section of 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:

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

• Render the maze map with the render() method:

>>> env.render()

• Try to use various methods the environment provides:

>>> start = env.get_start()
>>> start
State(r=0, c=1)
>>> env.get_goals()   # Notice the different return type, this returns a Set
{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)])

• 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 BRUTE in task 01-easy-search, see below.

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

Finally, try the task submission interface of BRUTE. Submit your agent.py module to task 01-easy_search. exactly according to the specifications (name of the functions, input parameters, output format, etc). Observe the feedback you get from the evaluation script.

The goal of this assignment is to implement an algorithm you'll see in the second lecture, A*, but if you can do the bonus “Easy Search” assignment fast enough and if you are used to Python, you can start working on the first mandatory assignment.

The full description of the assignment. Do not forget that the cost of transition between different positions does not have to be the same.

• visualisation of different search algorithms demonstrated on the n-1 puzzle problem