Brachistochrone

Light is one of the most amazing phenomena in the Universe. It is pure energy and has zero mass. If you could experience a moment as a photon, you would experience eternity in that moment, for light experiences no time of its own (technically you’d experience nothing as psychological experience is time dependent, but lets keep the poetic tone). It is one of the primordial constituents of the Universe and is considered sacred in all religions, ditto physics. Among other things, a path of light is Brachistochrone.

A Brachistochrone is a path of shortest travel time between any two points (brákhistos:shortest khrónos:time). It is different from shortest path which generally means path with shortest length. For example, one might want to take a longer taxi route between two close points in a city due to traffic. Similarly, if you are trying to reach a friend whose phone is busy, a path with shorter time could be calling their home or someone close to them, etc. as opposed to the shortest path of calling them directly. The Brachistochrone path is defined by constraints in the path, the length of the path being just one of them. Adding more constraints, like time, traffic, etc. means that the overall shortest path has to minimize on additional constraints.

Back to light, in 1905, Einstein had proposed that speed of light is constant. However, his proposal, which became the most important postulate of Special Relativity, ended up implying that the speed of light is the maximum limit to the speed of causality i.e. no two events in causal chain can influence one another faster than light, at least in the non quantum world we live in. We now know that the reason light is brachistochrone (shortest time) in space is because it travels the shortest path in ‘spacetime’, a higher dimensional set of equations that takes into account both the constraints of space and time.

History

The Brachistochrone nature of light was not discovered by Einstein however, nor any physicist but by a mathematician, and a great one, Pierre de Fermat, 250 years earlier, in 1662¹. This is highly interesting since time has no relevance in mathematics, for it is a distinctly physical phenomenon, but we note that the foundations of physics had yet to be formalized then and just appreciate the caliber of Fermat. In fact, Fermat had nailed the brachistochrone nature of light as the Fermat’s principle states: “light travels between two points along the path that requires the least time, as compared to other nearby paths.”¹. Johann Bernoulli, a prominent mathematician in this own right, was aware of Fermat’s principle and having first solved the problem himself in 1696, posed the following to the scientific community of Europe:

The Brachistochrone Problem: To determine the curve jointing two given points, at different distances from the horizontal and not on the same vertical line along which a mobile particle, acted upon by its own weight and starting its motion from the upper point, descents most rapidly to the lower point. (Johann Bernoulli, Acta Eruditorum, June 1696)²

Johann Bernoulli knew that this was a tough problem, even for the giants of his era. In fact, Galileo in 1638 had studied the problem. In his famous work ‘Discourse on two new sciences’, Galileo finds a shorter descent curve compared to a straight line between two points A and B. The path is a circle. Maybe seduced by the perfection of circle, or maybe due to lack to tools necessary to solve this problem (calculus), who knows, Galileo incorrectly concludes that a circular arc is brachistochrone. We today know that the correct curve that solves the problem is a cycloid and not a circle. Ironically, it was Galileo who coined the term ‘cycloid‘ and was the first to make a serious study of the curve³. Anyways, with the help of Fermat, Johann Bernoulli had his ingenious solution. He also knew that he had beat Galileo here. So why not pose the problem to Europe, throw your weight around a little?

Enter the Lion: Issac Newton, 53 years of age, was already considered GOAT by the European scientific community at the time the Brachistochrone problem was posed. However, Johann Bernoulli, along with his buddy Gottfried Leibnitz (another giant, invented integral calculus), wanted to test Newton. Johann Bernoulli had deliberately included these words in this challenge:

“…there are fewer who are likely to solve our excellent problems, aye, fewer even among the very mathematicians who boast that [they]… have wonderfully extended its bounds by means of the golden theorems which (they thought) were known to no one, but which in fact had long previously been published by others..”²

Obviously pointing to Newton-Leibniz controversy over calculus. And here is why Newton is the boss: Newton, who receives the problem from France late in January 1697, comes home around 4 p.m. that day, stays up till 4:00 a.m., solves the problem, mails the solution to Royal society the next day, and in a followup letter mentions “I do not love to be dunned and teased by foreigners about mathematical things.”⁴. Apparently, Newtons solution was published anonymously. Later when Bernoulli announced the winners of the contest, there was Leibniz, Jacob Bernoulli (the smarter brother, discovered ‘e’), l’Hopital (yep, that guy from 0/0 rule), and the one anonymous winner. Bernoulli recognized this anonymous winner in public,”..tanquam ex ungue leonem..” in Latin, which translates to “I recognize a lion by his claw.”⁴

Revival

If you are here with me still, I did something Johann Bernoulliesque. I posed the Brachistochrone problem, to myself, but revival had a twist:

The Brachistochrone.ai Problem: To be determined by any silicon based mind, the curve jointing two given points, at different distances from the horizontal and not on the same vertical line along which a mobile particle, acted upon by its own weight and starting its motion from the upper point, descents most rapidly to the lower point.

The reason for this was two fold: First, the problem is of finding an optimal function i.e. a function that minimizes time given dynamics of motion (Newtons laws). We know that Machine Learning is really good at these tasks. In fact, all Machine Learning is is function estimation. There are few really good ones out there: SVMs, GMMs and Neural Networks that have the titles of Universal Function Approximators⁵. So why not challenge this universality?

The second was an attempt to cast a scientific problem in a language other than calculus. Brachistochrone can be solved easily with Calculus of Variations today. However, just like computing numerical solutions to equations is a huge part of scientific toolbox today, maybe numerical approximations of functions of an unknown relationship and/or dynamics is viable.

Theory

In this section I outline the theory of the Brachistochrone.ai problem recasted in the language of Reinforcement learning (RL). In the RL sections I have tried my best to simplify the RL process and skipped the implementation details for this post.

Problem Reformulation

The original Brachistochrone problem seeks the overall path taken by a particle. In conventional approaches, this path is carved by the laws of physics that the particle simply follows. In our approach, we think of the particle as active participant with a decision capability. At every point in the space, the particle has a choice of where to step next. A series of random choices would lead to an inefficient path and most certainly not lead the particle to the goal point. In order to shrink the domain of the choices, we limit our world to a 2D space and cast the choice parameter as θ, a positive angle with respect to y axis in the 2D space. This implies that any point in space, our particle has a choice of θ to take to move to next point in space.

A Calculus Solution

Line: The choice of θ here is a constant given by the slope of particle’s start position $(x_i, y_i)$ and its goal position $(x_f,y_f)$ $\theta = tan^{-1}(\frac{y_f-y_i}{x_f - x_i}).$ Circular arc: The choice of θ varies at each point in space. At any point $(x_t,y_t)$ in time t, the θ is given by twice the slope with respect to the goal position $\theta(x_t,y_t) = 2tan^{-1}(\frac{y_f-y_{t-1}}{x_f - x_{t-1}}).$ Cycloidal arc (Optimal Path): Here as well, the choice of θ varies at each point in space. However the choice is not as simple as the circular arc. One of the ways we get θ is to solve a system of non-linear equations at each point. We first solve the non-linear system to get the parameters R and a of the cycloid: $x_f = Ra_f - Rsin(a_f) + x_i \\y_f = -R + Rcos(a_f) + y_i$ where R is the radius of the circular wheel and a is the affine parameter. Then any point $(x_{t-1},y_{t-1})$ , the particle solves the non linear equation to get its next $\theta_t$ : $y_{t-1} = -R + Rcos(a_t) + y_i\\\theta_t = tan^{-1}\Big(\frac{-sin(a_t)}{1-cost(a_t)}\Big).$

The optimality of the arc is given here. Now, if you are convinced, for a given a choice of θ, for any path, the position update rules of the particle in the next time step $\Delta t$ is given by Newton’s laws of motion: $d = v_{t-1}\Delta t - 1/2g\Delta t^2\\(x_t, y_t) = (x_{t-1} + dcos(\theta), y_{t-1} + dsin(\theta))\\v_t = \sqrt{v_{t-1}^2 - 2g\Delta y}$

A Reinforcement Learning Solution

In RL, there is an environment and there are agents acting in it. The Newton’s laws above are now the environment update rules. The observable states are position and velocity amplitude of the particle. The agent, in the environment, performs actions i.e. chooses θ. The agent plays multiple episodes with random choices of θ to begin with. The reward r for the agent is negative for each time step times the particle’s distance to the goal point. This is to motivate reaching the goal position in the least possible time. The act of reaching the goal point gives a high positive reward and ends the episode. Episodes are also ended with negative rewards as penalties when the particle skips the goal point and/or reaches boundaries of environment. Over time, policies are learned on what θ to choose with good policies maximizing the overall reward. Slowly, the agent will converge to a optimal policy that hopefully is close to the optimal solution of the cycloid.

One thing to note here is that the agent will play many episodes of this path finding game. The final path would come from a learned policy. There are parallels to this in physics, in Lagrangian and Hamiltonian viewpoints. Moreover, in Quantum Mechanics, a single unique classical path for a particle can be shown as a system with sum, or functional integral, over an infinitely many possible paths leading to quantum amplitudes. Hence if you think of the Universe as a quantum computer, what if the amplitudes are the learned policies and decoherence is actually the halting of nature’s inherent quantum path finding algorithm? Just a thought.

Back to RL, θ is a continuous variable between $[-\pi, \pi]$ . The size of the action space is then $|\mathbb{R}|$ at any point totaling $|\mathbb{R}^\mathbb{R}|$ many possible actions along the path! In practice, since computers are discrete engines the cardinality of the sample set is infinitely reduced but still intractable for most RL methods. I tried policy gradient methods and Deep Q Learning but they did not perform well (lack of convergence, didn’t reach goals for smaller time steps, noisy path, etc.). The successful one, was DDPG^6,7.

Deep Deterministic Policy Gradient (DDPG):

Although detailing DDPG is beyond the scope of this post, I outline some notes on DDPG concerning its architecture. DDPG combines Deep Q Learning (DQL) with Policy Gradient methods which are the two cutting edge methods in RL. It handles continuous action spaces which is the major limitation of DQL. For this, two (actor-critic) neural networks are employed. The actor network generates mu or the mean around actions while the critic determines the optimal policies Q. One can think of this as GANs where there is a generator and discriminator networks. The actor/generator starts out with random mu samples that are then criticized/discriminated by the Q network. Employing an expectation-maximization routine, both mu and Q values converge to optimal estimates of some normal distributions over time. Since the actor network learns the regression parameters of mu such as mean and variance, the actions are regularly sampled from continuous spaces. Finally, we don’t bother with actual Q values and DDPG converges to the optimal policy, which is Policy Gradient aspect of the algorithm. One can find more details of the algorithm here . Finally, the code along with open AI implementation of Brachistochrone can be found in my repo here.

Experiment

Setting start position of (0.2, 0.8) and goal position of (0.8, 0.2) with time step $\Delta t= 0.08s$ and $g = 0.0098ms^{-2}$ gives optimal time $t \approx 14.24s$ .

Results

Figures showing the path taken in random, line, circle, cycloid (optimal) paths and by the Reinforcement Learning (AI) agent for three different cases with time step = 0.08. The fourth figure shows case 3 but with time step = 0.5 to enhance random activity.

Summary

So did the AI agent do justice to the history rich Brachistochrone problem? I think we were successful here. Any noisy stochastic system is prone to irregularities but the DDPG managed to give some smooth solutions. Of course they are not the optimal analytical solution of a cycloid generated by a formula in elegance of calculus. But the paths are very close. One exciting next step in AI is to deduce analytic functions from its closest numerical counterparts which is a super hard problem. Meanwhile, an extension to our problem would be to create train and test sets with random starting points and learn the optimal policy to test generalization.

Tying all this back to light, at the time of Fermat, light wasn’t a well known phenomena so the Fermat’s Principle is more of an intelligent conjecture. In his era, light only traveled in straight lines. However, in 1916, Einstein showed that light too yields to gravity and bends its path around massive astronomical bodies. He was able to predict the actual positions of a nearby stars and their deflections from apparent positions precisely using his General theory of Relativity. Today we use the these refraction technique in gravitational lensing which has opened a new doorway to modern astronomy. Note that it was similar refraction that led to Bernoulli’s solution of cycloid. Now that being said, a general brachistochrone problem arises: What is the path that minimizes the proper time of a mobile light particle i.e. a photon between any two points in a spacetime affected only by (strong) gravity? A higher dimensional cycloid?⁸ The rabbit hole goes way deep..

References

M. Born and E. Wolf, 1970, Principles of Optics, 4th Ed., Oxford: Pergamon Press.
P Costabel and J Peiffer (eds.), Bernoulli, Johann I The correspondence of Johann I Bernoulli. Volume 2: The Correspondence with Pierre Varignon: First Part: 1692-1702, The Collected Works of the Mathematicians and Physicists of the Bernoulli Family (Basel, 1988).
Whitman, E. A. (May 1943), “Some historical notes on the cycloid”, The American Mathematical Monthly, 50 (5): 309–315
M de Icaza Herrera, Galileo, Bernoulli, Leibniz and Newton around the brachistochronous problem, Rev. Mexicana Fis. 40 (3) (1994), 459-475.
Balázs Csanád Csáji (2001) Approximation with Artificial Neural Networks; Faculty of Sciences; Eötvös Loránd University, Hungary
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra, Continuous control with deep reinforcement learning, CoRR abs/1509.02971 (2015)
Matthias Plappert et al: “Parameter Space Noise for Exploration”, 2017; arXiv:1706.01905.
Giannoni, F. et al. A timelike extension of Fermat’s principle in general relativity and applications, P. Calc Var (1998) 6: 263. https://doi.org/10.1007/s005260050091

2 Comments

ปั๊มไลค์
June 4, 2020

Like!! I blog frequently and I really thank you for your content. The article has truly peaked my interest.

kellyJah
January 9, 2022

hello. topic for me thanks kelly

i found this web and i would to help you with evolution. i am from UAE ;D