Optimal Control Strategies for Multi-Agent Sheep Herding
Drake Brown, Trevor Garrity, Daniel Perkins, Davis Hunter, Wyatt Pochman · 2025
Read Optimal Control Strategies for Multi-Agent Sheep Herding by Drake Brown, Trevor Garrity, Daniel Perkins, Davis Hunter, Wyatt Pochman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25115.txt.
Introduction
Drake Brown, Trevor Garrity, Daniel Perkins, Davis Hunter, and Wyatt Pochman model how dogs can herd sheep to a set point at least cost. They set state rules for both groups and a cost form for the task. A first code tool that solves edge value tasks was used to draw best paths.
That tool most oft failed to settle, due to the task's high size and bent rules. With a good first guess and tuned dials, it could be made to work. A shot based way also fell short. A loop based line and square method scaled best and took more sheep and dogs. It still shook when dogs and sheep came close, where bent rules bite.
Catalog record
| CREATOR | Drake Brown, Trevor Garrity, Daniel Perkins, Davis Hunter, Wyatt Pochman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Control Strategies for Multi-Agent Sheep Herding Drake Brown, Trevor Garrity, Daniel Perkins, Davis Hunter, Wyatt Pochman Abstract We develop a cost functional and state-space equations to model the problem of herding m m sheep to the origin using n n dogs. Our initial approach uses solve_bvp to approximate optimal control trajectories. But this method often fails to converge due to the system’s high dimensionality and nonlinearity. However, with a well-chosen initial guess and carefully selected hyperparameters, we succeed in getting solve_bvp to converge. We also explore alternatives including the shooting method and linearization with the iterative Linear Quadratic Regulator (iLQR). While the shooting method also suffers from poor convergence, the linearized iLQR approach proves more scalable and successfully handles scenarios with more agents. However, it struggles in regions where dogs and sheep are in close proximity, due to strong nonlinearities that violate the assumptions of local linearization. This leads to jagged, oscillatory paths and slow convergence, particularly when the number of sheep exceeds the number of dogs. These challenges reveal key limitations of standard numerical techniques in multi-agent control and underscore the need for more robust, nonlinear strategies for coordinating interacting agents. 1 Introduction Shepherds have long considered the question, what are the optimal routes for my m dogs to take to corral my n indignant sheep into their pen? Assuming dogs behave optimally in real life, this is closely related to the question, how many dogs m are required to successfully corral n sheep into their pen? Exploiting the facts that (i) sheep tend to flock together in groups and (ii) sheep are slower than dogs, shepherds have universally determined (through real-life experience) that there exists a solution m such that m\ll n . Here we propose a mathematical approach that allows heuristic estimation of the required parameter m through simulations. While inspired by shepherding, the implications of solving this control problem extend to many other scenarios where controllable agents are tasked to guide a another group of agents toward a desired destination. For example, solutions could be naturally applied to optimal control in robotic search-and-rescue missions, oil spill containment, and charged particle manipulation. 2 Background In general, previous researchers have applied heuristic algorithms to predict dog behavior. Strömbom et al. present a biologically-inspired model which attempts to replicate real-life herding behaviors, particularly the observed herding phases of “driving" and “collecting" [ 4 ] . Dog behavior is derived from the modeling choices that sheep are attracted to one another and repelled by dogs; the algorithm explicitly causes the dogs to cluster the sheep into a group (“collecting") before guiding the entire flock toward the target (“driving"). Results indicate the dogs often fail to corral the sheep in the case that m\ll n . More recently, Lama and Di Bernardo consider the herding problem under the dual assumptions that (i) dogs are only aware of nearby sheep and (ii) the sheep do not naturally flock together [ 3 ] . Sheep behavior is modeled by the same equations governing particle interaction in active matter [ 1 ] ; dog behavior is determined by imposing a fixed strategy. Building on existing works, our goal is to explore the shepherding problem through the lens of optimal control. In particular, we determine the optimal dog strategy with respect to a chosen cost functional. By modeling the system with state-space dynamics and applying Pontryagin’s Maximum Principle, we apply boundary value problem solvers and the iterative Linear Quadratic Regulator (iLQR) to derive efficient, theoretically grounded strategies for herding. 3 Modeling 3.1 Modeling Assumptions To tackle this problem, we begin by considering the behavior of the sheep. We assume each sheep wishes to maximize their distance from the dogs at each time t , especially moving away from the closest dog(s) (see Figure 1 ). Because sheep commonly travel in groups, we enforce no constraint on the distances between sheep, but we also do not impose any attractive forces between sheep. These modeling decisions are consistent with assumptions (i) and (ii) of [ 3 ] . Figure 1 : A visualization of the sheep’s strategy when herded by m=2 dogs and n=1 sheep. The sheep move away from all nearby dogs, with their velocities weighted inversely by each dog’s distance—giving more influence to those that are closest. Setting up the environment, we suppose the sheep and dogs are constrained to move on a two-dimensional plane, with the sheep pen at the origin. Let sheep i ’s position be given by the two-dimensional vector \mathbf{s}^{(i)}=(s_{x}^{(i)},s_{y}^{(i)}) , and let dog j ’s position be given by the two-dimensional vector \mathbf{d}^{(j)}=(d_{x}^{(j)},d_{y}^{(j)}) . We model the sheep strategy from Figure 1 using the following second-order ODE giving the acceleration of sheep i : (\mathbf{s}^{(i)})^{\prime\prime}=\sum_{j=1}^{m}\frac{\mathbf{s}^{(i)}-\mathbf{d}^{(j)}}{(\|\mathbf{s}^{(i)}-\mathbf{d}^{(j)}\|_{2}^{2}+\epsilon)^{\lambda/2}} (1) In the case \lambda=3 , this acceleration is proportional to Coloumb’s law governing the acceleration induced by charged particles on another like-charged particle, with the \epsilon term added to avoid numerically instability that would otherwise result as the distances approach zero. Note that this \epsilon term implicitly bounds the maximum possible acceleration of the sheep, with a larger value of \epsilon giving a smaller maximum acceleration. 3.2 Cost Functional and State-Evolution Equation The control problem is to find the optimal acceleration \textbf{u}^{(j)}=(\mathbf{d}^{(j)})^{\prime\prime} of each dog j , given the following goals: • The dogs wish to guide the sheep towards the origin (sheep pen); • The dogs wish to stay relatively close to the origin; • The dogs wish to limit their acceleration to preserve energy. To accomplish our goals, for some fixed time t_{f} , we wish to solve the following problem: minimize \displaystyle\int_{0}^{t_{f}}\left(\alpha\sum_{i=1}^{n}\|\mathbf{s}^{(i)}\|_{2}^{2}+\beta\sum_{j=1}^{m}\|\mathbf{d}^{(j)}\|_{2}^{2}+\sum_{j=1}^{m}\|\mathbf{u}^{(j)}\|_{2}^{2}\right)dt (2) subject to \displaystyle\begin{pmatrix}d_{x}^{(j)}\\ d_{y}^{(j)}\\ (d_{x}^{(j)})^{\prime}\\ (d_{y}^{(j)})^{\prime}\end{pmatrix}^{\prime}=\begin{pmatrix}(d_{x}^{(j)})^{\prime}\\ (d_{y}^{(j)})^{\prime}\\ u_{x}^{(j)}\\ u_{y}^{(j)}\end{pmatrix}\quad\forall 1\leq j\leq m,\qquad (3) \displaystyle\begin{pmatrix}d_{x}^{(j)}(0)\\ d_{y}^{(j)}(0)\end{pmatrix}=\mathbf{d}_{0}^{(j)}\quad\forall 1\leq j\leq m,\qquad (4) \displaystyle\begin{pmatrix}s_{x}^{(i)}\\ s_{y}^{(i)}\\ (s_{x}^{(i)})^{\prime}\\ (s_{y}^{(i)})^{\prime}\end{pmatrix}^{\prime}=\begin{pmatrix}(s_{x}^{(i)})^{\prime}\\ (s_{y}^{(i)})^{\prime}\\ \sum_{j=1}^{m}\frac{s_{x}^{(i)}-d_{x}^{(j)}}{(\|\mathbf{s}^{(i)}-\mathbf{d}^{(j)}\|^{2}+\epsilon)^{\lambda/2}}\\ \sum_{j=1}^{m}\frac{s_{y}^{(i)}-d_{y}^{(j)}}{(\|\mathbf{s}^{(i)}-\mathbf{d}^{(j)}\|^{2}+\epsilon)^{\lambda/2}}\end{pmatrix}\quad\forall 1\leq i\leq n,\qquad (5) \displaystyle\begin{pmatrix}s_{x}^{(i)}(0)\\ s_{y}^{(i)}(0)\end{pmatrix}=\mathbf{s}_{0}^{(i)}\quad\forall 1\leq i\leq n,\qquad (6) The relative importance of each goal is specified by the hyperparameters \alpha and \beta . Note that equation ( 5 ) is equivalent to equation ( 1 ) expressed as a first-order ODE; however, the state space is now 4(m+n) -dimensional. Thus, if we include the co-state, the system is 8(m+n) -dimensional. Even in the simple case of m=2 and n=1 , this is a 24-dimensional system. The high number of dimensions increases the spatial complexity of storing a solution and the temporal complexity of calculating the derivative function. Even worse, estimating or directly calculating the Jacobian matrix is signifcantly slower, with the Jacobian matrix containing 24^{2}=576 entries at each time step. Figure 2 : One potential dog strategy for m=2 dogs and n=1 sheep. Here, the dogs end by surrounding the sheep at equal distances, forcing the sheep to remain stationary in its pen at the origin. A snapshot of one potential corralling method is given in Figure 2 at time t=t_{f} . Note that our control-based approach does not allow us to impose hard inequality constraints on the state, so we cannot directly enforce that \|\mathbf{s}^{(i)}(t_{f})\|\leq r for some final time t_{f} (specifying the sheep must be contained within a pen of radius r at time t_{f} ). Instead, we enforce this as a soft constraint inside our cost functional. 3.3 Derivation of Optimal Control Using Pontryagin’s Maximum Principle