Infomage

This post starts to answer a question I get asked a lot. I hope to explain how the ultra-high-tech software used by NASA and the government works. It’s also very similar to the software Google is using to make their driverless cars! It’s also similar to my own open-source project.

Q: Why are model-based languages better than traditional programming languages?

This is the first part of a three part article explaining how the ultra high-tech software used by NASA and the military works. I’ll give examples you can download and try at home!

There is a lot of hype about the model-based revolution in computer science. But there is a mystery. If any algorithm can be written in C++ or Java, how can there really be a “better” language? The heart of the mystery lies in a funky little thing called the Church-Turing Thesis (http://en.wikipedia.org/wiki/Church-Turing_thesis). In the 1930′s the math crowd was deeply involved in the math of what would become computer science. Two of them, who would be really important in creating the foundation for what we take for granted today, accidentally discovered the same fact but from different perspectives. In fact, the perspectives where different enough that it took some time before they realized they were saying the same thing. Alonzo Church was creating a way of writing down mathematical functions; he wanted to be able to write down any function that could possibly be calculated. Meanwhile, Alan Turing was thinking about machines that could compute things. What would a machine have to be like in order to do any kind of computation? After they each proved that their projects where in a sense “complete”, it turned out that Alan’s theoretical machine could calculate any of Alonzo’s functions and vice-versa.

If you’ve thought about programming much you likely have figured out that you could use a language like Lisp to write a C++ or Java compiler and likewise you could use C like languages to write Lisp. Actually, it’s the case for any language that is “Turing Complete.” Even very different computer languages like Haskell or Prolog can be made to do all the others. And that means that none of them can do any computations that the others can’t also do.

There are languages that are not Turing Complete. XML and HTML are examples. But there are only a handful of magic ingredients necessary to make a language Turing Complete. The language must have features equivalent to these: The ability to do assignment statements (A=5), sequences of actions, repetitions of actions (loops), conditionals (if / then) and it helps to be able to define sub-routines and do arithmetic. That’s it!

So the mystery is, if these can do any calculation possible, how can we say that model-based programming is more powerful?

There are a number of ways that one language can be “better” then another. Programs written in non-structured languages like BASIC become hard to figure out and hard to debug. C is a great language when you need tight control over HOW the program gets the task done. C++ gives the same control but imposes restrictions that make it easier to tell what a piece of code does at a glance. Scripting languages like Python are better if you need more structure and don’t need tight control over how a computation is carried out.

But the claims given by proponents of model-based computing seem stronger than trade-offs between speed-of-programming vs. speed-of-execution. Official papers speak about real-time reasoning, advanced robot behavior, and extremely easy programming. Off the record, proponents are glowing about finally fulfilling the AI dreams of early computer scientists. A great paper you can Google by some of the leaders in the field is called “Model-Based Programming of Intelligent Embedded Systems and Robotic Space Explorers” (BRIAN C. WILLIAMS, MICHEL D. INGHAM). Consider this description from that paper:

In executing a control strategy, model-based executives reason about the models “on the fly,” to track system state, diagnose faults, and perform reconfigurations.

If you want to understand how cool this is, realize that it isn’t saying “Models let us do cool things like track system state, diagnose faults, perform reconfigurations, and so on.” It isn’t a list of three things. The “perform reconfigurations” thing is to FIX the “diagnosed faults” and the “diagnosed faults” are discovered, not by if-statements from a clever programmer, but by the “tracking system state. So, a traditional robot might keep moving it’s legs in the “walk” pattern even after it has fallen over. A modern robot will sense that it has fallen over and perform a “get up” maneuver which was written by the clever programmers. But a model-based robot is monitoring its state and the environment’s state. It’s “goal” is to walk or to get from point A to point B. If it’s state isn’t becoming “closer to point B” it can “diagnose the fault” and “perform a reconfiguration” without any help from the programmer — “on the fly”. That’s great because while a programmer might have created an “I’ve fallen and need to get up” sub-routine, I’m worried about the “I’ve been lassoed and am suspended over a pool of lava” problem.

Amazing! But it isn’t magic. Let’s look at how it works. We’ll start by looking at how we might try to get a robot to work with a traditional programming language.

Suppose we have a robot and we want it to move from its current location to a point five meters in front of it. And suppose we have programmatic control over the motors that control its wheels.

Now, stop for a second because I’m going to tell you what pattern to find in the next few descriptions. We’re going to start with a really crappy program that might or might not actually get the robot from point A to point B. Then we’re going to consider improvements to that program. But it isn’t too important how the program works. We’re going to step back and look at the pattern of how we improved the program. In other words, first we’ll use our brain to improve the program. Then we’ll look at how we did that! It is that activity that we want to focus on. It’s that activity that NASA is using to get robots to take actions in situations that the programmers could never have prepared for.

ROBBIE WITH STATIC PROGRAMMING

Back to our robot who I call Robbie. (Robbie shows up in my articles a lot.) Let’s say we have this command which turns either the left or the right wheel motor on:

motorControl(left, -0.5)

Instead of -0.5 we can pass in 0, which would stop the motor or 1 to make it go forward full speed. Negative numbers will make the motor (and thus the wheel it controls) turn backwards. 1 and -1 are maximum speeds forward or backwards.

Let’s play with poor Robbie for a moment. Let’s make him go in tight circles by spinning just his left wheel. If his right wheel is stopped, he’s going to turn a tight slow circle to the right. Lets start his left wheel and stop the right wheel:

motorControl(left, 0.3)
motorControl(right, 0)

If we want him to go forward we need both wheels to spin at the same speed. Let’s make up a new command called goStraight that makes him go forward at a certain speed. It will do this by setting both wheels to the same speed. Let’s use a variable named “Speed” to represent the speed we want him to go. Here is the definition:

define goStraight (integer Speed) =
     motorControl (left, Speed)
     motorControl (right, Speed)

Now we can use our new command. Here is how we could make him go straight at ¼ full speed:

goStraight(0.25)

Here is a definition of a command to make him come to a full stop:

define fullStop () =
    motorControl (left, 0)
    motorControl (right, 0)

And a command to make him spin in place by spinning one wheel forward and the other backwards at the same speed:

define spinInPlace (integer Speed) =
    motorControl (left, Speed)
    motorControl (right, -Speed)

You get the idea. We started with motor control commands and we now have a tool-kit of commands we could use to drive him all over the place. Now back to the task at hand. We want Robbie to move from his current spot (Point A) to Point B which is five meters in front of him.

Let’s make a wild guess that at full speed he goes about 1 meter per second. So if we send him off at full speed, straight ahead, he should get there in about five seconds.

So, let’s assume we have a command that just waits for a certain number of seconds to pass. If we want it to wait 5 seconds we type:

wait(5)

So here is how we could get Robbie from Point A to Point B. And remember, Robbie’s computer does these commands one-at-a-time and in order. Also, I’ll make a comment by putting two slashes before my comment.

goStraight(1) // This tells the computer to make Robbie go straight full speed.
wait(5)      // Next, the computer waits for 5 seconds.
fullStop()   // Lastly, the computer stops the motors.

So if nothing was in the way, and if our guess that the top motor speed moves Robbie at 1 meter per second was accurate, and if Robbie was facing exactly toward Point B and if Robbie’s wheels are exactly the same size, this program might get Robbie to Point B.

That would be fun to try. But what if Robbie missing the mark means that we don’t get half the kingdom and we don’t get to marry the Princess? We don’t want him miss so we need to move some of those ‘ifs’ into our program. (PATTERN ALERT!)

Another easy improvement: suppose we time Robbie going a whole kilometer and dividing by 1000 meters/kilometer we figure out that at speed 0.7689 Robbie is going, on average, one meter per second. Now that we have more information we can write a better program. (MORE PATTERN ALERT!)

Let’s give a name to that number so we can easily adjust it later if something changes:

oneMeterPerSecond = 0.7689

Here is the new improved static program:

oneMeterPerSecond = 0.7689
goStraight(oneMeterPerSecond) // start going straight at one meter/sec.
wait(5)                       // Next, wait for 5 seconds.
fullStop()                    // Lastly, stop the motors.

MAKING ROBBIE’S PROGRAM DYNAMIC

Robbie’s little program is, so far, not even close to model-based. But the last section gave us a starting place and a feel for how we might control a robot. The big problem is that the program is static. We run it, it goes to completion then stops whether the goal was reached or not. We need a program that can adjust for new circumstances as they arise. And it should keep trying until it get to the goal.

Here is a skeleton. The parts in ( ) and [ ] need to be filled in.

[do any preparation work]
while (location-is-not-point-B)
    [do something to get closer to point B] // These are “under” the while loop.
[lastly, do anything needed to finish]

Let’s use our old static program to fill in the blanks:

oneMeterPerSecond = 0.7689
while (it has not been 5 seconds)
    {goStraight(oneMeterPerSecond)} // These tasks keep repeating for 5 seconds.
fullStop()

This basically says “keep going straight until 5 seconds have passed, then stop.” But the structure is much more flexible. Now we can add adjustments and sensors. Let’s look at how. Also, remember to keep thinking about the overall pattern of how we are solving the problem in general.

Let’s play with a few of the problems we identified earlier. First, we’ll think about what to do if Robbie isn’t facing the right direction.

Remember how we started by creating some commands to use? GoStraight, fullStop, etc? From now I’ll just talk about what commands we’ll use and skip actually writing them. So, let’s assume we have written commands that tell which direction Robbie is facing and which direction to the goal point. We’ll call them:

botsDirection() and goalsDirection().

Also, we need a command that tells what point we are at. We’ll call it

botsPosition().

We can use that command to write a new command which turns the bot until it points toward a specific point:

turnToward( point )

Let’s try filling in the blanks of the skeleton program differently with our new commands:

while (botsPosition() != PointB) // ‘!=’ means “does not equal”
    if(botsDirection != goalsDirection)
        turnToward ( goalsDirection() )
        goStraight(0.5)
fullStop()

Notice the pattern: we had a problem (the bot may be facing the wrong direction). So we added new commands and added an “if” statement that detected then adjusted to correct for the problem.

Once again: 1) There’s a problem.   So 2) We add an ‘if’ statement to detect and 3) adjust to correct the problem.

We can solve any solvable problem this way. Let’s try another one. What about obstacles in the path?

We would have to fill in the blanks, but the overall solution could be something like this:

ScanPathForObstacles()
If ( ObstaclesAreFound() )
    FindPathAroundObstacles()
    GoStraightToPoint( FirstPointInThePath() )

This would take us to the next point. This chunk of code would be in the while-loop of out skeleton program so it would keep getting done over and over. So when Robbie got to the first point it would then find the next one and do it again. Eventually, it would get to the goal point.

Now let’s look at a tricky problem and see if we can solve it by making commands and adding an ‘if’ statement that detects the problem and makes adjustments to solve it. The problem I am thinking of is the problem of Robbie’s wheels not being the same size. Remember that to go straight we set both motors to the same speed. But if one wheel is smaller than the other (or if the motors are slightly different) then Robbie won’t be going straight.

Here is how we might do it:

Step one is to use the botsPosition() function to determine whether Robbie is going straight. It’s pretty easy; After each turn, we remember the position. Then we check whether the previous position was in a straight line along the direction Robbie was facing (which we know from the botsDirection() function). From this we can determine how much the bot is turning and how fast it went. We can update the oneMeterPerSecond variable as well as a variable that tells what percentage faster one side is moving than the other. That variable can be used in the goStraight() command to turn one wheel slightly slower.

The realization that almost any problem can be solved like this led to an improvement for some types of programs that came to be called “Good Old-Fashion Artificial Intelligence” or GOFAI.

GOOD OLD ARTIFICIAL INTELLIGENCE AND EXPERT SYSTEMS

Remember the skeleton program above? It can be made to be very general purpose. Consider this version:

[first, do any needed preparation]
then, while (the-goal-is-not-reached)
    [do something to get closer to the goal state]
[lastly, do any needed clean-up tasks]

We could even make a command that does goals:

define doGoal (goalToDo) =
    [do any needed preparation]
    while (the-goal-is-not-reached)
        [do something to get closer to the goal state]
    [do any needed clean-up tasks]

If this could work we could do cool things like:

doGoal( moveRobbieTo(PointB) )

How would this work? Whatever goal we want it to do (when we use the doGoal command), the system will merely do a look up for all the if’s and commands for that goal.

There are several advantages to this. First, now the commands we wrote (like goStraight) can also become “goals”. Thus we can add new ‘if’ statements to those commands which makes it possible for the robot to store and activate solutions to sub-problems like going straight.

We can even make goals out of commands like getBotsPosition(). So there could be ‘if’ statements to handle situations like broken sensors or situations like being near a magnetic field affects the compass sensor.

This kind of system is called an Expert System. They are programmed like this: People (experts) who know what kinds of problems can arise in certain situations put lots of ‘if’ statements into a database and organise them into queries or goals. The system can string them together and it makes programming for complex situations much easier.

It also provides automatic tracking because the system will log which if statements were used to make a decision. For example, which if’s were used to decide to turn on the wheel motors at a certain time. So you can ask “why” was a decision made. Very handy.

IT ISN’T ENOUGH

In the 1980’s computer folks were very excited that this type of system would make computers very useful. It was called “Artificial Intelligence” but it later became known as “Good Old Fashion Artificial Intelligence” because it didn’t do as much as was hoped for.

What if the expert who programmed the thing didn’t provide ‘if’ statements for “I’ve been captured and am hanging over a pool of lava?”

In retrospect it turned out that there are so many things that can go wrong you can never provide enough if statements. In NASA’s space ships this problem is solved using Model-Based programming.

MODELS AND INFINITE IF’s

The idea behind model-based programming is that instead of having an expert list all the things they think might go wrong, a model is constructed that represents the environment the robot (or whatever) is operating in. Then, the model can be used to, in a manner of speaking, generate new ‘if’ statements on the fly. In some cases they can even generate new models based on sensor input. In addition to being able to generate if’s, it can question the assumptions used to create the if’s. For example, the program might notice that logs show that moving both motors at the same speed does not cause the robot to move in a straight line. So it can look up the models that led to the assumption that turning both wheels should cause the bot to move straight. One assumption might be that both wheels are the same size. So it can adjust the model so that the wheels are not the same size, regenerate it’s “ifs’ database then try again. If it doesn’t work, back to the model; are the motors turning at the same rate?

At the beginning I asked the question “how are model based languages better than traditional programming languages?” The answer is apparent now; with traditional languages the programmer or a knowledge expert must explicitly program every possible problem that may be encountered. While this is easier using expert systems and good-old-fashion-artificial-intelligence, there are still a very large number of situations and it’s too hard to program them all. Model based systems work by generating and regenerating models in real time so that the if’s of the program can be deduced or inferred as needed.

NEXT ARTICLE

In Part Two of this series I’ll talk about what NASA’s models look like and how the engine is programmed. In Part Three I’ll show you how to do cool things for yourself using models. I’m excited about beginning to blog again; I have plans for articles about modeling really complex systems like social/political systems. We can ask questions like what would happen if all labor could be done by robots: surgery, auto-repair, hair-cutting, dish doing, laundry, vacuuming stairs, sorting garbage. A cool enough model will let us tweak things like how money flows, how regulation affects things, and so on. It’s an exciting time to live!

It’s labor day weekend here in the US. Yesterday we went to Santa’s Workshop to celebrate my now four-year-old son’s birthday. It’s an amusement park in the mountains that is super fun for kids and I enjoy being with my family. I’m also working full-time on my own model-based-programming software and on the open-source consumer tool that I hope will revolutionize the Internet. I want to express my deep gratitude to those who are helping my dream to come true. It means a lot to me.

Your loving-his-life friend,

Bruce Long