By Mike Sha
A common problem in robotics is finding all the possible positions the hand can end up. This is a question for algebraic geometry, which can be solved by homotopy continuation1. In this article, we’ll be taking the path of least resistance to these topics.
Algebra is “the study of mathematical symbols and the rules for manipulating these symbols”2. We learn algebra in grade school as the mindless rearrangement of x’s and y’s, but the utility of algebra goes beyond solving the quadratic equation.
High school algebra is all about conic sections, slices taken through a cone (Figure 1).
Further on in pre-calculus, you might have learned that when quadratics have no solution (Figure 2),
we can come up with complex solutions, such that the imaginary unit satisfies 𝑖2 = -1:
With a few rules on how to add and multiply complex numbers, Euler came with up the following surprising equation (Euler’s formula):
Let’s explore some of the consequences of this equation. First, there is a geometric interpretation of 𝑒iθ. We visualize a complex number in the x-y plane, a representation known as an Argand diagram. Euler’s formula for 𝑒iθ then represents a point on the circle of radius 1 on the Argand diagram:
The second consequence of Euler’s formula is we can solve the following polynomial
through simple geometry:
In figure 4, the solutions of Eq 2 are the points 𝑥 = 𝑒iθ where θ = 0, 2𝜋/5, 4𝜋/5, 6𝜋/5, 8𝜋/5 ; these points are evenly spaced around the unit circle in the complex plane and are known as the 5th roots of unity. According to the fundamental theorem of algebra3, these are all possible solutions to 𝑥5 = 1: this degree 5 polynomial (the highest power of appearing in the equation) has exactly 5 solutions in the complex numbers. Sometimes, the solutions coincide, giving fewer than 5 distinct solutions.
Now we can numerically solve any polynomial of degree 5. For example, we can choose
It’s known from a field of mathematics called Galois theory that the solutions to this equation cannot be expressed in a nice formula like the quadratic formula (Eq 1) or roots of unity (Eq 2). However, we can find numerical approximations of the zeros using a method known as homotopy continuation.
The central idea of homotopy continuation is that since we know the zeros of a degree 5 polynomial, namely 𝑓(x), we can track where the zeros go as we change 𝑓(x) into 𝑔(x).
Consider the new polynomial
When 𝑡=0, ℎ(𝑥,0) = 𝑓(𝑥) and when 𝑡=1, ℎ(𝑥,1) = 𝑔(𝑥). The key insight is that as we change 𝒕 from 0 to 1, the zeros of ℎ(𝑥, 𝑡) follow a path from the zeros of 𝑓(𝑥) to the zeros of 𝑔(𝑥). Why?
Remember the fundamental theorem of algebra: a degree n polynomial has exactly n complex zeros. For every value of 𝑡, ℎ(x, 𝑡) is a degree 5 polynomial, and so ℎ(x) always has 5 zeros.
Consider changing 𝑡 by a small amount 𝑑𝑡. Then the zeros of ℎ(𝑥, 𝑡) and ℎ(𝑥, 𝑡 + 𝑑𝑡) should be close to each other since we’re not changing by much. Thus, we can always find the new zeros a small distance away from the old ones, starting at 𝑡 = 0, moving in small steps 𝑑𝑡 until we get to 𝑡 = 1.
For an interactive demonstration see Monodromy of z^n + b z + 1 = 0 – Wolfram Demonstrations Project. Drag the slider for 𝑛 to 5. Drag the black dot (𝑏) around and watch where the red dots (the zeros). The red dots are initially at the 5th roots of unity (Figure 4). In this demonstration, 𝑏 takes the role of 𝑡. Check out ] An introduction to the numerical solution of polynomial systems4 for other applications of homotopy continuation.
Going back to the question of the robot arm, we can turn the lengths and angles of each segment of the robot arm into a system of polynomial equations. Homotopy continuation works in higher dimensions and with multiple equations at once. We can apply the homotopy continuation method to get all possible configurations of the arm which result in the final position of the hand.
The geometrical interpretation of mathematical problems is visually appealing, whereas the mess of algebra obfuscates the underlying intuition. However, the algebra makes that intuition precise. Finding deep connections like the ones between equations and shapes is the goal of modern mathematics and leads to deep results5.
My favorite such connection is a geometrical demonstration of the Pythagorean theorem (Figure 5). Ancient mathematicians thought of multiplying a number by itself as a literal “squaring.”
32+ 42= 52
Just as algebra is a precise expression of geometry, mathematics is a precise expression of science. Surprising applications of abstract ideas like homotopy continuation to the robot arm inevitably arise in science. I encourage the reader not to think of math as a collection of tedious word problems and algebraic manipulations, but as a pathway to a better understanding of the universe.
Algebra is the study of shapes and geometry with symbols. Formalizing geometry with algebra leads to surprising connections and new ways to solve equations.
For the reader familiar with calculus, here are the technical details of homotopy continuation.
Start with a solution of Eq 2, say 𝑥* so that 𝑓(𝑥*) =0. Now assume that 𝑥*(𝑡) is the path that the zero 𝑥* takes as we change 𝑡 from 1 to 0. Substitute 𝑥* = 𝑥*(𝑡) into Eq 4.
Differentiate with respect to 𝑡:
We can compute the right hand side from Eq 5, and solve for 𝑥*(𝑡). Equations like this can be solved numerically. This method works if Eq 6 doesn’t blow up. It turns out the equation blows up if two of the zeros coincide, and this is related to the critical points (blue) in the demonstration.