Gradient-Based Algorithms in the Brachistochrone Problem Having a Black-Box Represented Mathematical Model

• Autorzy: Dębski R.
• Języki publikacji: EN

Abstrakty

EN

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(μ,l ).

Słowa kluczowe

EN

black-box optimization; brachistochrone problem; optimal control; trajectory optimization

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2014
• Tom: nr 1
• Strony: 32--40
• Opis fizyczny: Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Dębski R.

• Department of Computer Science, AGH University of Science and Technology, Kraków, Poland

Bibliografia

• [1] J. Babb and J. Currie, “The brachistochrone problem: Mathematics for a broad audience via a large context problem”, The Montana Mathem. Enthus., vol. 5, pp. 169–184, 2008.
• [2] H. J. Sussmann and J. C. Willems, “300 years of optimal control: from the brachystochrone to the maximum principle”, Control Sys., IEEE, vol. 17, no. 3, pp. 32–44, 1997.
• [3] N. Ashby, W. E. Brittin, W. F. Love, and W. Wyss, “Brachistochrone with coulomb friction”, American J. Phys., vol. 43, p. 902, 1975.
• [4] J. C. Hayen, “Brachistochrone with coulomb friction”, Int. J. Non-Linear Mechan., vol. 40, no. 8, pp. 1057–1075, 2005.
• [5] A. S. Parnovsky, “Some generalisations of brachistochrone problem”, Acta Phys. Polonica – Ser. A Gen. Fhys., vol. 93, pp. 55–64, 1998.
• [6] A. M. A. Van der Heijden and J. D. Diepstraten, “On the brachystochrone with dry friction”, In. J. Non-Linear Mechan., vol. 10, no. 2, pp. 97–112, 1975.
• [7] J. Gemmer, R. Umble, and M. Nolan, “Generalizations of the brachistochrone problem”, arXiv preprint math-ph/0612052, 2006.
• [8] V. ˇCović and M. Vesković, “Brachistochrone on a surface with coulomb friction”, Int. J. Non-Linear Mechan., vol. 43, no. 5, pp. 437–450, 2008.
• [9] C. Farina, “Bernoulli’s method for relativistic brachistochrones”, J. Phys. A: Mathem. and General, vol. 20, no. 2, pp. L57–59, 1987.
• [10] H. F. Goldstein and C. M. Bender, “Relativistic brachistochrone”, J. Mathem. Phys., vol. 27, p. 507, 1986.
• [11] G. Mingari Scarpello and D. Ritelli, “Relativistic brachistochrones under electric or gravitational uniform fields”, ZAMM-J. Appl. Mathem. and Mechanics/Zeitschrift f ¨ur Angewandte Mathematik und Mechanik, vol. 86, no. 9, pp. 736–743, 2006.
• [12] S. M. LaValle, Planning Algorithms. Cambridge, U.K: Cambridge University Press, 2006 [Online]. Available: http://planning.cs.uiuc.edu/
• [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.
• [14] H. J. Sussmann and J. C. Willems, “The brachistochrone problem and modern control theory”, in Contemporary Trends in Nonlin-ear 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.
• [15] J. T. Betts, “Survey of numerical methods for trajectory optimization”, J. Guidance Contr. Dynam., vol. 21, no. 2, pp. 193–207, 1998.
• [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.
• [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.
• [18] E. Olvovsky, “Novel gradient-type optimization algorithms for extremely large-scale nonsmooth convex optimization”, PhD thesis, Technion-Israel Institute of Technology, 2005.
• [19] A. V. Rao, “A survey of numerical methods for optimal control”, Adv. Astronaut. Sci., vol. 135, no. 1, pp. 497–528, 2009.
• [20] R. Bellman, “The theory of dynamic programming”, Tech. rep., DTIC Document, 1954.
• [21] P. Poˇsik and W. Huyer, “Restarted local search algorithms for continuous black box optimization”, Evolut. Comput., vol. 20, no. 4, pp. 575–607, 2012.
• [22] P. Poˇsik, W. Huyer, and L. P´al, “A comparison of global search algorithms for continuous black box optimization”, Evolut. Comput., vol. 20, no. 4, pp. 1–32, 2012.
• [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.
• [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.
• [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.
• [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.
• [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.
• [28] M. B. Milam, “Real-time optimal trajectory generation for constrained dynamical systems”, PhD thesis, California Institute of Technology, 2003.
• [29] A.-L. Cauchy, “M´ethode g´en´erale pour la r´esolution des systemes d’´equations simultan´ees”, Comp. Rend. Sci. Paris, vol. serie A, no. 25, pp. 536–538, 1847.
• [30] R. Fletcher and C. M. Reeves, “Function minimization by conjugate gradients”, The Comp. J., vol. 7, no. 2, pp. 149–154, 1964.
• [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.
• [32] R. Dębski, A. Byrski, and M. Kisiel-Dorohinicki, “Towards an agentbased augmented cloud”, J. Telecommun. Inform. Technol., no. 1, pp. 16–22, 2012.
• [33] R. Dębski, T. Krupa, and P. Majewski, ComcuteJS: A web browser based platform for large-scale computations”, Comp. Sci., vol. 14, no. 1, pp. 143–152, 2013.
• [34] J. Stillwell, “Mathematics and its history”, The Australian Mathem. Soc., p. 168, 2002.
• [35] G. Galilei, H. Crew, and A. De Salvio, Dialogues Concerning Two New Sciences. Charleston: BiblioBazaar, 2010.