What is a Robot? (Or, the Elevator Problem)

3/1/2010

I walked in to the senior stats class with some notes and ideas for a robotics-based discussion. The first question is simple, but even professionals don’t have a good answer: what is a robot?

Go ahead, think about it.

Students came up with a working definition:

• a machine
• takes/executes instructions
• has some kind of intelligence

There is a big gray area of “intelligence.” We examined by example. Is a car a robot? A good number of kids actually said yes, which was unexpected for me. I thought they would say no, which was my original thought, because the driver is doing all of the work and thinking; the car is simply a dumb machine to do the driver’s will.

If a car has no steering wheel and no pedals, and drove you around, is that then a robot? Unanimous yes from the crowd.

Continuing the line of example, if you’re in the wheat fields of Nebraska and you have to drive a combine in the fields, is that a robot? Unanimous no: that’s just a fancy tractor. So now we have a range. The big, fancy combine that is completely manually controlled is not a robot, but a car that automatically navigates and drives to a destination is.

Let’s extend this. If you sit in an office and click on a screen telling the combine where to go, is that a robot?

If you don’t have to tell the robot where to go at all, and it does everything alone, is it then a robot?

This thought exercise is a good 20-minute talk on it’s own. I didn’t have time to complete the next section, which is the good engineering-y stuff.

Is an elevator a robot?

• It’s a machine
• It takes instructions and executes them
• It uses some kind of intelligence to process the order it services floors

Looks like a ‘yes’ to me. I do think an elevator is a robotic device, if only a simple one. The question of robot rights seems to come down to the layer of intelligence involved. With that, I walked the class through the design of an elevator control algorithm. Specifically, using a drawn elevator abstraction on the board, we built up cases of what the elevator should do, and wrote rules that handle the cases properly. This was done entirely in English, not pseudocode, for maximum accessibility.

First we examined the simplest possible rule: go to the floors in the order they are requested. To the high school juniors and seniors in the room, this immediately had problems. What if there’s a top floor request, then a bottom floor, then one in the middle, all almost at the same time. The elevator would skip the middle person, going to that floor strictly in the order that the request was made, creating unnecessary wait times.

The key rule that handles most cases is “Make pickups in the same direction first.” This sentence came from the students themselves, and generally works.

A more sophisticated rule is “Drop off the person who has been on the longest, during which you can pick up anyone you pass who wants to go in the direction you’re already going.”

Ohm’s Law

2/22/2010

Science: 9th grade Physics

Taught a class unit on Ohm’s Law. I didn’t write the material, it was standard science class. I simply stepped on invitation from the teacher, who is aware that I am familiar with the subject.

We did a simple circuit with one voltage source and one resistor, exploring the concepts of voltage and current. My favorite analogy is the two rivers: the slim but fast-moving Merrimack has low current (total water volume) but high speed (water speed). Multiplied together, the river is quite powerful. The other river is the Mississippi, which has a huge volume moving (high current) but doesn’t move very fast (low voltage). Both rivers can be argued to be quite powerful, whether due to immense volume/current or high speed/voltage. This analogue is very accessible and provides a good entry to the concept of two characteristics that combine to describe total power.

We then covered resistors in series, with additive equivalents. From there, I drew a parallel circuit and analyzed it in terms of the current flow. Using a current analogy to water splitting in a pipe at a Y-junction (secretly Kirchoff’s Current Law), we found the current in each leg, and from there what the total resistance of the parallel circuit must be. I then introduced the shortcut formula, which was taken eagerly to avoid the full analysis: 1/(1/R1 + 1/R2).

Freshman Algorithms

2/22/2010

Math: 9th grade Geometry

The major presentation was a 9th grade version of the Orders of Growth talk, which has evolved into a general algorithms talk. The focus is on characterizing the time complexity of algorithms.

Step 1: Introduce with sorting. Ask class to design a sorting algorithm. This takes a few minutes to put together as a step-by-step instruction list. We then analyze the “number of steps” to run this algorithm on a fixed data set, then think about for any sized data set (n-sized).

Step 2: Searching. Show how a linear search works (check every element in order). Then do a bisection search (jump to the middle, see if I need to go above/below to find the element, then recurse on the valid half). Show time difference between the two (which is significant). The bisection search comes out much faster, but has a weakness: it only works on a sorted list. If we assume our list is sorted, then we’re good to go.

Step 3: Search trees. Data doesn’t have to be arranged in a list. This section introduces data as nodes, which can have relationships to other nodes. By traversing a tree of nodes, an element can be found much faster than a list, given a few rules are always followed.

I’ve given this talk three times, and Step 3 was only reached once. Step 3 is also harder to teach, as the example drawn on the board needs to really work to get the point across, and it’s much harder to fake than lists.

Intro to Queueing (Stats Class)

2/8/2010

Today I did a half-period introduction to queues with the AP Prop & Stats class.

So we’re ata  bank. What line to you pick to stand in? The shortest line. Why? It will probably take the least amount of waiting. The “probably” is the key.

Working through…

How long does each person take? We don’t know, but we can guess an average and a range.

If  we assume that everyone takes the same amount of time to do their transaction, then the line length directly corresponds to the wait time for that line. But of course, that’s not how it works in reality.

Characterizing the Problem

What elements are in this kind of problem? (using example of the bank)

• Resources (tellers)
• Consumers/users (the people)

At any point, we don’t know:

• How many people will show up
• How long any person will take

We end with a discussion of other problem that look like this, which is surprisingly difficult. The easy choices come up first: other human service situations with lines and limited servers. Others also emerge with different levels of guidance: traffic and data moving through the internet were two strong suggestions.

Notes so far

1/13/2009

The laser module went ok, but on another iteration it can use some tweaking. I wanted from the beginning to use larger data sets, but did not for fear that it would require too much time in rote calculations, boring the students. With too little data, the problem wasn’t convincing.

Moving forward, I’ll distribute the points for calculation across students or groups of students, which allows more data to be done by hand in parallel. The by-hand requirement is good to keep the class working as a class without having to break to the computer lab. The groups would then bring their results together to draw the final picture on the board. With this, I can have more sophisticated hidden pictures/obstacles, making the project that much more engaging.

My intro to sound module went very well. My favorite addition to this material was the physical simulation of a transverse wave, where I set up a row of volunteer students standing, then added a “shove” at one end that propagated down the entire line. This was a good way to show that the wave moved very far while the particles of the media did not. This demonstration is good pedagogy, and is known as a “kinesthetic learning activity,” where taking physical action helps understanding of a concept.

Orders of Growth for Stats Class

12/16/2009

Stats class is starting to use logarithms for curve fitting and data straightening, so I developed a talk introducing related computer science context. This is relevant to my research area!

I put a series of numbers on the board: 2 3 1 6 and ask how long it would take to sort these numbers. Sure, it’s near instantly for a person to do, but how many steps are we actually carrying out? How many operations does it take?

The students collaboratively came up with an algorithm to sort that searches for the smallest number and moves it to the front.

(Future improvement: give a worse worst-case example off the bat.)

The students’ algorithm can sort 4 items in 11 operations, including moves and comparisons. This size of a list is easy to understand, but it’s so trivial that efficiency doesn’t matter. More operations are necessary as the list gets bigger. This relationship can be graphed, where the x-axis represents problem size and the y-axis the number of operations required.

Now I draw the growth curve of a linear function, with the help of the students, who never fail to remember that linear means x=y, which has a straight line graph. I then draw x-squared on the same graph, which the students are also very familiar with. I also draw a straight horizontal line to represent constant time

What is a process or algorithm that would operate linearly? What process would take more operations per problem size in a fixed, 1:1 constant ratio? The easy answer is usually counting. If there are n elements, then it takes n operations to count them all. Just for fun, I ask the students to come up with something that operates in constant time: stays the same no matter how big the input is. The answer I got was “odd or even?” which is a great example.

This question of “how many operations does it take relative to the size of the problem” has a computer science term behind it. The answer is a Big-O classification. A function is O(n) (pronounced “big-oh of n”) if it operates in linear time, meaning for the problem size n, the number of operations will also be about n.

Another example of a linear time operation is searching within an unordered list. In the worst case scenario a search will take you to the end of the list, which is n, the problem size. The operation in the search is to check every element, with a maximum of n, so the worst-case number of operations needed is n. I keep repeating this throughout the presentation.

Now, the fun part!

Let’s think about finding your name in an unordered list. This takes linear time in the worst case. (Here is a good moment to check if the students understand what the worst-case is, and why we want to look at it.)

How long, or how many operations, would it take to find your name on the list if the list is in alphabetical order? Guide the students to determining an algorithm principle to do this. The algorithm we ended up with was Bisection.

The jist of bisection:

• Jump halfway down the list.
• Look at the name you landed on.
• If your name comes before it, we can ignore the second half of the list.
• If your name comes after it, we can ignore the first half of the list.
• Repeat on the remaining section of the list.

The demonstration:

Hold up a piece of paper with some kind of list on it (it looks best with stuff printed on it that is list-like). Start at the top line. Ask “is this your name?” No. Jump to the middle.

What to we know about the middle line? The starting letter. We know our name comes before or after that point in the list.

Fold the paper in half to signify reduction of the field. The remaining half is the remaining section that we’re listed in somewhere.

Now repeat, by folding the paper again, reducing the set by half again. This shows that bisection reduces the data set very quickly.

Questions:

• What does this process depend on? The list being sorted, or in our case, alphabetized, and you knowing how to spell your name (funny, groaner).
• How many operations does it take to find your name with this method? What is the Big-O? the answer is O(log n).

I draw the log(n) curve on the board with the others. It is grows much more slowly than linear, meaning for big data sets it is faster. Does that make sense for the bisection method? How can a bisection search do it faster than a linear search?

The big answer is that bisection doesn’t check every element. it doesn’t even check half the elements, so it can zoom in on the correct answer much faster.

Conclusion, wrapup, fun times for all in math class.

About the Boeing 787

On December 15, 2009 I talked to physics classes about the new, upcoming Boeing 787 aircraft. The time was spent in discussion, where I posed questions on the design concepts and the students came up ideas. Most of the ideas were right, and exactly what Boeing did on the 787.

Setup: Everyone knows the 747, which is probably the most famous commercial aircraft in the world. Beoeing made newer, bigger models, but they didn’t sell nearly was well. What do you do to make companies want to buy your airplane?

The 787 boasts greater fuel efficiency than existing planes. How do you make a plane that is bigger, but have it consume less fuel?

There are two parts to the answer, and the students very successfully came up with both. The first part is improved aerodynamics. To illustrate this point, I had to teach how wings work, and how lift is created, illustrating Bernoulli’s Principle on the whiteboard. We then talked about turbulence over the wing, and how subtle adjustments of the curvatures can reduce that turbulence. I used the image from this wiki page to show it more precisely after I worked through the whiteboard drawing. Also, take a look at this picture of the 787. See anything somewhat strange? It’s the scalloping on the rear end of the engine cowl. That shape also reduces turbulence, which reduces air friction, which reduces drag, which reduces how much energy is needed to travel at a certain speed, which decreases fuel usage.

The big way to increase fuel efficiency other than aerodynamics is to reduce the weight of the aircraft. Great! So how do we do that? Every class quickly volunteered “materials,” “what it’s made out of,” or even “carbon fiber.” The answer to all of them is yes: high-tech composite materials, such as carbon fiber and plastics, are used extensively in the 787. In fact, each 787 has over 23 tons of carbon fiber in it. We then talked about how the molding and extruding process of composites allows us to create shapes to dissipate energy differently than we could do with traditional metals. Most historical aircraft (once we got past making them out of wood) are made from steel. What’s good about steel, class? It’s extremely strong, but incredibly heavy. Only 10% of the 787 is steel.

So the airplane is bigger and more fuel efficient. What else do we need to make it marketable? If you’re out shopping for a car, or anything, what’s the big thing you always look at? The price.

The 787 can be made for between 150 and 200 million dollars. That price is very normal for a large aircraft, and is actually 100 million less than the predecessor 777. How can we make the airplane so cheaply? It’s big, made out of fancy expensive materials, and had years of costly design and simulation hours. It all comes down to how we build the plane.

Traditionally, a large boat or aircraft is built in one place. You start with an empty dock, and you start welding the frame together, and eventually there’s a big cruise ship in that dock. Fill it with water, and you can float it out to sea. Building a vehicle all in one place like that is extremely expensive, as it requires every single tool required for the entire process to be in one place. The cost of manufacturing can be hugely reduced by distributing the construction around the world. Some plants already exist that can build wings well, so let them do it. Other companies can construct seats and electronics and hydraulics systems, so them do that. Put the worker-intensive stuff in countries with cheaper wage labor. All this gets the parts built cheaper, but creates an incredibly complicated supply chain. Boeing went so far as to build custom aircraft to carry the pieces of the new aircraft, so that they can be built and assembled in different places.

What else do we need? What’s the biggest thing you see on every car ad? Safety.

Take a look at the cockpit of the 787. It has a huge horizon display, and heads-up displays so pilots don’t have to take their eyes off the sky or ground to see important numbers. I gave an example of a pilot landing an aircraft in a snowstorm. Barely able to see the ground, the pilot does not want to have to look away even for a moment to check the airspeed. The new, fancy 787 cockpit is a newly designed and supposedly easier to fly, especially when compared against the 747 cockpit design.

That wraps it up: a discussion on how an aircraft manufacturer can make a plane that companies will actually want to buy. Time spent: about a half hour in front of each class.

Project Boot Camp

On December 1, 2009 I taught the geometry students the basics for building a good project poster board and presentation. I call this “Project Boot Camp.” Ok, not really, but it makes a good title.

All students in Mr. MacDonald’s math classes are doing math projects to be presented at a fair at the end of December. The time has come for them to start formulating their final products: the presentation and presentation aids.

We start with the basics of how to make a poster board.

Important things to remember:

The purpose of your board is to

1. Help your presentation. Have what you need to see.
2. Help cue your talk. You can follow your board to remember what to say.

Suggestions:

• Tell a story with your board.
• Don’t put pages of text on the board.
• Include anyting (pictures/graphs/etc) that you will want to reference or point at during your talk.

Speaker: David Brown, Motorola

On November 24, 2009 David Brown from Motorola came to speak to the students. His talk varied class to class, and his topics included:

• evolution of media
  • radio evolution
  • recorded media evolution (record/casettes/ipods)
• History of Motorola, what they actually do
  • Cell phones small potatoes
  • 60% market share in Cable TV equipment
• Business organization and heirarchy
• Money to be made at different stages of education and business
• Difference between a scientist and an engineer

David was very well received by the studetns and teachers. His insight was deep, but his presentation fresh and sufficiently youthful. Students asked many good, on-topic questions, which David answered very thoroughly.

This was a fun event for the students, who got to see a different take on technology.

First run of Laser Data Research Module

On November 11, 2009 I presented the first run of my research module: Laser Rangefinder Data Processing.

Overall it was recieved at what I’d call a firm B+. The points got across, but there is a lot of room for streamlining. Having tested the module out I learned some things.

• Make sure the kids have calculators. Having the teacher help with this is critical. Or, find some way to do sin/cos calculations in a collective manner without individuals doing math on calculators.
• Need to make the purpose of the module more engaging. Being able to visualize data is important, but the currnt introduction is not conveying that very well, nor how cool it really is.
• Need something animated, graphical, or a physical demonstration to get the students excited. (pertaining to bullet above).

The module content is based on the use of a Sick LMS-200 Laser Rangefinder in autonomous robotics. Laser devices like these are high-precision scanning devices capable of drawing a profile of all objects in the field of view. They are fast, extremely accurate, and very stable. The problem (as I pose it to the students) is the data it generates is not useful in it’s raw form. Given a list of numbers, can you tell where an obstacle is? Not really.

One of the heavy themes is data visualization: the act of taking numbers and drawing pictures that are more easily understood by humans. In our case, by making the information more understandable by humans, we can also make it more useful to the robot.

The concept of sine and cosine is introduced in order to generate the images of the laser’s field of view. The data returned from the laser is a series of distances, each one with an implied angle from the origin point associated with it. We break apart that data into distance/angle pairs, which are essentially coordinates in polar form. Using sine and cosine the students learn to convert those coordinates to rectangular form, which they can easily plot on graph paper, making the visualization.

We step through one simple set of data on the board, and then the students try to work through another set on their own. My goal was for the students to work individually and create their own picture, but a lack of calculators at hand turned it into a collaborative effort on the whiteboard.Without personal accountability there was no need to pay attention, and the less interested students were lost.

At the end, the concepts of sine and cosine may not have been fully understood, but the application of them seemed to stick, as the majority of students could do a polar/rectangular conversion properly.

There is still a lot of room for tweaking in the presentation. With one test run out of the way I have a good understanding of how to improve it. Combined with advisor input, this should be a very viable module sometime soon.