Boids Flocking Algorithm for Situation Assessment of Driver Assistance Systems

Driver assistance systems are increasingly becoming part of the standard equipment of vehicles and thus contribute to road safety. However, as they become more widespread, the requirements for cost efficiency are also increasing, and so few and inexpensive sensors are used in these systems. Especially in challenging situations, this leads to the fact that target discrimination cannot be ensured which may lead to false reactions of the driver assistance system. In this paper, the Boids flocking algorithm is used to generate semantic neighborhood information between tracked objects which in turn can significantly improve the overall performance. Two different variants were developed: First, a freemoving flock whereby a separate flock is generated per tracked object and second, a formation-controlled flock where boids of a single flock move along the future road course in a pre-defined formation. In the first approach, the interaction between the flocks as well as the interaction between the boids within a flock is used to generate additional information, which in turn can be used to improve, for example, lane change detection. For the latter approach, new behavioral rules have been developed, so that the boids can reliably identify control-relevant objects to a driver assistance system. Finally, the performance of the presented methods is verified through extensive simulations.

SECTION I. Introduction

Active safety measures such as Advanced Driver Assistance Systems (ADAS) are an elementary component of road-safety, especially with high market penetration [1]. In order to further increase road safety, the EU regulation 2019/2144 [2] obliges all OEMs to install an emergency brake assist (EBA) as well as lane departure warning system. Hence, as vehicles need to be equipped with the necessary sensors, the main goal is on cost efficiency, utilizing as few sensors while offering as many functions as possible. Consequently, the comfort function adaptive cruise control (ACC) becomes a default function also in the lower segments. Adaptive cruise control and other SAE-L1 advanced driver assistance systems have been studied extensively, see also [3].

For ACC, radar-only as well as radar+camera solutions are often used as sensor configurations. Despite budget sensors, the expectation especially on comfort functions is high. Ambiguities of the radar sensors due to low angular resolution are predominant and cannot be resolved completely by the camera. Therefore, target association is increasingly hard which leads to so-called ghost objects and/or lateral position ambiguities [4]. As a result of these ambiguities, false reactions of the system can occur, such as driver-take over scenarios from a field-operation test, which have been investigated in [5]. The cause is often not only a missing detection of the ACC-relevant vehicle but of a false interpretation of the scenario, i.e., that the detected vehicle has been falsely assessed to be not relevant, due to, for example, a false lane association. Target discrimination focuses on the correct lane association of vehicles to corresponding lanes [6], [7].

Boids flocking algorithm [8], [9], which has been introduced by Reynolds to model the motion of flocks of birds or schools of fish, uses behavioral rules to create emergent behavior of a swarm. The algorithm updates the position and velocity of each member of a flock (i.e., boid) on the basis of three simple movement rules: separation, cohesion, and alignment.

A flocking algorithm has been used in [10] to derive a control algorithm for multiple non-holonomic cars. Each car has been modeled as an individual boid which behaves according to the movement rules of the typical boid model. The proposed control managed a collision-free path of all boids, however, the use case was limited to a straight highway and, eventually, the assumption that all cars driving in the same direction will converge to the same speed does not hold in reality. Other formation-controlled approaches (e.g., [11], [12]), which consider the non-holonomic constraints of cars [13], focus on the ability to establish and maintain a predefined formation under various driving conditions.

In order to address the issue of target discrimination we propose to use the Boids flocking algorithm. The approach is of particular interest, as it allows to efficiently generate additional information about the movement of traffic participants based on the emergent behavior of a swarm. Two different approaches to Boids flocking algorithm are investigated: “Free-Moving Boids for Object Separation (FMBOS)” and “Formation-Controlled Boids for Object Selection (FCBOS)”.

For FMBOS, an individual flock of boids is created to follow each detected vehicle, i.e., for $N_{v}$ vehicles, $N_{f}$ flocks with $N_{b}$ boids each are generated whereby $N_{v} \leq N_{f}$ , depending on the quality of the tracked object. The corresponding detected vehicle acts as a lead for the swarm to follow. The aforementioned movement rules are applied to each boid of each flock. In addition, a further rule is introduced such that the individual flocks repel each other in the lateral direction. Thereby ensuring that the flocks maintain a lateral distance as long as they are within a given longitudinal distance.

In FCBOS, the movement rules of each boid in a flock are adapted to resemble the formation of parallel driving vehicles using a car-like motion model. The formation-controlled flock is guided by traces of the traffic participants and moves along the future road course. By comparing the position of the traffic participants with the position of the boids within the formation, a lane association is established even under adverse sensoric conditions.

The remainder of this paper is organized as follows: Section II explains the assumed system architecture of the driver assistance system. Section III introduces the generic Boids flocking algorithm, while Section IV as well as Section V focus on the movement rules of the free-moving boid flock and formation-controlled boid flock, respectively. Simulation results are presented in Section VI. Finally, Section VII draws the conclusion.

Throughout the paper, we adopt the following notation conventions: Bold-face capital and lower-case letters stand for matrices and vectors of appropriate dimensions, respectively. Furthermore, $\mathbf {A}(:,i)$ yields a vector of all elements in the $i$ th column of the matrix $\mathbf {A}$ , where $(:)$ is the MATLAB colon operator [14]. $()^{-1}$ represents the matrix inverse, $()^{\mathrm {T}}$ the transpose operator, and $\odot$ the Hadamard product.

SECTION II. System Architecture

A common deliberative system architecture for advanced driver assistance systems (ADAS) is shown in Fig. 1. According to Endsley [15], [16], one of the main tasks of an ADAS system it to generate a situational awareness (SA) which provides the basis for a safe and comfortable vehicle control. The SA model has three levels: 1. Perception, 2. Comprehension, and 3. Projection, which can also be identified in the provided system architecture.

FIGURE 1.

Simplified system architecture of a typical driver assistance system with longitudinal control (e.g., ACC).

Hereby, the sensors, e.g., camera and radar, provide the perception of the relevant information required for a driving function. This typically comprises moving and stationary objects, lane markings, stationary road-side objects, traffic signs, etc. Within the environment model (EM), the information provided by the different sensors is combined in order to generate a unified world model as well as to provide semantic information of the perception. With this information, a given traffic situation is projected into the future in order to plan a safe and comfortable maneuver.

With increasing market penetration, low-budget sensors with limited range and/or resolution are used [17]. Moreover, the bandwidth between sensors and an EM is typically low. While the interface between perception and comprehension has recently been defined [18], often the required information for a high-quality fusion is not provided to the EM. Hence, sensor failures can’t be completely resolved in EM and are forwarded to the Situation Assessment (SIT) module. Next to the short-term prediction of a traffic scenario, such as lane changes of other traffic participants and/or the ego vehicle, a task of SIT is to reduce the set of surrounding vehicles to the set of potentially control-relevant objects on the basis of a matrix formation, i.e., object-of-interest (OOI) selection [19], see also Fig. 2. The amount of OOIs varies depending on the function, whereas a common ACC typically uses only OOIs in front of the ego vehicle while a higher-level driving function also needs to consider OOIs behind or at the side of the ego vehicle. The subsequent maneuver planner module performs a risk assessment considering only OOIs and their potential future maneuvers.

FIGURE 2.

Definition of six objects-of-interest (OOI) for the control-object selection as well as the local coordinate system of the ego vehicle.

The object-of-interest selection is a key enabler for driver assistance systems such as ACC and EBA [20]. Relevant information for the determination of the OOIs is the future road course, the position as well as kinematic information of the road users. The future course of the road is typically determined by means of a camera-based lane detection and/or radar-based static object detection at the roadside (e.g., due to guard rails). The availability of this information cannot be guaranteed, since guard rails may not be present and road marks are insufficiently detected especially at far distances or at night. For this reason, a probabilistic assignment to a driving corridor is often additionally performed for the OOI selection [20].

Another important source of information is provided by the road users themselves through their semantic neighborhood relations. Thus, an OOI selection can be improved if the number of lanes and the neighborhood relations are known. For example, two parallel driving vehicles on a two-lane road can easily be assigned to their respective lane using the number of lanes and the neighborhood relation obtained from the flocks, even in the presence of major inaccuracies in road course estimation. Boids Flocking algorithm is proposed in this paper to efficiently use these semantic neighborhood relations to improve the OOI-selection and thereby reduce the number of false positive and negative accelerations of a driver assistance system.

Due to the common basis of our two approaches on the Boids flocking algorithm, the basic definitions as well as the motion rules of the generic Boids flocking algorithm are discussed below. In the subsequent chapters, we explain the specific extensions or adaptations for both the FMBOS and FCBOS approaches.

SECTION III. Boids Flocking Algorithm

Reynolds [8] introduced three main rules describing the movement of boids as an interaction between the individuals of one flock. The movement of each boid is influenced by

• Separation: The tendency of a boid to maintain a certain distance from the other boids within the visible range.

• Cohesion: The tendency of a boid to move to the average position of the boids within the visible range.

• Alignment: The tendency of a boid to align itself with the boids within the visible range with respect to orientation and velocity.

The three basic rules are applied to each boid and each flock within a certain radius. In the following, these rules of the Boids flocking algorithm are adapted to ADAS and are depicted in Fig. 3.

FIGURE 3.

Three main rules for boid movement within a flock. The $i$ -th boid, for which the rules are calculated for, is given in red color. All black boids belong to the same flock. In FMBOS, the black car is used as the leader if it is within the field of view of the specific boid.

We define the boids of the $j$ -th flock as $$\begin{equation*} \mathcal {B}_{j} = \left \lbrace{ \mathbf {b}_{1,j}, \mathbf {b}_{2,j},\ldots \mathbf {b}_{ N_{\mathrm {b}},j} }\right \rbrace\tag{1}\end{equation*}$$ with $j=1,\ldots, N_{\mathrm {f}}$ , where $N_{\mathrm {f}}$ is the number of flocks and $N_{\mathrm {b}}$ is the upper limit of boids within a flock. Each boid $\mathbf {b}_{i,j}$ contains the longitudinal and lateral position as well as velocity, and orientation. For the sake of readability, we omit the index $j$ of the flock, as boids do not contain flock-specific information, i.e., $\mathbf {b}_{i} = {[\mathbf {p}_{i}, \mathbf {v}_{i}, \Theta _{i}]}^{\mathrm {T}}$ , with $\mathbf {p}_{i} = {[p_{\mathrm {x},i}\, p_{\mathrm {y},i}]}^{\mathrm {T}}$ , $\mathbf {v}_{i} = {[v_{\mathrm {x},i}\, v_{\mathrm {y},i}]}^{\mathrm {T}}$ .

As can be seen in Fig. 3, the visible range of a boid (field of view, FoV) is modeled as an ellipse, opposed to typically a circular Section (cf. [9]), in order to consider the fact that vehicles are typically driving within the driving lanes. As a consequence, any boid that deviates too far laterally from the swarm is no longer considered by the swarm. The deviating boid may nevertheless perceive the swarm and is influenced by it in its movement.

Therefore, the set of boids, which are within the field of view of the $i$ -th boid, is given by $$\begin{equation*} \mathcal {B}_{\mathrm {FoV},i} = \left \lbrace{ \mathbf {b}_{j} \left |{ {\left ({\mathbf {p}_{j} - \mathbf {p}_{i}}\right)}^{\mathrm {T}} \mathbf {M}^{-1} \left ({\mathbf {p}_{j} - \mathbf {p}_{i}}\right) \leq 1 }\right. }\right \rbrace\tag{2}\end{equation*}$$ with $$\begin{align*} \mathbf {M}= \left [{\begin{array}{cc} \cos \Theta _{i} & - \sin \Theta _{i} \\ \sin \Theta _{i} & \cos \Theta _{i} \end{array}}\right] \left [{\begin{array}{cc} a^{2} & 0 \\ 0 & b^{2} \end{array}}\right] \left [{ \begin{array}{cc} \cos \Theta _{i} & -\sin \Theta _{i} \\ \sin \Theta _{i} & \cos \Theta _{i} \end{array}}\right]^{\mathrm {T}},\end{align*}$$ where the parameters of the ellipse are:

• $\Theta _{i}$ , the orientation angle of the boid given by $\mathrm {atan2}(v_{\mathrm {y},i}, v_{\mathrm {x},i})$ ; Note that the coordinate system according to ISO 8855 [21] is used, which means that the x-coordinate is in longitudinal and the y-coordinate in lateral direction (cf. Fig. 2).

• $a$ , the length of the first principal axis of the ellipse;

• $b$ , the length of the second principal axis of the ellipse.

• $| \mathcal {B}_{\mathrm {FoV},i}|$ , the cardinality of the subset: $N_{\mathrm {b, FoV}_{i}}$ . Note that the $i$ -th boid is not included in the set $\mathcal {B}_{\mathrm {FoV},i}$ ; therefore, $| \mathcal {B}_{\mathrm {FoV},i}| < | \mathcal {B}|$ .

In the following, the main steering rules are described.

A. Movement and Interaction Rules

Separation: Each boid has a tendency to keep a certain distance from the other boids in the flock, thus, avoiding a collision. This behavior ensures that the flock is spread both in longitudinal and lateral direction, effectively enlarging the field of view of the swarm. As described earlier, we assume that vehicles travel mainly within the driving lanes and the separation of the flock should also take this into account in the way that the boids have a larger separation in the longitudinal direction than in the lateral direction. However, this is not directly considered in the separation rule but in the weighting factor of the rule (cf. (9)). Several variations of the separation rule exists, whereas we follow the implementation of [22]: $$\begin{equation*} \mathbf {f}_{\mathrm {sep,}i} = - \sum _{j=1}^{ N_{\mathrm {b, FoV}_{i}}} \mathbf {p}_{i} - \mathbf {p}_{j}.\tag{3}\end{equation*}$$ This means, that the position of all boids visible to the $i$ -th boid is subtracted by the position of the $i$ -th boid.

Cohesion: Each boid is attracted towards the perceived center of the flock. This attraction counteracts the separation rule and causes the boids not to spread throughout the space. Otherwise, the boids would quickly lose the interaction with each other, due to the restricted field of view. The cohesion force is calculated by averaging the position of the $N_{\mathrm {b, FoV}_{i}}$ -boids and subtracting the result from the position of the $i$ -th boid: $$\begin{equation*} \mathbf {f}_{\mathrm {coh,}i} = \frac {1}{ N_{\mathrm {b, FoV}_{i}}} \sum _{j=1}^{ N_{\mathrm {b, FoV}_{i}}} \mathbf {p}_{j} - \mathbf {p}_{i}.\tag{4}\end{equation*}$$

Next to the attraction of each boid towards its perceived center of mass of the visible swarm, additional rules have been introduced in [9] with the rule Leader Following of particular interest, as it describes the tendency of a boid to move closer to a designated leader without actually overtaking the leader. In our proposed approach, each detected vehicle is a natural designated leader, which is followed by the boids of the corresponding swarm. Hence, the attracting force of the leader is given by $$\begin{equation*} \mathbf {f}_{\mathrm {lead,}i} = \mathbf {p}_{\mathrm {lead}} - \mathbf {p}_{i}.\tag{5}\end{equation*}$$

Alignment: Since every boid of a flock is supposed to follow the same designated leader, it stands to reason that eventually every member of the flock should have the same velocity. The alignment rule is calculated similarly to the cohesion rule, where the average of the perceived velocity is calculated first and the velocity of the $i$ -th boid is subtracted from it: $$\begin{equation*} \mathbf {f}_{\mathrm {ali,}i} = \frac {1}{ N_{\mathrm {b, FoV}_{i}}} \sum _{j=1}^{ N_{\mathrm {b, FoV}_{i}}} \mathbf {v}_{j} - \mathbf {v}_{i}.\tag{6}\end{equation*}$$

SECTION IV. Movement rules & Position Update Free-Moving Boids for Object Separation (FMBOS)

The previous movement rules belong to the generic Boid flocking algorithm. The focus in this chapter is on specific movement and update rules for the free-moving variant for object separation with multiple flocks.

A. Flock Repulsion Rule

An interaction between flocks is introduced in this paper, which is described by the flock repulsion behavior. The idea is that the repulsive forces of the neighboring flock support a clear separation of the boids and thus of the swarms, so that target discrimination is facilitated even if the object position is imprecise. The flock repulsion is denoted by $\mathbf {f}_{\mathrm {rep,}i}$ and is calculated in two steps.

First, the perceived center of the neighboring flock $k$ from the point-of-view of the $i$ -th boid is calculated by $$\begin{equation*} \mathbf {R}_{\mathrm {rep,}i}\left ({:,k}\right) = \frac {1}{ N_{\mathrm {b, FoV}_{k}}} \sum _{j=1}^{ N_{\mathrm {b, FoV}_{k}}} \mathbf {p}_{j}.\tag{7}\end{equation*}$$ Note here, that multiple flocks, for example on the left and right lane, can be perceived by one boid. It follows that the perceived center of mass of the neighboring swarms $\mathbf {R}_{\mathrm {rep,}i}$ are represented in a matrix of size $[2 \times N_{\mathrm {f,}i}]$ , with $N_{\mathrm {f,}i}$ the number of visible flocks by the $i$ -th boid.

The repulsing force can then be calculated with an exponential function whose value is exponentially decreasing with increasing distance of the swarms, with $$\begin{align*} \mathbf {f}_{\mathrm {rep,}i} = \left [{ \begin{array}{l} 0 \\ \sum _{j=1}^{ N_{\mathrm {f,}i}} \pm \exp \left ({\boldsymbol{\gamma }_{\mathrm {rep}}- |p_{y,i} - r_{\mathrm {rep,i,y,j}}|}\right) \end{array} }\right]\tag{8}\end{align*}$$ where the sign ± depends whether the flock is on the left or right side, respectively, and $r_{\mathrm {rep,i,y,j}}$ refers to the y-position in the $j$ th column of the matrix $\mathbf {R}_{\mathrm {rep,}i}$ . The value of the factor $\boldsymbol{\gamma }_{\mathrm {rep}}$ is chosen so that the repulsive force is close to zero when the swarms have a distance of approximately one lane width. Contrary to the other rules, the repulsing flock rule has a strong effect on the position of the boids when the distance is small. The rule is exemplary depicted in Fig. 4. Note here, that the flock repulsion is only carried out in lateral direction.

FIGURE 4.

Exemplary illustration of the flock repulsion rule for two flocks shown in grey and black color. The red boid, which belongs to the grey flock, uses the average position of the observed black flock.

B. Position Update Free-Moving Boids

The presented five behavioral rules are combined in an updated velocity vector $\mathbf {v}^{\prime} _{i}$ of the $i$ -th boid and added to the velocity vector $\mathbf {v}_{i}$ of the previous cycle: $$\begin{align*} \mathbf {v}^{\prime} _{i}=&\mathbf {v}_{i} + \mathbf {w}_{\mathrm {coh,}i} \odot \mathbf {f}_{\mathrm {coh,}i} + \mathbf {w}_{\mathrm {lead,}i} \odot \mathbf {f}_{\mathrm {lead,}i} + \mathbf {w}_{\mathrm {ali,}i} \odot \mathbf {f}_{\mathrm {ali,}i} \\&{} + \mathbf {w}_{\mathrm {sep,}i} \odot \mathbf {f}_{\mathrm {sep,}i} + \mathbf {w}_{\mathrm {rep,}i} \odot \mathbf {f}_{\mathrm {rep,}i},\tag{9}\end{align*}$$ where the weighting factor $\mathbf {w}_{\mathrm {rep,}i}$ for the repulsive behavior is given by $\mathbf {w}_{\mathrm {rep,}i} = [{0, 1}]^{\mathrm {T}}$ . The remaining weighting factors are optimized heuristically and the chosen values can be found in Tab. 1.

TABLE 1 Parameters of the FMBOS as Well as FCBOS Flocking Algorithm

Given the updated velocity vector, the new position of the $i$ -th boid can be calculated straightforward by $$\begin{equation*} \mathbf {p}^{\prime} _{i} = \mathbf {p}_{i} + \mathbf {v}^{\prime} _{i} \cdot \Delta t.\tag{10}\end{equation*}$$

C. Life Cycle of Boids

Unlike other publications using Boids flocking algorithm, it is assumed in this paper, that boids have a rather short lifetime, meaning a boid is spawned and will be eventually removed from the flock within a fixed duration of a few hundred update cycles, whereas each cycle is assumed to have a duration of about 80 ms.

As soon as a lead vehicle is consistently tracked, boids will be spawned by the lead vehicle every cycle until $N_{\mathrm {b}}$ boids per flock exist. The position of the lead-vehicle as well as the lateral and longitudinal velocity from the previous cycle will be provided to the new boid and serve as initial values. Boids which exceed their defined lifetime will be replaced by newly spawned boids.

It may occasionally happen that boids lose their connection to the swarm due to the restricted field of view. Thus, they are no longer guided by their leader and/or the flock. However, the distribution of the swarm should, on the one hand, be oriented to the position of the designated leader and, on the other hand, adapt to the structured driving within the lanes. Because of the mechanism of the restricted lifetime, no additional sanity checks are required for a boid, as its influence on the average position is limited.

D. Reachability Analysis with Dubins Path

Simulating the movement of the boids of each flock according to (9) and (10), it can be seen that the resulting path of each boid is only $G0$ -continuous and that boids may “jump” sideways. In order to constrain the movement of boids and keeping in mind that boids shall follow vehicles with non-holonomic constraints, the reachability of the updated position of a boid is checked by a path generated using a Dubins path [23]. Dubins paths consist only of straight paths (‘S’) and curve segments with a restricted radius, i.e., left curve (‘L’) and right curves (‘R’), respectively.

The minimum radius $r_{\mathrm {min}}$ is given by the longitudinal velocity $v$ and a fixed maximum lateral acceleration $a_{\mathrm {lat, max}}: r_{\mathrm {min}}= {v_{\mathrm {long}}^{2}}/{ a_{\mathrm {lat, max}}}$ .

The maximum lateral acceleration for each boid is chosen to be $9 \mathrm {m}/\mathrm {s}^{2}$ , which results in a radius of about 60 m at a velocity of 23 m/s. To calculate a Dubins path from the current position to the updated target position of a boid, the start and target pose need to be determined, whereas the orientation angles of start $\Theta _{i}$ and target pose $(\Theta _{i}^{\prime})$ of a boid are calculated by $$\begin{equation*} \Theta _{i} = \mathrm {atan2}\left ({\mathbf {v}_{\mathrm {y},i}, \mathbf {v}_{\mathrm {x},i}}\right),\; \Theta _{i}^{\prime} = \mathrm {atan2}\left ({\mathbf {v}^{\prime} _{\mathrm {y},i}, \mathbf {v}^{\prime} _{\mathrm {x},i}}\right)\tag{11}\end{equation*}$$ which yields $\boldsymbol{\xi }_{i} = {[p_{\mathrm {x},i}, p_{\mathrm {y},i}, \Theta _{i}]}^{\mathrm {T}}$ . With the given start and target pose as well as maximum radius, the resulting Dubins path will be evaluated. Exemplary evaluations are depicted in Fig. 5, whereas valid paths are given in green and invalid paths in red. It can be seen that as soon as detours are required to reach the target pose, this pose is discarded either due to its position and/or orientation. Instead, in an iterative process, the target pose is changed in both position as well as orientation within a small radius — and thus speed in lateral and longitudinal direction — until the target pose can be reached without detours or until a maximum number of iterations is reached.

FIGURE 5.

Exemplary illustration of resulting Dubins paths.

E. Potential Applications for Driver-Assistance Systems

A common problem with low-cost sensors, due to a reduced resolution, is that the position of the tracked object is often not accurate, especially when two traffic participants are driving in parallel with almost the same velocity. This may lead to a false lane association, target lane change prediction or a complete object loss in the SIT module and, as a result, a false vehicle reaction.

The main advantage of the free-moving boid approach lies within the additional information generated by the interaction between boids with the same flock as well as different flocks.

Due to the flock-repulsion rule, the average position of a flock remains clearly separated when two flocks are in parallel, i.e., two traffic participants are driving in parallel. The problem of insufficient target discrimination is that the behavior of TPs can no longer be predicted from their kinematic information alone. This means that whether a TP performs a lane change or stays within its lane cannot be determined by its position and/or lateral velocity/acceleration alone in case of insufficient target discrimination. False lane associations and/or prediction of lane change maneuvers can thus be improved, by considering the average positions of flocks. Specifically, as an indicator for the target separation the average distance between two flocks can be calculated by $$\begin{equation*} \mathbf {d}_{ij} = \frac {1}{ N_{\mathrm {b}}} \left ({\sum _{i=0}^{ N_{\mathrm {b}}} \mathbf {p}_{i} - \sum _{j=0}^{ N_{\mathrm {b}}} \mathbf {p}_{j} }\right).\tag{12}\end{equation*}$$

Moreover, the upcoming revisions of driver assistance systems are accompanied by increased performance requirements. For example, the second series of amendments to UN Regulation No. 131 (Advanced Emergency Braking Systems) significantly reduces the timing to initiate an emergency brake in specific scenarios [24]. In order to provide an early reaction while minimizing the false positive brake events, the system has to plausibilize the target movement, especially in adverse scenarios. Such dynamic maneuvers of a traffic participant, even without other traffic participants, are visible within the position and velocity distribution of boids within the same flock. By using this information, a criticality threshold of a maneuver can be generated.

The underlying assumption is, that the distribution of the longitudinal velocity of the boids follows a stationary process. The movement and interaction rules maintain a uniform distribution of boids in a flock. This assumption is valid as long as the acceleration of the leading vehicle is approximately stationary. To determine the distribution, the variance of the longitudinal velocity for a flock is derived over several cycles and denoted as $\boldsymbol{\sigma }^{2}_{\mathrm {stat}}= [\sigma ^{2}_{t=-n},\sigma ^{2}_{t=-n+1},\ldots, \sigma ^{2}_{t=-1}]$ .

In dynamic maneuvers of the TP this assumption is no longer valid. The following boids are pushed back more strongly during the dynamic braking of the TP, whereby the instantaneous variance deviates significantly from the stationary variance $\boldsymbol{\sigma }^{2}_{\mathrm {stat}}$ . A maneuver of a TP can therefore be classified as critical if the following condition holds $$\begin{align*} \mathrm {M}_{\mathrm {crit}}= \left \lbrace{ \begin{array}{llllll} 1, & {\mathrm{ if }} \sigma _{t=0}^{2} \geq \mathrm {E}(\boldsymbol{\sigma }^{2}_{\mathrm {stat}}) + 3\cdot \mathrm {Var}(\boldsymbol{\sigma }^{2}_{\mathrm {stat}}) \\ 0, & {\mathrm{ else. }} \end{array} }\right.\tag{13}\end{align*}$$

SECTION V. Movement Rules & Position Update Formation-Controlled Boids for Object Selection (FCBOS)

The underlying idea is to use the emergent behavior of a boid flock in order to facilitate the task of the object-of-interest (OOI) selection in arbitrary driving scenarios within structured environments (e.g., highways). For this purpose, a single flock of boids is generated in a longitudinally- and laterally-aligned formation similar to the OOIs (cf. Fig. 2). The boids align and distribute themselves using behavior rules like the previously defined rules. While the boids move and interact according to these behavior rules, each boid checks whether there is a traffic participant (TP) in its immediate vicinity, which is defined as an ellipse around the boid. If this is the case, that TP is assigned an OOI position by the corresponding boid in the swarm.

A. Vehicle Model & Preliminaries

In order to preserve a pre-defined structure of a flock, often the movement of boids is modeled with kinematic constraints (e.g., [10], [11]). A common approach to model the motion of car-like vehicles is to use the so-called single track model, which presents a good trade-off between the accuracy and the complexity of the model [13], [25], [26]. The basic model consists of two wheels connected by a rigid link, as can be seen in Fig. 6. It is assumed that the wheels do not slip at their contact point, hence, a lateral movement is only possible by turning the front wheel and simultaneously driving forward or backward.

FIGURE 6.

Geometry of the bicycle model.

The model has three state variables: the orientation $\Theta _{i}$ and the 2D-position $p_{x,i}$ , $p_{y,i}$ . As discussed in [27], the position of the model is defined as the position of the middle of the front wheel. The velocity $v_{B,i}$ and the steering angle $\phi _{i}$ are input variables which influence the movement of the individual boids. As a result, the motion of a boid in combination with the bicycle model can be described by [25]: $$\begin{align*} v_{\mathrm {x},i}=&\mathit {v}_{i} \cos \left ({\Theta _{i} + \phi _{i}}\right) \\ v_{\mathrm {y},i}=&\mathit {v}_{i} \sin \left ({\Theta _{i} + \phi _{i}}\right) \\ \dot {\Theta }_{i}=&\frac { \mathit {v}_{i}}{L_{\mathrm {B}}} \sin \left ({\phi _{i}}\right).\tag{14}\end{align*}$$

A position update of a boid is no longer calculated by changing the velocity vector $\mathbf {v}^{\prime} _{i}$ and position vector $\mathbf {p}^{\prime} _{i}$ directly, as described by (9) and (10). Instead, the front wheel velocity $\mathit {v}_{i}$ and the steering wheel angle $\phi _{i}$ are adapted.

The boid flock is initialized with as many boids as lanes are available. Without loss of generality, three lanes with three aligned boids are shown in the left part of Fig. 7. The initial distance between the boids, and hence between lanes is set to $d_{\mathrm {lat,init}}$ .

FIGURE 7.

Visualization of a boid formation and trace points of a traffic participant.

Traces of the moving TPs are used as additional input to the formation-controlled boid flock (cf. right part of Fig. 7). The position of a TP is sampled every $\Delta t_{\mathrm {s}}$ up to a maximum time duration of $t_{\mathrm {max}}$ . Consequently, a maximum of $w_{\mathrm {max}}=t_{\mathrm {max}}/\Delta t_{\mathrm {s}}$ trace points $(x^{T}_{n,w}, y^{T}_{n,w})$ are accumulated for the trace of the $n$ -th TP. The field of view of a boid is again assumed to be ellipsoid as defined in (2), however, the range restriction is only applied for the selection of trace points and/or traffic participants. That means, neighboring boids can see each other without range restriction, while the boid after the next boid is no longer visible, regardless of range. The number of neighboring boids of the $i$ -th boid and the number of visible trace points combined with the number of visible TPs, respectively, is given by $N_{\mathrm {b,}{i}}$ and $N_{\mathrm {TTP, FoV}_{i}}$ . Hereby, the number of neighboring boids is 1 when the $i$ -th boid is on the outer lane, and 2 when the $i$ -th boid is on an inner lane.

Furthermore, in order to calculate the distances with respect to other boids as well as trace points and traffic participants, a transformation of the ego-vehicle-centered coordinate system to the boid-centered coordinate system is required: $$\begin{align*} \mathbf {p}_{j,i}^{\mathrm {B}} = \left [{ \begin{array}{rr} \cos \left ({\Theta _{i} + \phi _{i}}\right) & \sin \left ({\Theta _{i} + \phi _{i}}\right) \\ -\sin \left ({\Theta _{i} + \phi _{i}}\right) & \cos \left ({\Theta _{i} + \phi _{i}}\right) \end{array} }\right] \cdot \left ({\mathbf {p}_{j} - \mathbf {p}_{i}}\right).\tag{15}\end{align*}$$ The boid-centered coordinate system is depicted in Fig. 8.

FIGURE 8.

Illustration of the boid-centered coordinate system with three boids.

B. Movement and Interaction Rules

The movement rules for the formation-controlled boids are similar but not equal to the already presented rules. However, they still follow the same concept of alignment, cohesion, and separation but require different inputs.

Alignment: The alignment rule shall minimize the longitudinal distance between boids. By calculating the average of the perceived velocity considering only the neighboring boids and subtracting the velocity of the $i$ -th boid, the weighting factor for the velocity update is calculated according to $$\begin{equation*} \Delta v_{\mathrm {B},i}^{\prime } = \frac {1}{ N_{\mathrm {b,}{i}}} \sum _{j=1}^{ N_{\mathrm {b,}{i}}} \frac {p_{\mathrm {x},j,i}^{\mathrm {B}}}{\Delta t}.\tag{16}\end{equation*}$$ However, the weighting factor $\Delta v_{\mathrm {B},i}$ cannot be used directly for a velocity update, because the motion of the boids would become very unstable. To mitigate this effect, the velocity update is stabilized with a simple PD-controller: $$\begin{equation*} v^{\prime} _{i} = \mathit {v}_{i} + \mathrm {P}_{v} \cdot \Delta v_{\mathrm {B},i}^{\prime } + \mathrm {D}_{v} \cdot \left ({\Delta v_{\mathrm {B},i}^{\prime } - \Delta v_{\mathrm {B},i} }\right).\tag{17}\end{equation*}$$

Cohesion & Separation: Since the boid flock is supposed to stay in a predefined formation, the two movement rules cohesion and separation are strongly coupled and depend mainly on two inputs. First, the lateral deviation of the initial distance $d_{\mathrm {lat,init}}$ shall be minimized by adapting the steering angle. Second, boids shall follow trace points as they indicate a likely road course. The two rules are based on the assumption that lanes run in parallel if no other information is available, thus relying only on the predefined initial distance. Once information is available in the form of trace points within the field of view of a boid, the lateral distance between boids may deviate from the initial distance.

The necessary steering angle change to minimize the difference to the initial lateral distance is calculated by the arcsine from the lateral deviation of the neighboring boids to $d_{\mathrm {lat,init}}$ divided by the traveled longitudinal distance given by $v^{\prime} _{i}\cdot \Delta t$ : $$\begin{align*} \Delta \phi _{\mathrm {B,i}}^{\prime } = \left \lbrace{ \begin{array}{ll} \mathrm {arcsin}\left ({\frac {p_{\mathrm {y},i+1,i}^{\mathrm {B}} + d_{\mathrm {lat,init}}}{ v^{\prime} _{i} \cdot \Delta t}}\right), & i=1 \\ \mathrm {arcsin}\left ({\frac {1/2 \cdot \left ({p_{\mathrm {y},i+1,i}^{\mathrm {B}} + p_{\mathrm {y},i-1,i}^{\mathrm {B}}}\right)}{ v^{\prime} _{i} \cdot \Delta t}}\right), & 1 < i < N_{\mathrm {b}}\\ \mathrm {arcsin}\left ({\frac {\left ({p_{\mathrm {y},i-1,i}^{\mathrm {B}} - d_{\mathrm {lat,init}}}\right)}{ v^{\prime} _{i} \cdot \Delta t}}\right), & i = N_{\mathrm {b}}. \end{array}}\right.\tag{18}\end{align*}$$ Analog to the considerations for the alignment rule, a PD-controller is also used to stabilize the change of the steering angle: $$\begin{equation*} \phi _{\mathrm {B,i}} = \mathrm {P}_{ \phi _{\mathrm {B}}} \cdot \Delta \phi _{\mathrm {B,i}}^{\prime } + \mathrm {D}_{ \phi _{\mathrm {B}}} \cdot \left ({\Delta \phi _{\mathrm {B,i}}^{\prime } - \Delta \phi _{\mathrm {B,i}}}\right).\tag{19}\end{equation*}$$

The influence of the trace points of an object as well as the object position itself on the update of the steering angle is described in the following. All trace points $\mathbf {p}_{n,:}^{\mathrm {T}}$ and all object positions $\mathbf {p}_{n}^{\mathrm {TP}}$ , which are within the field of view of the $i$ -th boid are considered. The average of these $N_{\mathrm {TTP, FoV}_{i}}$ position information is calculated and the necessary change in the steering angle is calculated by $$\begin{align*} \Delta \phi _{\mathrm {T,i}}^{\prime }=&\mathrm {atan2}\left ({\frac {\sum _{j=1}^{ N_{\mathrm {TTP, FoV}_{i}}} p_{\mathrm {y},j}}{ N_{\mathrm {TTP, FoV}_{i}}},\frac {\sum _{j=1}^{ N_{\mathrm {TTP, FoV}_{i}}} p_{\mathrm {x},j}}{ N_{\mathrm {TTP, FoV}_{i}}}}\right) \\=&\mathrm {atan2}\left ({\sum _{j=1}^{ N_{\mathrm {TTP, FoV}_{i}}} p_{\mathrm {y},j},\sum _{j=1}^{ N_{\mathrm {TTP, FoV}_{i}}} p_{\mathrm {x},j}}\right).\tag{20}\end{align*}$$

As before, the update of the steering angle is stabilized by a PD-controller: $$\begin{equation*} \phi _{\mathrm {T,i}} = \mathrm {P}_{ \phi _{\mathrm {T}}} \cdot \Delta \phi _{\mathrm {T,i}}^{\prime } + \mathrm {D}_{ \phi _{\mathrm {T}}} \cdot \left ({\Delta \phi _{\mathrm {T,i}}^{\prime } - \Delta \phi _{\mathrm {T,i}}}\right)\tag{21}\end{equation*}$$

Contrary to the velocity update of the free-moving boid flock (cf. (9)), it is not beneficial to have a weighted combination of the two steering angle updates. Instead, a prioritization is used in favor of the steering angle update based on the trace points $\phi _{\mathrm {T,i}}$ . If there are no trace points and/or TPs in the field of view of a boid, only $\phi _{\mathrm {B,i}}$ is applied as an update for the steering angle, else the boids should follow the trace points and/or TPs, hence $\phi _{\mathrm {T,i}}$ should be used as an update for the steering angle. This type of prioritization may lead to undesirable behavior where a boid falsely performs a lane change due to a lane change of a TP by following the corresponding trace points.

In order to prevent this behavior, two measures are implemented: First, the update of the steering angle based on trace points and TPs is only considered when at least two traces can be used within the flock for the generation. Second, the two steering angle updates, $\phi _{\mathrm {B,i}}$ and $\phi _{\mathrm {T,i}}$ , are compared with each other and, if the deviation is greater than a maximum steering angle $\Delta \phi _{\mathrm {max}}$ , $$\begin{align*} \delta _{i} = \left \lbrace{ \begin{array}{ll} 1, & {\mathrm{ if }} | \phi _{\mathrm {T,i}} - \phi _{\mathrm {B,i}}| > \Delta \phi _{\mathrm {max}}\\ 0, & {\mathrm{ else }}\end{array}}\right.,\tag{22}\end{align*}$$ only the steering angle update provided by the lateral deviation of the initial distance is considered and the prioritization is overridden, according to $$\begin{equation*} \phi _{i}^{\prime} = \phi _{i} + \delta _{i} \cdot \phi _{\mathrm {B,i}} + \left ({1-\delta _{i}}\right) \cdot \phi _{\mathrm {T,i}}.\tag{23}\end{equation*}$$ Additionally, it showed beneficial to leave the prioritization suspended for some cycles.

The prioritization between initial distance and trace information relies on the assumption that at least one boid in the flock is using the trace information and thereby guiding the remaining boids of the flock in the desired direction of other traffic participants.

In order to guide the flock even when all boids in the flock have no trace points or TPs in their field of view, the update of the steering angle is calculated based on the angle for the flock to move along a circle with a common instantaneous center of rotation for the average position of the traffic participants which are still in front of the flock and the average position of all boids in the flock: $$\begin{equation*} \phi _{g} \approx \arcsin \left ({\frac {2 \cdot L_{B}\cdot p^{\mathrm {TP}}_{\mathrm {y},m}}{{\left ({\mathbf {p}_{m}^{\mathrm {TP}}}\right)}^{\mathrm {T}} \mathbf {p}_{m}^{\mathrm {TP}}} }\right)\tag{24}\end{equation*}$$ with averaged position of all $N_{\mathrm {TP}}$ TPs transformed into the coordinate system created by averaging positions and angles of all boids in the flock $$\begin{equation*} \mathbf {p}_{m}^{\mathrm {TP}} = \frac {1}{N_{\mathrm {TP}}} \sum _{j=1}^{N_{\mathrm {TP}}} \mathbf {p}_{j}^{\mathrm {TP}}.\tag{25}\end{equation*}$$

C. Potential Application for Driver-Assistance Systems

As previously mentioned, the FCBOS approach can be well used to identify the objects-of-interest for an ADAS system (cf. Fig. 2). During each update cycle of the environment model, a swarm is initialized at the longitudinal position of the ego vehicle and simulated for a maximum time $t_{\mathrm {max}}$ . In each update step of the FCBOS simulation, the new position of each boid is calculated based on the behavioral rules and the underlying bicycle model.

The initial velocity $\mathit {v}_{i}$ of the $i$ th boid is chosen such that, in combination with the maximum simulation time $t_{\mathrm {max}}$ and the simulation step time $\Delta t$ , the assumed maximum sensor range of the ego vehicle is covered.

The boids thus traverse the course of the road, guided by trace points and/or road users. A traffic participant is associated with the respective OOI position whenever it enters the field of view of a boid. The specific OOI position is determined by the respective lane on which the corresponding boid is located.

The simulation of the boids is repeated in each update cycle of the environment model.

SECTION VI. Numerical Results

Two different sets of scenarios are considered for the investigation of the FMBOS and FCBOS variants, respectively. All scenarios are implemented in MATLAB using the Automated Driving Toolbox [28]. A standard sensor setup for advanced driver assistance systems is chosen for the ego vehicle, comprising a long range radar as well as a monocular camera. The objects of each sensor are tracked by a linear Kalman filter using a constant velocity and constant acceleration model. Subsequently, a multi-sensor multi-object tracker with a global nearest neighbor assignment is used to provide a single tracked object for each ground truth object.

Obviously, this setup describes a baseline fusion approach and can be well improved by using more sophisticated methods. However, the baseline approach is commonly used in ADAS functions oriented for the mass market.

The first scenario is a common curve-entry scenario for a two-lane road and is depicted in Fig. 9. The ego vehicle, driving on the right lane with an initial velocity of $v_{\mathrm {ego}} = 40\text{m}$ /s, approaches a slower vehicle on the same lane (ID:1) which drives with a velocity of $v_{\mathrm {TP1}}=30\text{m}$ /s. During the approach, the ego vehicle decelerates and maintains a headway distance of about 36m, which results in a timegap of $T_{\mathrm {G}} = d / v_{\mathrm {ego}} = 1.2\text{s}$ ; a typical headway distance of an ACC system. Simultaneously, the two vehicles approach a truck on the left lane (ID:2) with a relative velocity of $v_{\mathrm {rel}} = 6\text{m}$ /s. At about the apex of the curve, the rear bumper of the truck is aligned with the rear bumper of the first target.

FIGURE 9.

Scenario of a curve-entry with a 500m long straight Section followed by a left turn with a radius of 300m.

This scenario is particularly challenging for the environment model because the two vehicles are driving with a narrow lateral distance at a similar velocity and are observed under an angle while driving through the curve. As a result, the separation of the radar reflections from the two objects is challenging, which results in a lateral shift of the radar object towards the other object. A fusion with the camera object is not always able to mitigate this effect, as can be observed as well in the simulation results. The parameters of the FMBOS variant have been tuned empirically by observing the behavior of the flock of boids following their leader and are summarized in the upper part of Table 1. The goal is to allow the boids of each flock to laterally spread out to approximately one lane-width. The longitudinal spread of the flock needs to be restricted in order to not exceed the field-of-view and to restrict interference with following boids of other flocks in the same lane.

As mentioned in Section IV-E, the intention of the FMBOS is not to determine a better estimate of the ground truth position compared to the tracked objects but to mitigate the shortcomings of the sensors by providing additional information about the relative position of the two vehicles. Hence, the average lateral distance between the vehicles (ID:1 and ID:2) is taken as a measure for the target discrimination.

The numerical results for the object separation with FMBOS are shown in Fig. 10 for various lateral offsets between the trajectories of the targets ID:1 and ID:2. The distributions are generated from 100 simulation runs using an identical parameter set. The difference between runs is solely due to simulated sensor noise. Hereby, the target ID:1 and the ego vehicle drive in the center of the right lane and the lateral position of the truck driving in the left lane is shifted correspondingly. For each lateral offset two violin plots are given. Violin plots combine a boxplot with the probability distribution, which allows for a better comparison of the two setups [29]. The first violin plot, in red and blue color, depict the lateral separation determined by the boid flocks (in blue) and determined by the tracked objects (in red). Additionally, the lateral separation of the ground truth objects is given with the black violin plot, which is shifted to the right side in order to improve readability. The median of the distribution is represented by the black horizontal line in the center of the notch, whereas the mean value is denoted by the black star. Correspondingly, first and third quantile are represented by the borders of the dark colored area, while the light-colored region ranges from the first to the $99^{th}$ percentile.

FIGURE 10.

Split-violin plots for the distribution of the lateral distance between vehicles on left and ego lane. Lateral distance of boids in blue (left violin), lateral distance of tracked objects (i.e., inputs) in red (right violin), and lateral distance of ground truth objects in black. To improve readability, the black violin plots are shifted to the right side.

The results in Fig. 10 were generated when the two objects had a longitudinal distance of ±12m, as the effect of poor target discrimination only occurs when at least two objects are within close range. It can be clearly seen that the median of the lateral distance of both the TPs and the boids is well below the ground truth distribution. From the probability density function of the TPs, it can be observed that the median decreases to a lateral distance close to 0m with decreasing lateral distance between the two objects. As a consequence, based on the kinematic information, the two TPs would have to drive one behind the other, while the real objects were still laterally separated according to the specific setting. In the selected scenario, most of the radar reflections are from the side of the truck, resulting in a strong lateral offset of the radar object, which is not fully compensated by the camera object. In contrast, the median lateral distance of the boids is always above that of the TPs. Also, the distribution corresponds to a bimodal distribution, which is most pronounced for the ground truth lateral distance of 2.75m. This behavior is reasoned in the separation rule of the boids, which, as long as one swarm is in the field of view of the other swarm, maintains the lateral distance of the two swarms. As the longitudinal distance between the two objects increases, the swarm is more attracted to the TP lead object compared to the repulsive forces of the other swarm. In any case, the average lateral distance between flocks clearly indicate that the two TPs are not driving one after the other but parallel to each other.

The criticality for the FMBOS variant described in Section IV-E (13) is illustrated with the help of two NCAP scenarios (i.e., Car-to-Car Rear braking: CCRb with an initial distance of 12m and 40m). Both, ego vehicle and target vehicle are driving at a constant velocity of 50 kph. During the follow drive, the front vehicle brakes with an acceleration of $-2\text{m}/\text{s}^{2}$ and the ego vehicle comes closer until the collision occurs. For the criticality indicator to be used meaningfully, the threshold may only be exceeded in critical scenarios. The acceleration as well as distance are given in Fig. 11 for 12m distance and Fig. 12 for 40m distance, respectively. Whenever the criticality threshold $\mathrm {M}_{\mathrm {crit}}$ is fulfilled, the value is set to 1 for the dashed line. It can be seen that the criticality threshold is exceeded at the later end of both use cases. However, this is not directly an indicator of an imminent collision but an indicator of a strong and sufficiently long brake event to disturb the flock. As a consequence, few false acceleration values of a tracked vehicle can easily be classified as such, potentially preventing a false emergency brake event.

FIGURE 11.

NCAP CCRb −2m/s², initial distance=12m.

FIGURE 12.

NCAP CCRb −2m/s², initial distance=40m.

The performance of the FCBOS variant is evaluated in the same curve entry scenario with the true positive selection rate of the OOIs. The parameters of the FCBOS variant have been optimized using Bayesian Optimization provided by the STATISTICS AND MACHINE LEARNING TOOLBOX of MATLAB and are summarized in the lower part of Table 1. Each parameter set was evaluated in 4800 test scenarios which include, among others, driving straight ahead, driving around curves and changing lanes with varying positions as well as velocities of each object. The loss function was chosen to minimize the number of false positive OOI-selection over all scenarios. As described in Section V-C, the traffic participants are associated to OOIs, which means, for example, that the first object in the ego lane becomes OOI-0 (cf. Fig. 2). The correct associations of all objects are counted in each cycle and an average over 100 runs is generated for each predefined lateral distance of the objects. For comparison, a simple lane association was implemented based on the tracked objects, which assigns an object to the lane on which the object is located with at least 50% overlap. Two variants were investigated: First, the road course was taken as given (perfect course trajectory, pct) and second, the course was predicted based on the traces of the objects (trace course trajectory, tct). The equivalent true positive selection rate was generated for both variants for comparison. The corresponding results are given in Table 2. As can be seen from these results, the FCBOS-OOI-selection is for most cases slightly better than the lane association with a perfect course trajectory and outperforms the lane association based on a trace trajectory with more than 23% correct associations.

TABLE 2 True Positive Performance for OOI-Selection with FCBOS Compared to TPs With Perfect Course Trajectory, and TPs With Predicted Course Trajectory

SECTION VII. Conclusion

Two different variants of the Boids flocking algorithm were presented to be used in driver assistance systems.

The FMBOS Boids flocking algorithm was evaluated for the task of target discrimination. By creating an individual flock for each detected vehicle, together with the presented movement rules for boids, the simulation results show that the target separation of individual vehicles is consistently improved.

The average lateral position information of a swarm can be used either for lane assignment or to improve lane change detection in low-cost driver assistance systems. In addition, a new criticality measure was developed in this variant based on the distribution of boids within a swarm, which allows the identification of critical brake events.

The FCBOS variant, on the other hand, is able to generate semantic neighborhood relations and reliably select the so-called objects-of-interests. The newly developed motion rules of the formation-controlled boids can compensate for the imprecise position of traffic participants and the resulting poor trajectory prediction. In the scenarios investigated, a consistently high selection performance is achieved.

Although earlier and more stable responses are possible with the FMBOS and FCBOS variants, not all problems within an ADAS system can be addressed. For example, it is assumed that objects are not completely missed by the sensors. Likewise, latencies in detection cannot be corrected, so problems such as string stability in convoy driving are not improved.