This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

02 Search I

How to search when we do not know how far is the goal. What does it mean that an algorithm is complete, optimal?

  • discussion on the first assignment
  • AI-gym works for everyone?
  • Search Exercise

Completeness and optimality

We will discuss how to best search when we don't know how far is the goal. What does it mean that a search algorithm is complete, optimal.

Quiz I / Solving together

Search exercise

Let us start with a simple graph to practice searching, as it is easier to debug and understand. The lecture example you can try out here: ''kuigraphs.py''.

The basic communication is the same as for kuimaze. I.e.:

import kuigraphs
env = kuigraphs.KuiGraph()
observation = env.reset()
states_with_costs = env.expand(state) # list of tuples ('a',1)

state is a letter like in the lecture: 'S', 'a', … 'G'. Try out some search strategies. If you write them generally enough, your code will work also in the following case:

env = kuimaze.InfEasyMaze()

Think a little bit about the types of data structures you will need.

Students should think about representation of Nodes in search Trees, and how to implement Node and NodeList classes that permit to create and manipulate Nodes.

For teacher:

Search programming

  • The following Python libraries may help you for searches in a tree: queue and heapq.

Maze search: 1st mandatory assigment

In the environment from Search program an algorithm that will find the cheapest path. Do not forget that changing positions does not have to cost the same in every case.

courses/be5b33kui/labs/weekly/week_02.txt · Last modified: 2022/02/14 15:02 by gamafili