Shepherding robots herd swarms without talking to each other

Imagine a team of sheepdogs that never bark, never glance at one another, and never receive orders from a central handler, yet still manage to drive an entire flock into its pen. That is essentially what researchers at Osaka University have achieved in silico. In a study published in Frontiers in Control Engineering, Aiyi Li, Masaki Ogura, and Naoki Wakamiya present a shepherding algorithm in which multiple steering agents guide a group of passive agents using nothing but their own local observations, with zero communication between shepherds. The work tackles one of the most persistent assumptions in swarm guidance research, namely that some central coordinator or inter-agent messaging system must exist for coordinated herding to work at all.

The shepherding problem, as the authors describe it, involves designing the movement law of steering agents, called shepherds, to navigate another set of agents, called sheep, which are driven by repulsive forces from the shepherds. The concept is bio-inspired, drawing on the way real sheepdogs herd livestock, and it has attracted attention for applications in robotics, group dynamics, and even nanochemistry, where active particles could potentially steer passive ones. Most existing algorithms, however, assume a central coordinator that can observe the entire system and communicate instructions to every shepherd, an assumption the Osaka team argues is not realistic enough for emerging applications where such infrastructure may be unavailable or unreliable.

To understand what makes the new approach different, it helps to look at the underlying sheep model. Each sheep agent moves in discrete time steps on a two-dimensional plane, its movement vector composed of five forces: separation, alignment, cohesion, repulsion from shepherds, and a random disturbance. The first three forces are a modified implementation of the classic Boid model introduced by Craig Reynolds in 1987, which has become a standard framework for simulating flocking behavior. Separation ensures agents do not collide, alignment steers them toward the average heading of local neighbors, and cohesion pulls them toward the average position of nearby agents. The repulsion force from shepherds uses a diverging potential function so that the closer a shepherd gets, the stronger the sheep’s urge to move away, which is precisely the mechanism that makes herding possible in the first place.

The shepherds themselves operate under strict information constraints. Each has a finite recognition range and can detect only its relative position to the goal, the relative positions of sheep and other shepherds within that range, and nothing else. The authors note that the first two types of sensing could be realized with proximity sensors, while goal-relative positioning could be achieved with recent methodologies such as single beacon-based positioning systems. Crucially, no shepherd ever needs to know what another shepherd intends or plans, which is what distinguishes this work from earlier decentralized algorithms that still implicitly required communication, such as one that needs shepherds to understand each other’s intentions or another that requires multiple rounds of messaging to reach consensus on which sub-flock each shepherd should chase.

The algorithm builds on an existing single-shepherd method called the Farthest-Agent Targeting algorithm, or FAT. In FAT, the shepherd chases the sheep farthest from the goal, maintaining an appropriate distance before pushing it toward the goal region. While effective for a single shepherd, FAT has two problems when generalized to multiple shepherds: all shepherds would target the same sheep, and the flock tends to scatter when a shepherd chases a sheep on the opposite side of the flock. The Osaka team’s extension introduces a parameter alpha that modifies target selection. Each shepherd chooses as its target the sheep maximizing a weighted difference between the sheep’s distance from the goal and its distance from the shepherd. When alpha is zero, the algorithm reduces to FAT. When alpha is large, each shepherd simply targets the closest sheep, preventing the scattering phenomenon. A moderate value balances both objectives.

Cooperation between shepherds emerges not from any messaging but from the spatial distribution induced by inter-shepherd repulsion built into the algorithm. Each shepherd’s movement vector is a weighted sum of four components: chasing its target sheep, maintaining an appropriate distance from neighboring sheep, pushing toward the goal region, and repelling other shepherds to avoid competition. The repulsion between shepherds is weighted by the shepherd’s distance from the goal, because shepherds need to be relatively close to each other at the final stage of navigation. The result is that although each shepherd independently chases its own target, the collective behavior resembles coordinated herding, a form of emergent cooperation arising purely from local rules and physical proximity.

The authors evaluated the algorithm through extensive numerical simulations across three initial flock configurations, a small flock of twenty sheep, a large flock of fifty, and two separate flocks of twenty and thirty, combined with three shepherd placement patterns. They compared the proposed method against FAT, FAT with occlusion, and an online-target switching algorithm. The proposed method achieved almost one hundred percent success rate regardless of the number of shepherds or placement pattern, while also outperforming the baselines in completion time and average path length. Both completion time and path length steadily decreased as more shepherds were added, suggesting stable and synergistic coordination. Notably, the online-target switching algorithm failed entirely at herding two separate flocks, while the proposed method handled them successfully.

The team also tested the algorithm under two additional parameter sets, one where sheep were more sensitive to shepherd movements and one where they were harder to navigate. The proposed method consistently showed higher success rates, lower completion times, and shorter path lengths than the baselines across all scenarios. A slight decrease in success rate appeared under the sensitive scenario, which the authors attributed to interference behaviors when multiple shepherds coincidentally chose the same target and drove it further from the goal, and to the difficulty of simultaneously containing all sheep within the goal region when the flock parameters made them more reactive.

Perhaps most striking was the comparison with centralized algorithms. The authors tested point-offset circling control, where shepherds form an arc formation directed by a central controller, and potential-based caging, where shepherds occupy the vertices of a regular polygon surrounding the flock. Both centralized methods showed increasing completion times and decreasing success rates as the number of shepherds grew, and neither could handle two separate flocks at all. The authors analyzed that the poor performance stemmed from the large interaction distance between shepherds and the flock, and that centralized algorithms were neither robust nor resilient enough to adapt to changes in flock shape caused by sheep movement. The communication-free approach, by contrast, thrived precisely where the centralized methods struggled.

The robustness and resilience tests round out the picture. When the shepherds’ sensing range was varied from fifty to four hundred units, success rates dropped only when the range was too short, suggesting the algorithm needs shepherds with reasonably long sensing capabilities but tolerates substantial variation otherwise. When shepherds were prone to random failures with probabilities up to forty percent per time step, with recovery probability of ten percent, the algorithm maintained high success rates, with completion times rising but traversal distances remaining almost unchanged. Even with additive sensing noise weighted at ten units, the algorithm tolerated relatively large sensing errors across all initial configurations. The authors attribute this fault tolerance to the decentralized mechanism itself, since no single shepherd is indispensable and each operates independently based on its own observations. Future work, they note, includes investigating whether the communication-free coordination mechanism can extend to other navigation tasks and establishing mathematical properties such as stability and convergence, which remain challenging due to the nonlinearity of the underlying swarm model.

Subject of Research: Communication-free decentralized shepherding navigation of passive agent flocks with multiple steering agents

Article Title: Communication-free shepherding navigation with multiple steering agents

Article References: Li, A., Ogura, M., & Wakamiya, N. (2023). Communication-free shepherding navigation with multiple steering agents. Frontiers in Control Engineering, 4, Article 989232. https://doi.org/10.3389/fcteg.2023.989232

Image Credits: AI Generated

DOI: 10.3389/fcteg.2023.989232

Keywords: shepherding, swarm guidance, decentralized control, multi-agent systems, flocking, bio-inspired robotics, communication-free navigation, emergent coordination, robustness, resilience, control engineering, agent-based modeling