A lower bound computation method using energy-state approximation and its application to supersonic aircraft shortest path problems

In this paper, a lower bound computation method using energy-state approximation is proposed and applied to supersonic aircraft shortest path problems. The proposed algorithm is basically based on the forward dynamic programming combined with the branch-and-bound technique. This hybrid algorithm can reduce computational requirements and computer memory requirements of the conventional dynamic programming substantially by incorporating the bounding operation of the branch-and-bound into the computing process of the forward dynamic programming. The lower bound of the optimal solution which becomes necessary in execution of the hybrid algorithm is computed by the modified energy-state approximation which can be obtained by modifying partially the conventional energy-state approximation in order to satisfy the lower bound condition. This computation to obtain the lower bound solution is very simple without any difficulties. Also, in this paper, we propose some methods of lower bound reinforcement to obtain a greater reduction of computation requirements in the hybrid algorithm. The proposed hybrid algorithm uses many of the advantages of dynamic programming and can easily be applied to complicated nonlinear systems. In numerical examples of the minimum-time-to-climb problems of the supersonic aircraft, a typical solution obtained by the hybrid algorithm is equivalent to that of the steepest descent method within quantization errors of 0.7%. The number of computation requirements of the hybrid algorithm which is required to obtain optimal solutions is equal to or less than 1.4% at the ratio with the number of computation requirements in the conventional dynamic programming. The computing time is about 60 seconds on a computer with speed of 20 MIPS including 1 second for the computation of the lower bound. Also, when applying this method to problems on changing the boundary conditions of the original problem variously to examine the robustness of the hybrid algorithm, the number of computational requirements of the hybrid algorithm was equal to or less than 2% of that for any problems. On the other hand, when using a strengthened lower bound, this number was equal to or less than 1%. Also, we applied the hybrid algorithm to the supersonic aircraft, changing aerodynamical data variously in order to examine the influence of the change of the aerodynamical data of the supersonic aircraft comprehensively. As a result, the optimal path under various conditions could be generated unifyingly without needing skill when using this method was confirmed.