20 Jun 2017 Frankfurt - During the Quantum Annealing session on Tuesday morning at ISC17, Tobias Stollenwerk from the German Aerospace Center (DLR) in Cologne presented work that was done in close collaboration with people from NASA Ames. The problem he addressed, is a special issue in aerospace research, namely the deconflicting of wind-optimal trajectories. Tobias Stollenwerk explained that everyday there are around 1000 flights across the Atlantic. Currently, flights are routed through aerospace highways but people are thinking about doing something called free-flight trajectories to fit more flights into the limited airspace. The solution is to deploy wind-optimal trajectories but of course there will be conflicts. The challenge is how to avoid these conflicts.
This is done for example by deviating the trajectories globally. As a starting point, the team used simulated annealing to change the trajectories and avoid the conflicts. However, the team also tried to map the problem in order to solve it on a D-Wave machine. The team wanted to formulate the problem as an Ising model.
First, Tobias Stollenwerk tried to formulate the optimization problem. The easiest thing to do is to just keep the flight on the ground for a certain time and work with departure delays. Of course, one wants to keep the delay (d) as minimal as possible. Therefore, the total cost function is represented in the following formula: C = Sigmaidi, namely given as the sum of all possibilities of all departure delays. At the same time, one wants to avoid all the conflicts. This is the optimization problem.
These are obviously approximations. One could also think about manoeuvres but Tobias Stollenwerk preferred to start with the easy model because the D-Wave system has limited qubits. The team initially only worked with pairwise conflicts and considered three different pairwise conflicts. There are two trajectories that are dissecting each other. Whether they will be really in conflict depends on the arrival times and delays of both flights. So the problem is a difference of arrival times at a potential conflict k between flights i and j. If the difference in arrival time is very small, there is no conflict. If it is very large there is also no conflict but if it is close to zero there will be a conflict. One can say that the conflict is a real conflict if the difference in arrival time is smaller than three minutes.
The conflicts are accounted for in classes. It is often the case that there are parallel conflicts. If one wants to avoid those conflicts, one has to perform the simulation for all the trajectory points. There are constraints to avoid conflicts. The difference in departure delays should not be in a certain interval which is given by the arrival times. The optimization problem is written down as follows: one minimizes the total delay with a constraint in the difference of the departure delays. This is done for all the flights involved in conflict k. If one solves that problem, one has a solution that minimizes the cost function at all delays and at the same time avoids all the conflicts.
Tobias Stollenwerk explained that one has to subdivide the problem. This is a good thing because one wants to put some small testing problems onto the D-Wave machine. In the conflict graph, he showed that the green and the red flights are not in conflict with each other. One can write the problem down as a graph. Each of the nodes in the graph is a flight and each of the edges is a conflict. You can take one small subproblem that you can study. The red trajectories are an example of a bigger instance. In total, if one assumes a maximum departure delay of 18 minutes, one gets about 50 of these subproblems. Tobias Stollenwork showed the number of subproblems against the size for different maximum delays. There are a lot of small problems where one only has two flights with one conflict. There are only a few big classes of problems. These don't fit on the D-Wave machine. All the small subproblems however can be used to test the approach on the D-Wave machine.
The next thing you have to do is to discretize the problem because the original optimization problem had continuous variables. The departure delays will be discretized. The problem was solved with a classical constraint programming solver. The cost function is on the vertical axis and the discretization is on the horizontal axis. One can see the step-by-step discretization. If one has a fine discretization, one has an optimal solution but if one has a coarse discretization, the solution quality decreases. Therefore, you need a very fine discretization with time steps of one minute.
Now the problem can be mapped to a quadratic unconstrained binary optimization (QUBO). One has integer variables. The departure delay diis written as the sum over binary variables dialpha. The alpha can take all the values that the dican take. If one does that, one has to make sure that for a given i only one of these alphas is one or the other zero. One can write down the cost function as a QUBO. The first term of the cost function is just the sum of all the departure delays. The constraints are incorporated by two additional terms. The first term is due to the encoding. As Tobias Stollenwerk explained, only one of these alphas can be one for each flight. If this is the case, then this term is zero. The same is true for the third term which is the conflict avoidance. One sums up all the differences in the departure delays which are inside the interval. If the two bits are activated, the cost function increases but one doesn't want that. The ground state of this will not happen.
One has to put some sufficient penalty weights in front of these two terms in order to make sure that the ground state really fulfills these constraints so that the contribution to these two terms is zero. In order to find the minimal sufficient penalty weights, one can use an exact solver on a classical computer to solve the QUBO. The X-axis is one penalty weight and the other axis represents the other penalty weight. The green dots are valid solutions, Tobias Stollenwerk showed the audience, where the constraint contributions vanish. The black dots are the cases where the constraint contributions do not vanish, so the constraints are not fulfilled. One has to make sure to keep the penalty weights above the black boundary.
Then, one comes to the quantum annealing. The team embedded these problems into two of the D-Wave machines, the D-Wave 2X and the D-Wave 2000Q. The team could embed instances with up to 64 flights and 261 conflicts. The team embedded the problem on a chimera graph. Some parameters were tried out. The first one was the coupling between physical qubits which belong to one logical qubit. The team checked the number of annealing runs and also used gauging. The team calculated the time to solution with 99 percent probability, where p is the success probability that increases for larger problems and finer discretizations. T is the annealing time which is always 20 microseconds.
Tobias Stollenwork showed the result for this type of solution against the number of flights. There are three different curves. The red colour means a very fine discretization which one needs to get a quality solution. The green colour is more coarse and the blue colour is still more coarse. The audience could see that the time to solution increases for finer discretization and also for bigger problems and the success probability decreases. This is due to the limited precision of the machine.
First of all, the team wanted to get rid of the parameter of coupling in between the physical qubits and looked at the success probability, comparing the coupling against a certain number which is the measure for the precision needed on the machine. If the precision needed is about 30, the precision of the machine declines. The team hasn't investigated the different embedding approaches but just used the embedding algorithm from the D-Wave machine but there are also smarter things to think of instead of using the default method.
One can also incorporate manoeuvre delays. One can think of avoiding conflicts in the air which is more realistic. One can map this problem also to a QUBO but the team hasn't done any annealing runs on that problem.
Tobias Stollenwerk concluded that one can map the deconflicting problem to a QUBO. One needs fine discretization to solve the problem. The D-Wave annealing solutions are good for small instances. Next steps consist in reducing the needed precision by alternative embedding approaches and by solving the manoeuvre model on a D-Wave machine.