Navigation in LEGO MINDSTORMS Programming
- Understanding the Problem of Navigation
- Navigation Theory
- Using the Navigator API
- Creating a Navigator Robot
- TimingNavigator Accuracy
- Summary
This chapter is from the book
This chapter is from the book
This chapter is from the book
Topics in this Chapter
Understanding the Problem of Navigation
Navigation Theory
Using The Navigator API
Creating a Navigator Robot
TimingNavigator Accuracy
One of the most exciting, baffling challenges in robotics is navigation, which is important to mobile robots for obvious reasons. Without it, a robot will only be capable of wandering around aimlessly. Before we get into the finer points of navigation it is useful to define what we mean when talking about Navigation. In previous chapters we experimented with a small bumper-car robot that could move around a room with a moderate degree of success. It drove forward, and if it encountered an object it would back up and head off in another direction. Is this navigation? By strict definition, navigation is the science of directing the course of a vehicle. With robot navigation, a robot should be able to go from one point to another and have the ability to return to the original point. Furthermore, it should be able to find another position relative to the original position. This requires keeping track of where the robot is in one form or another, so a simple bumper-car robot would not be considered a navigator. With our task defined, let's get on with discovering navigational methods. This chapter, as well as Chapter 8, "Navigation with Rotation Sensors," and Chapter 10, "Navigation with a Compass Sensor," all give progressively more competent methods of RCX navigation, but each successive chapter requires additional components and a higher level of sophistication. In this chapter, the only thing you need is the basic RIS kit.
Understanding the Problem of Navigation
Why is navigation so difficult to program into robots? It seems like it should be easy to program accurate navigation; after all, navigation is extremely easy for humans. As an experiment, try navigating around your living room. As you do this, pay attention to the strategies that allow you to accurately move from one location to another. Try walking to one corner, then follow the wall to the other corner, then walk toward an object such as a television. These steps are easy for you because you are packed with sensors. Your sensors give you, among other things, a visual picture of where you are in relation to objects, and your sense of touch informs you when you brush against another object. You also have tons of memory (AI pioneer Alan Turing estimated a human has 10,000 million bits of memory, or 1.25 GB), so you can store (amazingly inaccurate) maps of your surrounding area; in fact most people have an adequate internal map of the city they live in. However, navigation within a small, visible space does not rely on any of this map data. The visual picture you see of your living room overrules any map representation you may have previously stored. To walk toward the television you don't simply point toward it, estimate how many steps you will take, then close your eyes and start walking. Instead, as you move toward it you are constantly self-correcting your direction, much like a missile homes in on a target. Now let's examine how this compares to the RCX.
We'll try to imagine your living room from the perspective of a robot. Our robot Tippy, from previous chapters, is equipped with a single touch sensor that is either on or off. It also has two motors it can control, and an internal timer that functions like a stopwatch. To put yourself in the robot's shoes, imagine climbing into a yellow box about one cubic meter in size. When the box is closed everything about the outside world becomes unknown. The box is equipped with a small control panel that contains a three-way switch (forward, stop, reverse) for the left wheel, another three-way switch for the right wheel, a stopwatch, and a light bulb (Figure 7–1). The light bulb will go on only when the bumper hits an object. We will also add the presence of a benevolent giant who exists outside the box. He may, according to his whim, give you small pieces of information that can help you in your task. Furthermore, we must introduce some pseudo-physics into this scenario. If the box scrapes by an object you will not hear it. If you back into an object, you will not be jostled or feel your momentum change. If you run over some objects on the floor, you will not feel a bump. If a wheel becomes stuck in midair, rotating freely, you will be unaware of this. This is exactly how Tippy experiences the world, and it is a very dark place.
)
Figure 7–1 Life inside the box. (Artwork courtesy of Wil Glass.)
Now let's see how well we can navigate within this scenario. Imagine you have a piece of paper and a pencil inside this box. The first thing you can do is mark an X representing your starting point. The strategy we employ is to measure the forward and backward movement using a stopwatch. We aren't really sure how fast the robot moves, but we do know that moving forward for four seconds is twice as far as moving for two seconds. Units are not really important to us because we have no idea of the scale of the outside world. One second could represent a centimeter, a meter, or 20 inches. To us it is irrelevant, so all measurements will be measured in seconds. Now it's time to boldly go forth, so we start the watch and switch both motors to forward. It's a little scary, knowing that at any moment the box could go plunging down a flight of stairs. After a time the touch sensor light goes on, so we halt the stopwatch and record the time. In this case, we have moved forward for four seconds, so we draw a line—say four inches long—due east from the X. This is our new position. We can also indicate on our piece of paper that an object was struck at that point by placing O1 next to the point. Now, because we are trying to emulate Tippy's world, our only recourse is to back up and turn in a new direction. Backing up is no problem—we just back up an arbitrary amount of, say, one second. To rotate we drive one motor forward and one in reverse, but we need to know how many degrees we have rotated. To calculate this, we need to know how long it takes to complete one full rotation. In our case, the giant has given us a piece of paper that tells us it takes four seconds to rotate 360 degrees. Thus, we decide to rotate to the right 90 degrees, or one second. Now we can carry on our way, navigating around the room and keeping track of when we bump into objects. After a while, we might even be able to make inferences about the room, such as where doorways and walls exist. At any time we can attempt to head back to our starting point, or to one of the other points within the area, using the coordinates we have written on the paper.
So, as you can see, we can perform some rudimentary exploration with little external information. The main source of external data is the light bulb—one bit—which is either on or off, but much can be inferred from changes in this state. This doesn't guarantee we are in fact where we believe we are, though. For all we know, the giant, in one of his more puckish moods, could be holding the box off the ground and pressing the touch sensor at random intervals (Figure 7–2). Barring any anomalies such as this, we should have a pretty good idea of our location at any given time. We could even go so far as to navigate to a specific section of the house. For this to succeed we have to ensure the starting point and orientation are always the same. The external giant could even hand a piece of paper through a slot that tells us the coordinates of the kitchen, bathroom, bedroom, and living room. By receiving some external data, it is possible for Tippy to get from one known location to another.
)
Figure 7–2 External conditions can affect accuracy. (Artwork courtesy
of Wil Glass.)
To really understand what the RCX robot sees, I heartily recommend navigating around your own living room. By involving yourself in what the robot experiences you can really start to understand how limited its perceptions of the world are. To do this you need to shut off as many senses as possible by turning off sources of sound such as a TV, a radio, an air conditioner, or a ticking clock. Better yet, use ear-plugs. You may want to blindfold yourself so you aren't subconsciously navigating by the brightness of a local light source. Please take extreme care if you decide to perform this experiment. I don't want to be responsible for intrepid roboticists falling down flights of stairs while blindfolded!