lecture 9

Асинхронний бектрекінг

ABT це розподілена версія централізованого DFS алгоритму для проблеми задоволення обмежень. ABT виконує той самий тип пошуку, але при цьому використовує обмін повідомленнями між агентами.

ABT алгоритм дещо краще виконується ніж DFS, цього можна досягти призначаючи пріоритет (впорядкування) агентів - чим більше обмежень, тим вищий пріоритет. Ця евристика дає непогані результати.

Отже, застосування алгоритму асинхронний бектрекінг (АБТ) потрібно задати пріоритет (впорядкування) агентів. Ми будемо вважати, що порядковий номер агента визначає його важливість - чим менше номер, тим вище пріоритет. Кожне бінарне обмеження відоме обом агентам перевіряється агентом з нижчим пріоритетом. Агенти початково з’єднані ребрами графа, що описують безпосередні обмеження (неможливо мати однаковий колір з обох кінців ребра). Також кожен агент містить множину сусідів, яка спочатку дорівнює його безпосереднім сусідам а пізніше поповнюється іншими. Агенти обмінюються повідомленнями, які бувають трьох типів: - ok? - handle-nogood - handle-new-neighbor.

Всі агенти чекають на повідомлення та опрацьовують їх за порядком надходження. На початку роботи алгоритму агенти отримують випадкове призначення та формують список nogood станів - станів, які суперечать розв’язку. Після цього кожний агент надсилає своїм сусідам, що мають нижчий пріоритет повідомлення ok?(agent, color) - що можна зрозуміти як спробу узгодити кольори початкового призначення.

Коли агент отримує повідомлення ok?(agent, color) від сусіда, він поміщає отриману інформацію в структуру, що називається agent view, після цього він перевіряє чи є його колір узгодженим з поточним agent view, тобто чи немає пари (його колір, отриманий колір) у переліку nogood станів. Якщо колір узгоджений, то агент просто видаляє повідомлення. Якщо колір неузгоджений, агент намагається вибрати інший колір та повідомити своїх низькопріоритетних сусідів про свій вибір. Якщо вибрати узгоджений колір неможливо то агент запускає процедуру відкату (backtracking).

При виконанні backtracking формується новий nogood з поточного agent view (ми використовуємо найпростіший спосіб). В цьому разі nogood складається з агентів, які суперечать вибору кольору поточного агента. Агент, який потрапив у backtracking вибирає найменш пріоритетного з переліку агентів з nogood та надсилає йому відповідне повідомлення.

В результаті розв’язок проблеми передається наверх по пріоритетності, якщо ж ситуація backtracking виникла у першого агента, формується повідмлення про те, що розв’язку не існує.

Theorem (ABT є повним). Алгоритм ABT завжди знаходить розв’язок якщо такий існує або формує повідомлення про те, що розв’язку не існує. (Yokoo et al., 1998).

Приклад

Розглянемо приклад виконання ABT для простого графу з двома кольорами. Виконаємо випадкове призначення (вибрали таке, щоб іллюструвати бетрекінг)

Всі агенти посилають повідомлення ok? своїм сусідам з нижчим пріоритетом. Агент 4 отримує повідомлення від 0, 2, 3. Агент 2 від 1. Намагаючись знайти узгоджений колір агенти 2, 4 змінюють колір на червоний.

Після цього агент 2 надсилає агенту 4 ok? (agent2 red), але 4 агент не може вибрати колір, який би був узгоджений з його сусідами, тому він формує nogood та повідомляє наступному за пріорітетом сусіду - агенту 3, що він не може нічого вдіяти. При цьому він надсилає свій agent view, в якому міститься інформація ((агент2 червоний), (агент0 синій), (агент3 червоний)). Агент 3 додає собі сусідів агентів 2, 0. Агент 3 змінює свій колір на червоний і розсилає ok? (agent3 red).

Однак це не допомагає, тому агент 3 формує свій nogood та викликає бектрекінг для наступного за пріоритетом сусіда (агента 2). Аналогічно nogood доходить до агента 1, і він змінює колір на червоний.

Агент 1 надсилає агенту 2 свій ok? (agent2 red) в результаті чого другий агент змінює свій колір.

Тепер агент 2 розсилає своїм сусідам ok?, внаслідок чого агент 3 змінює свій колір на синій.

Формується повідомлення Розв’язок знайдено.

Asynchronous Weak-Commitment Search

Покращенням ABT є AWC. Тут пріоритет агентів змінюється динамічно - чим більше бектреків, тим вище пріоритет.

extensions [table] ; розширення хеш - таблиці 

breed [nodes node] ; агенти - вершини графа

globals [colors] ; кольори, які будуть використовуватися

nodes-own [
  message-queue  ;; список вхідних повідомлень у форматі [тип-повідомлення текст-повідомлення]
  lower-naybors  ;; список сусідів з меншим пріоритетом 
  naybors        ;; розширений список сусідів 
  local-view     ;; відображення виду (номер-агента - колір)
  no-goods       ;; список пар (агент колір), які є обмеженнями
]

; визначення агентів і зв'язків між ними
to setup
  clear-all
  reset-ticks

  ask patches [set pcolor white]
  set colors [red blue green yellow]

  create-nodes num-nodes [
    set shape "circle"
    setxy random-pxcor random-pycor
    set color black
  ]

  repeat num-edges [
    ask one-of nodes [
      create-link-with one-of other nodes
    ]
  ]
end

; розташування агентів і зв'язків
to layout
  layout-spring nodes links 0.2 5 1
end

; визначення необхідних для алгоритму АБТ структур і змінних
to setup-abt
  ; призначаємо випадково кольори, визначаємо множини сусідів
  ask nodes [
    set color one-of colors
    set message-queue []
    set lower-naybors []
    set local-view table:make
    set naybors sort link-neighbors
    let i who
    ; вибірка сусідів з нижчим пріоритетом
    foreach naybors [
      [a] ->
      let w ([who] of a)
      if (w > i) [
        set lower-naybors fput a lower-naybors
      ]
    ]
    ; встановлення початкових обмежень
    set no-goods []
     foreach naybors [
      [a] ->
      let w ([who] of a)
      set no-goods sentence no-goods map [
        [b] ->
        normalize-nogood list (list who b) (list w b) ] colors
    ]
  ]
  ; розсилання повідомлень ок? зі своїм кольором сусідам з нижчим пріоритетом
    ask nodes [send-out-new-value]
end

to go
  let important-turtles turtles with [not empty? message-queue]
  ifelse (count important-turtles > 0) [

    ask important-turtles [handle-message]
  ][
    ifelse (bad-links = 0)[
      show "SOLUTION FOUND"
    ][
      show "NO MORE MESSAGES. NO SOLUTION"
    ]
    stop
  ]
end

to-report bad-links
   let violated-links links with [
    [color] of end1 != black and
    [color] of end2 != black and
    [color] of end1 = [color] of end2
]
report count violated-links
end

to-report constraint-violations?
  let violated-links links with [
    [color] of end1 != black and
    [color] of end2 != black and
    [color] of end1 = [color] of end2
]
report any? violated-links
end

to-report normalize-nogood [nogood]
  ;; Сортування обмежень для виключення дублікатів
  report sort-by [ [a b] -> (first a) < (first b) ] nogood
end

to send-out-new-value
  ;; Надсилання ок? сусідам з нижчим пріоритетом
  let my-message list "ok" (list who color)
  let i who
  foreach lower-naybors [ [a] ->
    ask a [set message-queue (lput my-message message-queue)]
  ]
end

to handle-message
 ; обробка повідомлень агентами

  if not empty? message-queue [
    let message first message-queue
    set message-queue but-first message-queue
    let message-type first message
    let message-value last message

    ifelse message-type = "ok" [
      let someone first message-value
      let val last message-value
      handle-ok someone val
    ][
      ifelse message-type = "nogood" [
        handle-nogood message-value
      ][
        handle-add-neighbor message-value
      ]
    ]
  ]
end

; обробка повідомлень типу ок?
to handle-ok [someone val]
  table:put local-view someone val
  check-local-view
end

; обробка повідомлень типу nogood
to handle-nogood [nogood]
 if(not member? nogood no-goods) [
    set no-goods fput nogood no-goods
    ;; for each new neighbor
    foreach (filter [
      [a] ->
      not member? (node first a) naybors ] nogood) [
      [b] ->
      let new-naybor turtle (first b)
      set naybors fput new-naybor naybors
      table:put local-view (first b) (last b)
      let message (list "new-neighbor" who)
      ask new-naybor [
        set message-queue lput message message-queue
      ]
    ]
    foreach naybors [
      [a] ->
      let w ([who] of a)
      if (w > who) and (not member? a lower-naybors) [
      
        set lower-naybors fput a lower-naybors
      ]
      ]
    
    check-local-view
  ]
  
end

; обробка повідомлень додати нового сусіда
to handle-add-neighbor [someone]
 if (not (member? (turtle someone) naybors)) [
    set naybors fput turtle someone naybors
    foreach naybors [
      [a] ->
      let w ([who] of a)
      if (w > who) [
         if (w > who) and (not member? a lower-naybors) [
        set lower-naybors fput a lower-naybors
         ]
      ]
    ]
   let message (list "ok" (list who color))
    ask node someone [
      set message-queue lput message message-queue
    ]
  ]
 
end

; перевірка сумісності свого кольору множині поточних nogoods
to check-local-view
  if not can-i-be? color [
   
     let try-these filter [ [a] ->
      not (a = color) ] colors
    let can-be-something-else false
    while [not empty? try-these] [
      let try-this first try-these
      set try-these but-first try-these

      if can-i-be? try-this [
        set try-these [] ;; break loop
        set color try-this
        set can-be-something-else true
        send-out-new-value

      ]
    ]
    if not can-be-something-else [
      backtrack
      
    ]
  ]
    
end


to-report can-i-be? [val]
 
  table:put local-view who val
  foreach no-goods [
    [a] ->
    if (violates? local-view a) [
      table:remove local-view who
      report false
    ]
  ]
  table:remove local-view who
  report true
end

;перевірка порушень
to-report violates? [assignments constraint]
  foreach constraint [
    [a] ->
    if not (table:has-key? assignments (first a) and (table:get assignments first a) = (last a)) [report false]
  ]
  report true
end

; процедура відкату 
to backtrack
  let no-good normalize-nogood find-new-nogood
  ifelse(not member? no-good no-goods) [
    if ([] = no-good) [
      show "EMPTY NO-GOOD FOUND - NO SOLUTION"
      stop
    ]
    set no-goods fput no-good no-goods
    
    let index []
    
    foreach no-good [[a] ->
      set index fput (first a) index]
    
    ask (node max index) [
      set message-queue lput (list "nogood" no-good) message-queue
    ]
  ] [ show "NOGOOD"]
 
end

to-report find-new-nogood
  report table:to-list local-view
end

breed [figures figure]
undirected-link-breed [edges edge]

figures-own [domain possible-steps step-performed?]
edges-own [weight]

globals [all-positions x-positions y-positions]

to setup
  clear-all
  reset-ticks
  ask patches[
    set pcolor grey
  ]
  set-positions
  draw-board
  create-figures queens [
    setxy 0 0
    set color white
    set domain all-positions
    set shape "chess queen"
  ]
  create-figures kings [
    setxy 1 0
    set color white
    set domain all-positions
    set shape "chess king"
  ]
  create-figures rooks [
    setxy 2 0
    set color white
    set domain all-positions
    set shape "chess king"
  ]

  create-figures knights [
    setxy 3 0
    set color white
    set domain all-positions
    set shape "chess knight"
  ]
   create-figures w-bishops [
    setxy 4 0
    set color white
    set domain all-positions
    set shape "chess bishop"
  ]
   create-figures b-bishops [
    setxy 5 0
    set color white
    set domain all-positions
    set shape "chess bishop"
  ]
  

  ask figures [
    create-edges-with other figures
  ]
  ask edges [
    hide-link
    set weight 1
  ]
  ask figures [
    set label who
  ]

end

to set-positions
  set all-positions []
  set x-positions n-values max-x [[i] -> (i + 1)]
  set y-positions n-values max-y [[i] -> (i + 1)]

  foreach x-positions [
    [i] ->
    foreach y-positions [
      [j] ->
      set all-positions fput list (i) (j) all-positions
    ]
  ]
end

to draw-board
  foreach all-positions [
    [i] ->
    let x item 0 i
    let y item 1 i
    ask patch x y [
      ifelse (((x mod 2) = 0) xor ((y mod 2) = 0)) [
        set pcolor 8
      ][
      set pcolor brown
      ]
    ]
  ]

end

to assign-figures
  ask figures [
    let assignment one-of domain
    while [count turtles-on patch (item 0 assignment) (item 1 assignment) >= 1]
    [
       set assignment one-of domain
    ]
    move-to-cell assignment
  ]
end

to move-to-cell [a]
  setxy (item 0 a) (item 1 a)
 
end