Herding Agents

Published February 26, 2018

Key:

  • Sheep are represented by smaller triangles.
  • Herding Dog is represented by the larger triangle.
  • Border fences are represented by white lines. The sheep avoid crossing this border. The dog does not.
  • The red circle represents the center of mass of the flock of sheep. It is calculated by averaging each sheep’s position.
  • The blue circle represents the dog’s target for the sheep. When the center of mass of the flock reaches this target, the dog is given a new target.

Live demo here / code here

Autonomous Agents

Autonomous agents are a way of modeling behaviors and systems by giving simple independent ‘creatures’ (known as agents) a set of rules by which to govern their movements and actions. An agent could have a single behavior: seek shelter. Or an agent could have a set of multiple behaviors: seek shelter, and avoid predators. What is particularly interesting about autonomous agents is the possibility of emergent group behaviors – behaviors that are never explicitly dictated, but result from the interaction of individual agents with a particular set of behaviors.

What follows is my attempt to model an emergent “herding” behavior between multiple types of autonomous agents with complementary behaviors: a flock of sheep and a herding dog. This is based in very large part on a herding algorithm developed at the Royal Society which can be found here(1). This team behind this article focussed in part on creating a herding simulation which avoided ‘hard-coding’ behaviors into the dog. Rather than specifically writing the back-and-forth motion of a herding dog behind a flock (which other efforts to create herding behaviors had done), for instance, they wrote a set of rules through which that behavior emerged. Also, as part of their effort to create a real-world baseline model, they attached GPS tracking backpacks to a flock of sheep and a herding dog. Very cool.

Understanding Herding Behavior

As you might imagine if you have ever seen (a video of) sheep herding before, the sheep avoid the herding dog as the herding dog tries to move the flock toward their destination target. In order to simulate this, however, we need to imagine the very specific rules that govern each agents’ actions. When do the sheep move and in which direction? When do they graze? When does the dog collect stray sheep and when does it drive the flock as a whole? The algorithm described in the article linked above lays out these rules of interaction in great detail. What follows is my summary of these rules for the sheep and herding dog agents:

Sheep Agent Rules:

  • If it is too close to other sheep in the flock, a sheep will move away from them.
  • If the herding dog is too close, a sheep will move towards the center of its neighbors to seek protection, and move away from the herding dog.

Herding Agent Rules:

  • If any sheep have strayed from the center of the pack, the herding agent will drive that sheep back towards the center of the flock.
  • If no sheep have strayed, the herding agent will try to drive the flock towards its destination.

Tuning the Simulation

In code, these rules become much more specific. As I was working through this project, however, I found it more helpful to compare my simulation to the real world – and how I understand sheep and dogs to behave – rather than returning to the specifics of the algorithm. By conceptualizing these rules as behaviors (as opposed to their underlying logical rules), identifying aberrant behaviors became simple. Sheep do not behave like X. Dogs do not behave like Y. The task of ‘tuning’ this algorithm – adjusting the weighting of the various forces acting on sheep and dog – became an iterative process. Adjust, watch, and compare to real world sheep and dogs.

For instance, the first ‘generation’ of this tuning produced an effective, if entirely over-excitable herding dog, and a set of sheep which barreled over one another to avoid this dog. As a herding simulation, it was effective, but as a simulation of sheep and dog, it was not:

Fittingly, this reminded me a great deal of this video of a young border collie being introduced to a herd of sheep for the first time:

Next Steps

After many such ‘generations’ of tuning and watching this simulation, I arrived at the simulation seen above. The sheep are somewhat more tame, the dog is somewhat reticent to run directly toward the center of the flock, and the herding remains reasonably effective. That said, there are still many improvements to be made to this simulation. What follows is a list of changes I would make to the algorithm:

  • The sheep agents could graze more convincingly if they exhibited a more advanced wandering behavior, rather than simply experiencing random urges to move in a random direction.

  • Currently, the dog has no sense of the shape of the flock. It knows the center of gravity of the flock (an average of the position of each sheep), and draws a perimeter around that center at a certain radius. When sheep stray beyond that radius, it seeks to collect them. Because of this, the dog will occasionally collect sheep which stay outside of the circle, even if they are still moving toward the correct target. A ‘smarter’ dog agent would understand the shape of the flock, and dynamically adjust its understanding of whether a sheep has strayed.

  • Occasionally, the dog will split the flock in half by running through the center in order to get to the other side. No real world herding dog would be guilty of this behavior. As a workaround for this problem, I made the dog slightly repulsed by the center of the flock. In future iterations, I would like the dog to actively avoid the flock (obstacle avoidance), rather than be repulsed by the flock. Ideally, and if the above improvement were made, the dog would constantly update the shape of its flock model, to avoid ever moving between a sheep and the center of the flock. If this were implemented, I believe the dog could define ‘straying’ behavior in a much more compelling and accurate way: if the volume of a bounding shape around a flock of size X becomes larger than f(X) = Y, collect those sheep furthest from the center

  • Add more dogs! Herding dogs often work in teams, and implementing a simple way for the dogs to be aware of one another and work together would allow larger flocks and more complex simulations.

(1) Strömbom, Daniel et al. “Solving the Shepherding Problem: Heuristics for Herding Autonomous, Interacting Agents.” Journal of the Royal Society Interface 11.100 (2014): 20140719. PMC. Web. 27 Feb. 2018.