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

Roman Dębski

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 2, page 351-365
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Roman Dębski. "An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems." International Journal of Applied Mathematics and Computer Science 26.2 (2016): 351-365. <http://eudml.org/doc/280125>.

@article{RomanDębski2016,
abstract = {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.},
author = {Roman Dębski},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {dynamic programming; black-box optimization; heterogeneous computing; micro HPC platform; cubic Hermite splines},
language = {eng},
number = {2},
pages = {351-365},
title = {An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems},
url = {http://eudml.org/doc/280125},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Roman Dębski
TI - An adaptive multi-spline refinement algorithm in simulation based sailboat trajectory optimization using onboard multi-core computer systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 2
SP - 351
EP - 365
AB - 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.
LA - eng
KW - dynamic programming; black-box optimization; heterogeneous computing; micro HPC platform; cubic Hermite splines
UR - http://eudml.org/doc/280125
ER -

References

top
  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. Zbl0057.12503
  4. Bellman, R. (1958). On a routing problem, Quarterly of Applied Mathematics 16(1958): 87-90. Zbl0081.14403
  5. Bellman, R. and Dreyfus, S. (1962). Applied Dynamic Programming, Princeton University Press, Princeton, NJ. Zbl0106.34901
  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. Zbl1158.49303
  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. Zbl0912.05056
  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. Zbl1322.93075
  15. Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische Mathematik 1(1): 269-271. Zbl0092.16002
  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. Zbl0969.65055
  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. Zbl1165.90675
  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. Zbl1207.01003
  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. Zbl1283.93320
  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. Zbl1283.93206
  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. Zbl1180.90251
  39. von Stryk, O. and Bulirsch, R. (1992). Direct and indirect methods for trajectory optimization, Annals of Operations Research 37(1): 357-373. Zbl0784.49023
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.