Sheep Herding Evan Weatherhead Dept. of Computer Science, Faculty of Science, University of Calgary, 2500 University Drive N.W., Calgary, Alberta, Canada T2N 1N4
[email protected]
Abstract. This project explores how one or more agents can be used to influence the patterns of a larger swarm of agents. To accomplish this, a sheep herding dog agent will interact with some number of sheep to move them throughout a virtual landscape.
1
Introduction
The topic of agents which interact with each other in a decentralized manner to simulate the behaviour of flocks or herds has been an area of active research over the past 25 years. Beyond simply creating visually appealing output, this sort of research can have tangible uses such as the modeling of how to make crowd management more efficient. Human movement patterns are more complex than that of animals, so first learning how to simulate and control these simple minded crowds will set the stage for modeling more complicated ones.
2
Related Work
The website of Craig Reynolds [1] serves as a excellent resource for much of the research done with flocking and swarming agents, which he refers to as boids. The work I have done uses many of the principles he has laid out on how an agent makes movement decisions. A study out of Oxford [2] has also attempted similar work by using physical robots acting on actual animals. In their work they found they could successfully herd a flock of live ducks across a field to a predetermined location using their robotic sheepdog.
3
Methods
The first part of this research was be to create a system with agents that appear to have somewhat reasonable flocking behaviours. I created a simulation where sheep had several states corresponding to what was happening around them, and to alter their movement rule sets based on this state. Additionally I added a dog agent which could be controlled by the user’s mouse. For this project I used NetLogo [3] to simulate the environment. This system has built in support for agents, patches to tell the type of ground the agents are on, and mouse support for controlling the dog agent.
2
Evan Weatherhead
Sheep agents were given three main properties outside of their movement rules which could be altered by the user: population, vision and memory. The population simply controls how many sheep will be in the environment, this number will not change while the simulation is running. The vision of a sheep is the radius in a full circle around the sheep which a given sheep agent can sense either the dog or other sheep. Although this property is called vision in this simulation it really encompasses both the visual and audio perception that a sheep has, as a real sheep have a visual range of about 191 to 306 degrees [4]. Finally the memory of a sheep will determine how long a sheep will continue to behave in a flocking manner after it no longer can see a dog. There are two states a sheep agent can be in, grazing and flocking. Grazing is their initial state, in which they will roam around slowly and will usually not go too far from where they started. Their flocking state is activated by either directly seeing a dog, or seeing a sheep that is already in a flocking state and has not reached their memory limit. In the second case the new sheep will inherit the lowest memory value (time since a dog has been seen) of the sheep around it so when the dog is no longer seen all sheep should stop in roughly the same flock pattern. Based on the rules set out by [1] the remaining configurable parameters will change how a flock behaves. All rules in this system have been implemented by allowing a maximum angle an agent can turn based on the rules, this behaviour is from [5], the original NetLogo flocking model used to base mine off of. Briefly there are three main rules: separation, alignment and cohesion. Separation (Figure 1) will try to keep the agents at least a certain distance away from each other. In this model there is an additional parameter called minimum separation which is how close agents will be before they will start applying the separation rule. The next two parameters, alignment (Figure 2) and cohesion (Figure 3), try to accomplish a similar goal of keeping the flock together. Alignment will try to steer towards the average heading of all agents around it, whereas cohesion will try to steer towards the average position of all agents around it.
Fig. 1. Separation. Adapted from [1].
Sheep Herding
3
Fig. 2. Alignment. Adapted from [1].
Fig. 3. Cohesion. Adapted from [1].
4
Results
There are no direct metrics used to score the worth of any particular configuration of this model. All of the testing has to be done by hand and therefore is biased by human error and judgement. Also, since the goal of the project is itself not well defined I feel there are several configurations which are well within an acceptable range. To help decide if a current configuration was useful or not the field environment had several rings of radius 15, 30 and 60 patches. The simulation would also display the percentage of sheep within each of these rings, and if at any time all sheep were within the smallest ring the simulation would end. By creating this very rough system for evaluation it could quickly be determined if the chosen parameters were largely better or worse than previous ones by determining if it was possible to group all sheep within certain rings. Through my testing I have discovered the following about the parameters in the simulation. The vision field will make sheep very non-responsive when set too low, but when set too high will make the sheep nearly impossible to group together as they will be running away no matter where the dog agent is. By making their memory low the dog agent is basically pushing the sheep around the field until it stops moving at which time the sheep immediately stop as well, and when it is very high the model collapses into a basic flocking model where the sheep flock around for a long time and the dog is no more than a mobile
4
Evan Weatherhead
obstacle. If the minimum separation is low than all of the sheep will stack on top of each other which is not physically realistic, and if this is set high the sheep will stay too far away from each other to be considered a flock. By setting the separation turning low the sheep will again stay fairly tightly packed together as it takes many ticks for their separation rules to be effective, but if it is too high it becomes easy for the flock to lose a member. The alignment and cohesion properties are closely tied to each other and it is hard to evaluate them apart from one another. When they are set to a low value the flock never stays together, it will drift apart very quickly. When these settings are higher the pack comes together too well which makes the separation rule’s affect almost nullified.
5
Summary
The goal of this project was to see if a model which is typically used for the flocking of birds could be used to simulate a flock of sheep instead, and if a separate agent could control the movement of this flock in a predictable manner. Once a stable configuration is set into the simulation I have found the sheep can almost always be herded into the smallest ring, successfully completing the simulation. While I have not found one specific configuration to be better than any others, there appears to be a large variety of settings which leaves the simulation controllable and allows the agents to behave in a slightly different manner. In future work I would like to add the ability to control more than one dog agent to see the effects this may have on the stability of controlling the flock. Also, I would like to add static and dynamic obstacles to the environment to help determine how difficult it would be to navigate around various environments.
References 1. Reynolds, C.W.: Flocks, herds, and schools: A distributed behavioral model. SIGGRAPH (1987) 25–34 2. Cameron, S.: Robot sheepdog project. (http://www.comlab.ox.ac.uk/stephen.cameron/sheepdog/) 3. Wilensky, U.: Netlogo. (http://ccl.northwestern.edu/netlogo/index.shtml) 4. Schoenian, S.: Sheep101. (http://www.sheep101.info/201/behavior.html) 5. Wilensky, U.: Netlogo flocking model. (http://ccl.northwestern.edu/netlogo/models/Flocking)
