Drones Path-Planning using Quantum Computing

As a major and global player in the aeronautical community, Thales brings its expertise in the field to the drone ecosystem to transform the future of unmanned aviation and urban air mobility (UAM / Urban Air Mobility). From flight avionics to the design and operation of UAV (Unmanned Aerial Vehicle) systems, through wireless communication systems, digital identity and cybersecurity, satellite systems enabling positioning and navigation, Thales is redefining what is possible in the UAS (Unmanned Aircraft System) sector. Thales also provides air traffic management solutions, including for small drones, long-range drones and VTOL (Vertical Take Off and Landing) taxi drone operating in restricted airspace.

Ensuring the safety of the skies is becoming more and more complex today. Whereas previously the aviation sector could grow on the basis of ever-increasing traffic flows, today air traffic management (ATM) has become much more complex with the advent of unmanned aerial systems. (UAS). Conventional trajectory calculation methods will not allow scaling up for an exponential increase in drones requiring short reaction times to re-route drone traffic with high levels of security.

Thus, the calculation of large-scale secure trajectories (hundreds of thousands of drones across a country) is a blocking point for the development of UTM (UAS Traffic Management). In particular, deconfliction strategies in air traffic management of drones to update their 4D trajectories in the face of unpredictable events or when priority trajectories are added in the airspace. Current CDR (Conflict Detection & Resolution) methods used for civil air traffic control will not scale-up. Drones also make it possible, because of their autonomy, to think about coordinating trajectories to reduce the decision-making bottleneck. This will require changing by a factor > 1000 in the acceleration of the calculation of coordinated trajectories to be applied on dense scenarios in a limited area with many 4D contracts, potential incidents and emergency procedures.

UTM is designed to meet the demand and expectations of a wide range of operations that are ever increasing in complexity and risk, thanks to an innovative and competitive open market of service providers. On the European side, the operational model envisaged, called U-Space, also identifies the needs for coordination between the actors, and for the distribution of decisions.

This use case aims to help establish the specifications and develop the scaling of future drones trajectory optimization algorithms based on quantum computers, by validating new computational concepts and studying their constraints for integration into solutions.

In classical calculation, there are two ways to calculate an optimal trajectory, the deterministic approach and the Monte-Carlo approach.

Many Githubs and open platform integrate Python codes for classical algorithms:

The deterministic approach assumes that we have an input cost map that defines the constraints to be checked (e.g. prohibited flight zones). This approach is numerical and makes it possible to solve anisotropic problems (physical properties of the medium vary according to the direction), with local constraints making the curves smooth.

Numerical methods for solving eikonal equations currently fall into two groups:

Computing minimal paths for non-holonomic models implementing curvature penalization requires solving degenerate eikonal equations on high-dimensional spaces. Reducing computing times by an order of magnitude would make it possible to envisage controlling systems (drones, etc.) in real time. Parallelization schemes on GPUs currently require the use of the canonical discretization stencil of the Cartesian grid, and are therefore not suitable for managing strong anisotropies. It does not allow trajectories to be calculated when considering several drones. Indeed the number of constraints grows exponentially with the number of drones.

References & codes :

Monte-Carlo Approach: Rapidly exploring Random Trees (RRT), and its extension RRT* (ensuring finding the optimal path with probabilistic completeness guarantees) has been one of the most prevalent and popular motion planning techniques for two decades. Recently, new algorithms have been developed as a MCPP algorithm (Monte-Carlo Path Planning), a MCTS-based (Monte-Carlo Tree Search) Path Planning. MCPP enjoys exponential convergence in choosing the optimal path in MDP problems and has convergence guarantees to find a feasible path in POMDP environments with limited distance observability. This MCTS-based path-planning framework can incorporate different exploration strategies, such as our state-of-the-art methods, Power-UCT, and TENTS, into POMDP path planning problems.

References:

We have identified first papers addressing Quantum Algorithms for Path Planning: