Simulation-based sailboat trajectory optimization using on-board heterogeneous computers

• Autorzy: Dębski R.

Identyfikatory

DOI

10.7494/csci.2016.17.4.461

• Języki publikacji: EN

Abstrakty

EN

A dynamic programming-based algorithm adapted to on-board heterogeneous computers for simulation-based trajectory optimization was studied in the context of high-performance sailing. The algorithm can efficiently utilize all OpenCL-capable devices, starting the computation (if necessary, in single precision) on a GPU and finalizing it (if necessary, in double-precision) with the use of a CPU. The serial and parallel versions of the algorithm are presented in detail. Possible extensions of the basic algorithm are also described. The experimental results show that contemporary heterogeneous on-board/mobile computers can be treated as micro HPC platforms. They offer high performance (the OpenCL-capable GPU was found to accelerate the optimization routine 41 fold) while remaining energy and cost efficient. The simulation-based approach has the potential to give very accurate results, as the mathematical model upon which the simulator is based may be as complex as required. The black-box represented performance measure and the use of OpenCL make the presented approach applicable to many trajectory optimization problems.

Słowa kluczowe

EN

black-box optimization; trajectory optimization; dynamic programming; heterogeneous computing; micro HPC platform

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2016
• Tom: Vol. 17 (4)
• Strony: 461--481
• Opis fizyczny: Bibliogr. 39 poz, rys., wykr., tab.

Twórcy

autor

Dębski R.

• Department of Computer Science, AGH University of Science and Technology, Krakow, Poland

Bibliografia

• [1] Arora N., Russell R.P., Vuduc R.W.: Fast Sensitivity Computations for Trajectory Optimization. Advances in the Astronautical Sciences, vol. 135(1), pp. 545–560, 2009.
• [2] Bellman R.: The theory of dynamic programming. Buletin of the American Mathematical Society, vol. 60, pp. 503–515, 1954.
• [3] Bellman R.: On a Routing Problem. Quarterly of Applied Mathematics, vol. 16, pp. 87–90, 1958.
• [4] Betts J.T.: Survey of Numerical Methods for Trajectory Optimization. Journal of Guidance Control and Dynamics, vol. 21(2), pp. 193–207, 1998.
• [5] Byrski A., Debski R., Kisiel-Dorohinicki M.: Agent-based computing in an augmented cloud environment. Computer Systems Science and Engineering, vol. 27(1), pp. 7–18, 2012.
• [6] Ceriotti M., Vasile M.: MGA trajectory planning with an ACO-inspired algorithm. Acta Astronautica, vol. 67(9–10), pp. 1202–1217, 2010.
• [7] Crauser A., Mehlhorn K., Meyer U., Sanders P.: A parallelization of Dijkstra’s shortest path algorithm. In: L. Brim, J. Gruska, J. Zlatuka, eds., Mathematical Foundations of Computer Science 1998, Lecture Notes in Computer Science, vol. 1450, pp. 722–731, Springer–Berlin–Heidelberg, 1998.
• [8] Dalang R.C., Dumas F., Sardy S., Morgenthaler S., Vila J.: Stochastic optimization of sailing trajectories in an upwind regatta. Journal of the Operational Research Society, 2014.
• [9] Debski R.: Gradient-Based Algorithms in the Brachistochrone Problem Having a Black-Box Represented Mathematical Model. Journal of Telecommunications & Information Technology, vol. 2014(1), pp. 32–40, 2014.
• [10] Debski R.: High-Performance Simulation-Based Algorithms for Alpine Ski Racer’s Trajectory Optimization in Heterogeneous Computer Systems. International Journal of Applied Mathematics and Computer Science, vol. 24(3), pp. 551–566, 2014.
• [11] Debski R., Byrski A., Kisiel-Dorohinicki M.: Towards an agent-based augmentedcloud. Journal of Telecommunications and Information Technology, vol. 1, pp. 16–22, 2012.
• [12] Debski R., Krupa T., Majewski P.: ComcuteJS: A Web Browser Based Platform for Large-scale Computations. Computer Science, vol. 14(1), pp. 143–152, 2013.
• [13] Dijkstra E.W.: A note on two problems in connexion with graphs. Numerische Mathematik, vol. 1, pp. 269–271, 1959.
• [14] Dramski M.: A comparison between Dijkstra algorithm and simplified ant colony optimization in navigation. Zeszyty Naukowe / Akademia Morska w Szczecinie, vol. 29 (101), pp. 25–29, 2012.
• [15] Dussault J.P.: Solving trajectory optimization problems via nonlinear programming: the brachistochrone case study. Optimization and Engineering, vol. 15(4), pp. 819–835, 2014.
• [16] Gaster B.R., Howes L.W., Kaeli D.R., Mistry P., Schaa D.: Heterogeneous Computing with OpenCL – Revised OpenCL 1.2 Edition. Morgan Kaufmann, 2013.
• [17] Harish P., Narayanan P.: Accelerating large graph algorithms on the GPU using CUDA. In: High performance computing – HiPC 2007, pp. 197–208, Springer, 2007.
• [18] Jasika N., Alispahic N., Elma A., Ilvana K., Elma L., Nosovic N.: Dijkstra’s shortest path algorithm serial and parallel execution performance analysis. In: MIPRO, 2012 Proceedings of the 35th International Convention, pp. 1811–1815, IEEE, 2012.
• [19] Lewis R.M., Torczon V., Trosset M.W.: Direct Search Methods: Then And Now.Journal of Computational and Applied Mathematics, vol. 124, pp. 191–207, 2000.
• [20] Marchaj C.: Aero-hydrodynamics of sailing. Dodd, Mead, 1980.
• [21] Marchaj C.: Sail Performance: Techniques to Maximize Sail Power. International Marine/McGraw-Hill, 2003.
• [22] Park C., Pan J., Manocha D.: Real-time optimization-based planning in dynamic environments using GPUs. In: Robotics and Automation (ICRA), 2013 IEEE International Conference on, pp. 4090–4097, IEEE, 2013.
• [23] Petres C., Romero-Ramirez M.A., Plumet F.: Reactive path planning for autonomous sailboat. In: 2011 15th International Conference on Advanced Robotics (ICAR 2011), pp. 112–117, IEEE, 2011.
• [24] Philpott A., Henderson S., Teirney D.: A Simulation Model for Predicting Yacht Match Race Outcomes. Operation Research, vol. 52(1), pp. 1–16, 2004.
• [25] Philpott A., Mason A.: Optimising yacht routes under uncertainty. In: The 15th Cheasapeake Sailing Yacht Symposium, 2001.
• [26] Pontryagin L.S., Boltyanski V.G., Gamkrelidze R.V., Mischenko E.F.: The Mathematical Theory of Optimal Processes. Interscience, NY, 1962.
• [27] Posik P., Huyer W.: Restarted local search algorithms for continuous black box optimization. Evolutionary Computation, vol. 20(4), pp. 575–607, 2012.
• [28] Posik P., Huyer W., Pal L.: A Comparison of Global Search Algorithms for Continuous Black Box Optimization. Evolutionary Computation, pp. 1–32, 2012.
• [29] Rippel E., Bar-Gill A., Shimkin N.: Fast graph-search algorithms for general aviation flight trajectory generation. Journal of Guidance, Control, and Dynamics, vol. 28(4), pp. 801–811, 2005.
• [30] Singla G., Tiwari A., Singh D.P.: New Approach for Graph Algorithms on GPU using CUDA. International Journal of Computer Applications, vol. 72(18), pp. 38–42, 2013, published by Foundation of Computer Science, New York, USA.
• [31] Stelzer R., Proll T.: Autonomous sailboat navigation for short course racing. Robotics and autonomous systems, vol. 56(7), pp. 604–614, 2008.
• [32] Stillwell J.: Mathematics and its History. Springer, third ed., 2010.
• [33] Stryk von O., Bulirsch R.: Direct and indirect methods for trajectory optimization. Annals of Operations Research, vol. 37(1), pp. 357–373, 1992.
• [34] Sussmann H.J., Willems J.C.: 300 years of optimal control: from the brachystochrone to the maximum principle. Control Systems, IEEE, vol. 17(3), pp. 32–44, 1997.
• [35] Sussmann H.J., Willems J.C.: The brachistochrone problem and modern control theory. Contemporary trends in nonlinear geometric control theory and its applications (Mexico City, 2000), pp. 113–166, 2002.
• [36] Szłapczynski J.: Customized crossover in evolutionary sets of safe ship trajectories. Int. J. Appl. Math. Comput. Sci, vol. 22(4), pp. 999–1009, 2012.
• [37] Szynkiewicz W., Błaszczyk J.: Optimization-based approach to path planning for closed chain robot systems. International Journal Applied Mathematics and Computer and Science, vol. 21(4), pp. 659–670, 2011.
• [38] Vasile M., Locatelli M.: A hybrid multiagent approach for global trajectory optimization. Journal of Global Optimization, vol. 44(4), pp. 461–479, 2009.
• [39] Wagner S., Kaplinger B., Wie B.: GPU Accelerated Genetic Algorithm for Multiple Gravity-Assist and Impulsive V Maneuvers. In: AIAA/AAS Guidance Navigation and Control Conference AIAA, vol. 4592, p. 2012, 2012.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.