“We choose to go to the Moon in this decade and do the other things, not because they are easy, but because they are hard; because that goal will serve to organize and measure the best of our energies and skills, because that challenge is the one that we are willing to accept, one we are unwilling to postpone, and one we intend to win, and the others, too.” - John F. Kennedy, Address at Rice University on the Nation’s Space Effort in 1962.

kennedy
Kennedy Inspecting Saturn IV in 1963 (from NASA's Apollo Image Gallery)

The Space Race between the United States and Soviet Union was an escalation of a copycat game involving the demonstration of one’s technological prowess against an ominous backdrop of lethal capability. Each unilateral advancement accomplished within the nuclear arms race of the Cold War merited a tenacious response to even the playing field and restore a tentative sense of deterrence between the world’s two superpowers of the time.

This delicate balance was toppled near the end of 1957 when the Soviet Union successfully launched two satellites to lower Earth orbit in quick succession. The Sputnik Crisis ensued, and although the United States responded with a successful orbiting of its own in early 1958, the Soviets were perceived to be well ahead in the Space Race.

By the time Kennedy publicly announced his commitment to land an American on the Moon, each rival had successfully taken a man out to space and back. But the excursions of lower Earth orbit represented only a small step towards the capabilities required to put a man on the Moon. With foresight, NASA’s Space Task Group began feasibility studies into a manned lunar mission in 1959. The need to develop the mid-course navigation and guidance of a lunar mission was identified as a primary research area to be undertaken by the Dynamics Analysis Branch of NASA Ames in Mountain View, CA.

A Serendipitous Encounter

Stan Schmidt, the 33-year-old chief of the Dynamics Analysis Branch at NASA Ames, was promptly presented a choice of research area by the Space Task Group: circumlunar guidance and navigation, or autopilot design of flexible liquid-fuel boosters. The eight engineers led by Schmidt were best suited to tackle the autopilot problem, but the group’s growing excitement for the mid-course navigation and guidance challenge quickly swayed them.

Both proposed research areas shared a common underlying theme: the challenge of autonomously bargaining with very uncertain vehicle dynamics while hurtling to the moon at rocketing speed. In contrast to the control of predictable rigid bodies, the booster autopilot would have to reckon with high levels of uncertainty and unpredictability regarding how the liquid-filled bodies would flex and vibrate throughout different regimes of flight - constantly threatening the imperative stability of the spacecraft if not adequately handled. Similarly, successful navigation to the Moon and back would require a navigation system capable of intelligently and reliably filtering valid information from noisy and biased on-board sensor measurements - poor estimates of the spacecraft’s own position and orientation in space would likewise lead to catastrophic failure.

Shortly after beginning work on the circumlunar navigation problem, Schmidt would recall:

“…it was clear that we were facing a rather massive effort with a staff that was utterly inexperienced in many of the required tasks (such as lunar trajectory analysis). Perhaps if we had fully comprehended the necessary effort we would have reconsidered our choice of problem area for the Branch research effort.” 1

Much of their challenge was rooted in the fact that the overwhelming majority of mathematical techniques available to practicing engineers are only applicable to a class of problems known to be linear. Linear problems have elegant properties which allow for clean solutions, but are rarely representative of real-world dynamics. The absence of linear mathematical properties is stark; the old adage goes: classification of mathematical problems as linear and nonlinear is like classification of the Universe as bananas and non-bananas. Sometimes, docile nonlinear problems may be cunningly broken down into a series of small linear problems. These smaller linear solutions can represent approximate solutions to an original nonlinear problem under certain assumptions. In 1960, Schmidt and his team would start striking success with such approximations. After receiving some guidance from members of the NASA Jet Propulsion Laboratory, the Dynamics Analysis Branch developed a program to analyze and simulate trajectories to the Moon and back; nonlinear midcourse corrections were calculated and simulated using linear perturbation techniques.

The requisite computer simulations were maturing in less than a year’s time, but the navigation solution had not yet taken shape. Feasibility dictated the navigation solution to be fully contained on-board; only the spacecraft’s own sensors and computers could be relied upon. This requirement introduced additional constraints of sensor reliability, measurement complexity, and processing power. Finding the middle ground among all the constraints was proving to be perplexing. The method of using iterative, weighted least-squares upon optical measurements of the Earth and Moon were ruled out due to complexity and computational requirements. Polynomial filtering of these optical measurements suffered a similar discardment due to insufficient navigational accuracy of the resulting solution.

Several members of the Dynamics Analysis Branch began leveraging their previous experience with homing missiles to investigate the implementation of Weiner filters for circumlunar navigation. Weiner filters had precedence in the domain of missiles to extract reliable data from a series of continuous - albeit noisy - sensor measurements. Given a linear time-invariant process, the Weiner filter pulls out a statistically optimal estimate of the signal from the noise. The Weiner filter was reputed to be efficient and powerful, but its limitations could not be resolved with the complexity and unpredictability of spacecraft navigation.

In sheer luck, an acquaintance of Stan Schmidt would visit the Dynamics Analysis Branch in the fall of 1960 to “discuss topics of mutual interest”1. Rudolf Kalman had known Schmidt for several years, but was unaware of the ongoing work at NASA Ames. Kalman had just published a paper with little fanfare titled “A New Approach to Linear Filtering and Prediction Problems” which extended upon the Weiner filter and importantly allowed for sequential filtering of time-varying signals. Kalman’s paper was unconventional, complex, and confusing to the members of the team, but there was enough interest generated during the meeting for Schmidt to instruct his engineers to study the paper in close detail.

“They all sat there, listening to Rudy, and I did, too. When he got through, I don’t think any of them understood, and I didn’t understand much, but after his discussion of it, I said, ‘I think this might have something to do with the [navigation problem].” - Stan Schmidt 2

Schmidt followed up with a visit to the Research Institute for Advanced Study to meet with Kalman. It was here that Schmidt had linked enough pieces together to realize he had a breakthrough in his hands. Kalman removed the stationary requirement of the Weiner filter and formulated a sequential, time-domain approach in lieu of Weiner’s frequency-domain approach; while the approach remained linear and optimal like the Weiner filter, Schmidt recognized that Kalman’s theory could be hammered into practice with the linear perturbation method already being used for trajectory analysis.

The brilliance of Kalman’s approach lied in its ability to sequentially determine a measure of certainty for each received sensor measurement; measurements are fused into the estimation of the whole system to the degree of its certainty. The filter continuously ingests measurement data, and can manage to infer unobservable quantities with astonishing accuracy in real-time. Alas, such estimation capabilities don’t come gift-wrapped. Sensors must be characterized, computational models must be worked out, and mathematical relationships between measurements and states of the system of interest must be derived. The routine of hacking estimates to unruly problems with simpler linear mathematical techniques would continue to ring true for Schmidt and his team.

The Extended Kalman Filter

Members of the Dynamics Analysis Branch began morphing the Kalman Filter (their apt reference for Kalman’s original technique applicable to linear systems) into a formulation that could be integrated into their simulation. This led to a refactoring of the filter into separate steps of discrete measurement updates and discrete system-state estimation updates; doing so allowed impractical time constraints of incoming sensor measurements to be lifted.

To address the nonlinearity of the navigation problem, the perturbation technique previously utilized by the team was altered in one important aspect. Instead of linearizing about the expected state of the vehicle, the team would linearize the system about the filter’s latest estimated state. The use of a Kalman filter with relinearizations about the estimated state is known as the Extended Kalman Filter, a technique that remains ubiquitous today.

With a clear vision of this new navigation solution, additional personnel were called upon to help develop the software to mechanize the filter into the simulation. A keen eagerness to analyze the navigation solution’s performance within simulated environments grew, but the constraints of their IBM 704 computer presented challenges. Handling the recursive matrix computations delayed the program by 6 months.

The software tasks had eventually gotten wrapped up, and the day to run the complete simulation arrived. After an hour of execution time, the results of the Extended Kalman Filter disappointed everyone. The Kalman Filter was a novel technique, and doubt of whether it could really work began to creep into the minds of the engineers. Luckily, a software error was subsequently caught and a second simulation confirmed the viability of the Extended Kalman Filter. By early 1961, the navigation and guidance for circumlunar space was confidently validated and verified via simulations. The simulation results achieved at NASA Ames was shared with researchers across the country, and the watershed innovations spearheaded by Kalman and Schmidt were immediately acknowledged by the research community.

Beyond the Extended Kalman Filter

Progress did not halt with the Extended Kalman Filter. Further modifications and improvements were incorporated before the navigation solution was implemented into Apollo’s on-board computer. With consultation from Schmidt, the Extended Kalman Filter also found its way into the Agena upper-stage and the C-5A navigation system within the 1960’s.

Kalman filters have been applied to a wide range of domains over the last 60 years. Extensions of the fundamental Kalman filter theory continue to develop in response to the evolving set of problems encountered across new applications. Developing and fine-tuning Kalman Filters require attention to several parameters such as filter initialization, convergence, and tuning. And the art of hacking solutions to be good enough under constraints remains.

References

  1. Discovery of the Kalman Filter as a Practical Tool for Aerospace and Industry by Mcgee and Schmidt, NASA Technical Memorandum (1985)

  2. Oral History Transcript of Stan Schmidt (2014), NACA Oral History Project