In Chapter 3 of The Arrows of Time (which you can read in the accompanying excerpt from the novel), Ramiro and Tarquinia need to intercept a rogue spacecraft that is accelerating along a fixed path. Their aim is to board it, so it is not enough merely to cross its path: they also need to match its velocity. This is a soft interception.
Given that they can operate their own engines at full thrust indefinitely, what path should they take in order to intercept the rogue as quickly as possible? Since the velocities involved are not so high as to give rise to relativistic effects, the alternative physics of the Orthogonal universe doesn’t come into play (apart from enabling the spacecrafts’ engines, which create kinetic energy by emitting light and require no fuel or propellant). So we can use the same Newtonian rules that apply at low velocities in our own universe.
This kind of problem — the determination of a mathematical function that maximises or minimises a certain quantity — is dealt with by the Calculus of Variations. In our case, the function we’re interested in will describe a path through space as a function of time, and the quantity we want to minimise is the time for this path to take us from the initial location of the pursuing gnat to some point on the rogue’s trajectory.
Suppose the location of Ramiro and Tarquinia’s gnat when they begin the pursuit is p0, its velocity is v0, and the maximum rate of acceleration their engines can produce is A. The rogue is undergoing constant acceleration in a fixed direction; if we call that acceleration vector a, the rogue’s trajectory over time is given by:
r(t) = r0 + w0 t + ½ a t2
We’re choosing to measure time from the moment the pursuit begins, so at t=0 we have the pursuing gnat at position p0 with velocity v0, while the rogue is at position r0 with velocity w0.
What we demand of any candidate path for the pursuing gnat, p(t), is:
Our goal is to find the path p(t) that makes the time until interception, T, as low as possible while meeting these conditions.
We will make our analysis slightly easier by assuming, without proof, that the pursuing gnat should fire its engines at maximum thrust for the entire journey, only changing the direction in which they’re fired. It makes intuitive sense that there’s always some advantage to be gained by accelerating at the greatest possible rate (and a more thorough analysis will confirm this). This lets us replace the last condition with an equality, rather than an inequality:
This constraint can also be expressed as:
p''(t) · p''(t) – A2 = 0
Now, in ordinary calculus, to minimise a function F(x, y, z) subject to some constraint, say G(x, y, z)=0, we would make use of the following trick, known as a Lagrange multiplier. Suppose we managed to solve the constraint equation G(x, y, z)=0 for one of the variables, say z. Then we’d be able to write:
f(x, y) = F(x, y, z(x, y))
and we would look for a minimum of f(x, y) by setting its derivatives with respect to x and y equal to zero:
∂x f(x, y) = ∂xF + ∂zF ∂xz = 0
∂y f(x, y) = ∂yF + ∂zF ∂yz = 0
We could also take derivates with respect to x and y of G(x, y, z(x, y)), which of course must be zero since z=z(x, y) is the solution to G(x, y, z)=0.
∂xG + ∂zG ∂xz = 0
∂yG + ∂zG ∂yz = 0
Altogether, we have four equations here. We can solve the last two for ∂xz and ∂yz, and substitute the results into the first two, giving us:
∂xF – (∂zF / ∂zG) ∂xG = 0
∂yF – (∂zF / ∂zG) ∂yG = 0
But this is also what we’d get from the three equations:
∂xF + λ ∂xG = 0
∂yF + λ ∂yG = 0
∂zF + λ ∂zG = 0
if the last of the three was solved for λ to give:
λ = – (∂zF / ∂zG)
So our initial problem is the same as finding the points where the derivatives of
S(x, y, z, λ) = F(x, y, z) + λ G(x, y, z)
with respect to x, y, z and λ are all zero, with the derivative with respect to lambda just giving us back the original constraint, G(x, y, z)=0. The extra variable, λ, is known as a Lagrange multiplier.
We can understand this more clearly by thinking about the geometry of the situation. The gradient of the function F is ∇F=(∂xF, ∂yF, ∂zF), and it describes a vector that is orthogonal to the “contours” or “level sets” of F: those sets of points in (x, y, z) space on which the value of F is constant. Similarly, the gradient of G is ∇G=(∂xG, ∂yG, ∂zG), and ∇G is orthogonal to the sets on which G is constant — including, of course, the set of points that satisfy the constraint equation G(x, y, z)=0. The three equations relating the derivatives of F and G that we wrote earlier can be summed up in terms of the gradients as:
∇F = –λ ∇G
If we start at some point in the set that satisfies the constraint equation, any path that remains in that set will have a tangent orthogonal to ∇G. But if ∇F is a multiple of ∇G, the same tangent vector will also be orthogonal to ∇F, and so we will also be moving along a path for which F has a constant value. So at such a point, satisfying the constraint guarantees that the derivative of F is zero, as must be the case around a local maximum or minimum.
This can easily be generalised to any number of constraint functions, G1, G2, G3, ... that must all be zero, in some space of any number of variables. Starting from a point that meets all of these constraints, moving along a path that is simultaneously orthogonal to ∇G1, ∇G2, ∇G3 ... will allow all the constraints to continue to be met. Now suppose that, at some point in the constraint set:
∇F = –λ1 ∇G1 – λ2 ∇G2 – λ3 ∇G3 – ...
Since any path through the constraint set at that point will have its tangent orthogonal to every one of the ∇Gi, the same tangent will also be orthogonal to ∇F. That means the derivative of F along any such path will be zero, making the point in question a candidate for a local maximum or minimum of F subject to the constraints G1 = G2 = G3 ... = 0.
Returning to our original problem, we want to impose the constraint:
p''(t) · p''(t) – A2 = 0
along the entire path of the pursuing gnat. If we think of each value of t as requiring a separate constraint, we need to “add up” the product of a separate Lagrange multiplier and the appropriate constraint for all of these different times. But for a continuum of values like this, we use an integral rather than a sum. So we write an integral that includes both the lapse of time along the path (the function we actually want to minimise) and a Lagrange multiplier times our constraint, with the Lagrange multiplier now a function of time:
I(p, λ) = ∫0T(p) 1 + λ(t) (p''(t) · p''(t) – A2) dt
Here the integral of 1 along the path gives the total elapsed time. We’ve written the endpoint of the integral as T(p), to stress that the time when the pursuer intercepts the rogue will depend on the choice of path. The actual value for T(p) is just the first positive solution of:
p(T) = r(T)
Our aim is to find a path pM(t) that minimises the time to interception while meeting all our requirements, and we will do this by finding the pM(t), along with a Lagrange multiplier λM(t), such that the derivative of the integral I(p, λ) with respect to any suitable variation in either function is zero. A suitable variation is one that allows the path to continue to meet the necessary boundary conditions: it must still have the same initial location and velocity, and it must still arrive at the rogue’s trajectory matching the location and velocity of the rogue. We will consider paths of the form:
p(t) = pM(t) + ε q(t)
and to meet the boundary conditions at t=0, we will impose the restrictions:
q(0) = 0
q'(0) = 0
Since pM (by definition) has the correct initial location and velocity, these restrictions ensure that the same is true for pM + ε q. At t=T, we will require:
pM(T) + ε q(T) = r(T)
pM'(T) + ε q'(T) = r'(T)
Keep in mind that T depends on the path as we vary it, so the first equation here is not a restriction on q but rather the means of determining the value of T, which is simply the first positive solution of this equation.
If we take the derivatives of these two equations with respect to ε, and then set ε equal to 0, we obtain (writing TM as an abbreviation for T(pM)):
q(TM) = [r'(TM) – pM'(TM)] (dT/dε)|ε=0 = 0
q'(TM) = [r''(TM) – pM''(TM)] (dT/dε)|ε=0 = [a – pM''(TM)] (dT/dε)|ε=0
We will also vary the Lagrange multiplier, setting:
λ(t) = λM(t) + ε μ(t)
Now we impose the condition that the derivative of our integral with respect to ε is zero:
d/dε I(pM + ε q, λM + ε μ) |ε=0 = 0
d/dε ∫0T(pM + ε q) 1 + [λM(t) + ε μ(t)] ([pM''(t) + ε q''(t)] · [pM''(t) + ε q''(t)] – A2) dt |ε=0 = 0
(dT/dε)|ε=0 [1 + λM(T) (pM''(T) · pM''(T) – A2)] + ∫0TM 2 λM(t) pM''(t) · q''(t) + μ(t) (pM''(t) · pM''(t) – A2) dt = 0
Given that pM, by definition, must meet the constraint that the magnitude of its acceleration is equal to A everywhere, this becomes:
(dT/dε)|ε=0 + 2 ∫0TM λM(t) pM''(t) · q''(t) dt = 0
We can transform the integral by the method of integration by parts, where the general rule is:
∫ab u(t) v'(t) dt = u(t) v(t)|ab – ∫ab u'(t) v(t) dt
Applying this twice to shift the derivates with respect to t from q''(t) onto λM(t) pM''(t), we obtain:
(dT/dε)|ε=0 + 2 [ λM(t) pM''(t) · q'(t)|0TM – d/dt (λM(t) pM''(t)) · q(t)|0TM + ∫0TM d2/dt2 (λM(t) pM''(t)) · q(t) dt ] = 0
The boundary conditions on q give us q(0) = 0 and q'(0) = 0, and also q(TM) = 0. Substituting in the only non-zero boundary condition, q'(TM) = [a – pM''(TM)] (dT/dε)|ε=0, we get:
(dT/dε)|ε=0 (1 + 2 λM(TM) pM''(TM) · [a – pM''(TM)])
+ 2 ∫0TM d2/dt2 (λM(t) pM''(t)) · q(t) dt = 0
This equation needs to hold for all variations q. It’s not hard to see that we can make the integral zero for any q if the product of the path’s acceleration and the Lagrange multiplier satisfies the differential equation:
d2/dt2 (λM(t) pM''(t)) = 0
If we satisfy this equation, we will then also need to ensure that the boundary term is, separately, equal to zero. The easiest way to see that we can achieve that is to go ahead and solve the equation, giving us:
λM(t) pM''(t) = C t + D
for two vectors C and D. Since the path pM has a constant acceleration A, we have:
|λM(t)| |pM''(t)| = |C t + D|
|λM(t)| A = |C t + D|
λM(t) = ± |C t + D| / A
pM''(t) = ± A (C t + D) / |C t + D|
If we start with some choice of C t + D and then multiply both vectors by a constant, that will cancel out completely in the solution for pM''(t), so it will have no effect on our ability to choose a path that meets the specific details of the problem: matching the location and velocity of the pursuing gnat initially and the rogue gnat at the point of interception. Now if we substitute our solution into the boundary term, omitting the overall factor of (dT/dε)|ε=0, we get:
1 + 2 λM(TM) pM''(TM) · [a – pM''(TM)]
= 1 + 2 (C TM + D) · [a – ± A (C TM + D) / |C TM + D|]
= 1 + 2 [(C TM + D) · a – ± A |C TM + D|]
If we introduce the abbreviation:
c = C TM + D
and then make the substitution c → α c, the boundary term becomes:
1 + 2 [α c · a – ± A |α| |c|]
If we assume α is positive, this can be made zero by setting:
α = 1/[2(± A |c| – c · a)]
and making an appropriate choice of sign (recall that this sign sets the overall relationship between the path’s acceleration and the direction C t + D). We expect the pursuing gnat to be accelerating in almost the same direction as the rogue at the moment of interception, so a positive sign will be appropriate if c · a is positive. Since we must have A > |a| in order for the pursuing gnat to be able to catch up with the rogue, the denominator on the right hand side will be positive, giving us a positive α as assumed. If c · a were negative, we could simply reverse our initial choices of C and D.
So, we’re able to make the boundary term and the integral both zero, so long as the path’s acceleration takes the form:
pM''(t) = A (C t + D) / |C t + D|
To find the general solution to this, let’s start with one particular solution. (Parts of what follows are adapted from reference [2], which deals with the problem of finding the fastest path for running between the bases in a baseball game.)
The hyperbolic sine function, sinh, is defined as:
sinh(x) = ½(ex – e–x)
Its inverse, arcsinh, can be found by solving a quadratic equation in ex and then taking the logarithm:
y = sinh(x)
2 y = ex – e–x
(ex)2 – 2 y ex – 1 = 0
arcsinh(y) = x = ln(y + √(1+y2))
The derivative of the natural log is just the inverse function, so the derivative of arcsinh is:
arcsinh'(y) = (1 + y/√(1+y2))/(y + √(1+y2)) = 1/√(1+y2)
This lets us find a simple vector function whose first derivative has a constant magnitude of A:
V(t) = V0 + A (arcsinh(t), √(1+t2))
V '(t) = A (1/√(1+t2), t/√(1+t2)) = A (1, t) / |(1, t)|
|V '(t)| = A
With a little more work, we can find the integral of this velocity:
X(t) = X0 + V0 t + A (t arcsinh(t) – √(1+t2), ½(arcsinh(t) + t √(1+t2)))
In order to generalise this, we can substitute t → β t + γ, while keeping the magnitude of the acceleration fixed by replacing A with A/β2. We are also free to rotate our coordinates through any angle θ. This leaves us with eight parameters we can vary: four from the vectors X0 and V0, along with β, γ, θ and the interception time T. Four equations need to be satisfied at t=0 to fit the initial location and velocity of the pursuing gnat, and four more need to be satisfied at t=T to match the location and velocity of the rogue.
The solution to this system of equations can be found numerically. The result is the curve shown in the novel, with an acceleration that changes direction over time but maintains a constant magnitude:
For further reading, [1] gives a much more rigorous treatment of the whole subject of the calculus of variations.
[1] The Calculus of Variations by M. Bendersky, Lecture Notes, City University of New York. Online (PDF)
[2] “Baserunner’s Optimal Path” by Davide Carozza, Stewart Johnson and Frank Morgan, The Mathematical Intelligencer, October 2009. Online version (PDF)
 |
 |