An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems

• Autorzy: Dębski R.

Identyfikatory

DOI

10.1515/amcs-2016-0025

• Języki publikacji: EN

Abstrakty

EN

A new dynamic programming based parallel algorithm adapted to on-board heterogeneous computers for simulation based trajectory optimization is studied in the context of “high-performance sailing”. The algorithm uses a new discrete space of continuously differentiable functions called the multi-splines as its search space representation. A basic version of the algorithm is presented in detail (pseudo-code, time and space complexity, search space auto-adaptation properties). Possible extensions of the basic algorithm are also described. The presented experimental results show that contemporary heterogeneous on-board computers can be effectively used for solving simulation based trajectory optimization problems. These computers can be considered micro high performance computing (HPC) platforms—they offer high performance while remaining energy and cost efficient. The simulation based approach can potentially give highly accurate results since the mathematical model that the simulator is built upon may be as complex as required. The approach described is applicable to many trajectory optimization problems due to its black-box represented performance measure and use of OpenCL.

Słowa kluczowe

EN

dynamic programming; black-box optimization; heterogeneous computing; micro HPC platform; cubic Hermite splines

PL

programowanie dynamiczne; obliczenia heterogeniczne; system komputerowy

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 2
• Strony: 351--365
• Opis fizyczny: Bibliogr. 42 poz., rys., tab., wykr.

Twórcy

autor

Dębski R.

• Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland

Bibliografia

• [1] Arora, N., Russell, R.P. and Vuduc, R.W. (2009). Fast sensitivity computations for trajectory optimization, Advances in the Astronautical Sciences 135(1): 545–560.
• [2] Bai, J., Chen, L., Jin, H., Chen, R. and Mao, H. (2012). Robot path planning based on random expansion of ant colony optimization, in Z. Qian et al. (Eds.), recent Advances in Computer Science and Information Engineering, Lecture Notes in Electrical Engineering, Vol. 125, Springer, Berlin/Heidelberg, pp. 141–146.
• [3] Bellman, R. (1954). The theory of dynamic programming, Bulletin of the American Mathematical Society 60(1954): 503–515.
• [4] Bellman, R. (1958). On a routing problem, Quarterly of Applied Mathematics 16(1958): 87–90.
• [5] Bellman, R. and Dreyfus, S. (1962). Applied Dynamic Programming, Princeton University Press, Princeton, NJ.
• [6] Bertsekas, D.P. (2000). Dynamic Programming and Optimal Control, 2nd Edn., Athena Scientific, Belmont, MA.
• [7] Betts, J.T. (1998). Survey of numerical methods for trajectory optimization, Journal of Guidance Control and Dynamics 21(2): 193–207.
• [8] Böttner, C.-U. (2007). Weather routing for ships in degraded conditions, International Symposium on Safety, Security and Environmental Protection, Athens, Greece.
• [9] Byrski, A., Dębski, R. and Kisiel-Dorohinicki, M. (2012). Agent-based computing in an augmented cloud environment, Computer Systems Science and Engineering 27(1): 7–18.
• [10] Ceriotti, M. and Vasile, M. (2010). MGA trajectory planning with an ACO-inspired algorithm, Acta Astronautica 67(9–10): 1202–1217.
• [11] Crauser, A., Mehlhorn, K., Meyer, U. and Sanders, P. (1998). A parallelization of Dijkstra’s shortest path algorithm, in L. Brim et al. (Eds.), Mathematical Foundations of Computer Science 1998, Lecture Notes in Computer Science, Vol. 1450, Springer, Berlin/Heidelberg, pp. 722–731.
• [12] Dalang, R.C., Dumas, F., Sardy, S., Morgenthaler, S. and Vila, J. (2015). Stochastic optimization of sailing trajectories in an upwind regatta, Journal of the Operational Research Society 66(5): 807–821.
• [13] Dębski, R. (2014a). Gradient-based algorithms in the brachistochrone problem having a black-box represented mathematical model, Journal of Telecommunications & Information Technology 2014(1): 32–40.
• [14] Dębski, R. (2014b). High-performance simulation-based algorithms for an alpine ski racer’s trajectory optimization in heterogeneous computer systems, International Journal of Applied Mathematics and Computer Science 24(3): 551–566, DOI: 10.2478/amcs-2014-0040.
• [15] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische Mathematik 1(1): 269–271.
• [16] Harish, P. and Narayanan, P. (2007). Accelerating large graph algorithms on the GPU using CUDA, in S. Aluru et al. (Eds.), High Performance Computing, Springer, Berlin/Heidelberg, pp. 197–208.
• [17] Jasika, N., Alispahic, N., Elma, A., Ilvana, K., Elma, L. and Nosovic, N. (2012). Dijkstra’s shortest path algorithm serial and parallel execution performance analysis, MIPRO 2012: Proceedings of the 35th International Convention, Opatija, Croatia, pp. 1811–1815.
• [18] Kojic, N., Reljin, I. and Reljin, B. (2013). Route selection problem based on Hopfield neural network, Radioengineering 22(4): 1182–1193.
• [19] Krozel, J., Lee, C. and Mitchell, J.S. (2006). Turn-constrained route planning for avoiding hazardous weather, Air Traffic Control Quarterly 14(2): 159–165.
• [20] Lewis, R.M., Torczon, V. and Trosset, M.W. (2000). Direct search methods: Then and now, Journal of Computational and Applied Mathematics 124(1–2): 191–207.
• [21] Li, H. and Lü, M. (2014). A three dimensional route planning method based on improved ant colony optimization algorithm, Xibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University 32(4): 563–568.
• [22] Marchaj, C. (2004). Sailing Theory: Aerodynamics of the Sail, Alma-Press, Warsaw, (in Polish).
• [23] Park, C., Pan, J. and Manocha, D. (2013). Real-time optimization-based planning in dynamic environments using GPUs, 2013 IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, pp. 4090–4097.
• [24] Pêtres, C., Romero-Ramirez, M.-A. and Plumet, F. (2011). Reactive path planning for autonomous sailboat, 2011 15th International Conference on Advanced Robotics (ICAR), Tallinn, Estonia, pp. 112–117.
• [25] Philpott, A.B., Henderson, S.G. and Teirney, D. (2004). A simulation model for predicting yacht match race outcomes, Operations Research 52(1): 1–16.
• [26] Philpott, A. and Mason, A. (2001). Optimising yacht routes under uncertainty, 15th Cheasapeake Sailing Yacht Symposium, Annapolis, MD, USA, pp. 89–98.
• [27] Pontryagin, L.S., Boltyanski, V.G., Gamkrelidze, R.V. and Mischenko, E.F. (1962). The Mathematical Theory of Optimal Processes, Interscience, New York, NY.
• [28] Pošík, P., Huyer, W. and Pál, L. (2012). A comparison of global search algorithms for continuous black box optimization, Evolutionary Computation 20(4): 509–541.
• [29] Rippel, E., Bar-Gill, A. and Shimkin, N. (2005). Fast graph-search algorithms for general-aviation flight trajectory generation, Journal of Guidance, Control, and Dynamics 28(4): 801–811.
• [30] Singla, G., Tiwari, A. and Singh, D.P. (2013). New approach for graph algorithms on GPU using CUDA, International Journal of Computer Applications 72(18): 38–42.
• [31] Stelzer, R. and Pröll, T. (2008). Autonomous sailboat navigation for short course racing, Robotics and Autonomous Systems 56(7): 604–614.
• [32] Stillwell, J. (2010). Mathematics and Its History, 3rd Edn., Springer, New York, NY.
• [33] Sun, J. and Wu, S. (2011). Route planning of cruise missile based on improved particle swarm algorithm, Beijing Hangkong Hangtian Daxue Xuebao/Journal of Beijing University of Aeronautics and Astronautics 37(10): 1228–1232.
• [34] Sussmann, H.J. and Willems, J.C. (1997). 300 years of optimal control: From the brachystochrone to the maximum principle, IEEE Control Systems 17(3): 32–44.
• [35] Szłapczyński, R. and Szłapczyńska, J. (2012). Customized crossover in evolutionary sets of safe ship trajectories, International Journal of Applied Mathematics and Computer Science 22(4): 999–1009, DOI: 10.2478/v10006-012-0074-x.
• [36] Szynkiewicz, W. and Błaszczyk, J. (2011). Optimization-based approach to path planning for closed chain robot systems, International Journal of Applied Mathematics and Computer Science 21(4): 659–670, DOI: 10.2478/v10006-011-0052-8.
• [37] Ćurković, P., Jerbić, B. and Stipančić, T. (2009). Swarm-based approach to path planning using honey-bees mating algorithm and art neural network, in Z. Gosiewska and Z. Kulesza (Eds.), Mechatronic Systems and Materials III, Solid State Phenomena, Vol. 147, Trans Tech Publications, Pfaffikon, pp. 74–79.
• [38] Vasile, M. and Locatelli, M. (2009). A hybrid multiagent approach for global trajectory optimization, Journal of Global Optimization 44(4): 461–479.
• [39] von Stryk, O. and Bulirsch, R. (1992). Direct and indirect methods for trajectory optimization, Annals of Operations Research 37(1): 357–373.
• [40] Wagner, S., Kaplinger, B. and Wie, B. (2012). GPU accelerated genetic algorithm for multiple gravity-assist and impulsive δV maneuvers, AIAA/AAS Guidance Navigation and Control Conference, Minneapolis, MN, USA, Vol. 4592, p. 2012.
• [41] Zamuda, A. and Sosa, J.D.H. (2014). Differential evolution and underwater glider path planning applied to the short-term opportunistic sampling of dynamic mesoscale ocean structures, Applied Soft Computing 24: 95–108.
• [42] Zhou, S., Zhu, G., Li, H.,Wang, Y. and Liu, X. (2011). Real-time route planning for uav based on weather threat, 2011 International Conference on Remote Sensing, Environment and Transportation Engineering (RSETE), Nanijng, China, pp. 2342–2345.

Uwagi

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