High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems

Roman Dębski

International Journal of Applied Mathematics and Computer Science (2014)

  • Volume: 24, Issue: 3, page 551-566
  • ISSN: 1641-876X

Abstract

top
Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation of the global solution. In the analyzed example it is the minimum-time ski line, represented as a piecewise-linear function (a method of elimination of unfeasible solutions is proposed). Serial and parallel versions of the basic optimization algorithm are presented in detail (pseudo-code, time and memory complexity). Possible extensions of the basic algorithm are also described. The implementation of these algorithms is based on OpenCL. The included experimental results show that contemporary heterogeneous computers can be treated as μ-HPC platforms-they offer high performance (the best speedup was equal to 128) while remaining energy and cost efficient (which is crucial in embedded systems, e.g., trajectory planners of autonomous robots). The presented algorithms can be applied to many trajectory optimization problems, including those having a black-box represented performance measure.

How to cite

top

Roman Dębski. "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 (2014): 551-566. <http://eudml.org/doc/271876>.

@article{RomanDębski2014,
abstract = {Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation of the global solution. In the analyzed example it is the minimum-time ski line, represented as a piecewise-linear function (a method of elimination of unfeasible solutions is proposed). Serial and parallel versions of the basic optimization algorithm are presented in detail (pseudo-code, time and memory complexity). Possible extensions of the basic algorithm are also described. The implementation of these algorithms is based on OpenCL. The included experimental results show that contemporary heterogeneous computers can be treated as μ-HPC platforms-they offer high performance (the best speedup was equal to 128) while remaining energy and cost efficient (which is crucial in embedded systems, e.g., trajectory planners of autonomous robots). The presented algorithms can be applied to many trajectory optimization problems, including those having a black-box represented performance measure.},
author = {Roman Dębski},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {trajectory optimization; heterogeneous computing; GPGPU; high-performance computing; alpine ski racing; dynamic programmin},
language = {eng},
number = {3},
pages = {551-566},
title = {High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems},
url = {http://eudml.org/doc/271876},
volume = {24},
year = {2014},
}

TY - JOUR
AU - Roman Dębski
TI - High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2014
VL - 24
IS - 3
SP - 551
EP - 566
AB - Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation of the global solution. In the analyzed example it is the minimum-time ski line, represented as a piecewise-linear function (a method of elimination of unfeasible solutions is proposed). Serial and parallel versions of the basic optimization algorithm are presented in detail (pseudo-code, time and memory complexity). Possible extensions of the basic algorithm are also described. The implementation of these algorithms is based on OpenCL. The included experimental results show that contemporary heterogeneous computers can be treated as μ-HPC platforms-they offer high performance (the best speedup was equal to 128) while remaining energy and cost efficient (which is crucial in embedded systems, e.g., trajectory planners of autonomous robots). The presented algorithms can be applied to many trajectory optimization problems, including those having a black-box represented performance measure.
LA - eng
KW - trajectory optimization; heterogeneous computing; GPGPU; high-performance computing; alpine ski racing; dynamic programmin
UR - http://eudml.org/doc/271876
ER -

References

top
  1. Babb, J. and Currie, J. (2008). The brachistochrone problem: Mathematics for a broad audience via a large context problem, The Montana Mathematics Enthusiast 5(2-3): 169-183. 
  2. Bellman, R. (1954). The theory of dynamic programming, Bulletin of the American Mathematical Society 60: 503-515. Zbl0057.12503
  3. Bellman, R. (1958). On a routing problem, Quarterly of Applied Mathematics 16: 87-90. Zbl0081.14403
  4. Betts, J.T. (1998). Survey of numerical methods for trajectory optimization, Journal of Guidance Control and Dynamics 21(2): 193-207. Zbl1158.49303
  5. Brodie, M. (2009). Development of Fusion Motion Capture for Optimisation of Performance in Alpine Ski Racing, Ph.D. thesis, Massey University, Wellington. 
  6. 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. 
  7. Ceriotti, M. and Vasile, M. (2010). MGA trajectory planning with an ACO-inspired algorithm, Acta Astronautica 67(9-10): 1202-1217. 
  8. Crauser, A., Mehlhorn, K., Meyer, U. and Sanders, P. (1998). A parallelization of Dijkstra's shortest path algorithm, in L. Brim, J. Gruska and J. Zlatuška (Eds.), Mathematical Foundations of Computer Science, Springer, London, pp. 722-731. Zbl0912.05056
  9. Dębski, R., Byrski, A. and Kisiel-Dorohinicki, M. (2012). Towards an agent-based augmented cloud, Journal of Telecommunications and Information Technology (1): 16-22. 
  10. Dębski, R., Krupa, T. and Majewski, P. (2013). ComcuteJS: A web browser based platform for large-scale computations, Computer Science 14(1): 143-152. 
  11. Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische Mathematik 1(1): 269-271. Zbl0092.16002
  12. Dramski, M. (2012). A comparison between Dijkstra algorithm and simplified ant colony optimization in navigation, Zeszyty Naukowe, Maritime University of Szczecinie 29(101): 25-29. 
  13. Gaster, B.R., Howes, L.W., Kaeli, D.R., Mistry, P. and Schaa, D. (2013). Heterogeneous Computing with OpenCL-Revised OpenCL 1.2 Edition, Morgan Kaufmann, Waltham, MA. 
  14. Harish, P. and Narayanan, P. (2007). Accelerating large graph algorithms on the GPU using CUDA, in S. Aluru, M. Parashar, R. Badrinath and V. Prasanna (Eds.), High Performance Computing-HiPC 2007, Springer, Berlin, pp. 197-208. 
  15. Hirano, Y. (2006). Quickest descent line during alpine ski racing, Sports Engineering 9(4): 221-228. 
  16. 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, Proceedings of the 35th International Convention, MIPRO 2012, Opatija, Croatia, pp. 1811-1815. 
  17. Kaps, P., Nachbauer, W. and Mossner, M. (1996). Determination of kinetic friction and drag area in alpine skiing, in C. Mote, R. Johnson and W. Hauser (Eds.), Ski Trauma and Skiing Safety, Vol. 10, American Society for Testing and Materials, Philadelphia, PA, pp. 165-177. 
  18. 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
  19. Pontryagin, L.S., Boltyanski, V.G., Gamkrelidze, R.V. and Mischenko, E.F. (1962). The Mathematical Theory of Optimal Processes, Interscience, New York, NY. 
  20. Pošík, P. and Huyer, W. (2012). Restarted local search algorithms for continuous black box optimization, Evolutionary Computation 20(4): 575-607. 
  21. 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. 
  22. 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. 
  23. 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. 
  24. Stechert, D.G. (1963). On the Use of the Calculus of Variations in Trajectory Optimization Problems, Rand Corporation, Santa Monica, CA. 
  25. Stillwell, J. (2010). Mathematics and Its History, 3rd edn., Springer, New York, NY. Zbl1207.01003
  26. 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. 
  27. Sussmann, H.J. and Willems, J.C. (2002). The brachistochrone problem and modern control theory, Contemporary Trends in Nonlinear Geometric Control Theory and Its Applications, Mexico City, Mexico, pp. 113-166. Zbl1047.93001
  28. 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
  29. 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
  30. Vanderbei, R.J. (2001). Case studies in trajectory optimization: Trains, planes, and other pastimes, Optimization and Engineering 2(2): 215-243. Zbl1011.49026
  31. Vasile, M. and Locatelli, M. (2009). A hybrid multiagent approach for global trajectory optimization, Journal of Global Optimization 44(4): 461-479. Zbl1180.90251
  32. von Stryk, O. and Bulirsch, R. (1992). Direct and indirect methods for trajectory optimization, Annals of Operations Research 37(1): 357-373. Zbl0784.49023
  33. Wuerl, A., Crain, T. and Braden, E. (2003). Genetic algorithm and calculus of variations-based trajectory optimization technique, Journal of Spacecraft and Rockets 40(6): 882-888. 
  34. Yokoyama, N. (2002). Trajectory optimization of space plane using genetic algorithm combined with gradient method, 23rd International Congress of Aeronautical Sciences, Toronto, Canada, pp. 513.1-513.10. 

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.