Beacon localization with the NXT

One of the most fundamental problems in mobile robotics is to know the position of the robot.  The question might seem simple, to get an answer is very difficult.  There are two fundamentally different approaches to answer this question. The first approach uses dynamics to keep track of the robots position in respect to its starting position. Most often this technique uses wheel encoders to keep track of wheel movement. This is translated into a position of the robot. This is known as odometry. The second approach uses external references of which the location is known to calculate the position of the robot. Navigation based on stars is the oldest example of this technique, the GPS system is a recent example. As much as we come to rely on GPS nowadays, it is not very useful for our small indoor robots. Indoors the GPS signal is week and the error of a GPS position is in most cases bigger than the range of our robots.

I created a robot that uses the same principles as the GPS system is based on to localize itself. Instead of GPS satellites I use  blinking LEDs (dLights from Dexter Industries) as beacons. The beacons are detected and identified using a standard NXT light sensor. Below you can see the robot in action. The robot is placed on a random location in a random direction in my room. It then has to find out where it is and then drive home.

The robot locates beacons by evaluating the variance in light level while scanning the horizon. Whenever a spot with large variation in light level is found, the robot stops to find out if this variation comes in a frequency that identifies one of the beacons. If so, the current heading of the robot is stored along with the identity of the beacon. If after a full scan three or more beacons are located then the robot has enough information to estimate its position. It does so by triangulation using a Snellius construction. Lejos software for the NXT has a class, lejos.robotics.localization.BeaconTriangle ,that implements all the difficult calculations. If more than tree beacons are located, the robot estimates its position by averaging the position estimated from all unique combinations three beacons. The result is an improved estimation.

Localization with a light sensor and light beacons

This time I introduce a new project: localization with a light sensor and light beacons. Localization, or navigation, is the art of determination of position and direction. The aim of the project is to determine the position and direction of a mobile robot with aid of a few beacons. Much like a sailor is able to determine the position of his ship with aid of a few lighthouses or known landmarks.

The beacons I use are dLight LEDs. Each beacon is blinking at a different rate, individual beacons can be recognized by it. Also lighthouses have a light characteristic to identify them by. The only difference between a light house and the beacons I use is in the blink rate, a lighthouse typically blinks once every couple of seconds, my beacons blink at a rate of 8 to 24 times a second.

The robot I use is the omniwheeled robot Agilis you might know from older posts. It can rotate on the spot and is equipped with a standard lego light sensor. I placed a tube in front of the light sensor to give it a narrow beam of detection. This makes it possible to localize the beacons with some accuracy. I also experimented with a lens to make it easier to detect faint light sources and to narrow down the angle of detection even further.

The localization process has three steps, localization of the beacons, identification of the beacons and calculating the robots position. The first two steps are done while the robot spins a full circle. The robot then tries to find as many beacons as possible. Once a beacon is found its location is determined and its identity established. After finishing the spin three beacons are selected and the robots location is calculated based on the relative angles between these beacons. I will discuss each of these steps in more detail over the next couple of posts starting with beacon localization in this post.

Beacon localization

Beacons are located by Agilis while spinning on the spot. While spinning the robot keeps track of its direction by means of odometry based on the motor encoders. How this is done is explained in one of my older posts about Agilis. It uses a single standard light sensor to detect the beacons. Once a beacon is found its angle is determined and stored for later use. There are two problems in locating a beacon. The first one is to recognize a beacon reliably under various circumstances. Sometimes the beacons are the brightest objects on the horizon, at other times they are not. Therefore my attempts to find beacons by light intensity proved unreliable. Especially when a beacon was further away from the robot or when the sun was shining in my room. Only when I realized that the beacons were the only blinking objects in my room I managed to locate them reliably. I wrote an algorithm that calculated the amount of variation in the light level and I took this as an indicator of a beacon. The graph below shows the results of a 180 degrees scan. The dark blue line shows the light level measured by the light sensor during the scan. The peak on the left side of the scan is caused by a beacon, the peak on the right by a light bulb. The light blue line below shows the amount of variation in the light level. As you can see it does peak when scanning the beacon, but it does hardly raise when scanning the light bulb. The algorithm proved very successful in other (more complex) conditions too. For those interested, the algorithm takes a running average (using a low pass filter) of the absolute difference between two consecutive measurements.

The second problem is to pinpoint the position of a beacon. This is both a physical problem, related to the sensor, as a logical problem, related to the algorithm used. The sensor has a rather wide beam of detection but is most sensitive to light sources right in front of it as the graph above shows. I narrowed the beam of detection by constructing a tube in front of the sensor with aid of technic connectors . I also tried a lens. Below is a graph made from a 360 degrees scan using a lens. I am not quite sure how I will narrow down the beam of detection in the final robot as there are drawback to each solution.
The second issue with pinpointing the location of a beacon is in the logic. You cannot simply sort the samples and then take the three biggest values. In this case you will end up with three points from the biggest peak. So you need to find the biggest value