Ifi6057w4

4. Nädal

Heuristiline otsing. AIMA chapter 3.5, TI 17 (eeldab ka 16 lugemist).

Hinnangufunktsioon, heuristiline funktsioon. Ahne otsing.

A*; selle optimaalsus ja täielikkus. Introduction to A* (mängu-AI / Python)

Loenguslaidid: PDF

Harjutustund

Ülesanne - 4st ruumist ("A", "B", "C", "D") koosnev tolmuimejamaailm. Leiame lühima lahenduse algolekust seisu, kus kõik ruumid on puhtad. Lõppolekus pole oluline, kus on tolmuimeja. Kasutame search.Problem klassi, et maailma kirjeldada.

import search

class VacWorld(search.Problem):
  def actions(self, state):
      act = []
      # ...
      return act
  def result(self, state, action):
      newstate = state.copy()
      # action on yks nendest: "Left", "Right", "Suck", "NoOp"
      return newstate
  def goal_test(self, state):
      # kui on k6ik puhas, return True
      # muidu return False

Oleku esitus

 algolek = {
   "A" : "Dirty",
   "B": "Clean",
   "C": "Clean",
   "D": "Dirty",
   "loc": "C"
 }

Poolik actions

 def actions(self, state):
      act = []
      vac_loc = state["loc"]
      if state[vac_loc] == "":
          act.append("")
      if vac_loc == "A":
          act.append("Right")
      # ...
      return act

Poolik result

  def result(self, state, action):
      newstate = state.copy()
      # action on yks nendest: "Left", "Right", "Suck"
      vac_loc = state["loc"]
      if action == "Suck":
          newstate[vac_loc] = "Clean"
      elif action == "Right":
          # vastavalt ruumile peab panema uue newstate["loc"] = ?  väärtuse
          # näiteks kui tolmuimeja oli ruumis "A" siis uues olekus on ta ruumis "B"
      elif action == "Left":
          # nagu "Right", aga vastassuunas ("B" muutub "A"-ks) jne
      return newstate

goal_test peab kontrollima, et kõik ruumid on puhtad

Testimiseks

 p=VacWorld(algolek)
 # print(p.actions(olek))
 # asi = search.breadth_first_tree_search(p)
 # asi = search.iterative_deepening_search(p)
 # print(asi.solution())