Ever since I was eight, one of my earliest memories of self-consciousness, I have dreamt of cars that drive themselves, where you could turn your seat towards the center and play a game of cards while travelling (entertainment those days!). I believed that by the time I’d be old enough to take control of the wheel, I would no longer need to.

When I was thirteen, it became pretty clear to me that this would not happen in time, and I began questioning whether we’d actually achieve this in my own lifetime.

Now, a couple of years later, having been astonished by how far Google is with their self-driving Prius (and now Audi TT’s and Lexus RH450h’s as well), empowered by Sebastian Thrun’s Programming a Robotic Car course, and supported by my high school, I have been working a self-driving car of my own.

Taking on passengers might take some more time, though.


Sequences have been lengthened – the actual computation time for updating the probabilities after move and sense is ~6ms each. It’s moving the robot that takes time.

sci-bot: noun A knowing / self-aware robot. From the Latin sciō + Czech robot

The guts

iRobot Create (from iheartengineering.com)
The Create is a decently priced platform (about $200) to base a robot on. Given that it is simply a Roomba without the vacuum cleaner guts means that you get a reliable, tested, and complete system (from battery recharging to motors) with a decent programming interface.

Zach Dodds et al. from the Rose-Hulman Institute of Technology has written a brilliant python wrapper for the Create’s serial interface. I use it because it simplifies commands like move forward at 25cm/s rotating at 30°/s from:

137 0 250 1 221

to the more intelligible:

robot.go(25, 30)

Laptop
The laptop acts as the middle man between the sensors and the robot, the brain some might say, interpreting the sensor data (the robot & LIDAR sensor just plug in over USB) and giving directions to the robot.

Hokuyo URG-04LX URG01 Laser (from Hokuyo)
While not exactly cheap at $1200, a LIDAR (short for Light Detection and Ranging) provides extremely accurate (around ±1 cm, though the URG01 is limited by Hokuyo to ±3 cm) distance information. Measuring distance given the change in phase of a reflected light wave it operates similarly to radar (though radar, using radio waves, is further along the electromagnetic spectrum). Using light rather than sound it is both quicker (after all you hear sound echo, but on a normal human scale don’t see light echo), less prone to interference and works over longer distances (military rangefinders reach 25km!) than say an ultrasound sensor. It may be overkill for a basic robot, but it becomes integral for advancing the robot.

The URG01 provides a 5.6m range over 240° (for reference, the Xbox Kinect sees about 55°) for 683 points along it’s rotation (it’s a laser diode and photo detector that rotate). Rotating at 10Hz (10 times a second) it provides about 6000 data points per second. Weighing 160g, it’s perfect for this application.

right is what the LIDAR sees in our hallway at home, with an outline of the hallway overlayed (one circle is 1m).

Consider it a tiny version of the LIDAR that’s used for Google’s cars and self-driving vehicle research…1.3 million data points / second…Wow!

Velodyne HDL-64E Laser Rangefinder (LIDAR) Pseudo-Disassembled

The brains

The robot uses basic Mote-Carlo localization (a histogram filter) to find out where it is at that moment in time. In other words, given a grid based map of the environment, the code will use probabilities to work out in which cell (or part of the map) it is likely to be. Given that this requires there to be a preexisting map of the world in which the robot is, it is not fully autonomous, or able to make decisions when things happen that you do not expect to happen (for example, somebody is standing in the hallway).

Anyway, it starts by having a map of environment, in this case our hallway at home represented by 1m² squares, or cells. Not only does the robot not know where it is, but it also doesn’t know in which direction it is facing – this becomes a big problem if you tell the robot to drive forward because you think its position is aligned with the North map, but it might actually be facing East, so it hit’s a wall… To counter this, there are four maps, one for each direction North, East, South, and West – in the East one, for example, we assume the robot is facing East, in the South one, we assume South, etc.

Since the robot has no idea where it is or what direction is is facing when it starts, each cell begins with the same probability of 2.8% (1 ÷ (9 cells × 4 orientations)):

2.8%
2.8% 2.8%
2.8%
2.8%
2.8%
2.8%
2.8% 2.8%

North

2.8%
2.8% 2.8%
2.8%
2.8%
2.8%
2.8%
2.8% 2.8%

East

2.8%
2.8% 2.8%
2.8%
2.8%
2.8%
2.8%
2.8% 2.8%

South

2.8%
2.8% 2.8%
2.8%
2.8%
2.8%
2.8%
2.8% 2.8%

West

Next, we take a look at what the sensor sees. In this case, say it it sees a wall to the left, space in front, and a wall to the right (in the code I’ve written, that is represented as [1, 0, 1]). With this new data, we can now cycle through all the cells and if this sensor measurement is what we’d expect at that location and orientation, we increase it’s probability, and if it is not, we decrease it. So this is what we get after the first sense:

0.5%
0.5% 0.5%
8.8%
8.8%
8.8%
8.8%
0.5% 0.5%

North

0.5%
0.5% 0.5%
0.5%
0.5%
0.5%
0.5%
0.5% 0.5%

East

8.8%
0.5% 0.5%
8.8%
8.8%
8.8%
8.8%
0.5% 0.5%

South

0.5%
0.5% 0.5%
0.5%
0.5%
0.5%
0.5%
0.5% 8.8%

West

And we see that it is unlikely that we’re facing East – after all, there is not a cell (facing east) in which we’d expect such a sensor reading.

Next up, we move the actual robot (after all, what use is it stationary?). The measurements from the LIDAR told us there is space ahead, so we move forward. If we can move to a particular cell, its probability becomes the probability of the cell that we moved from plus the probability that it stays on that cell (the robot’s movement is not perfect, so to factor that in, we add the (unlikely at about 10% – a value that I (somewhat arbitrarily) made up) chance that it doesn’t move). So, probabilities are shifted around and are changed a bit depending on whether we can move to a cell, or whether the robot breaks down. This forward movement then gives us:

0.5%
8.7% 0.1%
9.6%
9.6%
9.6%
1.4%
0.1% 0.1%

North

0.1%
0.1% 0.5%
0.1%
0.1%
0.1%
0.1%
0.1% 0.5%

East

1%
0.1% 8.7%
1.4%
9.6%
9.6%
9.6%
8.7% 0.1%

South

0.1%
0.5% 0.1%
0.1%
0.1%
0.1%
0.1%
8.7% 1%

West

Note how the probabilities have shifted and changed slightly.

Once we have a map (the first step, where each cell has a uniform probability) we just loop through sense() and then move() until we’ve either reached our destination or are happy with the result. So next there’s sense again with a reading, say, wall to the left, wall in front, and space to the right or [1, 1, 0]:

0.1%
28.9% 0
1.7%
1.7%
1.7%
0.2%
0 0

North

0.2%
0 0.1%
0
0
0
0
0 0.1%

East

0.2%
0 28.9%
0.2%
1.7%
1.7%
1.7%
1.5% 0.2%

South

0
0.1% 0
0
0
0
0
28.9% 0.2%

West

So, now there are three points where we’re (equally) likely to be. To improve the accuracy, we continue the loop with a move. This time, however, with the reading from the lidar saying that the only free space is to the right, we need to turn the robot 90° to the right, and then move forward. Since we change orientation, we need to move the maps as well. In this case, we turn right, so all the probabilities of the North map become the East map, all the probabilities of the East map becomes the South map, and so on. After the map turning, we just apply the normal move updating of probabilities – shift them and update them to include the chance of a failed move:

0
0 0
0
0
0
29.4%
3.3% 0

North

0
3.3% 29.4%
0.2%
0.2%
0.2%
0
0 0

East

0
0 0.2%
0
0
0
0
0 0

South

0
29.4% 3.3%
0
0.2%
0.2%
0.2%
0.3% 0

West

Continuing the loop, there is sense again with say, wall to the left, space in front, and wall to the right or [1, 0, 1] and we get the wonderful result of:

0
0 0
0
0
0
88.5%
0.5% 0

North

0
0.5% 4.7%
0
0
0
0
0 0

East

0
0 0.1%
0
0
0
0
0 0

South

0
4.7% 0.5%
0
0
0
0
0.1% 0.1%

West

and there, after moving only 2 meters, the robot has a pretty decent idea of where it is and which way it is heading. If only the real world were so easy!

You may notice that the movement in this case was the same as in the video earlier. You might also have noticed that we got slightly different results this time round. The reason for this, is that for some reason (I’m still not sure myself) the robot sensed that there’s nothing in the way or [0, 0, 0] instead of wall to the left, space in front, and a wall to the right or [1, 0, 1] right at the start. Thus, since [0, 0, 0] isn’t something we’d expect so see anywhere in the map, we lost that first piece of information and just moved forward without sense updating the probabilities. It is because of this (the sensor is sometimes wrong), that there’s also a factoring of the sensor data, though it is unlikely (I guessed it at 1%) that this will happen.

In retrospect, I suspect it might be because the LIDAR was still turning on, and since it runs in a separate process (on a separate core), the code didn’t realize that. Something that needs investigating.

Another pattern that you may have picked up, is that while sense adds information, the move function will sometimes make you lose information. This happens when the robot is driving up the straight part of the hallway (again, in the video) and is 83.2% sure that it that cell at the beginning, but by the end of the corridor, this drops to 64.8%. This because moving is far less reliable than sensing, so when we move in a straight corridor we begin to lose information. That’s not to say that move can’t add information, though – for example when turning corners (corners are fantastic for localization!).

Thankfully, computers exist to do all this menial computation for us, and to change this from a theoretical learning task to a practical application one, I’ve written this all up in python (3.2). The full code is available on GitHub: https://github.com/ahrensmalte/scibot and you don’t need a robot, gyroscope, or lidar to run it! (the localisation)

A few notes about the code though:

  • The lidar data gathering and interpreting runs in a separate process (not thread) to improve performance – most computers these days have more than one core, so why not use it? This means, however, that all serial communications, and so, need to run in that process, alas the readability and debuggability is somewhat affected. The performance improvements, however, I believe are worthwhile – cutting down time between computation and moving the robot from 1 second to almost instant (it still stutters though because it’s not a continuous map and planning, but discrete)
  • Gyroscope accuracy still leaves something to be desired (even after temperature calibrating it each time the robot is turned on – see sensors.py)

What’s next?

  • Taking the robot into a different (read more complicated) environment and seeing how it handles there
  • Using multiple sensor inputs to provide a more accurate output – for example using both the inbuilt wheel encoders and the gyroscope to measure turns (the gyroscope does not always pick up the start of the turn while the robot is still accelerating (linearly, nor radially) though is very accurate once it is in motion and the wheel encoders which aren’t precise, but do provide a rough guess)
  • Implementing A* (pronounced a star) so that once the probability is above, say, 90% the robot turns around and heads back to it’s ‘home’ location
  • Changing the current binary sensor output (wall-or-not) to a staggered one, which would allow the robot to traverse areas that don’t have at least two walls at each position – this would also allow the grid resolution to increase (the hallway, being 1m wide, was perfect for this basic implementation) so you’d get some more creative paths since there’s more than 9 places where the robot can be
  • Using path smoothing for more…elegant turns
  • Looking at more advanced Mote-Carlo localization implementations, like the ones discussed in this paper from Frank Dellaert, Dieter Fox, Wolfram Burgard, and Sebastian Thrun
  • and of course, an implementation where the robot can be in a completely new environment, and map it. SLAM (Simultaneous Localization And Mapping) comes to mind, though landmark detection is probably going to be the challenge – their’s RANSAC (RANdom SAmple Consensus) and a couple of other landmark detection algorithms

endnote: To CS373 roboticist’s reading this, the process of physically implementing what we learn (this probably applies to all education) adds a whole new level of understanding to what we do in class – I highly recommend it.
and to those you prefer the names Robo, Robert, Robotina, or Robbie (did I spell that right?): sorry, I used the gender equal and more ambiguous (perhaps derogatory though?) name scibot here instead. To those who enjoy playing cards: sorry, I actually do too.



I have an old RC (remote controlled) car lying around, that I got a few years ago. The battery, being Ni-Cd (and not too well treated), is dying so it hasn’t seen much use lately. Earlier in the year, while taking part in Sebastian Thrun’s brilliant Programming a Robotic Car class, I got inspired to build my robot-car. Well, at least a model version.


Where I’m currently at – that RC car controlled via an Arduino.

I saw David Singleton’s Neural-Networks Car, blog.davidsingleton.org/nnrccar, and that’s where I decided to start – converting that old RC car into an Arduino controlled one. The key from David Singleton being, controlling the remote via Arduino rather than directly controlling the car via Arduino (which would probably require some a lot of disassembly of the plastic mold).

After taking apart the plastic shell of the remote, I needed to find how to connect up the Ardiuno. The method I used was:

  1. Find ground (or just use the negative terminal of the battery) and connect one end of a wire there
  2. Look for the switches (forward / back, left / right) on the circuit board
  3. With the car & remote on, begin touching the other end of the wire to parts of the circuit and see what happens

Once you’ve found that connection (you’ll notice that the car begins to move…), that’s (between there and ground) where you’d add the transistor (a transistor is like a tap, with the base being the valve). Setting the Arduino pin (which you connect to the base) to LOW or HIGH then controls whether current can flow through the transistor, in essence, an electronic switch.

After playing around with that for some time, and buying 90cents worth of transistors (the 2N2222A NPN transistor) I was able to get it to work (connecting the Arduino’s ground with the remote’s ground, and having the transistor the right way round, were two things that I learnt in particular).


Image based on Howard Logsdon’s work at wiki.hplogsdon.com/Arduino/. GPL licensed.

Arduino Remote Circuit Diagram
Made with circuitlab.com

(more…)