Using collision cones to assess biological deconfliction methods

Abstract

Biological systems consistently outperform autonomous systems governed by engineered algorithms in their ability to reactively avoid collisions. To better understand this discrepancy, a collision avoidance algorithm was applied to frames of digitized video trajectory data from bats, swallows and fish (Myotis velifer, Petrochelidon pyrrhonota and Danio aequipinnatus). Information available from visual cues, specifically relative position and velocity, was provided to the algorithm which used this information to define collision cones that allowed the algorithm to find a safe velocity requiring minimal deviation from the original velocity. The subset of obstacles provided to the algorithm was determined by the animal's sensing range in terms of metric and topological distance. The algorithmic calculated velocities showed good agreement with observed biological velocities, indicating that the algorithm was an informative basis for comparison with the three species and could potentially be improved for engineered applications with further study.

Keywords: animal behaviour; collision avoidance algorithm; collision cones; multi-species comparison; nonlinear control; velocity obstacles.

Figure 1.

Trajectories of 20 bats emerging from their cave (blue-green lines; data point colour indicates frame number) and static objects within the frame (red lines). Trajectories of the same colour were present concurrently. Data are shown before smoothing was applied.

Figure 2.

Trajectories of 43 cliff swallows from one bridge site recording. Each colour represents an individual animal's trajectory.

Figure 3.

Trajectories of giant danio (blue-green lines) depicted within their fish tank (red surfaces); shown are (a) untrained giant danio prior to the food stimulus and (b) trained giant danio after the food stimulus. Each colour and line represents an individual animal's trajectory; all animals were present throughout the recording.

Figure 4.

In the zonal model, radii around the focus animal (black) define the type of interaction with other animals: those within d_r (red) are repulsive, those between d_r and (blue) are neutral or aligning, and those between and d_a (green) are attractive. Animals outside of d_a (grey) are not sensed or are ignored.

Figure 5.

In the topological distance model, a set of animals nearest the focal animal (black) is considered to comprise influential neighbours (green). Animals outside this inner grouping (grey) are not considered by the focal animal.

Figure 6.

The grey cone with dashed borders depicts the anatomy of a collision cone for an agent that is not in a conflict: indicates that falls outside the collision cone. The blue cones with solid borders depict collision cones for agents in conflict; potential optima are shown that are within the maximum velocity constraint (cyan) and as well as those that are infeasible (grey) at locations 1 and 2 on a single collision cone (open and closed circles, respectively) and location 3 on the intersection of collision cones (square).

Figure 7.

The sequence of figures (progressing from left to right) shows the evolution of an encounter with one agent (blue, solid arrows) using the DRCA algorithm to avoid conflict with another agent (red, open arrows). Figures (a–c) are in velocity space showing the collision cones for the scenarios depicted in position space in figures (d–f). The circles shown in velocity space correspond to the momentary speed of the agent following DRCA; the green highlighted arcs indicate safe velocities while the regions within the collision cones correspond to unsafe velocities, denoted in position space by the hashed region.

Figure 8.

Side and overhead view of two swallow trajectories (blue markers indicate positions, with colour indicating frame number) including a series of conflicts (red circled points). The DRCA optimal velocities without acceleration bounds are shown as exaggerated lines for correlated (black) and uncorrelated (grey) frames.

Figure 9.

The per cent correlation for each species with (darker bar with border on the right) and without (lighter bar on the left) acceleration limits applied to the DRCA optimal velocity. The error bars indicate one standard deviation above and below the mean per cent correlation (error values above 100% are not shown).

Figure 10.

The per cent correlation as a function of for bats (blue dashed), birds (green dashed-dot) and fish (red solid) with (thin line) and without (thick line) acceleration limits applied to the DRCA optimal velocity; markers indicate values that appear in figures 9 and 11. The x-axis is scaled by the standard deviation for each species, which is 2 m s⁻¹ for the flying species and 0.04 m s⁻¹ for the fish.

Figure 11.

The per cent correlation for bats (blue squares with dashed line), birds (green circles with dashed-dot line) and fish (red triangles with solid line) without acceleration limits applied to the DRCA optimal velocity for each species for a range of maximum topological distances ranging from one to all possible animals within the metric range (3 m for flying species and 0.3 m for fish).