Лекція 5

Алгоритм Белмана для обчислення функції корисності

Отже, розглянемо наступну ідею обчислення функції корисності, яка використовує принцип динамічного програмування. Сутність динамічного програмування полягає у використанні властивості оптимальної траєкторії: при невеликому зміщенні вздовж оптимальної траєкторії решта також залишається оптимальною для нового початкового положення. Тут суттєво використовується той факт, що корисність агента залежить від майбутніх (дисконтованих) виграшей. Розглянемо наступний алгоритм:

\[ \begin{align} & VALUE-ITERATION(T(\cdot), r(\cdot), \gamma, \epsilon) \\ & 1.\; \textbf{do} \\ & 2.\;u\leftarrow u'\\ & 3.\;\delta\leftarrow 0 \\ & 4.\quad\textbf{for}\; s \in S \\ & 5.\qquad \textbf{do}\;u'(s) \leftarrow r(s) + \gamma max_{a} \sum_{a} T(s,a,s')u(s')\\ & 6.\qquad \qquad \textbf{if}\; |u'(s)-u(s)|>\delta \\ & 7.\qquad \qquad \qquad \textbf{then}\; \delta \leftarrow |u'(s)-u(s)|\\ & 8.\; \textbf{until}\; \delta < \frac{\epsilon(1 - \gamma)}{\gamma}\\ & 9.\; \textbf{return}\; u' \end{align} \]

Алгоритм приймає на вхід МППР та помилку \(\epsilon\) та повертає функцію корисності \(u(s)\).

Давайте імплементуємо алгоритм для конкретної задачі

В даному випадку ми розглядаємо задачу, коли агент може рухатися вгору, праворучі ліворуч. При цьому додається ймовірністна помилка - дія, яку він хоче виконати здійснюється з ймовірністю 0.8, а інші дві з ймовірністю 0.1 кожна. Кодуємо процедури однократного обчислення функції корисності і повний алгоритм.

to value-iteration-once
   let delta 10000
   let my-turtle 0
   create-turtles 1 [
   set my-turtle self
   set hidden? true ]
    while [delta > epsilon * (1 - gamma) / gamma][
    set delta 0
    
    ask patches with [pcolor = black] [
      let best-utility -10000
      let x pxcor
      let y pycor
      foreach actions [
        [h] -> let a h
        let b one-of (remove a actions)
        let current-utility 0
        ; get main reward
        ask my-turtle [
          setxy x y
          perform a
          set current-utility (0.8 * utility) 
        ]
        ask my-turtle [
          setxy x y
          perform b
          set current-utility current-utility + (0.1 * utility) 
        ]
        ask my-turtle [
          setxy x y
          let c one-of (remove b (remove a actions))
          perform c
          set current-utility current-utility + (0.1 * utility)
        ]
        
        if (best-utility < [current-utility] of my-turtle)[set best-utility current-utility] 
      ]
      set utility (get-reward x y + gamma * best-utility)
      
 
    ]
     plot delta
    ]
  
end

Тепер запустимо до кінця

to value-iteration
   let delta 10000
   let my-turtle 0
   create-turtles 1 [
   set my-turtle self
   set hidden? true ]
    while [delta > epsilon * (1 - gamma) / gamma][
    set delta 0
    
    ask patches with [pcolor = black] [
      let best-utility -10000
      let x pxcor
      let y pycor
      foreach actions [
        [h] -> let a h
        let b one-of (remove a actions)
        let current-utility 0
        ; get main reward
        ask my-turtle [
          setxy x y
          perform a
          set current-utility (0.8 * utility) 
        ]
        ask my-turtle [
          setxy x y
          perform b
          set current-utility current-utility + (0.1 * utility) 
        ]
        ask my-turtle [
          setxy x y
          let c one-of (remove b (remove a actions))
          perform c
          set current-utility current-utility + (0.1 * utility)
        ]
        
        if (best-utility < [current-utility] of my-turtle)[set best-utility current-utility] 
      ]
      let old-utility utility
      set utility (get-reward x y + gamma * best-utility)
      if (abs (utility - old-utility) > delta)[
            set delta abs (utility - old-utility)
          ]
    ]
    plot delta
    show-utility
    ]
  
end

Тепер розглянемо більш загальну задачу “вихід з лабіринта”

В даній задачі ми:

генеруємо випадковий лабіринт. Клітинки якими можна пересуватися чорні, стіни - білі, вихід - коричневий.
дії агента детерміністичні - він може рухатись вперед, повертатися на 90 градусів праворуч і ліворуч (тобто станом у цій задачі є координати x, y та напрямок руху агента).
додається розширення для роботи з хеш-таблицями. Функція корисності зберігається у глобальній таблиці.
Кожен крок агента має винагороду -0.5, завершення 50, вхід у стінку -200.

Загальна послідовність кроків:

Визначити МППР.
Створити хеш-таблицю з функцією корисності.
Описати множину всіх станів.
Визначити найкращу дію для кожного стану.
Імплементувати ітераційний алгоритм обчислення функції корисності.

Починаємо з оголошення глобальних змінних

\[ \begin{align} & \color{green}{\textbf{extensions}}\; \textsf{table} \\ & \color{green}{\textbf{globals}}\; \textsf{[u headings actions]} \end{align} \]

Створюємо процедуру setup

to setup
  clear-all
  reset-ticks
  ask patches [set plabel-color green]
  ask patches with [
    abs pxcor = max-pxcor or abs pycor = max-pycor]
  [set pcolor white]
  ask patches with [pxcor = max-pxcor and pycor = 0]
  [set pcolor brown]
  ask patches with [
    abs pxcor < max-pxcor and abs pycor < max-pycor]
  [set pcolor one-of [white black black black]]
  set headings [0 90 180 270]
  set actions ["fd 1" "lt 90" "rt 90"]
  set u table:make
  create-turtles num [
    let p one-of patches with [pcolor = black]
    setxy [pxcor] of p [pycor] of p
    set color blue
    set heading one-of headings
  ]
end

Запускаємо:

Додамо процедуру go

to go
  tick
  ask turtles [
    take-best-action
  ]

end

to take-best-action
  run one-of actions
end

Продовжуємо. Додамо хеш-таблицю для обчислення функції корисності

to put-utility [x y dir utility]
  let state (list x y dir)
  table:put u state utility
end

to-report get-utility [x y dir]
  let state (list x y dir)
  if (table:has-key? u state) [
    report table:get u (list x y dir)
  ]
  put-utility x y dir 0
  report 0
end

Алгоритм обчислення функції корисності

to value-iteration
  let delta 10000
  let my-turtle 0
  create-turtles 1 [
    set my-turtle self
    set hidden? true
  ]

  while [delta > epsilon * (1 - gamma) / gamma][
    set delta 0
    ask patches [
      foreach headings [
        [h] -> let dir h
        let x pxcor
        let y pycor
        let best-action 0
        ask my-turtle [
          setxy x y
          set heading dir
          let best-utility item 1 get-best-action
          let current-utility get-utility x y dir
          let new-utility (get-reward + gamma * best-utility)
          put-utility x y dir new-utility
          if (abs (current-utility - new-utility) > delta)[
            set delta abs (current-utility - new-utility)
          ]
          set plabel (precision current-utility 1)
        ]
      ]
    ]
    plot delta
  ]
  ask my-turtle [die]
end

Потрібно ще реалізувати процедуру знаходження найкращої дії (для детерміністичного випадку - тут всі \(T(\cdot) = \{1,0\}\) )

to-report get-best-action
  let x xcor
  let y ycor
  let dir heading
  let best-action 0
  let best-utility -10000
  foreach actions [
    [a] ->
    run a  ; take action
    let utility-of-action get-utility xcor ycor heading
    if (utility-of-action > best-utility)[
    set best-action a
    set best-utility utility-of-action
    ]
    setxy x y
    set heading dir
  ]
  report (list best-action best-utility)
end

to take-best-action
  let best-action first get-best-action
  run best-action
end

to-report get-reward
  if (pcolor = brown) [report 50]
  if (pcolor = white) [report -200]
  if (pcolor = black) [report -0.5]
end

Спробуємо запустити.

Лекція 5

Олексій Ігнатенко

September 29, 2017

Лекція 5

Алгоритм Белмана для обчислення функції корисності

Давайте імплементуємо алгоритм для конкретної задачі

Тепер розглянемо більш загальну задачу “вихід з лабіринта”