; Asynchronous Backtracking Algorithm for the random binary CSPs
; by Ionel Muscalagiu ( mionel@fih.utt.ro )
; Jose M. Vidal and Hong Jiang
;The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
;where n is the number of variables, m is the uniform domain size, p1 is the portion of
;the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value
;pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought
;of as the density of the constraint graph, and p2 as the tightness of constraints.
;In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
;selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
;
breeds [nodes edges weights]
;nodes = agents
;each undirected edge goes from a to b
edges-own [a b weight-a weight-b wa-turtle wb-turtle number-of-edges ]
;links list of neighbor nodes (but links is a list of the 'who' of all nodes that have a constraint with me)
;the-neighbors the same but as an agentset
;neighbors-list is a list of the initial neighbors nodes
;done boolean that says if node (agent) is done or not
;message-queue contains the incoming messages. We take new ones out from the head.
;current-view is a list indexed by node number [[color0 priority0] [color1 priority1] ...] colorl = -1 and priority = -1 if unknown.
;nogoods is a list of inconsistent colors [color0 color11 ... ]
;messages-recieved is the number of messages this vertice has received.
;nogood_list is the list of nogood received
;nogood_sent_list is the list of nogood sent
nodes-own [links neighbors-list the-neighbors message-queue priority nogood_list nogood_sent_list
extendend-neighbors colorn current-view nogoods messages-received_ok messages-received_nogood nr_constraintc
AgentC_Cost agent_nogood messages-received messages-received_nogoodold FlagList Forbidden_Pairs]
globals [x-max y-max diam friction tot-edges filename tick stoptick init-power-edges domain-color-list
total-conflict-pairs no-more-messages done tmp nr_cicluri nn]
to setup-globals ; separate procedure for setting globals
locals [i max-edges]
set diam 4
set tick 0
set stoptick -2 ; set to some number to stop, generally for image collections
set x-max screen-edge-x - (diam / 2) + 1; 0.5
set y-max screen-edge-y - (diam / 2) + 1; 0.5
set filename "" ; change to collect images (or just use command center after setup)
set-default-shape nodes "circle"
set-default-shape edges "line"
set friction .25
set init-power-edges 2
set max-edges round (number-of-variables * (number-of-variables - 1 ) / 2)
set tot-edges round (max-edges * p1-network-connectivity)
set domain-color-list []
set i 0
while [i < number-of-values][
set domain-color-list lput item i [15 105 64 125 45 85 35 55 5] domain-color-list
set i i + 1
]
end
to setup ; Setup the model for a run, build a graph.
ca
file-close
clear-output
set-default-shape weights "none"
setup-globals
setup-patches
setup-turtles
setup-random-binary-problems
;LoadGrafFisier
;WriteGrafFisier
end
to setup-patches
ask patches [set pcolor white]
end
to setup-turtles
cct-nodes number-of-variables [
set color random-one-of domain-color-list
;set color item (random-int-or-float number-of-values) domain
set colorn position color domain-color-list
set label-color black
set size diam
set links []
set label who
setxy random-float (x-max) * (2 * (random 2) - 1)
random-float (y-max) * (2 * (random 2) - 1)
]
end
to setup-random-binary-problems ; Build a random binary CSP
locals [t t1 g p1 p2 el i pos temp]
set g (list turtle 1)
while [length g < number-of-variables] [
set t1 random-one-of nodes with [not member? self g]
set t item random length g g
ask t1 [connect-edge t]
set g subgraph turtle 1
]
while [count edges < tot-edges] [
set t random-one-of nodes
set t1 random-one-of nodes with [self != t and not member? t links]
if t1 != nobody [ask t1 [connect-edge t]]
]
ask nodes [
set the-neighbors nodes with [member? self (links-of myself)]
set neighbors-list []
ask the-neighbors
[
set neighbors-list lput who-of myself neighbors-list
set neighbors-list sort neighbors-list
]
]
set total-conflict-pairs round(p2-constraint-tightness * (number-of-values + 1 ) * (number-of-values + 1 ))
show "Total-conflict-pairs " + total-conflict-pairs
ask nodes
[
without-interruption[
set Forbidden_Pairs get-list length(neighbors-list) []
set pos 0
foreach neighbors-list
[
if ? < who
[ set i 0
while [i < total-conflict-pairs]
[
set p1 random-int-or-float number-of-values
set p2 random-int-or-float number-of-values
set el list p1 p2
if not member? el item pos Forbidden_Pairs
[
set temp lput el (item pos Forbidden_Pairs )
set Forbidden_Pairs replace-item pos Forbidden_Pairs temp
set i i + 1 ]
]
show item pos Forbidden_Pairs + " confict with the agent " + ?
set pos pos + 1
]
]
]
]
end
to-report subgraph [n] ; report the complete connected subgraph containing n1
locals[stack graph]
set graph (list n)
set stack (list n)
while [length stack > 0] [
foreach links-of first stack [
if not member? ? graph [
set graph lput ? graph
set stack lput ? stack
]
]
set stack but-first stack
]
report graph
end
; The run procedure which makes the model take one step.
; It moves the nodes so that we get a better layout. You can also click on a node and move it by hand.
to go
locals[t]
if filename = 0 [setup] ; an attempt to work even tho user forgets setup
if stoptick = -1 [stop]
no-display
step
display
if mouse-down? [
set t closest-xy mouse-xcor mouse-ycor nodes ;
while [mouse-down?] [
ask t [setxy mouse-xcor mouse-ycor]
no-display
ask edges with [a = t or b = t][adjust-edge]
step
display
]
]
check-movie
if stoptick = tick [stop]
end
to step ; Adjust the edges and nodes for one step of the model
locals[delta]
without-interruption [
ask edges [
set delta (spring-force * (size - spring-length)) / 2.0
ask a [set heading towards-nowrap b-of myself jump-nowrap delta]
ask b [set heading towards-nowrap a-of myself jump-nowrap delta]
]
ask nodes [
ask nodes with [self != myself] [
set delta distance-nowrap myself
set delta mutual-repulsion / (delta * delta)
set heading towards-nowrap myself
jump-nowrap (- delta)
]
]
ask edges [adjust-edge]
]
end
to check-movie ; if filename is non-empty, make another snapshot
if length filename > 0 [
export-view filename + substring "0000" (int log tick 10) 3 + tick + ".png"
]
end
;;;; Edge & Node utilities
to connect-edge [other-node] ; node proc: attach an edge between self and other
hatch 1 [
set breed edges
set a myself
set b other-node
set weight-a 1
set weight-b 1
hatch 1 [
set breed weights
set (wa-turtle-of myself) self
set label (weight-a-of myself)]
hatch 1 [
set breed weights
set (wb-turtle-of myself) self
set label (weight-b-of myself)]
ask a [set links lput b-of myself links]
ask b [set links lput a-of myself links]
set color black
set label no-label
adjust-edge
]
end
to-report sign [num]
ifelse num < 0 [report -1][report 1]
end
to-report closest-xy [x y agent-set] ; Return closest agent to x, y
report min-one-of agent-set [distancexy-nowrap x y]
end
to jump-nowrap [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
locals [x y]
set x xcor + dist * dx
set y ycor + dist * dy
if (abs x) > x-max [set x sign x * (x-max - (1 - friction) * ((abs x) - x-max))]
if (abs y) > y-max [set y sign y * (y-max - (1 - friction) * ((abs y) - y-max))]
setxy x y
end
to adjust-edge ; edge proc: reattach to a & b nodes
setxy xcor-of b ycor-of b
set heading towards-nowrap a
fd diam / 2 + 1
set (xcor-of wb-turtle) xcor
set (ycor-of wb-turtle) ycor
setxy xcor-of a ycor-of a
set size distance-nowrap b - diam
set heading towards-nowrap b
fd diam / 2 + 1
set (xcor-of wa-turtle) xcor
set (ycor-of wa-turtle) ycor
setxy xcor-of a ycor-of a
jump (size / 2) + (diam / 2)
end
to-report make-list [num element]
locals [i result]
set i 0
set result []
while [i < num] [
set result lput element result
set i i + 1
]
report result
end
to-report copy-list [l]
locals [r]
set r []
foreach l [
set r lput ? r]
report r
end
; n is length of list
; el is the element
to-report get-list [n el]
locals [i lst]
set i 0
set lst []
while [i < n] [
set lst fput el lst
set i i + 1]
report lst
end
;;;;;;;;;;
;;;Asynchrounous Backtracking algorithm
;Initialize the Asynchrounous Backtracking algorithm
to setup-ABT
ask nodes [
set messages-received 0
set messages-received_ok 0
set messages-received_nogood 0
set messages-received_nogoodold 0
set nr_constraintc 0
set AgentC_Cost 0
set current-view get-list number-of-variables -1
set nogoods get-list number-of-variables 0
set message-queue []
set-current-plot "Messages"
create-temporary-plot-pen "n-" + who
set-plot-pen-color (who * 10 + 5) mod 140
]
ask nodes [
initialize
set extendend-neighbors neighbors-list
]
set done false
set nr_cicluri 0
WriteColors
end
to WriteColors
file-close
if (file-exists? "culorit.txt" )
[file-delete "culorit.txt"]
file-open "culorit.txt"
ask nodes[
;ask the-neighbors
; [
file-print who +" " + colorn
; ]
]
file-close
end
to WriteSolution
show "Solution "
ask nodes [
write colorn + " "
]
end
to-report verifica_solutia
locals [good i]
set good true
;without-interruption[
ask nodes
[
without-interruption[
foreach neighbors-list
[
if (? < who and Conflict who ? colorn colorn-of turtle ? )
[
set good false
show "Conflict " + who + " cu " + ?
]
]
]
]
if good
[show "Good solution!"]
report good
end
to go-ABT
set no-more-messages true
set nr_cicluri nr_cicluri + 1
ask nodes [
if (not empty? message-queue)[
set no-more-messages false]]
if (no-more-messages) [
ifelse verifica_solutia
[WriteSolution]
[WriteSolution]
stop
]
if (done)
[show "No solution"
stop]
ask nodes [handle-message]
ask nodes [
set-current-plot "Messages"
create-temporary-plot-pen "q" + who
plot messages-received_nogood + messages-received_ok
]
end
to initialize
locals [msg]
foreach neighbors-list
[
set msg (list "ok" (list who colorn) AgentC_Cost)
ask turtles with [who = ? ]
[receive-message msg]
]
end
;get the next message from message-queue
to-report retrieve-message
locals [msg]
without-interruption [
set msg first message-queue
set message-queue butfirst message-queue]
report msg
end
to receive-message [msg]
without-interruption [
set message-queue lput msg message-queue]
end
to send-message [receiver msg]
without-interruption [ set message-queue-of (turtle receiver) lput msg (message-queue-of (turtle receiver))
]
end
;Get the msg and dispatch it to the appropiate function
to handle-message
locals [msg xj dj sender msgnog SenderC_Cost]
if (empty? message-queue) [stop]
set msg retrieve-message
;set messages-received messages-received + 1
if (first msg = "ok")
[
set xj item 0 (item 1 msg)
set dj item 1 (item 1 msg)
set messages-received_ok messages-received_ok + 1
set SenderC_Cost item 2 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
ok xj dj
]
if (first msg = "nogood")
[
set SenderC_Cost item 3 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
set sender item 1 msg
set msgnog item 2 msg
nogood sender msgnog
set messages-received_nogood messages-received_nogood + 1
]
if (first msg = "addl")
[
SetLink item 1 msg
]
end
; this is the Ok? procedure in the paper where Qj = Xj and Vj = dj
to ok [Qj Vj ]
set current-view replace-item Qj current-view Vj
check-agent-view
end
to-report agents-in-context [cont]
locals [i res]
set i 0
set res []
while [i < number-of-variables][
if (item i cont != -1)
[
set res lput i res
]
set i i + 1
]
report res
end
to-report locate-who-nogood [ n ]
locals [whon gasit lagent]
set lagent agents-in-context current-view
set whon n - 1
set gasit false
while [not gasit ]
[
ifelse ( member? whon lagent )
[set gasit true]
[set whon whon - 1]
]
report whon
end
to SetLink [ Sender]
locals [msg]
if not member? Sender extendend-neighbors
[
set extendend-neighbors lput Sender extendend-neighbors
set extendend-neighbors sort extendend-neighbors
set msg (list "ok" (list who colorn) AgentC_Cost)
send-message Sender msg
]
end
to-report Is_oldnogood [beef whosend]
locals [i]
set i 0
while [i < who ]
[
if ( (item i beef) != (item i current-view) and (item i beef) != -1 and (item i current-view) != -1 and member? i extendend-neighbors)
[report true]
set i (i + 1)
]
if ((item who beef) != (colorn) and (item who beef) != -1)
[report true]
report false
end
; this is the nogood procedure from the paper
to nogood [whosend beef ]
locals [ i j msg whonog oldvalue k]
;does this nogood apply to my current view?
if (Is_oldnogood beef whosend )
[
if (item who beef = colorn) ;and (member? whosend extendend-neighbors)
[
set msg (list "ok" (list who colorn) AgentC_Cost)
send-message whosend msg
]
stop
]
;mark current position as no good
;set nogoods replace-item colorn nogoods 1
set i 0
while [i < who ]
[
if (not member? i extendend-neighbors) and ((item i beef ) != -1)
[
set msg (list "addl" who )
send-message i msg
set current-view (replace-item i current-view (item i beef))
set extendend-neighbors lput i extendend-neighbors
set extendend-neighbors sort extendend-neighbors
set extendend-neighbors remove-duplicates extendend-neighbors
]
set i (i + 1)
]
set oldvalue colorn
set nogoods replace-item colorn nogoods 1
Check-agent-view1
if ( oldvalue = colorn )
[
set msg (list "ok" (list who colorn) AgentC_Cost)
send-message whosend msg
]
end
to-report Conflict [who1 who2 value1 value2]
locals [result el pos element]
set result false
if (neighbors? who1 who2)
[
set nr_constraintc nr_constraintc + 1
set AgentC_Cost AgentC_Cost + 1
set el list value2 value1
set pos position who2 neighbors-list
;show "Pozitia " + pos
;show item pos Forbidden_Pairs
set element item pos Forbidden_Pairs
if (member? el element )
[set result true]
]
report result
end
to check-agent-view
locals [ i j msg whonog consistent k col]
set i 0
set consistent true
while [ i < who ] ;for each vertices
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
if Conflict who i colorn item i current-view
[ set consistent false
]
set i i + 1
]
UpdateNogood
if ( not consistent )
[
set col 0
set k 0
while [ col < number-of-values and k = 0]
[
if ( item Col nogoods = 0 )
[
set i 0
set consistent true
while [ i < who ] ;for each vertices
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
if (Conflict who i col item i current-view)
[ set consistent false]
set i i + 1
]
if consistent
[ set colorn col
;setxy (colorn - screen-edge-x) (screen-edge-y - who)
set color item colorn domain-color-list
set msg (list "ok" (list who colorn) AgentC_Cost)
foreach extendend-neighbors
[
if (? > who )
[send-message ? msg]
]
set k 1
]
; [ set nogoods replace-item col nogoods 1]
]
set col (col + 1)
]
if (k = 0 )
[BackTrack]
]
end
to check-agent-view1
locals [ i j msg whonog consistent k col]
set col 0
set k 0
while [ col < number-of-values and k = 0]
[
if ( item Col nogoods = 0 )
[
set i 0
set consistent true
while [ i < who ] ;for each vertices
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
if (Conflict who i col item i current-view)
[ set consistent false]
set i i + 1
]
if consistent
[ set colorn col
;setxy (colorn - screen-edge-x) (screen-edge-y - who)
set color item colorn domain-color-list
set msg (list "ok" (list who colorn) AgentC_Cost)
foreach extendend-neighbors
[
if (? > who )
[send-message ? msg]
]
set k 1
]
]
set col (col + 1)
]
if (k = 0 )
[BackTrack ]
end
to BackTrack
locals [msg whonog]
if (who = 0);no consistent colors and I'm highest priority
[
show "No solution"
set done true
stop
]
set msg (list "nogood" who current-view AgentC_Cost )
set whonog locate-who-nogood who
send-message whonog msg
set current-view (replace-item whonog current-view -1)
UpdateNogood
check-agent-view1
end
to UpdateNogood
locals [i j]
set nogoods get-list number-of-values 0
set i 0
while [ i < who ] ;for each vertices
[
set j 0
while [ j < number-of-values ] ;for each color
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
if (Conflict who i j item i current-view) and (item i current-view != -1 )
[set nogoods replace-item j nogoods 1]
set j (j + 1)]
set i (i + 1)
]
end
to-report neighbors? [v1 v2]
report (member? v2 neighbors-list-of turtle v1) or (member? v1 neighbors-list-of turtle v2)
end
@#$#@#$#@
GRAPHICS-WINDOW
209
10
697
430
21
17
11.12
1
10
1
1
1
0
1
1
1
CC-WINDOW
5
469
1005
564
Command Center
0
BUTTON
1
11
56
44
NIL
setup
NIL
1
T
OBSERVER
T
NIL
BUTTON
62
12
136
45
Layout
go
T
1
T
OBSERVER
NIL
NIL
SLIDER
6
50
193
83
number-of-variables
number-of-variables
2
30
12
1
1
NIL
SLIDER
5
223
97
256
spring-force
spring-force
0
2
0.2
0.1
1
NIL
SLIDER
99
223
191
256
spring-length
spring-length
0
10
8.5
0.25
1
NIL
SLIDER
7
259
190
292
mutual-repulsion
mutual-repulsion
0
10
4.25
0.25
1
NIL
SLIDER
4
125
192
158
p1-network-connectivity
p1-network-connectivity
0.1
1
0.3
0.1
1
NIL
MONITOR
705
10
762
59
NIL
tick
3
1
MONITOR
767
10
824
59
edges
count edges
3
1
BUTTON
704
60
861
93
setup-ABT
setup-ABT
NIL
1
T
OBSERVER
T
NIL
BUTTON
704
94
836
127
go ABT
go-ABT
NIL
1
T
OBSERVER
T
NIL
BUTTON
704
128
836
161
go ABT
go-ABT
T
1
T
OBSERVER
T
NIL
TEXTBOX
716
175
862
286
1- setup\n2- Layout until it's pretty\n3- setup-ABT \n4- go-ABT
SLIDER
5
87
192
120
number-of-values
number-of-values
0
10
6
1
1
NIL
MONITOR
827
10
915
59
Msgs nogood
sum (values-from nodes [messages-received_nogood])
3
1
MONITOR
920
10
979
59
Msgs ok
sum (values-from nodes [messages-received_ok])
3
1
MONITOR
863
61
920
110
Cycles
nr_cicluri
3
1
MONITOR
842
110
955
159
Constraint checks
sum (values-from nodes [nr_constraintc])
3
1
MONITOR
834
165
985
214
Concurrent constraint checks
max (values-from nodes [AgentC_Cost])
3
1
SLIDER
5
164
191
197
p2-constraint-tightness
p2-constraint-tightness
0.1
1
0.3
0.1
1
NIL
PLOT
1
297
191
432
Messages
NIL
NIL
0.0
100.0
0.0
10.0
true
false
TEXTBOX
705
242
996
455
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),\nwhere:\n- n is the number of variables;\n- m is the uniform domain size; \n- p1 is the portion of the n * (n - 1) /2 possible\n constraints in the graph; \n- p2 is the portion of the m*m value pairs in each constraint that are disallowed by the constraint. \n\nThat is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.
@#$#@#$#@
Title: Random binary CSPs using Asynchronous Backtracking
Author: Ionel Muscalagiu, Jose M. Vidal and Hong Jiang
Description:
This is the implementation of the Asynchronous Backtracking for the random binary problems. We generate and solve the random binary problem using the Asynchronous Backtracking algorithm from
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
where n is the number of variables, m is the uniform domain size, p1 is the portion of
the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.
In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250
circle
false
0
Circle -7500403 true true 35 35 230
line
true
0
Line -7500403 true 150 0 150 301
none
true
0
@#$#@#$#@
NetLogo 3.0
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@