CASCADE

Scaling up to safe, effective, and efficient air navigation for high density drone traffic

The image of a future city with complex dense air traffic patterns like those we see on roads is a common one in science fiction. With road networks often filled to capacity it is natural to think of moving traffic into 3d space. But whilst the technology of drones and personal air vehicles is moving ahead swiftly, we are in danger of transferring the traffic jams we experience on the road network to the sky network. Previous research has looked at understanding the future of unmanned air traffic (Balakrishnan et al. 2018), optimum path planning for UAVs (Yang et al. 2015) and collision avoidance (Huang et al. 2019). The Scalability theme in CASCADE is looking at how the intensity of drone operations in the UK and beyond can be increased by many orders of magnitude to increase productivity whilst maintaining or improving safety. The problem is a grand challenge in that it involves many factors beyond the technical including economic, social, and legal. We are interested in thinking about novel approaches that embrace elements of centralised control combined with decentralised self-organising behaviours and considering that there will always be a mixture of machines and people. We also work within the established goals of UAV traffic management (Hu et al. 2020): Safety-  product of collision probability and severity is acceptably low; Efficiency – time, energy and space resources are minimised; Effectiveness – transport network connects required nodes. The management objective is an effective network that maximises efficiency for a given level of safety.

To help think about traffic management in a holistic manner we have looked at a variety of both engineered and natural multi-agent systems (Andreadis et al. 2014), where we consider a transport system to be any system where groups of mobile agents are trying to achieve individual goals within the context of larger organisational objectives. From a traffic management perspective, we find it useful to discriminate systems based on the intensity of the traffic and the degree to which control is decentralised, figure 1.  In the bottom left we have satellite networks which have a very low traffic intensity and are centrally controlled. Satellites are generally very far apart, and their orbits are precalculated to avoid conflict as there is very limited ability to take evasive action. In the top right we place the natural transport systems exemplified by flocks, herds, and schools. In these, the density of individual agents is very high and there may be very rapid reconfigurations or changes in direction. These behaviours are based on local decision making – each agent is aware of its neighbours but has no global knowledge of what the whole system is doing. Looking at the other corners of this diagram, in the top left we have used the example of a drone light show display. Here, the drones are very close together and maybe performing complex manoeuvres as a group, but the whole system is completely controlled centrally. In the bottom right, we place general aviation. Here, because density is low and pilots are assumed to be smart and responsible, traffic management can largely be delegated to the pilot’s control.

Traffic intensity (also referred to as traffic pressure (Helbing 1996)) is the product of both traffic density (number of agents in a given volume of space) and degree to which agents are trying to go in different directions (velocity variance).  Figure 2 attempts to categorise different types of traffic according to density and velocity variance, with the grey curve nominally representing a similar level of traffic intensity. In this scheme, air traffic and road traffic have similar levels of intensity but by different means: Road traffic is very dense, but the velocity variance is kept low by placing vehicles in lanes. Air traffic is generally low density but far less proscriptive in terms of lanes and hence has a relatively high velocity variance. The example we give here for very high intensity traffic is crowds, e.g., at a busy market. Here, agents are tightly packed together and all trying to get to different places.

A research question we are asking in CASCADE is – how can we manage very high intensity crowd-like drone traffic flows, e.g., between drone distribution warehouses and high densities of consumers? We believe that for very high intensity traffic flows, some degree of decentralised control is essential. What can we learn from the design of road networks and the successful behaviours of flocks, herds, and schools to help find solutions?

An initial observation is that nature can produce both linear lane-like flows of animals (Guy et al. 2012) and intense circulatory flows, as observed in so-called bait balls of small fish in the ocean. Nature can instil common instincts across populations of animals but has no means of real time centralised control, hence relies on decentralised control at the level of the individual animal to generate emergent behaviours that give the appearance of central management.

We ask the question – can we engineer a set of relatively simple rules inspired by natural behaviours of animals and flow of fluid that allow dynamic formation of a transport network that meets traffic management objectives for very high-density drone traffic of the future?

The elements of a transport network that we are considering are lanes, branches, and intersections. For our purposes, a lane of traffic is a collection of agents relatively close together moving in the same direction. A branch is where two or more lanes merge into one (a converging branch) or a single lane divides into two more separate lanes (a diverging branch). An intersection is where two or more lanes must pass through the same point in space. In a road network this type of intersection might be a crossroads or roundabout. Formal intersections are only required in two dimensional networks, such as simple roads. Where there is a third dimension available, it is always possible to route lanes and branches such that a formal intersection is not required, e.g., using a ‘spaghetti’ like junction, however this may end up being very complex.

So, how can you get 3d drone traffic to form lanes, branches, and intersections, all without using centralised control? Some design ideas for managing 3d drone traffic are shown in Figure 3.

From work on flocking, we know it is relatively easy to generate consolidated group like behaviours by applying general velocity alignment and cohesion rules. Lane forming is slightly different in that you want to select agents that are going in a similar direction, then guide to them to all use the same path. The lane forming rule has two main parameters: the radius (sphere of influence) over which the rule operates, and the strength (or weighting) compared to other rules in operation. With a small radius, traffic will tend to form into multiple smaller lanes whereas with a larger radius there will be fewer, larger lanes. With a high rule weighting, the lane forming behaviour will dominate other behaviours such that agents will prioritise lane following over for example the goal of trying to get to their destination in the most direct manner. As an innovative step we are using swirl in lanes like that of a vortex flow in fluids. It turns out that swirl helps the process of lane branching, allowing agents to join or leave a lane with minimal conflict with the other traffic. As a relatively simple starter problem in lane formation, we can consider convoys of agents as elastic strings between fixed start and end points. The lane formation process is then of stretching these strings to bring together lanes going in the same direction and push apart lanes going in opposite directions. A video of an investigation of this process is shown below.

A converging branch will form when lanes become sufficiently close that agents form a single combined lane. A diverging branch forms when destination vectors of groups of agents in a single lane become sufficiently different that the lane splits into two. From our research we have found that the traffic intensity generated during lane convergence is much less than during lane divergence. This is due to it being easier to mix two separate flows than it is to unmix them. A 2d simulation of this lane mixing process is shown below for varying control parameters in the lane forming algorithm.

The current stage of work is that we are starting to integrate lane forming, following, and merging. To do this a torus ‘test track’ was developed which provides a predefined circular or elliptical path for the drones to follow in a continuous manner. These can then be joined together to form what is known as a genus g surface to investigate convergent and divergent branches. A video showing a preliminary investigation using a single and double torus is shown below.

So where does this leave us? Like all good science, our investigations so far have led to far more questions than answers. There were both surprising failures and surprising success. For example, it would seem that merging traffic would be the same difficulty as unmerging, but the unmerging process leads to far more traffic pressure. This led us to the concept of lanes as swirling tubes, so that the traffic could easily unmerge from a lane without having to intersect the paths of other agents. As a surprising success, the lane finding work with the convoy like flows produced good results form the start. It appears that even in complex traffic scenarios the lane forming rules provide a very strong attractor that has very stable solutions. Perhaps also surprising was the simplicity of the final implementation of the lane following rules on our torus test track – just a few lines of code are needed to embed the rule, but the resulting emergent behaviour is endlessly fascinating.

Conclusions

• True 3d traffic management taking inspiration from animal motions in nature and fluid flow in physics has a lot to offer in terms of traffic topologies that go well beyond transplanting the current 2d road network into the sky
• Decentralised control of autonomous agents using classical flocking rules allows investigation of emergent behaviours that can be used as the building blocks of complex 3d traffic networks
• We have developed and evaluated a number of novel lane finding, forming and merging concepts that form part of a longer journey into development of safe, effective and efficient decentralised transport networks for high density traffic.

Bill Crowther, Sam Knox, Peter Hollingsworth, University of Manchester

References

Andreadis, G. et al. (2014). Classification and Review of Multi-agents Systems in the Manufacturing Section. Procedia Engineering, 69, pp.282–290.

Balakrishnan, K. et al. (2018). Blueprint for the Sky.

Guy, S.J. et al. (2012). Least-effort trajectories lead to emergent crowd behaviors. Physical Review E, 85(1), p.016110. [online]. Available from: https://journals.aps.org/pre/abstract/10.1103/PhysRevE.85.016110 [Accessed July 13, 2021].

Helbing, D. (1996). Gas-kinetic derivation of Navier-Stokes-like traffic equations. Physical Review E Volume, 53(3), pp.2366–2381. [online]. Available from: https://journals.aps.org/pre/pdf/10.1103/PhysRevE.53.2366 [Accessed August 26, 2020].

Hu, X. et al. (2020). Risk Assessment Model for UAV Cost-Effective Path Planning in Urban Environments. IEEE Access, 8, pp.150162–150173.

Huang, S., Teo, R.S.H. and Tan, K.K. (2019). Collision avoidance of multi unmanned aerial vehicles: A review. Annual Reviews in Control, 48, pp.147–164.

Yang, L. et al. (2015). A literature review of UAV 3D path planning. Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 2015-March(March), pp.2376–2381.