This story is over 5 years old.

The Mathematics of Herding Sheep

Dogs: outsmarting humans even at algorithm design.
Image: Jennifer Morton

Sheepdogs think algorithmically. Using just two fundamental rules, the dogs analyze the state of a given herd and determine the best action to take among a limited set of possibilities.

The resulting effectiveness is so astounding that a description of these dog algorithms could have profound uses in not just herding and livestock management, but in controlling crowds and even cleaning up the environment.


This is according to a new study in the Journal of the Royal Society Interface describing a general algorithm derived from sheepdog/herd behaviors by which a single individual can influence the group behavior of a massive and unwilling crowd.

"Some of the most striking examples of this collective [swarm-like] behaviour occur in the presence of threat; when flocks, shoals and herds aggregate and evade their predators," the authors, led by evolutionary biologist Andrew King, note.

This behavior is thought to be governed by a powerful theory called the "selfish herd." First described in 1971 by the evolutionary biologist WD Hamilton, this theory explains the "gregarious" behavior of individuals in a herd under threat.

Simply, when a herd member perceives themselves to be in danger, they tend to seek cover, pushing as deeply into the herd as possible. As a whole, this tendancy acts as a centripetal force, pulling the herd inward on itself into a vortex of increasingly dense states. This persists until the threat is gone.

Sheepdogs know all about selfish herds and they utilize this knowledge to accomplish herding tasks beyond the capabilities of human shepherds. "But herding of larger groups (more than 40 individuals) typically requires multiple shepherds," the authors write. "However, single sheep dogs can successfully herd flocks of 80 or more sheep both in their everyday work and in competitive herding trials."


They do this via the aforementioned two simple rules. When sheep become dispersed beyond a certain point, dogs put their effort into rounding them up, reintroducing predatory pressure into the herd, which responds according to selfish herd principles, bunching tightly into a more cohesive unit.

With that accomplished, moving the herd from place to place once again becomes efficient. Simply, if all of the sheep ("flocking agents") are within a certain radius of the herd's center, the sheepdog aims in the driving direction; if this is not the case, the sheepdog aims for the sheep that's the furthest away from this center.

Based on sheepdog/sheep observations using GPS devices—the animals wore backpacks—"the shepherd tends to initially collect the agents until they are cohesive, at which point it starts to drive the group," the current paper observes. "Once the agents are mobile, the shepherd switches between driving and collecting modes until the task is completed and the agents are delivered to the target location in the lower left corner of the field."

As an algorithm, the researchers found success rates consistently at 100 percent, so long as the relationship between the number of possible neighbors an individual herd member might possibly have remains more than half of the total herd size.

"One way of overcoming this problem and potentially allow the shepherd to deal with groups of arbitrary size is to programme it to sequentially bring in subgroups of a size it can handle," King's teamwrites.

This worked somewhat, but a problem that arose often was of the shepherd ending up at the center of a cluster of subherds. The two herding tasks in a multiherd situation sort of just get mixed up: the bringing together gets tangled with the directional driving.

Finally, the authors conclude, "Our approach should support efficient designs for herding autonomous, interacting agents in a variety of contexts. Obvious cases are robot-assisted herding of livestock, and keeping animals away from sensitive areas, but applications range from control of flocking robots, cleaning up of environments and human crowd control.

"In the case of flocks of mobile robots, for example, engineers have designed virtual or explicit leaders to guide groups to target headings, or else assumed that a heading is sensed by the whole group," they continue.

Dogs: outsmarting humans even at algorithm design.