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

Dębski, R.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 3, pp. 551-566.

Résumé

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.

Détail

Keywords: trajectory optimization, heterogeneous computing, GPGPU, high performance computing, alpine ski racing
Mots-clés : optymalizacja trajektorii, obliczenia heterogeniczne, obliczenia wysokiej wydajności, narciarstwo alpejskie

Bibliographie

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

[3] Bellman, R. (1958). On a routing problem, Quarterly of Applied Mathematics 16: 87–90.

[4] Betts, J.T. (1998). Survey of numerical methods for trajectory optimization, Journal of Guidance Control and Dynamics 21(2): 193–207.

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

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

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

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

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

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

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

[30] Vanderbei, R.J. (2001). Case studies in trajectory optimization: Trains, planes, and other pastimes, Optimization and Engineering 2(2): 215–243.

[31] Vasile, M. and Locatelli, M. (2009). A hybrid multiagent approach for global trajectory optimization, Journal of Global Optimization 44(4): 461–479.

[32] von Stryk, O. and Bulirsch, R. (1992). Direct and indirect methods for trajectory optimization, Annals of Operations Research 37(1): 357–373.

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