Swarm Path Planning
Swarm Path Planning
Reproducing potential-field formation control — building the artificial fields that hold a group of robots in formation, and an honest account of where my implementation fell short.
01.
The Idea
A swarm is a group of robots that cooperate to achieve a shared objective, communicating locally rather than through a single commander. I find this a compelling direction for planetary exploration and search-and-rescue: many cheap agents can cover far more ground than one expensive one, and the group degrades gracefully when individuals fail.
This project is a reproduction of the potential-field method from Barnes, Fields and Valavanis, “Unmanned Ground Vehicle Swarm Formation Control Using Potential Fields” (15th Mediterranean Conference on Control & Automation, 2007). The appeal of their approach is its simplicity: instead of rigidly assigning each robot a slot, you sculpt a vector field that the whole swarm flows along, and the formation emerges from the field’s shape.
02.
The Field
Each robot is treated as a particle moving on a surface generated by a bivariate normal “hill” centred at $(x_c, y_c)$:
\[f(x, y) = e^{-\left((x - x_c)^2 + \gamma\,(y - y_c)^2\right)}\]The control variable $\gamma$ is the ratio of the minor to major axis — it sets the eccentricity of the formation, turning a circle into an ellipse. The gradient of this hill gives each member its velocity and heading:
\[d_x = f(x, y)\,2(x - x_c), \qquad d_y = f(x, y)\,2\gamma\,(y - y_c)\]To make the swarm follow a trajectory, the formation has its own local frame, so the coordinates are rotated by the heading $\phi$ before the gradient is evaluated:
\[x_{rot} = \cos(\phi)(x - x_c) - \sin(\phi)(y - y_c), \qquad y_{rot} = \sin(\phi)(x - x_c) + \cos(\phi)(y - y_c)\]The members are attracted to a target ring — the $R^*$ ellipse — defined by
\[R^{*2} = (x - x_c)^2 + \gamma\,(y - y_c)^2 ,\]and the overall controller is a weighted sum of $N$ vector fields acting on the swarm:
\[V(x, y, t) = \sum_{i=1}^{N} w_i(x, y, t)\,\vec{V}_i(x, y, t)\]03.
Shaping the Field with Sigmoids
A raw gradient field pushes particles to infinity or collapses them to the centre. The trick that makes formations hold is a set of sigmoid limiting functions that switch the field on and off at the right radius. Writing the weighted distance as
\[r = \sqrt{(x - x_c)^2 + \gamma\,(y - y_c)^2},\]an inside field $S_{in}$ pushes outward and dies just inside the ring, while an outside field $S_{out}$ pulls inward and dies just outside it:
\[S_{in}(r) = 1 - \frac{1}{1 + e^{\,\alpha_{in}\,(r - (R^* - \Delta R_{in}))}}, \qquad S_{out}(r) = 1 - \frac{1}{1 + e^{-\alpha_{out}\,(r - (R^* + \Delta R_{out}))}}\]A third, Gaussian limiting function confines a perpendicular field that drives members around the ring (rather than across it):
\[N_{\perp}(r) = e^{-\alpha_{\perp}\,(r - R^*)^2}\]Combined, the velocity of a member becomes the inward/outward gradient plus the perpendicular circulation term:
\[\begin{bmatrix} v_x \\ v_y \end{bmatrix} = (S_{in} - S_{out}) \begin{bmatrix} d_x \\ d_y \end{bmatrix} + \mathrm{SGN}\cdot N_{\perp} \begin{bmatrix} d_x \\ d_y \end{bmatrix}_{\!\perp}\]The net effect is meant to “trap” every robot inside a narrow band $R^* - \Delta R_{in} < r < R^* + \Delta R_{out}$, while an additional avoidance field keeps members spaced apart. The parameters $\alpha$ control how sharply each field dies out, and are tuned so each sigmoid reaches a small value $\varepsilon$ at the band edge.
04.
What Worked — and What Didn't
I reproduced the field construction and the limiting functions, and individual pieces behaved as expected — the bivariate-normal gradient and the inside/outside sigmoids produced sensible attraction toward the ring. What I could not reproduce was the clean, stable formation the paper demonstrates. My sigmoid limiting functions never quite shaped the field the way I wanted: members would reach the band but the formation wouldn’t settle into the tidy circle or ellipse, drifting or bunching instead of dispersing evenly.
My current suspects, roughly in order:
- Parameter derivation. The $\alpha$ values are derived from the chosen $\varepsilon$ and band widths; small errors there change where each field “dies out,” which is exactly what governs whether the band traps members.
- The perpendicular term. The $\mathrm{SGN}$ multiplier that flips the circulation direction is easy to get subtly wrong, leaving members orbiting instead of settling.
- Gradient normalisation and time-stepping, which can quietly amplify or damp the field near the band.
I’m documenting this as an honest post-mortem rather than a polished result — the method is elegant, and getting it fully working is unfinished business I’d like to return to.