国立研究開発法人産業技術総合研究所 ウェブサイト,
モレキュラーバイオシステム研究部門 ウェブサイト,
バイオ分子モダリティ研究グループ 主任研究員
National Institute of Advanced Science and Technology (AIST) Web,
Molecular Biosystems Research Institute Web,
Biomolecular Modality Research Group, Senior Researcher
Nakamura, M.: Two extensions of heterogeneous boid model to avoid metastable patterns. Artificial Life and Robotics 25(4), 578-587 (2020) Web,
Nakamura, M.: Dynamic patterns formed by heterogeneous boid model composed of agent groups moving reversely. Artificial Life and Robotics 27(2), 373-383 (2022) Web,
Nakamura, M.: Stable dynamic patterns generated by retrograde model. Artificial Life and Robotics 30(2) (2025) Web,
Recent study
Study of Heterogeneous Boid
To improve loading times, videos and detailed descriptions have been embedded within gray buttons. Please click the button to view the content.
Background
Boid
Boid is a model of animal group movements, as a simple multi-agent system communicating locally.
This model originates from the fish school model (Sakai, S. and Suzuki, R., 19721) and 19732)), and has been widely applied (Reynolds, C. W., 19873), Olfati-Saber, R., 20064), Sayama, H., 20075), Vicsek, T. and Zafeiris, A., 20126)).
1) Sakai, S., Suzuki, R.: A model of the schooling of fishes (in Japanese). The Institute of Electronics and Communication Engineers of Japan (IECE), MBE (1972)
2) Sakai, S., Suzuki, R.: A model for group structure and its behavior (in Japanese). The Institute of Electronics and Communication Engineers of Japan (IECE), MBE (1973)
3) Reynolds, C.W.: Flocks, herds, and schools: a distributed behavioral model. Computer Graphics 21(4), 25-34 (1987)
4) Olfati-Saber, R.: Flocking for multi-agent dynamics systems: algorithms and theory. IEEE Transaction of Automatic Control 51(3), 401-420 (2006)
5) Sayama, H.: Decentralized control and interactive design methods for large-scale heterogeneous self-organizing swarms. In: Advances in Artificial Life, vol. 4648, pp. 675-684. Springer, LNAI (2007)
Boid agents align and cohere with their neighbors and avoid collisions with (separate from) their nearest neighbors.
Boid agents within the same cluster interact with each other, either directly or indirectly through others, while agents in distant clusters cannot interact. To expand interactions, the agents should be unified into a single cluster.
In this study, the stability of generated pattern is defined as follows: Stable pattern: the model remains (or repeats) a certain pattern, maintaining a unified cluster.
Heterogeneous Boid
A heterogeneous boid composed of several types of agents also originates from the fish school model (Sakai, S. and Suzuki, R., 19732)).
In Nakamura, M., 2020, 2022, and 2025, motion equations and simulation conditions are given as follows:
These are the motion equations of \(i\)th agent (1 \(\le i \le N, N\): the number of agents).
$$ \frac{\vec x_i(t+\Delta t) - \vec x_i(t)}{\Delta t} = \vec v_i(t) \qquad (1)$$
$$ \begin{align}
\frac{\vec v_i(t+\Delta t) - \vec v_i(t)}{\Delta t}=\sum_{\{j: \left| \vec \xi_{i, j}(t) \right| \lt r_s(T_i, T_j)\}} w_s(T_i, T_j) \frac{\vec \xi_{i, j}(t)}{\left| \vec \xi_{i, j}(t) \right|} \newline
+ \sum_{\{j: \left| \vec \xi_{i, j}(t) \right| \lt r_a(T_i, T_j)\}} w_a(T_i, T_j) \frac{\left( \vec v_j(t) - \vec v_i(t) \right)}{N_{a, i}} \\
+ \sum_{\{j: \left| \vec \xi_{i, j}(t) \right| \lt r_c(T_i, T_j)\}} w_c(T_i, T_j) \frac{\left( - \vec \xi_{i, j}(t) \right)}{N_{c, i}} \qquad (2)
\end{align} $$
$$N_{a,i} = \sum\nolimits_{\{j:\left| \vec \xi_{i, j}(t) \right| \lt r_a(T_i, T_j)\}}1, \qquad N_{c,i} = \sum\nolimits_{\{j:\left| \vec \xi_{i, j}(t) \right| \lt r_c(T_i, T_j)\}}1 \qquad (3)$$
Three terms in Eq. (2) denote the Separation, Alignment, and Cohesion forces.
When \(N_{a,i}\) or \(N_{c,i} = 0\), the 2nd or 3rd term in Eq. (2) is decided as 0.
Details of these equations are listed as follows:
\(\vec x_i(t)\) and \(\vec v_i(t)\): the position and velocity of \(i\)th agent at time \(t\), respectively.
\(\Delta t = 1\): this is the time lag from sensing to action.
\(\vec \xi_{i,j}(t) = \vec x_i(t) - \vec x_j(t) \) (\(1 \le i, j \le N\)): the distance between \(i\)th and \(j\)th agents.
\(T_i\) and \(T_j\) denote the types of the \(i\)th and \(j\)th agents (\(1 \le T_i, T_j \le k\), \(k\): the number of types).
\(\{j: \left| \vec \xi_{i, j}(t) \right| \lt r\}\) means the all \(j\)th agents within \(r\) from \(i\)th agent, not including \(i\)th agent itself.
\(w_s(g, h)\), \(w_a(g, h)\), and \(w_c(g, h)\) denote the weights of sepatation, alignment, and cohesion from the \(h\)th-type agent to the \(g\)th-type agent, and \(r_s(g, h)\), \(r_a(g, h)\), and \(r_c(g, h)\) denote their effective ranges, respectively (\(1 \le g, h \le k\)). They are arranged in \(k \times k\) matrices as \(W_s =\left[ w_s(g, h)\right]\), \(\dots\), and \(R_c=\left[ r_c(g, h)\right]\).
The set \(\{W_s, \dots, R_c\}\) denotes the local interaction of the agents.
The heterogeneous boid is simulated under the following environment:
Environment: \(N\) agents move within a 100\(\times\)100\(\times\)100 cube (\(N\)=10,000, basically).
Boundary Condition: Agents nearing the boundary of the cube avoid collision and bounces back inside the cube. This condition works to keep the agent cluster at low speed.
Initial State: Agents are divided into types evenly and distributed around the center of the cube.
By adjusting interactions, the model can form stable patterns with large-scale symmetrical structures (cluster shape and agent flows), reflecting the local interactions.
Such patterns remain stable regardless of the number of agents \(N\) and are defined as scalable.
Such stable and scalable patterns are useful as templates for the collaboration of such agents.
I. The simplest model : heterogeneous Boid Composed by Two Types of Agents (Nakamura, 2020)
The simplest model is a heterogeneous boid composed of two types of agents.
It is simulated with fixed
$$W_s =\left[
\begin{smallmatrix}
0.05 & 0.05 \\
0.05 & 0.05 \\
\end{smallmatrix}
\right],
R_s =\left[
\begin{smallmatrix}
1.0 & 1.0 \\
1.0 & 1.0 \\
\end{smallmatrix}
\right], R_a =\left[
\begin{smallmatrix}
2.5 & 2.5 \\
2.5 & 2.5 \\
\end{smallmatrix}
\right], R_c =\left[
\begin{smallmatrix}
3.0 & 3.0 \\
3.0 & 3.0 \\
\end{smallmatrix}
\right]$$ and varying \(W_a\) and \(W_c\).
Three Stable and Scalable Patterns
By tuning \(W_a\) and \(W_c\), the model forms three static patterns of the stable and scalable cluster with large-scale symmetrical structures.
Hemispherical pattern
When agents of the same type align and cohere more strongly than the different type, the interface between the types of agents is minimized to a planar shape. This shot is simulated with
\(W_a =\left[
\begin{smallmatrix}
0.1 & 0.0 \\
0.0 & 0.1 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.02 & 0.01 \\
0.01 & 0.02 \\
\end{smallmatrix}
\right]\).
Saddle-shaped pattern
When agents cohere with the same type and are aligned with the different type, this model forms the cluster with a saddle shape interface, which maximizes the interface and minimizes the cluster surface, simultaneously. These shots are simulated with
\(W_c =\left[
\begin{smallmatrix}
0.05 & 0.0 \\
0.0 & 0.05 \\
\end{smallmatrix}
\right]\) and
\(W_a =\left[
\begin{smallmatrix}
0.0 & 0.1 \\
0.1 & 0.0 \\
\end{smallmatrix}
\right]\)
or \(W_a =\left[
\begin{smallmatrix}
0.0 & 0.3 \\
0.3 & 0.0 \\
\end{smallmatrix}
\right]\)
or \(W_a =\left[
\begin{smallmatrix}
0.0 & 0.7 \\
0.7 & 0.0 \\
\end{smallmatrix}
\right]\).
The curvature of the interface changes with \(W_a\).
Spherical-shell pattern
When the interaction differs between types, the interface is minimized to a spherical shell.
This is simulated with \(W_a =\left[
\begin{smallmatrix}
0.05 & 0.0 \\
0.0 & 0.1 \\
\end{smallmatrix}
\right]\) and \( W_c =\left[
\begin{smallmatrix}
0.05 & 0.01 \\
0.01 & 0.01 \\
\end{smallmatrix}
\right]\).
Videos are simulated with \(N\) = 10,000.
Transformation among Stable Patterns by Switching Interaction
When simulated from the ordered initial state with a large-scale structure, under appropriate interaction, the simplest model forms the corresponding stable pattern.
The following video shows that when switching between interactions corresponding to stable patterns, the pattern generated by the model changes accordingly.
The large-scale structures in the stable patterns help smooth transformation among them, as shown in the videos
\(W_a\) and \(W_c\) are switched soon after the videos begin.
HEM:\(W_a =\left[
\begin{smallmatrix}
0.1 & 0.0 \\
0.0 & 0.1 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.02 & 0.01 \\
0.01 & 0.02 \\
\end{smallmatrix}
\right]\) where the hemispherical pattern is stable.
SAD:\(W_a =\left[
\begin{smallmatrix}
0.0 & 0.1 \\
0.1 & 0.0 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.05 & 0.0 \\
0.0 & 0.05 \\
\end{smallmatrix}
\right]\) where the saddle-shaped pattern is stable.
SPH:\(W_a =\left[
\begin{smallmatrix}
0.05 & 0.0 \\
0.0 & 0.1 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.05 & 0.01 \\
0.01 & 0.01 \\
\end{smallmatrix}
\right]\) and SPH':\(W_a =\left[
\begin{smallmatrix}
0.1 & 0.0 \\
0.0 & 0.05 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.01 & 0.01 \\
0.01 & 0.05 \\
\end{smallmatrix}
\right]\) where the spherical-shell pattern and its inversion are stable.
\(\qquad \qquad \qquad\) HEM \(\to\) SAD \(\quad \qquad \qquad \qquad \qquad \qquad\) SAD \(\to\) HEM \(\qquad \qquad \qquad\) HEM \(\to\) SPH \(\quad \qquad \qquad \qquad \qquad \qquad\) SPH \(\to\) HEM \(\qquad \qquad \qquad\) SAD \(\to\) SPH \(\quad \qquad \qquad \qquad \qquad \qquad\) SPH \(\to\) SAD \(\qquad \qquad\) SPH \(\to\) SPH' (inside-out)\(\quad \qquad \qquad\)Videos were presented at SWARM6 (2023).
Videos are simulated with \(N\) = 10,000.
Emergence of Metastable States
When simulated from the random initial state without structure, metastable states dominate even under appropriate interaction, as shown in the sequence.
This sequence is simulated with \(W_a =\left[
\begin{smallmatrix}
0.1 & 0.0 \\
0.0 & 0.1 \\
\end{smallmatrix}
\right]\) and \(W_c =\left[
\begin{smallmatrix}
0.02 & 0.01 \\
0.01 & 0.02 \\
\end{smallmatrix}
\right]\) where the hemispherical pattern is stable.
Changing agent action replaces the metastable state with the stable hemispherical pattern, as follows.
By adding noise in the agent's action, agent cluster deforms and the interfaces merge into one.
The noise term \(\vec \nu_i(t)\) is added to Eq. (2). \(\vec \nu_i(t)\) is uniform-randomly distributed on a sphere of radius 0.04.
When agents change to the additional third type (type 3) on the interfaces, interfaces keep moving until the last one remains. Blue dots on the interface(s) denote type 3 agents.
An additional third type (type 3) of agent is introduced. When an interface between agents of the two types (type 1 and 2) is detected or lost, the agent changes its type as follows.
When an agent of type 1 or 2 detects an interface, it changes to type 3.
When a type 3 agent cannot detect an interface, it changes to type 1 or 2, at the rate of \(\frac{r_2}{r_1 + r_2}\) or \(\frac{r_1}{r_1 + r_2}\) (\(r_{1}\), \(r_{2}\): the rate of all agents of type 1 and 2, variable).
Otherwise, an agent keeps its type.
\(i\)th agent detects an interface when it satisfies the following conditions:
The rate of type 1 agents within the sensing area of \(i\)th agent and that of type 2 are simultaneously greater than 0.3.
The centers of type 1 and 2 agents within the sensing area of \(i\)th agent are distant: \(\quad \left|\vec I_i\right|/r_c(*, *) \ge 0.35\) where $$\vec I_i = \sum\nolimits_{\{j:\left| \vec \xi_{i, j}(t) \right| \lt r_c(T_i, T_j)\}}\frac{g(j)\left(\vec x_j(t) - \vec x_i(t)\right)}{N_{c,i}}, \quad g(j) = \begin{smallmatrix}
1: & j\text{th agent is type 1}\\
-1: & j\text{th agent is type 2}\\
0: & j\text{th agent is type 3}\\
\end{smallmatrix}$$
Under appropriate interaction, the model with a small \(N\) forms the three stable scalable patterns similar to those formed with a large \(N\), even when simulated from either random or structured initial state.
II. The retrograde Model (Nakamura, 2022 and 2025)
A retrograde model is the heterogeneous boid simulated under the condition that two types of agents move in reverse, passing through the gap between them.
When simulated with \(W_s =\left[
\begin{smallmatrix}
0.05 & 0.05 \\
0.05 & 0.05 \\
\end{smallmatrix}
\right]\), \(W_a =\left[
\begin{smallmatrix}
0.03 & -0.003 \\
-0.003 & 0.03 \\
\end{smallmatrix}
\right]\), \(W_c =\left[
\begin{smallmatrix}
0.02 & 0.03 \\
0.03 & 0.02 \\
\end{smallmatrix}
\right]\), \(R_s =\left[
\begin{smallmatrix}
1.0 & 0.1 \\
0.1 & 1.0 \\
\end{smallmatrix}
\right]\), \(R_a =\left[
\begin{smallmatrix}
2.5 & 2.5 \\
2.5 & 2.5 \\
\end{smallmatrix}
\right]\), \(R_c =\left[
\begin{smallmatrix}
3.0 & 3.0 \\
3.0 & 3.0 \\
\end{smallmatrix}
\right],\) the two types of agents oscillate in the reverse phase within cluster(s), repeating fragmentation and fusion of cluster(s).
Oscillation of the two types of agents breaks the cluster.
Just before breaking, the cluster transforms into a dumbbell shape.
To unify the clusters, an additional third type of agent is introduced as a stabilizer, thereby expanding the interaction as \(W_s =\left[
\begin{smallmatrix}
0.05 & 0.05 & 0.05 \\
0.05 & 0.05 & 0.05 \\
0.05 & 0.05 & 0.05 \\
\end{smallmatrix}
\right]\), \(W_a =\left[
\begin{smallmatrix}
0.03 & -0.006 & 0.0\\
-0.006 & 0.03 & 0.0\\
0.0 & 0.0 & w_{a}(3,3)\\
\end{smallmatrix}
\right]\), \(W_c =\left[
\begin{smallmatrix}
0.02 & 0.03 & 0.03\\
0.03 & 0.02 & 0.03\\
0.03 & 0.03 & w_{c}(3,3)\\
\end{smallmatrix}
\right]\), \(R_s =\left[
\begin{smallmatrix}
1.0 & 0.1 & \rho \\
0.1 & 1.0 & \rho \\
\rho & \rho & 1.0 \\
\end{smallmatrix}
\right]\), \(R_a =\left[
\begin{smallmatrix}
2.5 & 2.5 & 2.5 \\
2.5 & 2.5 & 2.5 \\
2.5 & 2.5 & 2.5 \\
\end{smallmatrix}
\right]\),and \(R_c =\left[
\begin{smallmatrix}
3.0 & 3.0 & 3.0\\
3.0 & 3.0 & 3.0\\
3.0 & 3.0 & 3.0\\
\end{smallmatrix}
\right]\).
Agents are divided into the three types evenly and their types are fixed.
By varying \(w_{a}(3,3)\), \(w_{c}(3,3)\), and \(\rho\), the retrograde model generates diverse dynamic patterns.
Three Stable Dynamic Patterns
By tuning \(w_{a}(3,3)\), \(w_{c}(3,3)\), and \(\rho\), this model generates three dynamic patterns of the stable and scalable cluster with large-scale agent flows.
Irregular-oscillating pattern
When simulated with \(\rho\)=0.1 and over wide ranges of \(w_{a}(3,3)\) and \(w_{c}(3,3)\), the reverse-phase oscillation of the two types of agents is observed. This pattern repeats i) the simple oscillation with a period of 100\(\sim\)250 steps and ii) the transient violent deformations of the cluster, intermittently. Before the deformation, the cluster transforms into a reinforced dumbbell shape, where the third type agents surrounding its center unify the cluster strongly. Video is an example, simulated with \(w_{a}(3,3)\)=0.03, \(w_{c}(3,3)\)=0.03, and \(\rho\)=0.1.
Rotating pattern
When simulated with \(w_{a}(3,3)\)=0.1, \(w_{c}(3,3)\)=0.1, and \(\rho\)=1.0, the reverse rotation of the two types around the core of agents of the third type is observed. The cluster repeatedly deforms into spherical, discoidal, and branched phases in the cycle of 1000\(\sim\)1500 steps, as the rotation grows (spherical\(\to\)discoidal phase) and destabilizes (branched\(\to\)spherical phase).
Locked-in pattern
When simulated with \(\rho\)=1.0 and over wide ranges of \(w_{a}(3,3)\) and \(w_{c}(3,3)\), neither rotation nor oscillation of the agents is observed, as agents of the third type block any coordinated movement. Video is an example, simulated with \(w_{a}(3,3)\)=0.03, \(w_{c}(3,3)\)=0.03, and \(\rho\)=1.0.
Videos were presented at SWARM7 (2024).
Emergence of Metastable States
As the number of agent \(N\) increases, long-lasting metastable states emerge when simulated from the random initial state.
Metastable oscillatory state
When simulated with \(w_{a}(3,3)\)=0.01, \(w_{c}(3,3)\)=0.1, and \(\rho\)=0.1, a long-lasting oscillatory pattern emerges.
In this video, cluster transforms into a dumbbell shape around step 55,000, and break up soon. In sessions, its duration distributes between 45,000 and more than 100,000.
Metastable rotating state
When simulated with \(w_{a}(3,3)\)=0.1, \(w_{c}(3,3)\)=0.01, and \(\rho\)=0.1, a long-lasting rotating pattern lasts for over 30,000 steps, and is gradually replaced by the stable irregular-oscillating pattern by step 50,000.
The video shows the metastable rotating state around step 10,000.
Videos were presented at SWARM7 (2024). They are simulated with \(N\) = 10,000 and from the random initial state.
Scalability of Three Stable Patterns
Under appropriate interaction, the model with a small \(N\) forms the stable patterns similar to those formed with a large \(N\).
Irregular-oscillating pattern
\(w_{a}(3,3)\)=0.03, \(w_{c}(3,3)\)=0.03, and \(\rho\)=0.1.
Rotating pattern
\(w_{a}(3,3)\)=0.1, \(w_{c}(3,3)\)=0.1, and \(\rho\)=1.0.
Locked-in pattern
\(w_{a}(3,3)\)=0.03, \(w_{c}(3,3)\)=0.03, and \(\rho\)=1.0.
Videos are simulated with \(N\) = 1,000 from the random initial state.
On the contrary, duration of the metastable states decreases sharply when simulated with \(N\) = 1,000.
The duration of metastable oscillating state decreases approximately from 50,000 to 20,000 step on average, when simulated with \(w_{a}(3,3)\)=0.01, \(w_{c}(3,3)\)=0.1, and \(\rho\)=0.1.
They are a shot of broken cluster taken at step 23570.
The metastable rotating pattern disappers, and the stable irregular-oscillating pattern is formed directly from random initial state, when simulated with \(w_{a}(3,3)\)=0.1, \(w_{c}(3,3)\)=0.01, and \(\rho\)=0.1.
They are a shot of the irregular-oscillating pattern taken at step 3500.
Appendix: Transformation between Stable Dynamic Patterns by Switching Interaction
If \(r_s(*,*)\) changes when switching interaction, the volume of the cluster changes violently.
When switching \(\rho\), the cluster explodes (\(\rho\)=0.1 \(\to\) 1.0) or breaks up (\(\rho\)=1.0 \(\to\) 0.1). Such violent changes disturb the smooth transformation among stable patterns.
So this part displays the transformation between the locked-in and rotating patterns without volume change of the clusters.
Transformation is simulated with fixed \(\rho\)=1.0, switching \(w_{a}(3,3)\) and \(w_{c}(3,3)\).
When switching \(w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.01\(\to\)0.1, the cluster transforms from locked-in to rotating pattern smoothly. \(\quad w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.01\(\to\)0.1
When switching \(w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.1\(\to\)0.01 directly, the cluster breaks up (video on the left).
By interspersing a short buffer period (\(w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.1\(\to\)0.05 for 200 steps\(\to\)0.01), the cluster transforms from rotating to locked-in pattern smoothly (video on the right). \(\quad w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.1\(\to\)0.01 \(\qquad \qquad\) \(w_{a}(3,3)\)=\(w_{c}(3,3)\)=0.1\(\to\)0.05\(\to\)0.01
Videos were presented at SWARM6 (2023).
Summary
By tuning local interaction, heterogeneous boid (the simplest and retrograde model) generates scalable and stable patterns with large-scale symmetrical structures reflecting the interaction.
When these models with a large \(N\) are simulated from a random state, even under the appropriate interactions, they often generate metastable states. To detect and remove (decrease) such metastable states, the following revisions are proposed;
These models with a small \(N\) form the stable patterns, regardless of whether the initial state is random or structured.
When simulated from a structured state, these models with a large \(N\) form the stable patterns smoothly.
We modified agents' action to arrange cluster's structures. The modified models form the similar stable patterns.
