Safe airplane and drone traffic

Teaming up with Thales: identifying optimum drone paths through space and time

The Thales Group was among those wanting to know how quantum computers could get their new business models off the ground. Thales air traffic management systems ensure safe and efficient movement of aircraft through all phases of operation. But aside from planes, more and more drones will be in the sky in the future. From flying taxis to monitoring and delivery drones that supply ur­gently needed medications, the potential is huge. Thales plans to expand its business model so it can keep track of these newer flying objects as well. But previously proven systems are not up to the new challenges: In addition to optimum flight routes, no-fly zones and times must be factored in, and collisions must be avoided – all for a large number of drones. This means new methods are needed. With this in mind, Thales contacted the team headed by Dr. Nico Piatkowski at the Fraunhofer Institute for Intelligent Analysis and Information Systems IAIS in Sankt Augustin, near Bonn.

“Finding the shortest route is the basis of any navi­gation system today. But once they are asked to find multiple shortest routes that also interact with each other, traditional computers quickly run up against their limitations. In our scenario, the number of possible in­teractions is large because the drones must be kept from colliding with each other or with buildings. With quantum computers, we can code this kind of information direct­ly into the qubits,” Piatkowski explains. For Thales, he and his team initially formalized the question and all the relevant factors in mathematical terms. They extracted a 3D model of Bonn from a geodatabase containing height and altitude information and then added the fourth di­mension, time. The team modeled the various potential paths taken by multiple drones as tube-like spaces in this graph to prevent any coinciding routes. The issue: There would be more than 1.2 million nodes − places where a drone could theoretically be present − above Bonn’s city center alone. That is far too many for present-day quantum computers.

To help with this, the researchers have lifted some of the burden on the quantum computers by reassigning tasks that traditional computers can do very well anyway: “We set the start and destination points and have a tra­ditional computer calculate the shortest routes. All the quantum computer has to do then is take these pre-selected paths and identify the routes with no col­lisions. So it is no longer consid­ering 1.2 million points. Instead, it only has to take a few hundred paths into consideration.” The quantum result is then checked again by a traditional algorithm, and if there are still collisions nonetheless, the number of possible paths can be expanded. “This means finding out which part of the problem is suitable for a quantum computer and which isn’t is a crucial point,” Piatkowski notes.

For their calculations, the researchers compared a simulated annealing software algorithm, a D-Wave quan­tum computer and the IAIS Evo Annealer hardware, patented at their institute, which simulates how a quan­tum computer works. This allows them to investigate, with much greater efficiency than before, the extent to which it will be possible to use quantum computing to solve specific mathematical problems in the future. “We’re already getting profitable results on both systems with zero collisions and optimum route length for an example with 20 drones in a limited area,” Piatkowski says, pleased. The researchers have thus been able to show that the drone pathfinding problem can be used with qubits. As the next step, they plan to test the quantum algorithm they cre­ated on additional quantum computers.