Gradient-Based Algorithms in the Brachistochrone Problem Having a Black-Box Represented Mathematical Model
DOI:
https://doi.org/10.26636/jtit.2014.1.1003Keywords:
black-box optimization, brachistochrone problem, optimal control, trajectory optimizationAbstract
Trajectory optimization problems with black-box represented objective functions are often solved with the use of some meta-heuristic algorithms. The aim of this paper is to show that gradient-based algorithms, when applied correctly, can be effective for such problems as well. One of the key aspects of successful application is choosing, in the search space, a basis appropriate for the problem. In an experiment to demonstrate this, three simple adaptations of gradient-based algorithms were executed in the forty-dimensional search space to solve the brachistochrone problem having a blackbox represented mathematical model. This experiment was repeated for two different bases spanning the search space. The best of the algorithms, despite its very basic implementation, needed only about 100 iterations to find very accurate solutions. 100 iterations means about 2000 objective functional evaluations (simulations). This corresponds to about 20 iterations of a typical evolutionary algorithm, e.g. ES(µ, λ).
Downloads
References
[1] J. Babb and J. Currie, „The brachistochrone problem: Mathematics for a broad audience via a large context problem”, The Montana Math. Enthus., vol. 5, pp. 169-184, 2008.
View in Google Scholar
[2] H. J. Sussmann and J. C. Willems, „300 years of optimal control: from the brachystochrone to the maximum principle”, IEEE Control Syst., vol. 17, no. 3, pp. 32-44, 1997.
View in Google Scholar
[3] N. Ashby, W. E. Brittin, W. F. Love, and W. Wyss, „Brachistochrone with Coulomb friction”, Amer. J. Phys., vol. 43, p. 902, 1975.
View in Google Scholar
[4] J. C. Hayen, „Brachistochrone with Coulomb friction”, Int. J. Non-Linear Mech., vol. 40, no. 8, pp. 1057-1075, 2005.
View in Google Scholar
[5] A. S. Parnovsky, „Some generalisations of brachistochrone problem”, Acta Phys. Polonica - Ser. A Gen. Phys., vol. 93, pp. 55-64, 1998.
View in Google Scholar
[6] A. M. A. Van der Heijden and J. D. Diepstraten, „On the brachystochrone with dry friction”, Int. J. Non-Linear Mech., vol. 10, no. 2, pp. 97-112, 1975.
View in Google Scholar
[7] J. Gemmer, R. Umble, and M. Nolan, „Generalizations of the brachistochrone problem”, arXiv preprint math-ph/0612052, 2006.
View in Google Scholar
[8] V. Čović and M. Vesković, „Brachistochrone on a surface with Coulomb friction”, Int. J. Non-Linear Mech., vol. 43, no. 5, pp. 437-450, 2008.
View in Google Scholar
[9] C. Farina, „Bernoulli’s method for relativistic brachistochrones”, J. Phys. A: Math. Gen., vol. 20, no. 2, pp. L57-59, 1987.
View in Google Scholar
[10] H. F. Goldstein and C. M. Bender, „Relativistic brachistochrone”, J. Math. Phys., vol. 27, p. 507, 1986.
View in Google Scholar
[11] G. Mingari Scarpello and D. Ritelli, „Relativistic brachistochrones under electric or gravitational uniform fields”, ZAMM - J. Appl. Math. Mech., vol. 86, no. 9, pp. 736-743, 2006.
View in Google Scholar
[12] S. M. LaValle, Planning Algorithms. Cambridge, U.K: Cambridge University Press, 2006 [Online]. Available: http://planning.cs.uiuc.edu/
View in Google Scholar
[13] L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mischenko, The Mathematical Theory of Optimal Processes. New York-London: Wiley, 1962.
View in Google Scholar
[14] H. J. Sussmann and J. C. Willems, „The brachistochrone problem and modern control theory”, in Contemporary Trends in Nonlinear Geometric Control Theory and its Applications, A. Anzaldo-Meneses, B. Bonnard, J.-P. Gauthier, and F. Monroy-Perez, Eds. Singapore: World Scientific Publishers, 2002, pp. 113-165.
View in Google Scholar
[15] J. T. Betts, „Survey of numerical methods for trajectory optimization”, J. Guidance Contr. Dynam., vol. 21, no. 2, pp. 193-207, 1998.
View in Google Scholar
[16] W. A. Golfetto and S. da Silva Fernandes, „A review of gradient algorithms for numerical computation of optimal trajectories”, J. Aerosp. Technol. Manag., vol. 4, no. 2, pp. 131-143, 2012.
View in Google Scholar
[17] A. Jameson and J. Vassberg, „Studies of alternate numerical optimization methods applied to the brachistochrone problem”, in Proc. OptiCON ’99 Conf., Newport Beach, CA, USA, pp. 281-296, 1999.
View in Google Scholar
[18] E. Olvovsky, „Novel gradient-type optimization algorithms for extremely large-scale nonsmooth convex optimization”, PhD thesis, Technion-Israel Institute of Technology, 2005.
View in Google Scholar
[19] A. V. Rao, „A survey of numerical methods for optimal control”, Adv. Astronaut. Sci., vol. 135, no. 1, pp. 497-528, 2009.
View in Google Scholar
[20] R. Bellman, „The theory of dynamic programming”, Tech. Rep., DTIC Document, 1954.
View in Google Scholar
[21] P. Pošik and W. Huyer, „Restarted local search algorithms for continuous black box optimization”, Evolut. Comput., vol. 20, no. 4, pp. 575-607, 2012.
View in Google Scholar
[22] P. Pošik, W. Huyer, and L. Pál, „A comparison of global search algorithms for continuous black box optimization”, Evolut. Comput., vol. 20, no. 4, pp. 1-32, 2012.
View in Google Scholar
[23] M. Ceriotti and M. Vasile, „MGA trajectory planning with an ACO-inspired algorithm”, Acta Astronautica, vol. 67, no. 9-10, pp. 1202-1217, 2010.
View in Google Scholar
[24] M. Vasile and M. Locatelli, „A hybrid multiagent approach for global trajectory optimization”, J. Global Optimiz., vol. 44, no. 4, pp. 461-479, 2009.
View in Google Scholar
[25] M. Vasile, L. Summerer, and P. De Pascale, „Design of earth-mars transfer trajectories using evolutionary-branching technique”, Acta Astronaut., vol. 56, no. 8, pp. 705-720, 2005.
View in Google Scholar
[26] N. Yokoyama, „Trajectory optimization of space plane using genetic algorithm combined with gradient method”, in Proc. 23rd Int. Congr. Aerospace Sciences, Toronto, Canada, 2002.
View in Google Scholar
[27] D. R. Jones, M. Schonlau, and W. J. Welch, „Efficient global optimization of expensive black-box functions”, J. Global Optimiz., vol. 13, no. 4, pp. 455-492, 1998.
View in Google Scholar
[28] M. B. Milam, „Real-time optimal trajectory generation for constrained dynamical systems”, PhD thesis, California Institute of Technology, 2003.
View in Google Scholar
[29] A.-L. Cauchy, „Méthode générale pour la résolution des systèmes d’équations simultanées”, Comptes Rendus Acad. Sci. Paris, vol. 25, pp. 536-538, 1847.
View in Google Scholar
[30] R. Fletcher and C. M. Reeves, „Function minimization by conjugate gradients”, Comput. J., vol. 7, no. 2, pp. 149-154, 1964.
View in Google Scholar
[31] A. Byrski, R. Dębski, and M. Kisiel-Dorohinicki, „Agent-based computing in an augmented cloud environment”, Comput. Syst. Sci. Eng., vol. 21, no. 1, pp. 7-18, 2012.
View in Google Scholar
[32] R. Dębski, A. Byrski, and M. Kisiel-Dorohinicki, „Towards an agent-based augmented cloud”, J. Telecommun. Inform. Technol., no. 1, pp. 16-22, 2012.
View in Google Scholar
[33] R. Dębski, T. Krupa, and P. Majewski, „ComcuteJS: a web browser based platform for large-scale computations”, Comput. Sci., vol. 14, no. 1, pp. 143-152, 2013.
View in Google Scholar
[34] J. Stillwell, „Mathematics and its history”, The Australian Math. Soc., p. 168, 2002.
View in Google Scholar
[35] G. Galilei, H. Crew, and A. De Salvio, Dialogues Concerning Two New Sciences. Charleston: BiblioBazaar, 2010.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2014 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
