Simulation-Based Sailboat Trajectory Optimization using On-Board Heterogeneous Computers
DOI:
https://doi.org/10.7494/csci.2016.17.4.461Keywords:
black-box optimization, trajectory optimization, dynamic programming, heterogeneous computing, micro HPC platformAbstract
A dynamic programming-based algorithm adapted to on-board heterogeneous
computers for simulation-based trajectory optimization was studied in
the context of high-performance sailing. The algorithm can efficiently utilize
all OpenCL-capable devices, starting the computation (if necessary, in singleprecision)
on a GPU and finalizing it (if necessary, in double-precision) with
the use of a CPU. The serial and parallel versions of the algorithm are presented
in detail. Possible extensions of the basic algorithm are also described. The
experimental results show that contemporary heterogeneous on-board/mobile
computers can be treated as micro HPC platforms. They offer high performance
(the OpenCL-capable GPU was found to accelerate the optimization routine 41
fold) while remaining energy and cost efficient. The simulation-based approach
has the potential to give very accurate results, as the mathematical model upon
which the simulator is based may be as complex as required. The black-box represented
performance measure and the use of OpenCL make the presented
approach applicable to many trajectory optimization problems.
Downloads
References
Arora N., Russell R.P., Vuduc R.W.: Fast Sensitivity Computations for Trajectory Optimization. Advances in the Astronautical Sciences, vol. 135(1), pp. 545–560, 2009.
Bellman R.: The theory of dynamic programming. Buletin of the American Mathematical Society, vol. 60, pp. 503–515, 1954.
Bellman R.: On a Routing Problem. Quarterly of Applied Mathematics, vol. 16, pp. 87–90, 1958.
Betts J.T.: Survey of Numerical Methods for Trajectory Optimization. Journal of Guidance Control and Dynamics, vol. 21(2), pp. 193–207, 1998.
Byrski A., Dębski R., Kisiel-Dorohinicki M.: Agent-based computing in an augmented cloud environment. Computer Systems Science and Engineering, vol. 27(1), pp. 7–18, 2012.
Ceriotti M., Vasile M.: MGA trajectory planning with an ACO-inspired algorithm. Acta Astronautica, vol. 67(9–10), pp. 1202–1217, 2010.
Crauser A., Mehlhorn K., Meyer U., Sanders P.: A parallelization of Dijkstra’s shortest path algorithm. L. Brim, J. Gruska, J. Zlatuka, eds., Mathematical Foundations of Computer Science 1998, Lecture Notes in Computer Science, vol. 1450, pp. 722–731, Springer Berlin Heidelberg, 1998, ISBN 978-3-540-64827-7.
Dalang R.C., Dumas F., Sardy S., Morgenthaler S., Vila J.: Stochastic optimization of sailing trajectories in an upwind regatta. Journal of the Operational Research Society, 2014.
Dębski R.: Gradient-Based Algorithms in the Brachistochrone Problem Having a Black-Box Represented Mathematical Model. Journal of Telecommunications & Information Technology, vol. 2014(1), pp. 32–40, 2014.
Dębski R., Byrski A., Kisiel-Dorohinicki M.: Towards an agent-based augmented cloud. Journal of Telecommunications and Information Technology, vol. 1, pp. 16– 22, 2012.
Dębski R., Krupa T., Majewski P.: ComcuteJS: A Web Browser Based Platform for Large-scale Computations. Computer Science, vol. 14(1), pp. 143–152, 2013.
Dijkstra E.W.: A note on two problems in connexion with graphs. Numerische Mathematik, vol. 1, pp. 269–271, 1959.
Dramski M.: A comparison between Dijkstra algorithm and simplified ant colony optimization in navigation. Zeszyty Naukowe / Akademia Morska w Szczecinie, vol. 29 (101), pp. 25–29, 2012.
Dussault J.P.: Solving trajectory optimization problems via nonlinear programming: the brachistochrone case study. Optimization and Engineering, vol. 15(4), pp. 819–835, 2014, ISSN 1389-4420.
Dbski R.: High-Performance Simulation-Based Algorithms for Alpine Ski Racer’s Trajectory Optimization in Heterogeneous Computer Systems. International Journal of Applied Mathematics and Computer Science, vol. 24(3), pp. 551–566, 2014.
Gaster B.R., Howes L.W., Kaeli D.R., Mistry P., Schaa D.: Heterogeneous Computing with OpenCL - Revised OpenCL 1.2 Edition. Morgan Kaufmann, 2013, ISBN 978-0-12-405894-1.
Harish P., Narayanan P.: Accelerating large graph algorithms on the GPU using CUDA. High performance computing–HiPC 2007, pp. 197–208, Springer, 2007.
Jasika N., Alispahic N., Elma A., Ilvana K., Elma L., Nosovic N.: Dijkstra’s shortest path algorithm serial and parallel execution performance analysis. MIPRO, 2012 Proceedings of the 35th International Convention, pp. 1811–1815, IEEE, 2012.
Lewis R.M., Torczon V., Trosset M.W.: Direct Search Methods: Then And Now. Journal of Computational and Applied Mathematics, vol. 124, pp. 191–207, 2000.
Marchaj C.: Aero-hydrodynamics of sailing. Dodd, Mead, 1980, ISBN 9780396077398.
Marchaj C.: Sail Performance: Techniques to Maximize Sail Power. International Marine/McGraw-Hill, 2003, ISBN 9780071413107.
Park C., Pan J., Manocha D.: Real-time optimization-based planning in dynamic environments using GPUs. Robotics and Automation (ICRA), 2013 IEEE International Conference on, pp. 4090–4097, IEEE, 2013.
Pêtres C., Romero-Ramirez M.A., Plumet F.: Reactive path planning for autonomous sailboat. Advanced Robotics (ICAR), 2011 15th International Conference on, pp. 112–117, IEEE, 2011.
Philpott A., Mason A.: Optimising yacht routes under uncertainty. The 15th Cheasapeake Sailing Yacht Symposium, 2001.
Philpott A.B., Henderson S.G., Teirney D.: A Simulation Model for Predicting Yacht Match Race Outcomes. Oper. Res., vol. 52(1), pp. 1–16, 2004, ISSN 0030364X.
Pontryagin L.S., Boltyanski V.G., Gamkrelidze R.V., Mischenko E.F.: The Mathematical Theory of Optimal Processes. Interscience, NY, 1962.
Pošı́k P., Huyer W.: Restarted local search algorithms for continuous black box optimization. Evolutionary Computation, vol. 20(4), pp. 575–607, 2012.
Pošı́k P., Huyer W., Pál L.: A Comparison of Global Search Algorithms for Continuous Black Box Optimization. Evolutionary Computation, pp. 1–32, 2012.
Rippel E., Bar-Gill A., Shimkin N.: Fast graph-search algorithms for generalaviation flight trajectory generation. Journal of Guidance, Control, and Dynamics, vol. 28(4), pp. 801–811, 2005.
Singla G., Tiwari A., Singh D.P.: New Approach for Graph Algorithms on GPU using CUDA. International Journal of Computer Applications, vol. 72(18), pp. 38–42, 2013, published by Foundation of Computer Science, New York, USA.
Stelzer R., Pröll T.: Autonomous sailboat navigation for short course racing. Robotics and autonomous systems, vol. 56(7), pp. 604–614, 2008.
Stillwell J.: Mathematics and its History. Springer, third ed., 2010, ISBN ISBN 0-387-95336-1.
von Stryk O., Bulirsch R.: Direct and indirect methods for trajectory optimization. Annals of Operations Research, vol. 37(1), pp. 357–373, 1992.
Sussmann H.J., Willems J.C.: 300 years of optimal control: from the brachystochrone to the maximum principle. Control Systems, IEEE, vol. 17(3), pp. 32–44, 1997.
Sussmann H.J., Willems J.C.: The brachistochrone problem and modern control theory. Contemporary trends in nonlinear geometric control theory and its applications (Mexico City, 2000), pp. 113–166, 2002.
Szłapczyński: Customized crossover in evolutionary sets of safe ship trajectories. Int. J. Appl. Math. Comput. Sci, vol. 22(4), pp. 999–1009, 2012.
Szynkiewicz W., Błaszczyk J.: Optimization-based approach to path planning for closed chain robot systems. Int. J. Appl. Math. Comput. Sci, vol. 21(4), pp. 659– 670, 2011.
Vasile M., Locatelli M.: A hybrid multiagent approach for global trajectory optimization. Journal of Global Optimization, vol. 44(4), pp. 461–479, 2009.
Wagner S., Kaplinger B., Wie B.: GPU Accelerated Genetic Algorithm for Multiple Gravity-Assist and Impulsive V Maneuvers. AIAA/AAS Guidance Navigation and Control Conference AIAA, vol. 4592, p. 2012, 2012.
Downloads
Published
How to Cite
Issue
Section
