<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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</p></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

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

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

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine...

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

Publié en ligne: 25 sept. 2014

Pages: 551 - 566

Reçu: 20 août 2013

DOI: https://doi.org/10.2478/amcs-2014-0040

Mots clés
trajectory optimization, heterogeneous computing, GPGPU, high-performance computing, alpine ski racing

© by Roman Dębski

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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

Publié en ligne: 25 sept. 2014

Pages: 551 - 566

Reçu: 20 août 2013

DOI: https://doi.org/10.2478/amcs-2014-0040

Mots cléstrajectory optimization, heterogeneous computing, GPGPU, high-performance computing, alpine ski racing

© by Roman Dębski

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
trajectory optimization, heterogeneous computing, GPGPU, high-performance computing, alpine ski racing