Strategic and Tactical Path Planning for Urban Air Mobility: Overview and Application to Real-World Use Cases

Abstract

Urban air mobility requires safe and efficient airspace management, as well as effective path planning and decision-making capabilities to enable access to the urban airspace, which is predicted to be very densely populated. This paper tackles the problem of strategic and tactical path planning by presenting a framework specifically designed for accounting for several constraints and issues of the urban environment. Multi-objective and multi-constraint planner algorithms are developed to this aim, along with an innovative method for information simplification and manipulation. Navigation-aware and optimized trajectories were retrieved from the strategic approach. Tactical path planning was developed using three approaches that react differently to unpredicted conditions. The entire strategic–tactical pipeline was tested in two real-world use cases, representing common missions in urban environments, such as medical delivery and short-range air taxi. The results demonstrate the effectiveness of the proposed methodology in generating the strategic path and show the different outcomes of the proposed tactical approaches, thus highlighting their advantages and drawbacks.

1. Introduction

The market of unmanned aerial systems (UAS) has witnessed a rapid growth in the last decade, fostering research towards innovative algorithms and instruments to enhance their reliability, autonomy and safety. Urban air mobility (UAM) represents the next frontier of the UAS market, and a huge effort is being carried out in that direction in view of a wide variety of applications. As an example, missions such as urban taxi [1], inspection and surveillance [2] could experience a significant performance improvement (e.g., reduction of mission time) if performed by highly autonomous unmanned aerial vehicle (UAV). The development of urban air mobility will completely change our cities with a huge quantity of UAVs that require to be accommodated in the airspace. The increased UAV density also calls for new regulations [3] that are being developed to bridge the gaps between novel technologies and urban safety requirements [4]. In this framework, path planning and traffic management tasks are of paramount relevance to meet these safety requirements and enable UAV access to a traffic dense airspace.

UAV path planning, aiming to define the best route from a start to a goal point, is a widely discussed problem in the open literature, and several algorithms have been developed to specifically accommodate mission needs. In general, path planning requires accounting for UAV dynamic constraints, energy consumption (and thus wind and weather conditions [5,6,7,8]) and fixed and mobile obstacles to meet safety and effectiveness requirements [9]. When it comes to urban scenarios, navigation issues can arise for vehicles using the classical GNSS/inertial fusion scheme due to the non-nominal GNSS coverage conditions, which is experienced next to buildings and infrastructures. Indeed, these structures cause GNSS signal shadowing or deviation, leading to either signal obstruction or multipath phenomena, respectively. In these scenarios, path effectiveness, should also account for the capability to follow the planned trajectory while keeping a bounded navigation error and fulfilling the required navigation performance (RNP) [10]. Conversely, safety requirements are also linked to the need for minimizing the ground risk [11]. Several works in the open literature have addressed planning problems by accounting for ground risk mitigation [12,13], GNSS coverage fault [14], wind condition and its effect to energy consumption [6]. Nevertheless, an integrated framework which tackles all these aspects altogether is required to effectively enable safe access to the urban airspace.

The “SMARTGO” (gnsS-enabled urban air Mobility through Ai-powered environment-awaRe Techniques for strateGic and tactical path planning Operations) project [15], funded by the Italian Space Agency (ASI) and carried out by a consortium composed by the University of Naples “Federico II” (as coordinator), TopView S.r.l. and Euro.Soft S.r.l. aims to develop strategic and tactical path planning algorithms that can handle several information levels to meet urban environment requirements and constraints. Besides path planning approaches, the project also aims to gather and synthesize relevant information about the urban environment useful for path planning and at defining innovative U-space services based on the project outcomes. Data gathering includes processing satellite images with innovative algorithms, which are also based on artificial intelligence for terrain classification and ground risk estimation. Tackling both planner design and information gathering bridges the gap between data retrieval and usage and ensures information collection and representation is specifically tailored to planner’s needs.

This paper briefly describes the main algorithmic outcomes of the project in terms of path planning and focuses on the application of the entire algorithmic chain to real-world test cases that have been specifically identified for the project’s needs. A brief overview of the project and a preliminary version of both the strategic and tactical algorithms have already been presented in [15]. Then, a more detailed version of the tactical framework and the developed approaches to tackle with unpredicted events during flight has been described in [16]. In addition, a detailed description of the strategic path planning algorithm is reported in [17]. This work extends the previous contributions of the authors by providing the following innovative points:

• It describes the final version of both tactical and strategical path planning algorithms.
• It provides a systematic approach to deal with tactical planning and its multiple alternatives to overcome any type of unpredicted event.
• It analyzes the tactical and strategic results on relevant environments by applying the entire strategic–tactical path planning flowchart and also highlighting the strategic path selection approach.

The remainder of this paper is structured as follows. Section 2 analyzes the constraints to be taken into account at both tactical and strategic level while also detailing the procedure for information retrieval. Both strategic and tactical path planning algorithms are summarized in Section 3. Test cases and their related information to be used at path planning level are reported in Section 4, and Section 5 shows the tactical and strategic path planning results. Finally, Section 6 draws conclusive remarks.

2. Environment and Vehicle Based Constraints

Risk, weather and no fly zone information, as well as 3D geometries, mobile obstacles and vehicle specifications and constraints must be taken into account to plan for a safe and effective path. Vehicle-based constraints include maximum airspeed and flight path angle, as well as battery capacity, maximum allowed wind velocity and navigation system performance. Environment-based constraints can, in general, be divided into two categories depending on whether they are connected to the airspace or not. Airspace-based constraints include (but are not limited to) no-fly-zones, maximum and minimum flight altitudes, traffic information, contingency landing site location and possible airspace structure and/or speed rules, as foreseen, for instance, in the geovectoring approach [18]. On the other hand, the other environmental constraints include general information about the scenario such as 3D geometry, weather information and estimate of ground risk.

Because the majority of the developed planning approaches are designed to deal with spatial based information, SMARTGO information gathering and organization aims at simplifying most of the aforementioned sources in multi-dimensional maps. This is done to reduce the information processing to be carried out at the path planning level. Specifically, the following maps are defined and used as planning inputs:

• 3D map with fixed obstacles and no fly zones. Fixed obstacle maps are obtained from publicly available representation of the environment available on open source platforms, such as CityGML [19] or OpenStreetMap.
• Risk map. A 2D map that contains information about level of risk associated to each latitude and longitude coordinates. It is computed from satellite images and GIS databases. As detailed in [15], risk map retrieval first uses satellite imagery to classify terrain with a VGG16 convolutional neural network (CNN) [20] trained with the EuroSAT database. Then, information from the GIS database and building footprints is integrated to further segment terrain classification and localize critical structures, such as power plants, railway stations, subways, airports and hospitals. Level of risk going from 1 to 4, with increasing damage entity forecasted in case of vehicle fault, is extracted from segmented information of the terrain so that:
  • Class 1 includes low-risk areas such as natural and rural ones;
  • Class 2 includes industrial areas characterized by low people density;
  • Class 3 includes urban environments. In this scenario a subclassification is performed to distinguish between buildings and populated areas such as squares and streets;
  • Class 4 includes critical infrastructures (e.g., train stations and hospitals) and it is again divided in various subcategories.

An example of risk level over a portion of Naples city (Italy) is reported in Figure 1.

3.

Landing site maps are 2D maps containing cost information, which increases as the distance from the contingency landing area increases.

4.

Weather or wind maps are multidimensional maps corresponding to each ground point information about wind intensity and direction in terms of azimuth and elevation. In this work, the wind dependency on altitude is not considered, which is consistent with currently available weather maps.

5.

GNSS coverage maps. GNSS coverage maps are defined with the aim of spatially representing the information about navigation performance, thus avoiding the need to propagate navigation error covariance during the path planning process. Indeed, the navigation performance of the majority of UAVs (which are usually implementing INS/GNSS data fusion) is strictly connected to both the inertial instrument specifics and GNSS coverage. A GNSS coverage map is a 2.5D map connected to the dilution of precision (DOP) level, defining the elevation at which the DOP becomes smaller than a certain threshold. As the GNSS constellation varies as a function of time, a time-varying GNSS coverage map is expected over a selected time interval. The approach followed in the SMARTGO project samples the time interval and defines an elevation map for each sample. The so-defined elevation maps are merged in a worst-case logic to have a constant GNSS coverage map to be used during the whole mission time. Several GNSS coverage maps can be defined as a function of the selected DOP threshold. As an example, Figure 2 shows three GNSS coverage maps obtained over a portion of Naples city center with different colors. It can be noticed that the map’s offset with respect to the buildings reduces as the selected DOP threshold (i.e., D_j) increases. Computing each GNSS challenging map can be very time demanding if a very large scenario is considered. However, in many cases, the need for detailed GNSS coverage maps may arise only in proximity of take-off and landing areas. The approach followed in the SMARTGO project uses this idea, thus estimating the GNSS coverage maps only in the surroundings of the start and the end point and assuming the map altitude is equal to the terrain plus an offset in the other areas.

6.

Traffic information is provided via vehicle-to-vehicle (V2V) or infrastructure-to-vehicle (I2V) communications. This work assumes the entire flight plan of the other vehicles is fed to the ownship both in the strategic phase and during the flight. Flight plan information of the intruder is stored in 3D time-varying occupancy maps, detailed in [16]. N occupancy maps varying with time are used to prevent continuously checking for intruder possible collision, each one covering a time interval equal to Δt. The n-th occupancy map is used for checking collision in the time segment going from t_n−1 to t_n (t_n = t₀ + nΔt, being t₀ the starting time of the mission). The representation of the intruder in each occupancy map is given by its path during the associated time interval enlarged with time and spatial margins. The nature of traffic maps allows them to be merged with the fixed obstacle maps so as to speed up the collision check operation.

3. Path Planning Framework

Planning framework, whose flowchart is shown in Figure 3, foresees two phases, i.e., the strategic phase (detailed in Section 3.1), which is aimed at evaluating an optimized trajectory for the UAV before the flight, and a tactical phase (described in Section 3.2), which continuously checks the trajectory during the flight and takes action in the case an unpredicted event occurs that compromises the trajectory safety and effectiveness. The need for decomposing the planning approach in two phases [21] comes from guaranteeing path optimality while reducing the computational cost during flight, as tactical replanning is only demanded at finding deviations from the nominal (strategic) trajectory. To ensure the latter condition, a strategic path planner must be carried out with the largest amount of available information, following the better-informed, better-planned logic.

Both strategic and tactical solutions are conceived to deal with all the set information reported in Section 2, or a subset of them in a scalable and adaptive way. Due to the large amount of information to be dealt with and the huge dimension of the scenario where the planner is considered to operate (with mission ranges in the order of few kilometers), sampling based approaches, such as rapidly exploring random trees (RRT) [22] and its modifications, are preferred in this work to graph search method, such as A* [23] because of the high cost linked to sampling all the nodes belonging to the environment. Feasible segments to add to the solution tree are those which:

• are not intersecting with any fixed (including NFZ) or mobile obstacle;
• are compliant with the battery capacity and with the maximum velocity and flight path angle limits;
• have an altitude between the maximum and minimum flight altitude computed above the ground level;
• never lie below the GNSS coverage map used as reference;
• do not enter in areas whose wind intensity is higher than the one the UAV can tolerate.

3.1. Strategic Path planning

The strategic path planning approach developed within the SMARTGO project is characterized by two steps, which are depicted in Figure 3. The first step is based on a custom version of the batch informed three (BIT*) algorithm [24] embedded in the open motion planning library (OMPL) framework [25]. More details about STEP I algorithmic implementation are provided in [17]. Both constant (e.g., fixed obstacles and NFZ, landing site, risk and wind maps, as well as GNSS coverage volumes) and time varying information (i.e., traffic) are used as input in this step. The final path is a 4D trajectory which is constrained to the feasible trajectory conditions reported in Section 2. An optimized trajectory is obtained by minimizing:

$$f\left(s\right)={\alpha }_s{C}_s\left(s\right)+{\alpha }_l{C}_l\left(s\right)+{\alpha }_r{C}_r\left(s\right)+{\alpha }_w{C}_w\left(s\right)$$

(1)

Costs C_x and weighting factor α_x can be referred to path length (s), landing site (l), risk (r) and energy (w) information. Landing site and risk costs are obtained by integrating the normalized version of the landing and risk maps along the trajectory. Energy cost is obtained by using a simplified model based on rotor theory and described by [17]. C_s represents the path length.

STEP I is repeated several (J) times, while the GNSS coverage map input changes as a function of the DOP. The second step selects the minimum cost solution among the J available ones. The trajectories are first smoothed with polynomial trajectory planning [26] and then navigation state covariance propagation is performed to verify path navigation feasibility, i.e., the fact that positioning error is always lower than a positioning error threshold (Δp_max). Any solutions not fulfilling this requirement is discarded and the 4D strategic (nominal) path is obtained as the one with minimum cost among the remaining alternatives.

3.2. Tactical Path Planning

Tactical planner is aimed at fast finding a path that can be followed by the UAV if safety and effectiveness of the strategic path are jeopardized during the flight. Optimality is non-accounted for at this level, and the first feasible alternative is considered as tactical solution. Therefore, all the information sources, which are only used for the aim of cost definition (i.e., landing site location and ground risk) are discarded at tactical level, and their modification cannot trigger any level of tactical replanning. Conversely, updates of GNSS maps, fixed and mobile obstacles and wind conditions may call for trajectory update. As far as wind modification is concerned, it not only alters the UAV energy consumption, but it also modifies the zones in which the UAV is allowed to fly due to the maximum admissible wind velocity. Tactical path planner assumes the ownship has a lower priority than the other UAVs, so it has to maneuver in case of conflict. It implements three different solutions, referred to as levels in Figure 3, that are specifically designed to counteract several events that could occur during the tactical phase. The three levels are characterized by an increasing level of computational complexity and their performance is summarized below. For further algorithmic details, the reader is referred to [16].

• Level 1 is aimed at modifying the time history of the trajectory without altering its geometry so as to keep the path optimality. Time history is modified by scaling down the UAV velocity using an ad hoc scaling function, which decelerates the vehicle before the encounter through a deterministic approach. Because spatial modification of the trajectory is not foreseen in this approach, Level 1 can be only used for avoiding mobile obstacle collision in the case of non-frontal confliction geometries. In addition, despite the low computational time, this approach extends the mission time and can be not suitable for vehicles whose nominal path requires an energy consumption close to the battery capacity.
• Level 2 provides spatial modification of the trajectory in the surroundings of the location of the unfavorable event(s). The planner uses a customized version of the RRT algorithm conceived as a global replanner that only provides a local modification of the trajectory because it is informed to return to the strategic path. The global nature of this approach avoids sequential replanning if multiple unfavorable events are experienced by the UAV, thus saving time. Due to the spatial modification of the trajectory, this solution is not only able to deal with both fixed and mobile obstacle geometries, but it can also be used to counteract wind velocity and GNSS coverage maps alteration. The heuristic nature of the RRT makes this solution non-deterministic. In addition, a higher computational time is experienced with respect to the previous approach. However, since only a local modification is provided to the strategic path, its optimality remains almost unaltered while also providing a small increase in flight time, as demonstrated in [16].
• Level 3 of the tactical planning provides a global modification of the trajectory starting from its last non-corrupted point. From that point, a completely new trajectory is recomputed with an algorithm still based on RRT, but not informed to return to the strategic trajectory. This solution, which completely alters the path after the unfavorable event, should be chosen when a significant modification of the flight conditions has been experienced with respect to the scenario available at the strategic level. Due to the similar algorithmic scheme, this level shares the same heuristic nature of Level 2, as well as the higher computational time with respect to Level 1.

Among the proposed solutions, the one to be chosen during tactical phase is not trivial to be identified. Although a simple geometry consideration can be made to deem whether to use Level 1 solution or not, this is not true for the other two levels and their output must be compared to this aim. Therefore, the tactical planner is conceived to run all the levels sequentially and compare their solutions, if available, to choose the one with the minimum cost. A flowchart of the tactical planning is reported in Figure 4.

Level 1, which has the lowest computational cost, is the first to be run (it runs only if compliant to the conflict geometries), then Level 2 is queried. The level sequence runs until a timeout, and the tactical output is picked among all the available solutions at that time. During the flight, the current path is checked for any unfavorable event (i.e., contingency). If the time to the contingency (t_coll) is greater than the replanning timeout (t_rep), the tactical replanning levels are run sequentially and the best cost path is selected to update the flight plan. In the case no available solution is found by tactical planning or t_coll ≤ t_rep, contingency landing actions are activated.

4. Use Cases

Strategic and tactical pipeline have been applied to two test case scenarios. The first represents an urban air taxi problem, specifically designed to transport passengers from airport to business center and port. The second scenario includes the delivery of medical supplies from the mainland to an island, thereby saving time with respect to ship-based transportation. Two scenarios have been identified in the Naples area and its surroundings and are reported in Figure 5. Risk, landing site, wind and GNSS coverage maps estimated with three different thresholds, i.e., D₁ = 2, D₂ = 3, D₃ = 4 are reported both for air taxi and medical delivery cases in Figure 6 and Figure 7, respectively.

Because the two identified scenarios have a huge extension, the GNSS coverage map has been computed only in a portion of the environment which is closer to the start or the end point of the trajectory. They were obtained using a starting time of 11:30 UTC of 19th April 2022. A time interval of 20 min has been considered, with a time span of 5 min. The ground grid has 5 m spacing. A uniform wind intensity of 5 m/s has been used for both missions.

The air taxi scenario is reported in Figure 5a. It envisages transfers from Capodichino airport to Naples business center or port. The three locations have been represented on the map with an asterisk, a cross and a circle, respectively. Both the top and lateral views have been reported in the Earth north up (ENU) coordinate frame originated at 40°51′56″ N, 14°17′20″ E, as well as the rectangles where GNSS coverage maps have been computed. For the sake of concreteness, the satellite map of the identified area is also reported. The lateral view highlights the high slope of the scenario. A maximum flight altitude estimated above the ground level and equal to 150 m has been assumed. Two missions have been considered, i.e.:

• Mission 1. From Airport ([−511, 1290, 105] ENU coordinates) to Port ([−591, −2541, 20] ENU coordinates).
• Mission 2. From Airport ([−511, 1290, 105] ENU coordinates) to Business district ([−485, −950, 50] ENU coordinates).

The medical delivery scenario involves the Procida island and its closest city on the mainland, i.e., Monte di Procida, which is about 4 km far. Even if several ship connections, taking about 16 min, are organized in the summer season (from June to September), very few transportations (twice a day and only on weekdays) are foreseen in the winter season, making impossible to directly deliver urgent medicines. A dedicated drone service could not only spare time but also be operated on-demand. The scenario extension (both in the lateral and top view) and its satellite view have been reported in Figure 5b. The start and arrival location includes a pharmacy in Monte di Procida (40°47′20″ N 14°3′0″ E and 100 m altitude) and the Procida local medical unit (40°45′25″ N 14°1′11″ E and 60 m altitude), which are reported with a cross and a circle in the figure, respectively. A maximum flying altitude of 150 m above the terrain level (or the sea level when the aircraft flies in the Procida channel) has been assumed.

5. Results

Strategic and tactical planning have been carried out assuming as aircraft a DJI M300 RTK [27], whose main parameters are reported in

Table 1. Vehicle specifics.

Constraints		Value
Battery capacity	ξ (mAh)	11,870
Maximum airspeed	(m/s)	23
Max wind speed	(m/s)	15
Cruise speed	vc (m/s)	10
Maximum Flight Path Angle	α (°)	15
Max Positioning error	Δpmax (m)	2
IMU Parameters 1	Acc. In-run stability (mg)	0.11
	Velocity random walk (m/s/√h)	0.06

¹ Only accelerometer parameters are included since navigation error covariance propagation is run with a simplified approach.

. Navigation performance of the IMU sensor has also been included, which is assumed to be the one of the medium grade IMU HG1120CA50 from Honeywell [28]. The positioning error threshold is assumed to be equal to 2 m so that any trajectory which overcomes this value at least once during the flight must be discarded. In order to trigger every tactical level to output a solution, in this work, tactical information is only limited to intruder trajectory updates. The entire path planning pipeline results will be detailed in the medical delivery scenario, which involves a single mission, in Section 5.1. On the other hand, results related to the air taxi scenario are shown in Section 5.2.

5.1. Medical Delivery Scenario

Strategic path planning results are obtained using in STEP I α_s = α_w = 1, α_r =4, α_l = 2 as weighting factors, thus privileging trajectories which reduce the ground risk and are closer to the landing sites. STEP I paths are reported in Figure 8, along with the strategic obstacles’ paths. A trajectory for each GNSS challenging map is obtained, with the cost breakdown reported in

Table 2. Medical delivery scenario. Strategic solution costs breakdown.

GNSS Coverage Map Threshold	Cost Functions (m)					Flyable	Comput. Time (s)
	Cs	Cr	Cl	Cw	f
D1	6650.7	1836.8	6472.8	7018.6	33,961.9	yes	53.0
D2	5440.8	1301.9	5098.4	5830.2	26,675.4	yes	55.3
D3	6384.0	1481.0	5807.1	6859.1	30,781.3	yes	60.3

. The costs are estimated over the smoothed trajectory computed in STEP II. Results of trajectory flyability test (maximum trajectory positioning error lower than Δp_max) are also reported in the Table. All the trajectories are compliant with navigation requirements, and D₂ (highlighted in green in Table 2), which minimizes the cost function (f) is picked as the strategic (nominal) solution. Computational time of each solution estimated on an Intel i7 pc with a 2.59 GHz processing unit has been also reported in the Table, demonstrating the planner requires less than one minute for output each trajectory.

Tactical deconfliction accounts for unknown (tactical) obstacles that the UAV has to avoid during the flight. With the aim of testing tactical planner performance, these trajectories have been specifically designed in order to intersect the strategic path. Information about these trajectories is transferred to the UAV by the U-Space Service Provider (USSP) or via a vehicle-to-vehicle data link. This information, together with the UAVs flight plans known in the strategic phase, must be taken into account to generate a safe and collision free path. The trajectory costs obtained after tactical deconfliction are reported in

Table 3. Medical delivery scenario. Tactical solution costs breakdown.

GNSS Map Thr.	Tactical Level	Total Time (s)	Max Nav Err. (m)	Comp. Time (s)	Cost Functions (m)
					Cs	Cr	Cl	Cw	f
D2	Strategic	543.5	1.19		5440.8	1301.9	5098.4	5830.2	26,675.4
	1	1174.6	1.25	1.7	5440.8	1301.9	5098.4	6300.2	27,145.3
	2	546.0	1.20	4.2	5457.5	1292.3	5110.4	5838.5	26,686.1
	3	584.0	1.19	5.2	5958.5	1747.0	5484.7	6244.4	30,160.3

, along with the maximum navigation error, the computation time and the overall flight time that (except for Level 1 approach, which experiences a huge time delay) does not increase significantly. Using the same GNSS coverage map accounted for in the strategic path definition as a boundary allows keeping the navigation error smaller than Δp_max. As expected, the lowest cost solution is the one associated with Level 2, which is specifically designed to produce local variation from the strategic path by keeping its cost function almost unaltered. Because the Level 1 3D trajectory coincides with the strategic one, all the spatial based costs (risk, landing site and path length) are equal. However, this is not true for the energy cost, which is increased due to the high waiting time to avoid tactical obstacles. As far as the computation times are concerned, Level 1 solution, based on a deterministic approach, gives the smallest contribution. On the other hand, about 5 s are required to solve the deconflictions for spatial based solutions. These values are compatible with typical values of tactical replanning cut off time which is of the order of 10 s.

Tactical results are reported in Figure 9, either for spatial based solution (i.e., associated to Level 2 and 3) and time scaling results (Level 1), which are depicted in Figure 9a,b, respectively. Figure 9a shows both the lateral and the top view of the Level 2 and 3 trajectories by also reporting the information of strategic and tactical intruders (top view) and the GNSS coverage map associated to the nominal trajectory, i.e., whose threshold is D₂ (lateral view). The Level 3 solution has a larger deviation from the strategic path than Level 2, as expected. This deviation from the optimal path produces an increase of the trajectory cost. Figure 9b compares the velocity history of the strategic path with respect to the tactical one, noting the huge delay produced by the time scaling approach. Indeed, the ownship is slowed down twice and the avoidance of the second intruder produces a huge velocity reduction (near to zero) and a very long waiting time to avoid collision.

5.2. Air Taxi Scenario

Air taxi strategic paths have been obtained using the same weights of the previous section. The strategic costs breakdown and computational time for the two missions are reported in

Table 4. Air taxi scenario. Strategic solution costs breakdown.

Miss. No	GNSS Map Threshold	Cost Functions (m)					Flyable	Computation Time (s)
		Cs	Cr	Cl	Cw	f
1	D1	4168.0	2.4905	2.8956	4189.7	24,110.9	yes	26.3
	D2	4098.6	2449.0	3347.8	4118.3	24,708.4	yes	22.0
	D3	4110.2	2580.3	3125.7	4131.2	24,813.9	yes	25.4
2	D1
	D2	2358.5	1449.9	2042.7	2349.2	14,592.7	yes	21.9
	D3	2502.2	1510.7	1925.3	2490.8	14,886.4	yes	23.6

, where the nominal solution (i.e., the one having the minimum cost) for each mission has been highlighted in green. A lower computational time (about 20 s) is required in this case to obtain the solution, which depends on the different scenario geometry. Mission 2 does not have the D₁ solution, because the point located in the business center falls below its associated GNSS coverage map. The selected strategic path is the one associated with D₂. When mission 1 is accounted for, the lowest cost trajectory is the one associated to D₁, even if a shorter length is obtained using D₂. This is due to the large landing site weighting factor, which tries to push the trajectory far from the shortest length one in order to make it pass over landing site locations. Results for Mission 1 and 2 are reported for the first step of the strategic planning algorithm in Figure 10a,b, respectively, along with the paths of the strategic intruders.

The trajectory updates during the tactical phase are shown in Figure 11 and Figure 12 for mission 1 and 2, respectively. A zoomed portion of the scenario, which encloses the trajectory in each mission, has been reported to better visualize the tactical variation of the path. For each figure, the Level 1 solution in terms of velocity history is reported in subfigure b, whereas the Level 2 and 3 trajectory deviation from the strategic path are shown in subfigure a. As in the previous section, the strategic (nominal) trajectory is also reported, as well as the trajectories of both the strategic and tactical intruders (in top view) and the GNSS coverage map associated with the strategic solution (in lateral view).

The tactical paths’ cost breakdown is reported in

Table 5. Air taxi scenario. Tactical solution costs breakdown.

Miss. No.	GNSS Map Thresh	Tactical Level	Total Time (s)	Max Nav Err. (m)	Comp. Time (s)	Cost Functions (m)
						Cs	Cr	Cl	Cw	f
1	D1	Strategic	414.1	1.19		4168.0	2.4905	2.8956	4189.7	24,110.9
		1	492.4	1.21	0.2	4168.0	2.4905	2.8956	4223.2	24,142.5
		2	414.6	1.19	2.0	4156.9	2504.5	2990.0	4191.1	23,246.0
		3	407.3	1.19	6.2	4115.3	2519.4	3006.3	4114.9	24,320.3
2	D2	Strategic	233.6	1.35		2358.5	1449.9	2042.7	2349.2	14,592.7
		1	339.7	1.36	0.4	2358.5	1449.9	2042.7	2367.2	14,611.4
		2	235.7	1.36	2.7	2365.6	1465.7	2123.9	2369.6	14,845.7
		3	252.1	1.41	2.0	2558.5	1556.3	2029.6	2546.7	15,389.6

, which also states the computational cost and the maximum navigation error. The latter, as in the previous case, slightly differs from the strategic one, thus not exceeding the maximum limits. Computation time is very low for the Level 1 (below the second) and is at a maximum 6 s when Level 2 and 3 are considered. Figure 12 again shows that the path obtained with Level 2 locally deviates from the strategic trajectory by providing less modification, also in terms of path cost. Conversely, when the Level 3 solution is used, path cost increases because the path is completely rebuilt without any knowledge of the ground information and costs. This could sometimes lead to a reduction of the trajectory length and duration (as in Mission 1). However, in all the cases, an increase of overall cost is provided.

6. Conclusions

Strategic and tactical planning algorithms to tackle UAV flight in urban environments have been presented and tested in this work, with the aim to provide an adaptive and scalable framework for urban operations. Indeed, the developed planning algorithms can deal with multiple sources of information by using the whole set of data or a subset of them. The design of the strategic path can be tailored to the user’s needs by acting on the weighting cost factor, which spatially deviates the solution path towards the highest priority requirement. In addition, tactical modification to the trajectory allows reacting to unfavorable conditions, still ensuring the safety and effectiveness of the path. The entire algorithmic chain has been tested on two scenarios that involve air taxi within a very complex and obstacle-dense urban environment, and medical delivery from mainland to island. Results demonstrate the effectiveness of the proposed algorithms in yielding optimized and time-saving trajectories, thus highlighting the advantage of using unmanned aircraft to perform such operations. The promising results of the current work fulfill the SMARTGO ambition by creating an approach that can be used as a milestone for future urban air mobility planning algorithm design. Future efforts are aimed at further developing the conceived architecture and assessing its performance in very high traffic density, including flight rules and/or structured airspace. As an example, the tactical planner computational burden can be further reduced in order to better comply with dense, rapidly evolving scenarios, thus requiring better software engineering, which is foreseen as further algorithm improvement.