Embedded Files
Density-aware flight planning for large-scale drone operation
Density-aware flight planning for large-scale drone operation
Summary
Background
In urban areas where UAM demand is expected to be concentrated, the risks of contact between aircraft can frequently be at the highest level. To minimize such risks, there needs strategic planning to keep traffic density levels under a defined threshold.
Objective
This ongoing study aims to develop a density-aware flight planning strategy that keeps the traffic density level in the airspace below the desired threshold while minimizing the total distance travelled by drones.
Contribution
The proposed approach allocates a sequence of airspace volumes that each aircraft can reserve and use to avoid congested regions. As a result, UAM traffic can be redirected to lower-density or less-congested airspace without sacrificing too much additional flight cost. Further research on capacity-aware routing is underway, where capacity can be defined as a function of geospatial complexity and airspace complexity within each spatial unit.
Traffic density map with 400 agents (solved case)
Hexagon units are displayed in green and orange when occupied by 1 and 2 agents, respectively. Black grid indicates 3 or more agents are occupying the grid at the same time.
Motivation
Redirecting drone traffic to lower-density or less-congested airspace can reduce the risk of contact between drones and can therefore be considered an important first step in strategic flight planning.
Suppose that a group of drones plans to fly from the south to the north, as shown in the figure. Case 1 shows that all drones choose to go through congested regions on the left side. However, there is an alternative option to pass through less-congested regions on the right side, at the cost of taking a slightly more flight time (Case 2).
Proposed approach
Key concepts
Key concepts
The proposed approach aims to keep the traffic density level in urban airspace below the desired level and at the same time to minimize the total distance traveled, by allocating a sequence of airspace volumes that each aircraft should use to complete its operation. To do so, the following aspects need to be considered.
Modeling the spatial structure of urban airspace:
The expected large amount and variety of aeronautical data, as well as the complexity and uncertainty of emerging air traffic, pose challenges to low-altitude airspace management. For efficient handling of such data, there needs a spatial data structure that supports advanced modeling techniques.
There can be several approaches to modeling the 3D structure of airspace, including decomposition into uniform/non-uniform polygons (link1, link2) and hierarchical data structures.
Concept of reserving airspace volumes:
One of the common concepts in UTM or UAM traffic management is to have the operators reserve a sequence of airspace volumes to use. To keep the probability of conflicts low within each volume, one can control the number of aircraft that can use the volume.
A traffic density threshold k can be assigned to a static volume of airspace so that k+1 aircraft are not allowed to reserve the same volume at the same time period. The threshold can differ by volume, depending on obstacle configuration and traffic patterns or complexity inside the volume.
Strategic planning to make aircraft avoid high-density regions:
Once the traffic density threshold is determined, those who violate the threshold need to take an alternative sequence of airspace volumes, trying to take as little extra flight distance as possible.
Suppose that the airspace is divided into uniformly sized grids and that it takes one time step to move from one grid to another. Given n initial grid sequences of n aircraft, the solver checks for density threshold violations.
For a designated violation case, the AI-based solver explores the available options for each of the two agents involved. Options can be to choose an alternate grid sequence of the same length (option 1), wait for one additional time step at a droneport (option 2), or take an additional time step to detour high-density grids (option 3).
A 2D layer of airspace subdivided into uniform hexagonal grids (agents a_i,a_j,a_k,a_l to use the spatial unit S_m at time t)
Reserving a unit volume of airspace
Option 1 - Bypassing the concerned grid (in orange), flying through four grids
Option 3 - Bypassing the concerned grid (in orange), taking through one additional grid
Assumptions
Assumptions
Airspace is decomposed into uniform hexagonal grids. Each hexagon grid is a node, and edges are formed between adjacent grids. Edge weights are assumed equal.
It is assumed that each agent has a uniform speed and size.
A conflict is a tuple <agent ai, agent aj, vertex v or edge e, time t>, where agent ai and agent aj occupy vertex v or edge e at time step t.
Agents are only allowed to take a 'wait' action at the starting position.
Uniform traffic density threshold is assumed for each grid (e.g. no more than 4 agents can simultaneously enter the same grid).
The planner finds an optimal solution, where optimality is in terms of the total travel distance by all agents.
The above assumptions are for preliminary studies currently in progress, and some assumptions may be modified in future studies, as written in the conclusion section.
<Conflict definition >
<An example of city-wide airspace being subdivided into uniform hexagonal units>
Algorithm
The algorithm used in this study follows the basic principles of Conflict-Based Search (CBS) [1][2][3], the state-of-the-art multiagent pathfinding (MAPF) algorithm, that has been widely studied in the field of AI-based planning for autonomous robot scheduling in smart factories [4] and indoor drone navigation [5].
Initial pathfinding: The shortest path is computed for each vehicle, without considering conflict resolution with other vehicles.
Construct a conflict table: the planner finds all conflicts among agents and checks if the density threshold is violated in each spatial unit. It also checks if there is a cardinal conflict, where a cardinal conflict is a conflict that at least one agent must take an extra time step to avoid conflict with another agent.
Path refinement for cardinal conflicts: the planner searches for alternative path options for agents associated with density threshold violation. It solves cardinal conflicts first, by suggesting the agent to wait for 1 time step at the starting position or by finding an alternate path that requires an extra time step of 1.
Path refinement for non-cardinal conflicts: the planner searches for an alternative path option for an agent so that it can "bypass" high-density regions without having to take an extra time step. If there is no such “bypass” for a non-cardinal conflict, the planner either makes the agent to wait for 1 time step at the starting position or finds an alternative path that requires an additional time step of 1
< Flow chart of the proposed algorithm>
Case study 1
Conventional multi-agent pathfinding (MAPF) case, with a uniform density threshold of 1
CBS solves MAPF by decomposing it into a large number of constrained single-agent pathfinding problems. Computation time is proportional to the number of agents, the ratio between the grid size and the map size, the number of conflicts, and the complexity of conflicts.
While the CBS-based MAPF algorithm gives an optimal solution and guarantees completeness, the algorithm often takes a considerably long computation time or fails to find a solution when more agents are involved in a larger-scale maps with complex topology [1-3].
The below clips show a case study result of applying the algorithm for 20 agents in a small area. The density threshold is 1 for all grids, meaning that it is a conventional MAPF problem where only 1 agent can use a grid at the same time. There were a total of 15 conflicts, and the planner found a solution with the total travel time increased by 4 additional time steps.
Hexagonal grid domain with 20 origin and destination pairs
Origin and destination are indicated by blue circle and red cross, respectively (some origin or destination points overlap)
Each hexagon grid is represented as a node, and edges are formed among adjacent grids. The resulting graph G has a total of 91 nodes and 240 edges.
One side of a hexagon grid is of length 10, and edge weights are assumed uniform.
Shortest initial paths for 20 agents
(unsolved case)
It is assumed that each agent has a uniform speed and that it takes 1 time step* to move from one node to another adjacent node
A conflict occurs if multiple agents occupy the same node (node conflict) or the same edge (edge conflict)
Initially, there are a total of 15 conflicts.
* in the visualization, agent is shown to take five moves in one time step.
De-conflicted paths for 20 agents
(solved case)
Agents are only allowed to take a 'wait' action at the starting position
Agent #5, #14 (red) waited for 5 time steps, whereas agent #15 (purple) waited for 1 time step at their starting position
Agent #17 (yellow) took a detour with additional 1 time step to avoid other agents, rather than waiting.
Agent #1, #2, #16 (green) took an alternative path with no additional cost ("bypass")
Others took the same path as before. As a result, the total travel time increased by 4 time steps.
Runtime is 5.691 seconds on a standard PC with Intel Core i5 6600 3.9GHz CPU and 16GB RAM.
Case study 2
Density-aware planning for 400 agents, with a uniform density threshold of 2 (obstacle-free environment)
Suppose the map is subdivided by hexagonal spatial unit with 1973 nodes and 5723 edges. I generated OD pairs for 400 agents and found the shortest paths for all agents.
The number of agents occupying a hexagon unit at each time step is shown in traffic density map.
Maximum traffic density map shows the maximum number of agents occupying each hexagon unit throughout the time horizon.
There are 142 cases that 3 or more are occupying the same grid.
Traffic density map with 400 agents
(unsolved case)
Hexagon units are displayed in green and orange when occupied by 1 and 2 agents, respectively. Black grid indicates 3 or more agents are occupying the grid at the same time.
Maximum traffic density map
(unsolved case)
When 400 agents are generated in this area of interest, there are 142 cases that 3 or more are occupying the same grid.
The planner finds alternative paths for agents in conflict so that the density level per grid is kept under the predefined threshold of 2. In other words, only 1 or 2 agents can simultaneously use the same volume.
Out of 400 agents, 2 agents took a 'wait' action at the starting positions, whereas 70 agents took bypass routes that have the same travel distance as the initial route.
Traffic density map with 400 agents
(solved case)
Hexagon units are displayed in green and orange when occupied by 1 and 2 agents, respectively.
Maximum traffic density map
(solved case)
The maximum traffic density is kept below 3 per grid throughout the time horizon. 72 agents changed its route, and the total travel time by all agents only increases by 2 steps.
Case study 3
Density-aware planning for 50 agents, with a uniform density threshold of 3 (obstacle-rich environment)
Consider a map subdivided into 1672 hexagonal grids. Suppose that 10% of grids are blocked. The planner finds alternative paths for agents in conflict so that the density level per grid is kept under the predefined threshold of 3. In other words, only 3 agents can simultaneously use the same volume.
Out of 50 agents, 4 agents took a 'wait' action at the starting position, and 2 agents took an alternative path that requires an extra time step. 6 agents took bypass routes that have the same travel distance as the initial route.
Hexagon units are displayed in yellow, orange, and red, if it is occupied by 2 , 3, and 4 agents, respectively. Black grid indicates unavailable airspace that agents cannot pass through.
The maximum traffic density is kept below 4 per grid throughout the time horizon. Out of 50 agents, 12 agents changed its route, and the total travel time by all agents only increases by 6 steps.
Challenges & Future directions
This study is currently under development, and several improvements will be made upon the current version considering the following aspects:
Scalability: The proposed method should be applicable to the actual city-wide airspace. The performance of the solver primarily depends on the density threshold, the number of agents, the proportion between grid size and map size, and the number and complexity of conflicts.
Heterogenous density threshold: Rather than setting a uniform density threshold to all grids, it would be more realistic to adaptively allocate agents to a grid, taking into account the complexity of expected conflicts inside the grid. In addition, grids with complex obstacle configuration may require heterogenous density thresholds.
Heterogenous agents: To account for heterogeneous agents with different speeds, sizes and safety margins, the current definition of conflict needs to be modified. One solution is to make each agent reserve its current grid as well as its subsequent grid.
Positional uncertainty: In the current version, each aircraft is assumed to reserve and use one grid at one time step, where each time step is related to the estimated time the aircraft enters and exits a grid. In the real world, there is uncertainty about whether aircraft will enter and exit a grid at the expected time. To take into account such case in the proposed approach, the solver can be modified to make aircraft reserve its neighboring grids in addition to the current grid. This will create more conflicts and increase computational burden due to the increased constraints on finding alternative routes that avoid the concerned grids.
Incorporating flight dynamics: The current grid-based pathfinder returns a path that follows the center coordinates of hexagonal grids. Directly using a graph-based path as a trajectory results in a piecewise linear path, requiring the aircraft to make a 120-degree turn at some nodes. In the future work, it is necessary to take into account the flight dynamics of aircraft in order to more accurately estimate the position of aircraft at each time step. To create a smoother trajectory that reflects the aircraft's kinematic constraints, a path smoothing or trajectory optimization step needs to be added to the pathfinding step.
Using different altitude layers: The current version only considers a 2D slice of airspace. The solver can be modified to assign an agent in conflict to another altitude, if too much extra time steps are required to avoid high-density areas at the current altitude.
Using direction maps for pathfinding: The smaller the number of droneports, the fewer route combinations connecting each OD pair exist, causing agents to repeatedly use the same sequence of grids over time. One can use a direction map [6] to specify air highways that only allow flow in a specified direction. Given a set of OD pairs, the direction map shows the most popular direction (i.e. median direction) drones are heading at each grid over the time horizon . Spatial clustering can be applied to specify a sequence of grids with similar directional components as highways. Whether this approach will be effective in reducing the number of conflicts or improving the solver's performance is the subject for further study. When there are several combinations of OD pairs, specifying the direction that aircraft are allowed to flow may worsen the overall complexity. In such case, it would be more appropriate to assign aircraft to different altitude bands based on their headings, as extensively studied in Metropolis 1 and Metropolis 2 project [8,9].
Scalability of the proposed method
(grid edge length of 400 m, 1,000 agents)
The figure shows the case of 1,000 agents that the traffic density at each grid is kept below 10.
Given the grid size, the number of agents, the complexity of anticipated conflicts, the map topology are the main factors affecting the perfomance of the method.
Heterogenous density threshold
Instead of a uniform density threshold, the set of aircraft that can enter a specific grid at some time step can be determined based on the complexity of expected conflicts or the obstacle configuration inside the grid.
Extended definition of a conflict
If each agent reserves its current grid and its subsequent grid, then more conflicts will be generated, resulting in increased computational burden due to the increased constraints on finding alternative routes that avoid the concerned grids.
Visualization of agents' headings at each time step in case study 3
Direction map (median direction component of each grid)
The fewer the droneports, the fewer route combinations connecting each OD pair exist, causing agents to repeatedly use the same sequence of grids over time.
In this case, one can use the direction map to specify highways that only allow flow in a certain direction, to reduce the overall complexity of conflicts.
Visualization of 400 agents' headings at each time step in case study 2
Direction map (median direction component of each grid)
When there are several combinations of OD pairs, specifying the direction that aircraft are allowed to flow may worsen the overall complexity.
In such case, it would be more appropriate to assign aircraft to different altitude bands based on their headings, as extensively studied in Metropolis 1 and Metropolis 2 project [8,9].
References
[1] Sharon, G., Stern, R., Felner, A. & Sturtevant, N. R. Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015).
[2] Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., & Shimony, E. (2015, May). Icbs: The improved conflict-based search algorithm for multi-agent pathfinding. In Eighth annual symposium on combinatorial search.
[3] Li, J. et al. Multi-Agent Path Finding for Large Agents. Proc. AAAI Conf. Artif. Intell. 33, 7627–7634 (2019).
[4] Cohen, L., Uras, T. & Koenig, S. Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding. Proc. 8th Annu. Symp. Comb. Search, SoCS 2015 2015-Janua, 2–8 (2015).
[5] Hönig, W., Preiss, J. A., Kumar, T. S., Sukhatme, G. S., & Ayanian, N. Trajectory planning for quadrotor swarms. IEEE Transactions on Robotics, 34(4), 856-869 (2018).
[6] Jansen, M. R. & Sturtevant, N. R. Direction Maps for Cooperative Pathfinding. Proc. Fourth Artif. Intell. Interact. Digit. Entertain. Conf. 185–190 (2008).
[7] Cohen, L., Uras, T. & Koenig, S. Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding. Proc. 8th Annu. Symp. Comb. Search, SoCS 2015 2015-Janua, 2–8 (2015).
[8] Hoekstra, J. M., Ellerbroek, J., Sunil, E., & Maas, J. (2018). Geovectoring: reducing traffic complexity to increase the capacity of uav airspace. In International Conference for Research in Air Transportation, Barcelona, Spain.
[9] Doole, Malik, et al. "Constrained Urban Airspace Design for Large-Scale Drone-Based Delivery Traffic." Aerospace 8.2 (2021): 38.
Page updated
Google Sites
Report abuse