**Sophisticated algorithms boost satellite performance on the cheap**

**“Let me get this straight,”**said a NASA mission controller after we finished describing our plan to steer a sun-observation satellite at top speed. “You want to make the satellite do something it wasn’t designed for?”

We glanced at one another across the conference room table.

“Well…yeah!”

In some ways, a satellite is like an outdated computer: You want
better performance and an upgrade is too expensive, so you overclock the
one you’ve got. With little more than a free afternoon and a bit of
hacker know-how, you instruct the software operating your motherboard to
ramp up your clock speed, and voilĂ ! Better performance.

As we told the mission controllers at NASA in 2010, we’re taking this
concept to a new level by improving the performance of an entire
satellite. We’re not overclocking its onboard CPUs, but the idea is
similar. By carefully choreographing the satellite’s movements, we can
command it to do something it wasn’t originally designed to do—rotate
faster. Such speedy maneuvering would allow existing imaging spacecraft,
such as military and weather satellites, to more quickly capture
time-sensitive events, such as the birth of a hurricane or the movement
of enemy troops. And, like a savvy overclocker, we can do this without
making any modifications to the hardware.

**All about the line:**Like the “racing line” [orange] followed by a race car, the fastest possible turning path a satellite can take is rarely the shortest one [blue].

*Click on image to enlarge.*

We were confident we could pull off the feat because we had done
something similar before. Back in 2007, NASA used a method developed by
our team members at the Charles Stark Draper Laboratory in Houston to rotate the International Space Station without using a single drop of fuel.
Typically, turning this football-field-size spacecraft—to allow a
resupply vehicle to dock at an available port—requires firing its
thrusters and can cost NASA upward of US $1 million in propellant.

This time, the Draper group teamed up with engineers at the Naval Postgraduate School, in Monterey, Calif. And in 2010, we carried out our promise to make the NASA observation satellite scan the sky faster than even its mission controllers thought possible.
By operating spacecraft beyond their purported limits, we can extend
their life and usefulness without installing new hardware and driving up
costs.

So how do we achieve this clever hack? Ultimately, we overclock a
satellite by uploading a set of precise steering instructions from the
ground to its onboard flight computer, essentially overriding its
automated route. But that’s the easy part. The real challenge is
figuring out what those instructions should be, which requires solving
mathematical puzzles known as optimal control problems.

That may sound simple enough. After all, we merely want to find the
optimal path a satellite must take to reorient itself in the least
amount of time or using the least amount of fuel. But we’ll give you a
hint: The fastest or most fuel-efficient route isn’t always the shortest
one. When we take into account all the variables that might affect how a
satellite moves—its mass, its shape, its altitude, the influence of
gravity, and the configuration of its solar arrays, among many other
things—the problem quickly grows extraordinarily complex.

Only within the last decade have we achieved the computing power and
mathematical algorithms necessary for solving optimal control problems
that reflect all the harsh realities of space. Now that we have these
tools, their uses are many. Beyond improving satellite performance, we
could equip airplanes, ships, and cars with software for solving optimal
control problems on the fly, enabling them to compute the best routes
based on real-time conditions such as wind patterns, ocean currents, and
freeway traffic.

**Maneuvering a satellite**takes many steps. In order to rotate an observation satellite toward a new target, for example, an operator must first transmit a command from a ground station on Earth, typically by using frequencies in the S band (2 to 4 gigahertz). A command consists of a target orientation in space and a time code that tells the satellite when to start moving. A radio antenna mounted on the spacecraft receives the signal and relays it to an onboard computer, which stores the command in its memory.

To execute the command, the computer calculates the path the satellite
must follow to reach its destination. All satellites today are equipped
with basic software programs that simply compute the shortest route from
start to finish. This “smallest-angle rotation” describes the arc of a
circle, like the path traced by the hand of a clock. The flight computer
then guides the satellite along this path by controlling
battery-powered electric motors, which speed up or slow down a set of
flywheels. These spinning mechanical wheels store angular momentum. When
the speed of a flywheel changes, it creates a torque on the satellite
that causes the spacecraft to rotate in the direction opposite the
change in the whirring wheel. By simultaneously activating several
flywheels in different positions, we can direct a satellite to turn in
any direction, as a ball bearing would.

Although the smallest-angle path is the most direct and the easiest to
compute, it is rarely the quickest or most fuel-efficient way to rotate a
satellite. The concept is analogous to cornering in a race car. Drivers
know that if they take a corner too sharply at high speed, the sideways
force on the wheels will overcome their traction on the road, causing
the car to spin out. The driver can maintain a higher speed and complete
a course fastest by following the longer arc of the “racing line”
rather than hugging the inner, albeit shorter, edge of the track
[see illustration, “All About the Line”].

Steering a satellite is not much different, although here the problem
isn’t traction but how quickly the flywheels can rotate. Satellites
typically have four or more motor-flywheel sets, each oriented along a
different rotational axis. Taking the smallest-angle path often limits a
satellite to using only a few of its flywheels. So in order to execute a
turn more quickly and avoid overburdening its motors, the satellite
must take an alternate path. While it may be less direct, the longer
path lets the spacecraft make optimal use of all its flywheels at once,
generating more torque.

Aerospace engineers have known for decades that when they guide
satellites along the shortest path, they can’t maneuver them at top
speeds. But without sophisticated computational tools, they had no way
of knowing until recently what the optimal rotational path should be.
The solution, we can assure you, isn’t intuitive. In fact, it took many
generations of mathematicians and computer scientists to develop the
methods we used to solve this optimal control problem.

**Turn, Turn, Turn:**To “hack” the turning path of a satellite, such as NASA’s TRACE (Transition Region And Coronal Explorer, shown here), specially engineered software calculates a sequence of radio commands. A ground controller then transmits the commands to the satellite, setting in motion a network of electrical and mechanical parts.

*Click on image to enlarge.*

**Any mathematician asked about**the origins of optimization theory will surely recount the story of Queen Dido. According to the Roman poet Virgil, Dido fled her murderous brother’s kingdom in what is now Lebanon and led her followers to the coast of North Africa. There, she struck a deal with the locals: She could take a small piece of land, but only as much as she could enclose using the hide of an ox. Dido cleverly carved the ox hide into a long, thin strip, and then laid the strip in a semicircle so that each end dipped into the Mediterranean Sea. Thus she founded the ancient city of Carthage.

Now immortalized among mathematicians as “Dido’s problem,”
the queen’s solution describes the largest possible area whose boundary
is a line intersected by a curve of a given length. No one knows how
she arrived at this result, which mathematicians did not rigorously
prove until the 19th century. By then, they had realized that solving
even the simplest optimization problems was no easy task. For centuries,
some of the greatest mathematical minds struggled to find a systematic
way to tackle them.

Another famous optimization problem was posed in 1696 by Johann Bernoulli, an early master of calculus. The brachistochrone problem, whose name is derived from the Greek words

*brachistos*(shortest) and*chronos*(time), asked for the quickest path between two points in the presence of gravity. Imagine, for instance, a marble resting on a ledge. Your task is to construct a ramp to roll the marble from the ledge into a bucket across the room. Assuming there is no friction, how would you shape your ramp to plop the marble into the bucket in the least time possible?
At this point, you have probably guessed that the answer is not a
straight line. Indeed, many famous mathematicians, including Bernoulli
himself, showed that the optimal marble-rolling path is a special kind of curve known as a cycloid,
which is generated by tracing the path of a point on the rim of a wheel
as it rolls along a straight line. Unfortunately, their methods for
deriving this solution worked only for simple problems like the
brachistochrone. There were many more optimization problems out there,
but still no universal method by which to solve them.

In the 18th century, the great Swiss mathematician Leonard Euler
finally devised a general approach for attacking these problems. His
method involved breaking up a problem into several smaller problems that
are easier to solve. Take the rolling marble problem: In reality, the
marble is constantly moving, accelerating and decelerating. But if you
slice up its motion into a sequence of time-frozen snapshots, like the
pages of a flip-book, you create solvable equations with fixed speeds
and positions rather than varying ones. Then, by reassembling all your
slices, you can find a very close approximation of the solution to your
original problem.

Euler’s method of discretization eventually evolved into the powerful calculus of variations,
which served as the standard for solving optimization problems until
about the 1960s. While the technique was great for solving the
brachistochrone problem and other relatively simple puzzles, it was of
little use for addressing real-world engineering systems. The trouble
was that Euler’s method considered only how systems change naturally, in
the absence of human intervention. The rolling marble, for instance,
couldn’t be bumped or pushed halfway through its journey.

But most real-world systems, such as airplanes, involve knobs or other
controls that can be adjusted to change the behavior of the system. Such
variables may include the amount of pressure on a gas pedal or the
position of the flaps on an airplane wing. In order to account for them,
mathematicians Lev Pontryagin in the Soviet Union and Richard Bellman
in the United States expanded on Euler’s ideas in the 1960s to develop
what is known as optimal control theory.

**IN GOOD TIME:**A famous puzzle asks for the quickest path between two points in the presence of gravity and the absence of friction. By following a cycloid curve [orange], a falling ball arrives at the finish faster than if it had taken any other route, including the shortest one [blue].

*Click on image to enlarge.*

Yet there was only so much complexity mathematicians could deal with
when doing calculations by hand. Computers were ideal for solving
optimal control problems, because these problems could be broken down
into smaller, parallel parts. And as computers got faster, they were
able to solve ever more detailed problems. But there were still some
optimal control problems—maneuvering satellites, for example—that
continued to fall under what Bellman called “the curse of
dimensionality.” In order to get an accurate solution, you had to slice
the problem into smaller and smaller pieces until eventually, the number
of pieces grew so large that the problem became intractable and a
computer could no longer solve it within a reasonable amount of time.

In the past two decades, mathematicians have focused on developing more
efficient ways of approximating optimal control problems by taking
fewer, smarter slices. Rather than divvy up a problem uniformly, these
methods tailor the slicing to best reflect how a system is changing. As a
very simple example, suppose you’re tracking daylight intensity during a
24-hour period and are limited to making just 24 measurements. In order
to get the most accurate picture, you would logically want to make more
frequent measurements during sunrise and sunset than during nighttime.

Researchers are now building these ideas into software packages. For
instance, engineer Michael Ross and mathematician Fariba Fahroo
at the Naval Postgraduate School, in Monterey, Calif., have developed a
computer program that has allowed us to solve even the thorniest
problems involving satellite systems.

Appropriately, they have named this clever computer program Dido, in a nod to the queen of Carthage.

**It is one thing to develop**promising new computational theories but quite another to test them in action. In March 2010, NASA announced it was retiring a veteran sun-observing satellite, the Transition Region And Coronal Explorer, or TRACE. But before mission controllers powered down the spacecraft and shut off communication, its engineers decided to try one last experiment. They knew it was theoretically possible to calculate the commands for rotating a spacecraft at optimal speed, but it had never been tried before on a real satellite. They wondered if TRACE, which had not veered more than 15 degrees during its 12-year life, could execute a “perfect turn.”

So they called up Ross at the Naval Postgraduate School and asked if he
was interested in putting Dido to work. Ross, in turn, called us. Three
years prior, our Draper team members had used Dido to successfully
solve a different optimal control problem: the rotation of the International Space Station using no fuel.
By making optimal use of gravity and aerodynamic drag, our
solution—dubbed the zero-propellant maneuver—guided the station in a
long, curved path, such as a boat takes when sailing. The little
artificial power needed came from the spacecraft’s gyroscopes—spinning
momentum storage devices that run on solar-powered batteries and are
normally used to make small adjustments in orientation. Although the
full 180-degree turn took nearly 3 hours rather than the typical 40
minutes, flight controllers never had to power up the station’s
fuel-guzzling thrusters.

Our goal for TRACE wasn’t to save fuel but to move the satellite
faster. The first step was to create a mathematical model of the
satellite that was as detailed as possible, incorporating all the
physical properties of its various parts and position in space. Next, we
had to identify any constraints on its speed. These included the size
and configuration of its four sets of motors and flywheels, as well as
the quality of its sensors. Because TRACE wasn’t designed to move
quickly, its three simple mug-size gyroscopes could detect speeds of up
to only 1 degree per second—about a sixth that of the second hand of a
clock—along each of its three axes of rotation. To keep TRACE from
drifting off course, we decided to play it safe and cap its speed at
half a degree per second along each axis.

Finally, we plugged all this information into Dido and churned out
optimal rotation paths, or shortest-time maneuvers, for TRACE to follow
from one destination to another. In all, we choreographed more than 20
different maneuvers—in each case pointing the satellite’s telescope at
multiple points in the sky. As we expected, the paths were never
straight lines. Rather, they looked more like the meandering footsteps
of a dancer performing a waltz. For this reason, TRACE’s flight
controllers at NASA took to calling the experiment “dancing with the stars.”

**DANCING WITH THE STARS:**In one experiment with TRACE, mission controllers rotated the satellite to point at six different celestial targets by following two different paths. The typical smallest-angle path [blue] required just one command per target and took 877 seconds to complete. The shortest-time path [orange], calculated using state-of-the-art optimal control software, required 775 commands total. TRACE executed them all in 775 seconds—a speed upgrade of 12 percent.

*Click on image to enlarge.*

Getting TRACE to perform these dance steps required a bit of trickery.
The satellite’s onboard software, remember, is programmed to guide TRACE
along the smallest-angle rotation given a target destination and a
starting time. TRACE would therefore execute any commands we gave it
using this smallest-angle algorithm. If we wanted the satellite to
follow a more complex curve, we had to break up the route into a
sequence of very short, small-angle rotations that, when stitched
together, closely approximated our original curve. In order to perform a
single shortest-time maneuver with TRACE, we had to upload to its
onboard flight computer a sequence of several hundred commands.

In total, TRACE can store 900 commands, so we could upload all our
commands for a maneuver at once. For instance, we designed one maneuver
to point TRACE toward a series of six targets arranged in a star-shaped
pattern and uploaded 775 commands to be executed, one every second. To
our delight, TRACE dutifully performed them all in exactly 775 seconds.
When we directed TRACE in the same maneuver using the typical single
command per target, the satellite took 877 seconds to complete these six
smallest-angle rotations. The experiment showed that our optimal
maneuver could speed up TRACE by more than 12 percent over its normal
capability [see illustration, “Dancing With the Stars”].

This may not sound like a dramatic improvement. But given the
constraint posed by the satellite’s rate sensors, we believe this
experiment, though impressive in its own right, underestimates the
potential of our technology. In fact, we have tested similar maneuvers
on stripped-down replicas of satellites on Earth and were able to
increase turning speeds by as much as 50 percent. For a military or
weather satellite, such a performance boost could mean the difference
between capturing a critical event and missing it. For commercial
imaging satellites such as GeoEye and France’s SPOT satellites, it could
provide a significant bump in business.

It took three centuries to bring Bernoulli’s math to market—or 28
centuries, if you concede that his inspiration began with Queen Dido.
And the work goes on. Eventually, optimal-control problem-solving
software will be built in to satellites themselves. This will allow them
to generate optimal maneuvers autonomously and in real time, saving
operators even more time or fuel.

One way to do this may be to program a dedicated processing core that
could be built in to a satellite’s avionics hardware. For example, Elissar Global,
founded by Ross and his colleagues in 2007, has developed a processor
called the KR8100, which is the world’s first embedded general-purpose
optimal control computer. (Elissar, by the way, was Queen Dido’s
Phoenician name.) It’s not hard to imagine that someday soon, these
smart chips will be installed in airplanes, ships, robots, and perhaps
even race cars.