Overclock My Satellite

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 over­burdening 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.