What Is It?
This model implements Luc Steels’s Mars Rover as described on pages 87-90 of An Introduction to MultiAgent Systems by Michael Wooldridge. The premise is that we are exploring mars and want to collect rock samples, but don't have any maps of the planet. The only directional aid that agents get is a signal being broadcast by their home base. The model has been simplified by placing rocks randomly rather than in clusters and by not including obstacles. However, the model still is useful for showing how the subsumption architecture works. The agents are able to gather all the rocks on the planet while only following a simple set of rules.
How It Works
The surface of Mars is brown. Rocks are yellow, and little red things go around collecting rocks following Steels’s rules (though since there are no obstacles they don’t avoid any). The rules are as follows:
- If detect an obstacle, then change direction.
- If carrying a sample and at the base, then drop sample.
- If carrying a sample and not at the base, then travel up gradient.
- If detect a sample, then pick it up.
- If true, then move randomly.
For the implementation details, see the code at the end of this post.
How To Use It
- Set the number of rocks using the density slider (sets the probability that a patch will have a rock).
- Set the number of agents using the agents slider.
- Click setup.
- Click go.
- Enjoy.
Note: You probably want to set the speed somewhat less than normal speed if you want to see the agents do anything.
Things To Notice
- The agents will turn yellow when they are carrying a rock.
- There is a very clear pattern that emerges as the agents collect rocks.
Things To Try
Try varying the number of rocks and agents that are used in the model. Notice how these variables affect the ticks count.
Statistics
Having tried the Things To Try, the following results were obtained:
Trial Rock_Density(%) Agents Ticks World_Width World_Height
-----------------------------------------------------------
1 0 1 0 33 33
2 10 1 33875 33 33
3 10 1 35972 33 33
4 10 1 27755 33 33
5 10 1 25424 33 33
6 10 1 29035 33 33
7 10 1 30202 33 33
8 10 1 26603 33 33
9 10 1 36722 33 33
10 10 1 29996 33 33
11 10 1 40116 33 33
12 25 1 75699 33 33
13 25 1 86087 33 33
14 25 1 69149 33 33
15 25 1 95385 33 33
16 25 1 72853 33 33
17 25 1 76499 33 33
18 25 1 66466 33 33
19 25 1 80146 33 33
20 25 1 65707 33 33
21 25 1 74179 33 33
22 50 1 156396 33 33
23 50 1 134617 33 33
24 50 1 143432 33 33
25 50 1 152254 33 33
26 50 1 128466 33 33
27 50 1 146120 33 33
28 50 1 141298 33 33
29 50 1 147672 33 33
30 50 1 132458 33 33
31 50 1 149841 33 33
32 75 1 208558 33 33
33 75 1 215217 33 33
34 75 1 216132 33 33
35 75 1 216998 33 33
36 75 1 204697 33 33
37 75 1 197894 33 33
38 75 1 231247 33 33
39 75 1 204660 33 33
40 75 1 211460 33 33
41 75 1 210881 33 33
42 100 1 257532 33 33
43 100 1 270158 33 33
44 100 1 272040 33 33
45 100 1 268110 33 33
46 100 1 280271 33 33
47 100 1 271552 33 33
48 100 1 286124 33 33
49 100 1 282930 33 33
50 100 1 273898 33 33
51 100 1 301218 33 33
52 10 2 16641 33 33
53 10 2 24731 33 33
54 10 2 17003 33 33
55 10 2 13623 33 33
56 10 2 14998 33 33
57 10 2 22293 33 33
58 10 2 20632 33 33
59 10 2 14791 33 33
60 10 2 15987 33 33
61 10 2 17962 33 33
62 25 2 35413 33 33
63 25 2 44229 33 33
64 25 2 34760 33 33
65 25 2 36499 33 33
66 25 2 40602 33 33
67 25 2 33971 33 33
68 25 2 36735 33 33
69 25 2 30398 33 33
70 25 2 37354 33 33
71 25 2 34742 33 33
72 50 2 76617 33 33
73 50 2 77408 33 33
74 50 2 69923 33 33
75 50 2 68173 33 33
76 50 2 75557 33 33
77 50 2 72323 33 33
78 50 2 69636 33 33
79 50 2 69644 33 33
80 50 2 67176 33 33
81 50 2 76639 33 33
82 75 2 108909 33 33
83 75 2 100665 33 33
84 75 2 103948 33 33
85 75 2 97966 33 33
86 75 2 97379 33 33
87 75 2 103539 33 33
88 75 2 105896 33 33
89 75 2 96591 33 33
90 75 2 97260 33 33
91 75 2 102854 33 33
92 100 2 131871 33 33
93 100 2 136403 33 33
94 100 2 132495 33 33
95 100 2 130203 33 33
96 100 2 130112 33 33
97 100 2 133642 33 33
98 100 2 137357 33 33
99 100 2 138744 33 33
100 100 2 136951 33 33
101 100 2 136948 33 33
102 10 5 6017 33 33
103 10 5 7242 33 33
104 10 5 5505 33 33
105 10 5 6119 33 33
106 10 5 9012 33 33
107 10 5 5738 33 33
108 10 5 6278 33 33
109 10 5 5369 33 33
110 10 5 6804 33 33
111 10 5 6714 33 33
112 25 5 13315 33 33
113 25 5 14039 33 33
114 25 5 16385 33 33
115 25 5 15419 33 33
116 25 5 14675 33 33
117 25 5 15137 33 33
118 25 5 16924 33 33
119 25 5 14248 33 33
120 25 5 14413 33 33
121 25 5 13090 33 33
122 50 5 29843 33 33
123 50 5 30464 33 33
124 50 5 28481 33 33
125 50 5 27702 33 33
126 50 5 25994 33 33
127 50 5 33664 33 33
128 50 5 28645 33 33
129 50 5 26338 33 33
130 50 5 30487 33 33
131 50 5 28254 33 33
132 75 5 41359 33 33
133 75 5 44621 33 33
134 75 5 43040 33 33
135 75 5 42194 33 33
136 75 5 38586 33 33
137 75 5 40332 33 33
138 75 5 43612 33 33
139 75 5 37622 33 33
140 75 5 41940 33 33
141 75 5 41180 33 33
142 100 5 54824 33 33
143 100 5 52535 33 33
144 100 5 54967 33 33
145 100 5 55521 33 33
146 100 5 54105 33 33
147 100 5 54513 33 33
148 100 5 51928 33 33
149 100 5 56092 33 33
150 100 5 52144 33 33
151 100 5 58660 33 33
152 10 10 3220 33 33
153 10 10 2873 33 33
154 10 10 3533 33 33
155 10 10 3326 33 33
156 10 10 4445 33 33
157 10 10 3514 33 33
158 10 10 3689 33 33
159 10 10 3407 33 33
160 10 10 3567 33 33
161 10 10 3434 33 33
162 25 10 7445 33 33
163 25 10 6448 33 33
164 25 10 8841 33 33
165 25 10 6634 33 33
166 25 10 8154 33 33
167 25 10 7579 33 33
168 25 10 7202 33 33
169 25 10 7037 33 33
170 25 10 8039 33 33
171 25 10 6803 33 33
172 50 10 15104 33 33
173 50 10 15550 33 33
174 50 10 15261 33 33
175 50 10 14024 33 33
176 50 10 13168 33 33
177 50 10 14470 33 33
178 50 10 14929 33 33
179 50 10 14932 33 33
180 50 10 12942 33 33
181 50 10 13928 33 33
182 75 10 20660 33 33
183 75 10 21319 33 33
184 75 10 22171 33 33
185 75 10 21382 33 33
186 75 10 20810 33 33
187 75 10 19754 33 33
188 75 10 19541 33 33
189 75 10 21344 33 33
190 75 10 22509 33 33
191 75 10 20908 33 33
192 100 10 28449 33 33
193 100 10 28210 33 33
194 100 10 27605 33 33
195 100 10 28082 33 33
196 100 10 27982 33 33
197 100 10 29248 33 33
198 100 10 27699 33 33
199 100 10 27550 33 33
200 100 10 28275 33 33
201 100 10 27917 33 33
202 10 25 1273 33 33
203 10 25 1808 33 33
204 10 25 1405 33 33
205 10 25 1383 33 33
206 10 25 1483 33 33
207 10 25 1058 33 33
208 10 25 1186 33 33
209 10 25 1428 33 33
210 10 25 1513 33 33
211 10 25 1508 33 33
212 25 25 3371 33 33
213 25 25 3470 33 33
214 25 25 2579 33 33
215 25 25 3086 33 33
216 25 25 2826 33 33
217 25 25 3130 33 33
218 25 25 3011 33 33
219 25 25 3384 33 33
220 25 25 3287 33 33
221 25 25 2928 33 33
222 50 25 6051 33 33
223 50 25 5527 33 33
224 50 25 5929 33 33
225 50 25 5870 33 33
226 50 25 5876 33 33
227 50 25 5596 33 33
228 50 25 5830 33 33
229 50 25 5467 33 33
230 50 25 5871 33 33
231 50 25 5494 33 33
232 75 25 8602 33 33
233 75 25 8692 33 33
234 75 25 9311 33 33
235 75 25 7865 33 33
236 75 25 8725 33 33
237 75 25 8387 33 33
238 75 25 8709 33 33
239 75 25 9783 33 33
240 75 25 9245 33 33
241 75 25 8374 33 33
242 100 25 10834 33 33
243 100 25 10655 33 33
244 100 25 11397 33 33
245 100 25 12520 33 33
246 100 25 11549 33 33
247 100 25 11736 33 33
248 100 25 10971 33 33
249 100 25 10774 33 33
250 100 25 11859 33 33
251 100 25 10858 33 33
252 10 50 1041 33 33
253 10 50 861 33 33
254 10 50 917 33 33
255 10 50 611 33 33
256 10 50 870 33 33
257 10 50 1287 33 33
258 10 50 903 33 33
259 10 50 1057 33 33
260 10 50 869 33 33
261 10 50 967 33 33
262 25 50 1893 33 33
263 25 50 1507 33 33
264 25 50 1686 33 33
265 25 50 1592 33 33
266 25 50 2194 33 33
267 25 50 1520 33 33
268 25 50 1352 33 33
269 25 50 1895 33 33
270 25 50 1725 33 33
271 25 50 1586 33 33
272 50 50 2970 33 33
273 50 50 2845 33 33
274 50 50 3515 33 33
275 50 50 2822 33 33
276 50 50 2863 33 33
277 50 50 3219 33 33
278 50 50 3248 33 33
279 50 50 2723 33 33
280 50 50 3404 33 33
281 50 50 3033 33 33
282 75 50 4445 33 33
283 75 50 4506 33 33
284 75 50 4191 33 33
285 75 50 4273 33 33
286 75 50 4111 33 33
287 75 50 4217 33 33
288 75 50 4549 33 33
289 75 50 4291 33 33
290 75 50 4500 33 33
291 75 50 4409 33 33
292 100 50 5472 33 33
293 100 50 6001 33 33
294 100 50 5775 33 33
295 100 50 5336 33 33
296 100 50 5644 33 33
297 100 50 5552 33 33
298 100 50 6051 33 33
299 100 50 5889 33 33
300 100 50 5880 33 33
301 100 50 5729 33 33
Note that this graph plots points that have varying numbers of agents. There are six different agents settings: 1, 2, 5, 10, 25, and 50. Points with the same agents setting appear as vertical clusters. From the graph we can see that there is a direct linear relationship between the time it takes for the model to complete and the rock density.
Points in this graph have varying rock densities which appear as vertical clusters. We can see that as the number of agents increases the time taken to run the model decreases, but the relationship does not look linear. As the number of agents increases the magnitude of the slope decreases. This suggests that one gets diminishing returns for increasing the number of agents used. Also, notice that as the number of agents increases the deviation from the mean within any given cluster decreases.
We would expect that with a large enough number of agents on each round an agent would land on a patch with a rock or get one step closer to a patch with a rock. When agents enter a patch with a rock one of them would pick it up and some other one would continue outward toward whatever rocks remain. Thus the time to collect all of the rocks would be two times the distance to the furthest rock plus two. The plus two is due to the time taken to pick up the rock and to drop it. With small numbers of agents there is a much greater chance that as a whole the agents may not be progressing toward their goal.
Extending The Model
The current model does not include obstacles or obstacle avoidance; however, obstacle avoidance would not be hard to implement. There are two cases to consider when navigating around obstacles: when exploring and when returning a rock to the ship. When exploring, if an obstacle is in front of an agent, the agent can change direction; however, when returning home the agent’s direction is always determined by the signal gradient from the ship. Obstacles are avoided because they hinder the signal and thus would never be uphill along the gradient. Experimenting to see how obstacles affect the time it takes for all of the rocks to be gathered would be interesting.
Also, the current model assumes that all of the rocks are uniformly distributed, but resources are more likely to be clustered. The model could be extended to see how the clustering of resources affects the efficiency with which the rocks are recovered, and other algorithms can be tried in order to optimize for rocks with specific clustering characteristics.
Lastly, the methods used to gather and analyse statistics on the model were rather crude. Some tools and strategies that may help include the R extension, the logging facilities, and scripting runs. A task could be added for doing several runs and plotting the results. Ideally, there should be a framework that indentifies all of the model parameters and automatically runs a battery of simulations that will result in statistically significant data. The framework should then make it easy to view the data in numerous different ways.
Credits and References
The code is based on the description of Luc Steels’s Mars rover model as described in Mike Wooldridge’s book An Introduction to Multiagent Systems (pages 88 and 89).
Code
;; Luc Steels' Mars rover program rendered in Netlogo
;;
;; Simon Parsons
;; October 2011
;;
;; Extended by:
;; David Campbell
;; October 2011
globals [rocks hx hy] ; The number of rocks and spaceship coordinates.
turtles-own [carrying?] ; Whether or not the turle is carrying a rock.
patches-own [signal] ; Strength of the spaceships signal.
;; setup includes coloring the background, choosing which patches have rocks
;; and picking a base/spaceship location.
to setup
reset
paint-background
pick-rocks
land-spaceship
;;ask patches [set pcolor signal] ;; visualize the signal
end
;; Log data from each run to the Command Center so that it may be analysed later.
to log-run
type rock-density type "\t"
type agents type "\t"
type ticks type "\t"
type world-width type "\t"
type world-height type "\t"
type "\n"
end
;; Resetting kills the turtles, sets the rock count to 0, and resets the coordinates
;; of the base.
to reset
reset-ticks
set rocks 0
set hx 0
set hy 0
ask turtles [die]
ask patches [set signal 0]
end
;; The background is brown, to match the martian landscape.
to paint-background
ask patches [set pcolor brown]
end
;; Picking rocks is what patches do, so ask them to do it.
to pick-rocks
ask patches [have-rock?]
end
;; A patch decides randomly if it has a rock (only one per patch).
;; if so, it paints itself yellow and increases the rock count.
to have-rock?
let chance random 100
if (chance < rock-density and not (pcolor = yellow))
[set pcolor yellow
set rocks rocks + 1]
end
;; The location of the base for the Mars rovers is selected randomly.
;; its coordinates are stored in hx and hy.
to land-spaceship
ask one-of patches
[if (pcolor = yellow) [set rocks rocks - 1] ;; The shapeship picks up the rock if there is one below it when landing.
set pcolor black
set hx pxcor
set hy pycor]
ask patches
;; Align the signal values with the size of the world (looks nicer if the signal is visualized).
[set signal (max (list world-width world-height)) - (distancexy hx hy)]
end
;; While there are still rocks to be gathered, keep running.
to go
if-else(rocks > 0)
[run-agents]
[log-run
stop]
;; increment the tick counter to keep track of how many moves the model takes to complete.
tick
end
;; If we don't yet have enough agents, create a new one.
;; Eitehr way, get the agents to do their thing.
to run-agents
if (count turtles < agents)
[create-turtles 1
[set xcor hx
set ycor hy
set color red
set carrying? false]]
ask turtles [follow-rules]
end
to follow-rules
;; If carrying and at base, drop the rock.
ifelse (carrying? and xcor = hx and ycor = hy)
[set rocks rocks - 1
set carrying? false
set color red][
;; Qtherwise, if carrying, follow the signal toward base.
ifelse (carrying?)
[uphill signal][
;; Otherwise, if over a rock, pick it up.
ifelse (pcolor = yellow)
[set carrying? true
set pcolor brown
set color yellow]
;; Otherwise, move randomly.
[right random 360
forward 1]]]
end
No comments:
Post a Comment