Tuesday, May 27, 2008

Remote Agent

The Phoenix Mars Lander touched down successfully on the surface of Mars on Sunday. It was no mean feat. The landing sequence was considered so risky that the official mission page on the NASA web site describes it as Seven Minutes of Terror! They note that

...in the international history of the space age, only five of 13 attempts to land on Mars have succeeded.

Check out this great picture of the part of the landing sequence where Phoenix descends into the Martian atmosphere with its parachute.

A crucial mission sequence is called a critical sequence. In a critical sequence you get one and only one chance to to execute the sequence right, with a failed sequence implying a failed mission. Critical sequences include landings (like the one that Phoenix executed flawlessly), orbit insertions (such as Cassini inserting itself into Saturn's orbit), and some flybys (such as Stardust's flyby of Comet Wild 2 to collect and return comet dust).

Talk of critical sequences reminds me of our work on the Remote Agent. I was at NASA through much of the 1990s working as a research scientist in an Artificial Intelligence (AI) research lab. Some time in 1995 the NASA Administrator, Dan Goldin, gave an inspiring speech. In it he outlined a vision that would allow NASA to significantly step up space exploration in spite of shrinking budgets. The key, he said, was to develop new technologies in such diverse areas as propulsion, MEMS, and autonomy. And he established the New Millennium Program to carry out his vision.

We (i.e., a group of AI researchers) were energized by this speech and decided to do something about it. Specifically, we thought that we could build a Remote Agent---an on-board autonomous agent to provide high-level control to achieve mission objectives. We pitched our idea to spacecraft engineers at JPL. Naturally, the spacecraft engineers were skeptical---after all, what did a bunch of AI researchers know about spacecraft autonomy? But they were open minded---they said they'd believe us if we could show them how the Remote Agent would handle Cassini's critical sequence (Saturn orbit insertion) in a simulated environment. And to make sure that the simulated environment didn't abstract away the hard parts of the critical sequence, they assigned an accomplished spacecraft engineer to lead the project.

We worked hard for the next 5 months or so, leading up to a demonstration of the system to various senior engineers at JPL. Everything was going smoothly, when suddenly an unexpected bug hit us (unexpected in the sense that it was not part of the demonstration script, though we were aware of this bug in our earlier testing but hadn't had the chance to track it down and fix it). The bug was in the communication between the Remote Agent and the underlying spacecraft simulation, and it manifested itself as a failure of the main rocket engines just as they were being turned on to slow down the spacecraft in preparation for orbit insertion!

The Remote Agent responded beautifully to this unexpected turn of events! It noticed that the main rocket engine had failed, switched to the back up engine, replanned the insertion sequence, and successfully inserted the spacecraft into orbit around Saturn (all in simulation of course---the real Cassini mission didn't use the Remote Agent!).

The success of this demonstration led directly to doing this for real on Deep Space 1, the first of the New Millennium missions. On May 17, 1999, the Remote Agent took control of Deep Space 1 to start the first of two on-board autonomy experiments. Being in mission control during these experiments was one of the most thrilling moments of my professional life!

You can read all about the Remote Agent here and about the actual experiments here. No discussion of a space mission is complete without a photograph of the spacecraft. I wanted to include a photograph of me with Deep Space 1 (in the testing bay at JPL). Unfortunately, I couldn't locate that photograph :-( So instead, you'll have to make do with the following poster. I have a big version of this poster at home---a parting gift from my NASA colleagues when I left NASA.

Sunday, May 25, 2008

Phoenix Mars Lander

Looks like the Phoenix has landed! I am always amazed by how complex space missions succeed when the engineers get essentially only one chance to get it right.

Check out the first images from Mars here.

Growing Vegetables in EarthBoxes

Some days ago I wrote about the possibility of growing vegetables in EarthBoxes. Last weekend I converted cheap talk into action---I bought 3 EarthBoxes and planted a variety of vegetables! Here's a picture of 2 of the EarthBoxes (I got the third after I took this photograph).

The EarthBox on the right has two varieties of tomatoes, while the EarthBox on the left has basil, serrano peppers, and two varieties of bell peppers (two golden bells and a purple bell). The third EarthBox is full of bush beans. So following Michael Pollan's advice, I've taken the first step toward growing some of our own food (given my expertise in the matter, we'll be happy if we get at least one meal out of this!).

In terms of the the EarthBox promise of "virtually no effort", it's looking pretty good right now. Over the last week, taking care of the plants has involved simply topping off the water reservoir through the fill tube that you can see at the front right of each EarthBox. It takes less than 5 minutes a day. And, except for the basils, the plants are looking well hydrated. (The basils' leaves are slightly curled up, which may mean that they aren't getting quite enough water, though they're clearly getting water; they're not obviously dried up or anything.) So there is a good chance that we might actually land up with something we can eat!

Saturday, May 24, 2008

Nerdy dads

Ha! I'm not the only nerdy dad reading The Number Devil to his kids!

And everyone in our household is thoroughly enjoying it, I may add.

Sunday, May 18, 2008

What is Mathematics: GCD

This is the third in the series of posts on the book What is Mathematics. This post is about the the Greatest Common Denominator (GCD) of a pair of numbers.

The GCD of a pair of positive integers a and b (denoted here as gcd(a, b)) is simply the largest positive integer that divides both a and b. The Euclidean algorithm is a simple way to compute the GCD. The Euclidean algorithm is based on the observation that for any positive integers a and b there exist integers q and r with 0 ≤ r < b such that

a = b × q + r

Note that r is simply the remainder when you divide a by b. From this it is easy to show that u is a common divisor of a and b if and only if u is a common divisor of b and r. Since the set of common divisors are identical, it follows that the greatest common divisors are also identical, i.e.,

gcd(a, b) = gcd(b, r)

To get the Euclidean algorithm, one simply applies the above result recursively to gcd(b, r) until we get to rn-1 and rn such that gcd(rn-1, rn) = 0. When this happens, we can conclude that gcd(a, b) = rn. (We would, of course, use mathematical induction to prove this formally.)

One important property of gcd(a, b) that can be derived from the above is that there exist positive or negative integers k and l such that

gcd(a, b) = k × a + l × b

Using this, the book presents a simple proof of the fundamental theorem of arithmetic. The proof starts by using the above property to show that if a prime p divides a × b then it divides either a or b. One can then easily show that purportedly different prime factorizations of a number are in fact identical.

Finally, the book introduces Euler's function. Two integers a and b are said to be relatively prime if

gcd(a, b) = 1

Euler's function, usually denoted φ(n), is the number of integers from 1 to n that are relatively prime with n. Note, in particular, φ(1) = 1 and φ(p) = p - 1 when p is prime. The book claims that Euler's function is a number-theoretical function of great importance (though it does not expand on this claim immediately).

One interesting property of Euler's function is the generalization of Fermat's little theorem: if n is any integer and a is relatively prime with n then

aφ(n) ≡ 1 (mod n)

Wednesday, May 14, 2008

Farm Bill

Greg Mankiw's recent post on the Farm Bill discusses various reasons why President Bush wants to veto the bill. If even some of these reasons are true (and I have no reason to doubt them), this looks like pork at its best and the bill deserves to be vetoed.

Tuesday, May 13, 2008

Growing vegetables

Several weeks ago Michael Pollan, author of books such as The Omnivore's Dilemma, had an article entitled Why Bother in the NY Times Magazine. The article starts by asking why we as individuals should bother to do anything about climate change. He outlines a number of reasons why it doesn't seem to make sense to bother ranging from the puniness of our efforts, to the negation of our efforts by others, to a lack of clarity on what exactly would help.

But then he proceeds to argue that given the seriousness of the consequences of not bothering, it is absolutely essential to do ones part to reverse climate change:

Going personally green is a bet, nothing more or less, though it’s one we probably all should make, even if the odds of it paying off aren’t great. Sometimes you have to act as if acting will make a difference, even when you can’t prove that it will.

Okay, so you've decided to do something about it. But what? Pollan has a suggestion:

But the act I want to talk about is growing some — even just a little — of your own food.

An interesting thought. My kids have been wanting me to garden with them for quite some time now. But having grown up in a high-rise in a big city, I didn't get to learn anything about gardening, let alone developing a love for it...:-( So I don't have a green thumb, and I've generally viewed gardening as a chore, and so have not obliged my kids.

But over the weekend, when reading the Google blog post on growing ones food, I was reminded of EarthBox. The EarthBox is a

... maintenance-free, award-winning, high-tech growing system controls soil conditions, eliminates guesswork and more than doubles the yield of a conventional garden-with less fertilizer, less water and virtually no effort.

Note particularly the "virtually no effort" clause and, of course, I'm a sucker for "high-tech systems"...:-) So I'm going to get one of these to see if I can at least grow some tomatoes for a few salads and the occasional pasta sauce. I'm not sure that using an EarthBox is exactly what Michael Pollan had in mind. But it's the closest I'm going to get to growing my own food!

Thursday, May 8, 2008

Memories of Independence Days

Today is the 60th anniversary of Israel's independence. Alon has a very nice post on the occasion, describing what his father did on the day Israel gained independence. In reading that post, I was reminded of the story of another friend's father's memory of Indian independence.

My friend's father and his family lived in Lahore (in present day Pakistan). Being Hindu, when news of independence and the partition of India and Pakistan arrived, it was clear that they had to flee Lahore. But how to flee safely---atrocities were being committed in the name of religion. Turns out that they had a loyal Muslim driver who offered to drive them across the border. So the whole family hid in the back of a lorry (truck) and the Muslim driver drove it toward the border. Along the way a mob stopped the lorry and asked to search the back for fleeing Hindus. But the driver stared down the mob, using his own religious persuasion to convince the mob that there was no need to look in the back. Fortunately, the mob let the lorry go without a search and they escaped to India. My friend's father went on to become a very senior government official in India.

For a powerful dramatization of Lahore right before and during independence, I strongly recommend the movie 1947 Earth starring Aamir Khan and Nandita Das. It's a story told through the eyes of a little Parsi girl growing up in Lahore (the Parsis were viewed as being neutral in the Hindu-Muslim conflict). Aamir Khan is absolutely amazing and the climactic scene in the movie haunts me to this day.

Sunday, May 4, 2008

What is Mathematics: Prime numbers

This is the second in the series of posts on the book What is Mathematics. This post is about some important results on prime numbers.

One of the most basic results is that there are infinitely many primes. As a kid in middle or high school, I remember being fascinated by the proof of this result. The proof, given by Euclid, is straightforward and is a great example of an "indirect proof". You start by assuming that there are only a finite number of primes. Then consider the number, n, that is one more than the product of all these primes. Since n is larger than all the primes, it is not prime, and must have prime factors. But n is clearly not divisible by any of these primes (by construction, dividing by any prime leaves a remainder of 1). This leads to a contradiction, so that our assumption must be false and there are, indeed, infinitely many primes.

The fundamental theorem of arithmetic (again given by Euclid) states that every integer greater than 1 can be factored into a product of primes in only one way. The book has a very nice proof of this theorem (again an "indirect proof" that starts by assuming that the prime factorization is not unique).

There have been various attempts to find formulae that produce primes, though no such general formula has been found. However, the prime number theorem provides a remarkable formula for the distribution of primes. Let An denote the number of primes from 1 to n. Then the prime number theorem states that (An / n) tends to (1 / log n) as n tends to infinity (where log n is the natural logarithm of n). The proof of this theorem requires advanced methods and is not discussed in the book (though there's apparently some discussion toward the end).

The book introduces some interesting open problems related to primes. Of these, the most famous is Goldbach's conjecture. This conjecture states that any even number greater than 2 can be expressed as a sum of two primes. Goldbach proposed this in 1742 in a letter to Euler, asking Euler to prove or disprove it. Empirically the result appears to be true. However, while much progress has been made, the proof remains elusive.

Finally, a fundamentally important theorem due to Fermat (also called Fermat's little theorem) states that if p is a prime that does not divide the integer a then

ap - 1 ≡ 1 (mod p)

where (mod p) says that the congruence (≡) is modulo p (i.e., both sides have the same remainder when divided by p). The proof in the book is based on observing that no pair of multiples of a of the form ka (where 1 ≤ k < p) can be congruent modulo p. For if k1ak2a (mod p), then (k1 - k2)a ≡ 0 (mod p) which implies that a is divisible by p (since both k1 and k2 are less than p). Similarly, ka cannot be congruent to 0 (mod p). Thus, each of the above (p - 1) multiples of a are congruent to (a distinct) one of 1, 2, ..., (p - 1), and therefore

1 × 2 × ... × (p - 1) ap - 1 ≡ 1 × 2 × ... × (p - 1) (mod p)

from which the result follows.

On a side note, Fermat's little theorem plays a central role in the Miller-Rabin primality test. Primality testing is essential to the RSA public key cryptosystem that is used to secure various web-based activities like ecommerce, online banking, and online stock trading using https.

Friday, May 2, 2008

Better hair care

There's been a lot of talk about how electronic health care records can dramatically transform and improve the health care industry. But Alon has a better idea: hair care records!

Securing your wireless network

In a previous post I questioned the utility of securing your wireless network. Nonetheless, suppose you do want to secure it. Ars Technica has this great post on the ABCs of securing your wireless network. Check it out if you're at all concerned about the issue. Here's the bottom line:

Generally speaking, any router that supports WPA is "good enough" in terms of its overall security. WEP, as we've previously stated, is an "only if you must" protocol, but it's still a better option than transmitting in the clear.

WEP (Wired Equivalent Privacy) is an older security standard than WPA (Wi-Fi Protected Access). While there are different flavors of WPA available, Ars Technica notes that the differences between them are small compared to the improvement of WPA over WEP. So use WPA (unless you want your Nintendo DS to connect to your network--the DS doesn't support WPA).

Early in the article they debunk various myths that:

...do more harm than good by lulling the end-user into a false sense of security.

These include hiding or changing the SSID (the name of your wireless network), disabling DHCP, or filtering MAC addresses. This last method happens to be the one I use currently. From a security perspective:

The problem with filtering by MAC address, however, is that these addresses are easily faked and readily detected by anyone using appropriate monitoring software.

However, it may be appropriate given my earlier post about not really needing security:

...filtering MAC addresses is the only one with even a minimal level of value. MAC address filtering can keep obnoxious and non-tech-savvy neighbors from easily freeloading on your wireless network, but it won't do much else.
/* Google Analytics tracking */