Solving the shepherding problem: heuristics for herding autonomous, interacting agents

Daniel Strömbom, Richard P. Mann, Alan M. Wilson, Stephen Hailes, A. Jennifer Morton, David J. T. Sumpter, Andrew J. KingJournal of The Royal Society Interface 2014 · DOI

TL;DR

Researchers have developed a novel algorithm that mimics how sheepdogs herd flocks, using a simple yet effective strategy of switching between "collecting" dispersed agents and "driving" cohesive groups. This model not only reproduces observed sheep-dog behavior but also offers a blueprint for designing robots to manage the collective movement of autonomous agents in various applications, from robotics to crowd control.

What Problem Does This Paper Address?

The "shepherding problem" – how a single agent can effectively guide a group of independent, interacting individuals towards a goal – is a fundamental challenge observed in nature (e.g., sheepdogs herding sheep) and has significant implications for engineering applications like crowd management, robot coordination, and environmental cleanup. While it's clear that experienced sheepdogs can expertly herd large flocks, the underlying algorithmic principles they employ remain largely unknown. Previous computational models often relied on hard-coded "weaving" behaviors or were limited to small groups. This paper aims to bridge this gap by proposing and validating a general algorithm that captures the essence of this complex behavior, explaining how a single shepherd can manage large, dynamic groups.

Methods

The authors propose a self-propelled particle model where individual agents (sheep) follow simple rules: they are attracted to the local center of mass of their nearest neighbors, repelled by other agents at close distances, and repelled by the shepherd. The shepherd, however, operates with a more sophisticated, adaptive strategy. Its behavior is dictated by the spatial distribution of the agents:

  • Collecting Mode: If any agent is too far from the group's global center of mass (GCM), the shepherd moves towards the furthest agent to bring it back into the fold.
  • Driving Mode: If all agents are sufficiently cohesive (within a defined distance from the GCM), the shepherd moves towards a "driving position" behind the group, aiming to move the entire flock towards the target.

This adaptive switching between collecting and driving, rather than a fixed movement pattern, is the core innovation. The model also incorporates a small amount of noise to help resolve potential deadlocks. They also explore a "local shepherd" variant for managing even larger groups by focusing on subgroups.

Datasets

The primary dataset used for validation comes from real-world herding experiments involving a trained Australian Kelpie sheepdog and 46 merino sheep. The sheep and dog were fitted with GPS loggers to record their movement data. This dataset was used to compare the model's simulated behavior (specifically, the shepherd's positioning relative to the flock) against actual observed behavior. The authors also generated extensive simulation data for various group sizes and parameters to analyze the algorithm's performance and robustness.

Key Insights and Ideas

  • Adaptive Switching is Key: The most significant insight is that a simple, adaptive switching strategy between "collecting" and "driving" modes, based on the group's cohesion, is sufficient to reproduce complex herding behavior. This contrasts with previous models that often relied on more complex, hard-coded movements.
  • Emergent Behavior: The characteristic side-to-side motion of the shepherd, often explicitly programmed in other models, emerges naturally from the interplay of the driving and collecting behaviors. This suggests that complex behaviors can arise from simple underlying rules.
  • Scalability: The algorithm demonstrates a degree of scalability, successfully managing larger groups than many previous models, particularly when the shepherd considers a sufficient number of nearest neighbors.
  • Topological vs. Metric Interaction: The paper touches upon the idea that agents might respond to the topological arrangement of their neighbors (who is next to whom) rather than just their metric distance, a concept supported by some biological observations.

Key Results

  • The proposed algorithm successfully herded simulated groups of agents towards a target destination.
  • The model's simulation results closely matched empirical data from sheep-dog herding experiments, particularly in the shepherd's positioning relative to the flock's center of mass and the furthest agent.
  • The proportion of time spent in driving and collecting modes varied predictably with group size, with collecting time increasing for smaller groups and driving time dominating for larger, more cohesive groups.
  • The algorithm showed a high success rate for global shepherding (where agents consider all others) across a range of group sizes and neighbor interaction parameters, with success rates remaining high down to approximately 0.53N nearest neighbors.
  • The "local shepherd" variant, designed for very large groups, achieved an approximate 80% success rate in bringing in subgroups, though it sometimes got stuck between clusters.

Limitations and Future Work

  • Local Shepherd Limitations: The local shepherd algorithm, while improving scalability, is not always successful and can get stuck between subgroups. The authors suggest that an external instruction might be needed to resolve such deadlocks.
  • Agent Behavior Assumptions: The model assumes agents are attracted to the center of mass of at least half the group, which might not hold true for all species or scenarios. Further research could explore how different agent interaction rules affect herding success.
  • Shepherd's Perception: The model assumes the shepherd can accurately perceive agent positions and distances. Future work could investigate the impact of noisy or limited sensory information on the shepherd's performance.
  • Real-world Complexity: While the model reproduces key features, real-world herding involves more complex factors like terrain, individual animal personalities, and learned behaviors, which are not fully captured.
  • Future Applications: The authors highlight potential applications in robot-assisted livestock herding, crowd control in low-visibility environments, and coordinating swarms of cleaning robots. Further exploration of these applications is a natural next step.

Summary updated

Abstract

Herding of sheep by dogs is a powerful example of one individual causing many unwilling individuals to move in the same direction. Similar phenomena are central to crowd control, cleaning the environment and other engineering problems. Despite single dogs solving this 'shepherding problem' every day, it remains unknown which algorithm they employ or whether a general algorithm exists for shepherding. Here, we demonstrate such an algorithm, based on adaptive switching between collecting the agents when they are too dispersed and driving them once they are aggregated. Our algorithm reproduces key features of empirical data collected from sheep-dog interactions and suggests new ways in which robots can be designed to influence movements of living and artificial agents.
BibTeX
@article{strombom2014solving,
  author = {Daniel Strömbom and Richard P. Mann and Alan M. Wilson and Stephen Hailes and A. Jennifer Morton and David J. T. Sumpter and Andrew J. King},
  title = {{Solving the shepherding problem: heuristics for herding autonomous, interacting agents}},
  journal = {Journal of The Royal Society Interface},
  year = {2014},
  doi = {10.1098/rsif.2014.0719},
}
Figure