A Discrete-Continuous Algorithm for Free Flight Planning

Round 1

Reviewer 1 Report

The manuscript proposes a hybrid discrete-continuous algorithm for flight planning in free flight airspaces, which is an interesting problem that deserves attention. The authors provide error and complexity estimates. They also carry out a computational study and analyse the choice of the switch over point. The paper appears to be well written and comprehensively referenced.

It would be good to have a thorough comparison with other well-known existing algorithms developed for this problem.

Author Response

We'd like to thank you for your helpful comments and remarks. We have addressed the issues raised as stated below, and are confident that the revision improved the manuscript considerably.

We absolutely agree that a comparison of state of the art algorithmic approaches and different implementations is worthwile. However, the actual performance of different implementations depends very much on technical details, and would shift the focus of the manuscript completely. Algorithms, on the other hand, can mainly be compared in terms of their asymptotic complexity and, to a limited extent, constant effort factors. We have extended the text in that respect, discussing algorithmic approaches for continuous trajectory optimization in more detail and relating the used A* algorithm to approaches like A*-RRT and its variants on the discrete side, which have different trade-offs between computational effort and global optimality.

Reviewer 2 Report

The authors state in the abstract that they propose a flight planner for not ocluded flight spaces, using A* algorithm. Well, A*RRT algorithms are usually used to obtain a feasible path in non-convex search spaces, and using them for not occluded flight spaces might seem strange at first.

There are multiple approaches, such as A*-RRT, A*-RRT*, RRT*FN, RRT*-AR, RT-RRT*, Theta*-RRT, RRT-GPU, APF-RRT, MVRRT*, RRT-Blossom, or RRdT* which do the job as well. The introduction, esp. the state of the art - seems too short to discuss all the points.

Section 2 - please discuss why discretization is employed, as the Maximum Principle is a very strong tool, and resorting to discretized space, deprives you of the possiblity to tell you have both necessary and sufficient conditions (see Optimal COntrol of Athans).

It is strange why do the authors decide to discretize the search space, as the solution could simply be obtained analytically? Please discuss this issue.

Shortest path algorithm - if you have no occlusion, the shortest path goes along the Euclidean distance, and is a segment of the line. Why should you use the A* algorithm is other solutions, for free spaces exist? Would not it be better to cast the problem to a penalty function one to search the space or to obtain the solution with relaxed constraints?

Please discuss in depth the difference between your approach and limitation (possible limitations) of variational calculus/Maximum Principle or, simply, dynamic programming with penalty function???

Otherwise, why did not you try to use Newton-Raphson algorithm with Armijo step rule to override the problem?

Finally, the authors have compared fully-discrete solution to their combined approach. The analytical solution is missing, though, for comparative purposes.

Author Response

The authors state in the abstract that they propose a flight planner for not ocluded flight spaces, using A* algorithm. Well, A*RRT algorithms are usually used to obtain a feasible path in non-convex search spaces, and using them for not occluded flight spaces might seem strange at first.

A* variants are currently state of the art in (non-free) flight planning restricted to given airway networks. While we only consider the free-flight subproblem, practical flight planning will, for the foreseeable future, include some restrictions to airway networks on the route even if large free-flight areas are crossed, such that A* is the natural departure point for our work.

There are multiple approaches, such as A*-RRT, A*-RRT*, RRT*FN, RRT*-AR, RT-RRT*, Theta*-RRT, RRT-GPU, APF-RRT, MVRRT*, RRT-Blossom, or RRdT* which do the job as well. The introduction, esp. the state of the art - seems too short to discuss all the points.

We're grateful for this valid suggestion, and have extended the text with a discussion of RRT algorithms as alternative graph construction and refinement algorithms.

Section 2 - please discuss why discretization is employed, as the Maximum Principle is a very strong tool, and resorting to discretized space, deprives you of the possiblity to tell you have both necessary and sufficient conditions (see Optimal COntrol of Athans).

Since for smooth but otherwise arbitrary wind fields no analytic solution to the trajectory optimization problem exists, discretization is unavoidable. This is, of course a very different kind of discretization compared to predefined graphs in which shortest paths are computed. We have extended the text by stating this explicitly. Even when using the maximum principle, this results in a nonlinear boundary value problem which can only be solved numerically by discretization, e.g., using single/multiple shooting, collocation, or spectral methods. This renders checking optimality conditions subject to discretization errors -- similar to the direct approach of discretizing the optimal control problem into a nonlinear program.

It is strange why do the authors decide to discretize the search space, as the solution could simply be obtained analytically? Please discuss this issue.

Given an arbitrary wind field, the solution cannot be found analytically at all. Thus, discretization is unavoidable.

Shortest path algorithm -- if you have no occlusion, the shortest path goes along the Euclidean distance, and is a segment of the line. Why should you use the A* algorithm is other solutions, for free spaces exist? Would not it be better to cast the problem to a penalty function one to search the space or to obtain the solution with relaxed constraints?

Straight lines are only shortest paths in the absence of any gradients in the wind field. As usually commercial flights pass windy areas, shortest paths can be much more complex. Indeed, even though the free flight area is assumed not to be occluded, spatially variable wind can lead to separate locally optimal paths -- comparable to occlusions contained within the free flight area. Thus, the A* algorithm is used here to approximate globally optimal paths well enough for Newton-type continuous optimal control methods to converge to the global optimum (with high probability -- reasonable theoretical guarantees do not yet exist).

Please discuss in depth the difference between your approach and limitation (possible limitations) of variational calculus/Maximum Principle or, simply, dynamic programming with penalty function???

Following the suggestion of all referees, we have extended the text by discussing optimal control approaches as well as path planning approaches in more detail, and adding several more references.

Otherwise, why did not you try to use Newton-Raphson algorithm with Armijo step rule to override the problem?

This is actually a good point, thanks. While linesearch in Newton's method extends the domain of convergence, it cannot guarantee convergence even to a local minimizer if the (reduced) objective is nonconvex. Depending on the wind, this is the case and leads to multiple local minima. Trust region methods treating nonconvex QPs appropriately converge to some -- hopefully nearest -- local minimizer except for pathological situations.
Thus, reliable convergence to a global minimizer requires starting in a sufficiently small neighborhood of the solution, for which we use the global yet approximate A* optimization. We feel that, in doubt, using a finer graph discretization and orinary Newton method is more robust and reliable, and maybe even more efficient, than relying on trust region or linesearch globalization strategies. We have extended the text by a brief discussion of this aspect.

Finally, the authors have compared fully-discrete solution to their combined approach. The analytical solution is missing, though, for comparative purposes.

As mentioned before, unfortunately there is no analytical solution against which we could compare.

Reviewer 3 Report

• The article presents an hybrid method to determine flight paths in free spaces based on a discrete step performed by A^* shortest path algorithm and a Newton step to refine the result. The algorithm called DisCOptER is tested on four test problems. The algorithm is compared to a pure discrete optimization approach and it is shown that it is far more superior to the latter.
• The article is well written and the methods are well presented. there are some small typos and English mistakes that should be corrected.
• The authors should include in their bibliography some references related to trajectory optimization (that is an optimal control problem) and for which many methods and references do exist in the literature, some of them able to reach global optima. 
• As shown on Figure 7, the method can experience some convergence issues for problems c and d, depending on graph density h and graph connectedness width l since a suitable solution should be provided to the Newton solver. It is obvious that the optimal graph characteristics should depend on the velocity field (or its gradients) characteristics. The authors should comment on that point more precisely and propose alternatives.
• The authors should compare their algorithm with a state-of-art hybrid algorithm for trajectory optimization for which many softwares exist.

Author Response

The article presents an hybrid method to determine flight paths in free spaces based on a discrete step performed by A* shortest path algorithm and a Newton step to refine the result. The algorithm called DisCOptER is tested on four test problems. The algorithm is compared to a pure discrete optimization approach and it is shown that it is far more superior to the latter.
The article is well written and the methods are well presented. there are some small typos and English mistakes that should be corrected.

The authors should include in their bibliography some references related to trajectory optimization (that is an optimal control problem) and for which many methods and references do exist in the literature, some of them able to reach global optima.

Thanks for the suggestion. In line with recommendations by all the reviewers, we have extended the text by discussing both continuous optimal control approaches and discrete path planning methods in more detail, including several additional references.

As shown on Figure 7, the method can experience some convergence issues for problems c and d, depending on graph density $h$ and graph connectedness width l since a suitable solution should be provided to the Newton solver. It is obvious that the optimal graph characteristics should depend on the velocity field (or its gradients) characteristics. The authors should comment on that point more precisely and propose alternatives.

This is a valid concern. In principle, there are two possible ways to address this issue: by deriving analytical error bounds in terms of some norm of the wind field, or by designing truly adaptive algorithms. Both ways have their merits and their (relative) weaknesses, and both are topic of ongoing research. However, both are also rather complex, and their inclusion would extend the paper by a very significant amount. Thus, we prefer them here, but have added a brief remark on that aspect.

The authors should compare their algorithm with a state-of-art hybrid algorithm for trajectory optimization for which many softwares exist.

We absolutely agree that a comparison of state of the art algorithmic approaches and different implementations is worthwile. However, the actual performance of different implementations depends very much on technical details, and would shift the focus of the manuscript completely. Algorithms, on the other hand, can mainly be compared in terms of their asymptotic complexity and, to a limited extent, constant effort factors. We have extended the text in that respect, discussing algorithmic approaches for continuous trajectory optimization in more detail and relating the used A* algorithm to approaches like A*-RRT and its variants on the discrete side, which have different trade-offs between computational effort and global optimality.

Round 2

Reviewer 2 Report

Thank you for your replies to my comments. Now I do understand the idea of avoiding analytical solutions, however at the same time I believe that using algorithms with escape property to avoid local minima, such as algorithms with momentum, as those of NNs, would either way do the job, e.g. to find a deep enough local minimum. 

Nevertheless, I have to accept your arguments, and am grateful for extending the paper with the text you inserted after the first round of reviews. The paper is acceptable in the current form. 

Reviewer 3 Report

The authors have answered my requests about their work. I recommend therefore, the publication of their article.