Transparent Path Planning For Uncrewed Air Traffic Management

Abstract

With the rapid advancement of technology, drones are being actively deployed across various domains. To manage their growing presence in the airspace, Uncrewed Air Traffic Management (UTM) has been proposed and is currently under development. Given the expected high volume of drone traffic, UTM will rely heavily on high levels of automation, as it is impractical to control each drone manually in the manner of traditional Air Traffic Control (ATC). However, this reliance on automation presents potential risks, particularly in airspace around airports where crewed aircraft are taking off and landing. Since completely reliable automation has not yet been achieved, anomalies or failures in UTM systems could increase the risk of collisions between drones and crewed aircraft. Therefore, UTM still warrants human supervision to ensure the safety of drone operations.

As automation becomes more advanced and complex, it also becomes increasingly difficult for humans to supervise, thereby hindering their trust and acceptance. Previous research suggests that some form of “seeing-into” transparency may be required to address this issue and support effective human supervision of automated systems. In this dissertation, “seeing-into” transparency is categorised into operational transparency and engineering transparency. Operational transparency offers (real-time) insights into the automation’s states, actions, goals, and environmental impact, helping operational users maintain situation awareness and respond effectively to changing conditions. Engineering transparency, in contrast, discloses the inner workings of automation, enabling users to develop a deeper understanding of automation behaviour. This research adopts a bottom-up approach, beginning with engineering transparency and progressing towards operational transparency.

This dissertation focuses on achieving transparent path planning in UTM routing. To this end, a visual approach was first proposed to reveal the internal processes of path-planning algorithms, with a focus on graph- and sampling-based ones, as shown in Chapter 2. To demonstrate the effectiveness of the approach, a novel web-based pathfinding visualiser was developed that incorporates various classic and advanced path-planning algorithms, such as A*, Theta*, Anya, Polyanya, Rapidly-exploring Random Tree (RRT), RRT*, Informed RRT* and Batch Informed Tree (BIT*). To evaluate the impact of the proposed approach on algorithm runtime, extensive benchmark tests were performed on public datasets. Results show that extracting all search trees during the search process may significantly slow down the original algorithms. For large-scale, real-time operations, it is recommended to record only necessary data during the search and perform search tree extraction afterwards for visualisation.

To further investigate the effectiveness of algorithmic transparency, a user study was conducted to evaluate its impact on human understanding, as presented in Chapter 3. Considering that directly presenting the search process may overwhelm users, particularly in operational contexts, the path-planning transparency was structured into six distinct levels. Results indicate that as the transparency level increases, so does human understanding. However, the relationship between transparency and understanding is not a linear one. When the algorithm behaves contrary to human expectations and increased transparency fails to provide a clear explanation, users may become even more confused than without the additional transparency. For non-expert users unfamiliar with the algorithm, full transparency is often critical for meaningful understanding. The user study suggests that sampling-based algorithms may be easier to comprehend than graph-based algorithms. While the randomness inherent in sampling-based algorithms makes their behaviour difficult to predict, their overall rationale and underlying principles are meaningful and intuitive to humans.

As the ultimate goal of this dissertation is to achieve transparent path planning for UTM, the focus was then shifted from path-planning algorithms to UTM routing, broadening the concept of algorithmic transparency from purely engineering concerns to encompass operational dimensions, as shown in Chapter 4. A unified transparency taxonomy was developed, integrating diverse aspects of algorithmic transparency. Based on the proposed taxonomy, twenty transparency elements and their corresponding visual prototypes were devised for UTM routing. A survey study was then conducted to investigate the needs and preferences of Air Traffic Controllers (ATCos) and drone experts regarding these elements and prototypes. Results show that operational transparency is deemed more useful than engineering transparency in nominal UTM scenarios, whereas engineering transparency becomes more valuable when UTM routing fails. In the survey, operators were also asked to group the transparency elements, and their groupings aligned with the proposed transparency taxonomy.

The survey study captures only the initial opinions of operators, shaped by their prior knowledge and experience. To gain more insights, a human-in-the-loop experiment was performed to further examine the actual usage of various transparency elements in dynamic scenarios, where time pressure is a key concern, as shown in Chapter 5. Results show that information regarding the Closest Point of Approach (CPA) between drones and crewed aircraft is the most useful element for supporting tactical UTM supervision. When UTM routing fails, operators typically seek more information, such as constraint changes and details about the algorithm’s inner workings, to understand the failure and to gather clues that inform their intervention strategies. Similar to the user study presented in Chapter 3, the experiment in Chapter 5 also suggests that in UTM contexts, sampling-based algorithms might be more suitable for supervision than graph-based algorithms. This is likely because the search tree visualisation of sampling-based algorithms could more clearly convey the algorithms’ exploration efforts, offering useful cues for human intervention, such as indicating regions that are likely to be conflict-free.

In conclusion, this research achieves algorithmic transparency in path planning and demonstrates its application within UTM contexts. It contributes further empirical evidence to the growing body of research underscoring the importance and benefits of algorithmic transparency. The findings suggest that algorithmic transparency can enhance human understanding, but its utility in operational settings may be limited by situations, time pressure, and workload. As operators develop trust or expertise, their need for transparency may diminish. Overall, transparency is essential to facilitating trustworthy automation, especially when it is not yet fully reliable.