Pages

Sunday, March 11, 2012

Steels's Mars Rover in NetLogo

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:

  1. If detect an obstacle, then change direction.
  2. If carrying a sample and at the base, then drop sample.
  3. If carrying a sample and not at the base, then travel up gradient.
  4. If detect a sample, then pick it up.
  5. If true, then move randomly.

For the implementation details, see the code at the end of this post.

How To Use It

  1. Set the number of rocks using the density slider (sets the probability that a patch will have a rock).
  2. Set the number of agents using the agents slider.
  3. Click setup.
  4. Click go.
  5. 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

Alt Graph of Ticks vs. Rock Density(%)

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.

Alt Graph of Ticks vs. Agents

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