1.md

Workshop 1

• problems_1.pdf
• solutions_1.pdf

1. State Model

#State Model

• 8-Puzzle
  • State space S
    • a set of all unique-sequenced array[0..8] of 0..8 indicating the digit on each position in the frame, with 0 representing the missing tile
  • Initial state s_0 ∈ S
  • Set of goal states S_G ⊆ S
    • S_G = {[1,2,3,4,5,6,7,8,0]}

  • Applicable actions function A(s) for each state s ∈ S

      ```
      A(s) = { <s, s'> | s' = s.swap(s.indexof(0), s.indexof(0)-1) /\ s,s' ∈ S }
      ∪ { <s, s'> | s' = s.swap(s.indexof(0), s.indexof(0)+1) /\ s,s' ∈ S }
      ∪ { <s, s'> | s' = s.swap(s.indexof(0), s.indexof(0)-3) /\ s,s' ∈ S }
      ∪ { <s, s'> | s' = s.swap(s.indexof(0), s.indexof(0)+3) /\ s,s' ∈ S }
      ```
    

  • Transition function f(s, a) for s ∈ S and a ∈ A(s)
    • f(s, <s, s'>) = s'
  • Cost of each action c(a, s) for s ∈ S and a ∈ A(s)
    • c(a, s) = 1 for s ∈ S and a ∈ A(s)
• Travelling Salesman Problem
  • Consider a set of cities V to visit in any order, a starting city location v_start , and a set of edges E specifying if there’s an edge from two cities <v, v'>
    • State space S
      • S = { <v_current, V_current> | v_current ∈ V, V_current ⊆ V }
    • Initial state s_0 ∈ S
      • if needing to return to the first city
        • s_0 = <v_start, V>
        • or s_0 = <v_start, {}>
      • if not needing to return to the first city
        • s_0 = <v_start, V - {v_start}>
        • or s_0 = <v_start, {v_start}>
    • Set of goal states S_G ⊆ S
      • { <v, {}> | v ∈ V }
      • or { <v, V> | v ∈ V }
    • Applicable actions function A(s) for each state s ∈ S
      • A(s) = { <v, v'> | <v, v'> ∈ E }
    • Transition function f(s, a) for s ∈ S and a ∈ A(s)
      • f(<v_current, V_current>, <v_current, v'>) = <v', V_current - {v'}>
      • or f(<v_current, V_current>, <v_current, v'>) = <v', V_current ∪ {v'}>
    • Cost of each action c(a, s) for s ∈ S and a ∈ A(s)

2. Heuristic Search

#Heuristic search 启发式搜索

• Is h admissible?
  • yes
    • h (s_1) = 4 < h* (s_1) = 6
    • h (s_2) = 3 < h* (s_2) = 5
    • h (s_3) = 5 < h* (s_3) = 10
    • h (s_4) = 3 < h* (s_4) = 5
    • h (s_5) = 2 < h* (s_5) = 3
    • h (s_6) = 2 < h* (s_6) = 4
    • h (s_7) = 0 <= h* (s_7) = 0
• Is h consistent?
  • yes
    • h(s_1) - h(s_2) = 1 < 2
    • h(s_1) - h(s_3) = -1 < 2
    • h(s_1) - h(s_4) = 1 <= 1
    • h(s_2) - h(s_5) = 1 < 2
    • h(s_3) - h(s_7) = 5 < 10
    • h(s_4) - h(s_6) = 1 <= 1
    • h(s_5) - h(s_7) = 2 < 3
    • h(s_6) - h(s_7) = 2 < 4
• iterations
  • iteration 1
    • OPEN
      • n_1 = <s_1, 4, 0, nil>
  • iteration 2
    • OPEN
      • n_2 = <s_2, 5, 2, s_1>
      • n_3 = <s_3, 7, 2, s_1>
      • n_4 = <s_4, 4, 1, s_1>
    • CLOSED
      • n_1 = <s_1, 4, 0, nil>
  • iteration 3
    • OPEN
      • n_2 = <s_2, 5, 2, s_1>
      • n_3 = <s_3, 7, 2, s_1>
      • n_5 = <s_6, 4, 2, s_4>
    • CLOSED
      • n_1 = <s_1, 4, 0, nil>
      • n_4 = <s_4, 4, 1, s_1>
  • iteration 4
    • OPEN
      • n_2 = <s_2, 5, 2, s_1>
      • n_3 = <s_3, 7, 2, s_1>
      • n_6 = <s_7, 6, 6, s_6>
    • CLOSED
      • n_1 = <s_1, 4, 0, nil>
      • n_4 = <s_4, 4, 1, s_1>
      • n_5 = <s_6, 4, 2, s_4>
  • iteration 5
    • OPEN
      • n_3 = <s_3, 7, 2, s_1>
      • n_6 = <s_7, 6, 6, s_6>
      • n_7 = <s_5, 6, 4, s_2>
    • CLOSED
      • n_1 = <s_1, 4, 0, nil>
      • n_4 = <s_4, 4, 1, s_1>
      • n_5 = <s_6, 4, 2, s_4>
      • n_2 = <s_2, 5, 2, s_1>
  • iteration 6
    • OPEN
      • n_3 = <s_3, 7, 2, s_1>
      • n_7 = <s_5, 6, 4, s_2>
    • CLOSED
      • n_1 = <s_1, 4, 0, nil>
      • n_4 = <s_4, 4, 1, s_1>
      • n_5 = <s_6, 4, 2, s_4>
      • n_2 = <s_2, 5, 2, s_1>
      • n_6 = <s_7, 6, 6, s_6>

• path
  • s_1 -> s_4 -> s_6 -> s_7
• Is this the optimal plan? Has the algorithm proved this?
  • yes, as h is admissible. If there is a cheapest path then it should have already been expanded due to its smaller f value