On robot maps

Warning: this post kind of meanders. It's useful for me to have a brain dump, though.

Last year I took Udacity's Intro to Self-Driving Cars nanodegree, which was a lot of fun but it has a few downsides. The biggest is that you're ultimately just writing programs that show some text on a screen and whatnot, and the problems, while not trivial, weren't really that hard. We didn't have to implement (or ever use) a Kalman filter, for example; it's hard to make things stick when you're not really applying them... I did keep a pretty good notebook though, and that's been helpful.

We tended to model the world as a 2D matrix; there was one matrix for probabilities of obstacles, for example, and one for position. For each of these, there was some current matrix and an update matrix. Lots of matrices.

I've had the itch to start building small autonomous robots again; now that I have a decent base platform to work with [1] (though I'm still figuring out how to integrate an ARM controller into the stack), I've been able to start thinking about navigation.

For whatever reason, when I've thought about this before, I thought about it like one would think of topo maps: there's some absolute grid in the world (more or less), and the goal is to place oneself on this fixed grid. I struggled a bit thinking about how to go about this, how to represent this. It turns out I've had a wrong mental model for approaching this.

Then I started thinking about a grid centred on the robot: when the robot moves, the grid is shifted in the appropriate position. I'm using ultrasonic sensors with a maximum range of 400 cm, so maybe an 800x800 grid to keep some space around where we've been in the past? I'm just sort of picking a number and running with it, but 2x the sensor range and keeping the same units as the sensors. Okay 800x800, but consider the memory constraints of the different brains that I've got available:

Controller RAM (bytes)
Uno 2048
SAMD21 32K
Teensy 3.2 256K
Teensy 3.6 256K
SAMD51 192/256K
Pi Zero W 512M
Pi 3B+ 1024M

Some neurons started firing, and so I started thinking about grid resolutions and sizes. Since the grid is going to be a map of probabilities of where I think obstacles are, my instinct is to use doubles - that's what we used in SDC course. Let's look at some options.

Side # cells as grid of doubles Notes
800 640000 4.88 MB cm resolution, 2x sensor range
400 160000 1.28 MB cm resolution, sensor range
40 1600 12800 B dm resolution, sensor range

So it's obvious pretty quickly that the 800x800 grid isn't going to work, especially not given that I have an AVR board right now. The first thing I did was started looking at ways to implement more efficient, compact grids, which I sort of started doing while making dinner last night. This led down a rabbit hole of interesting paper titles (unfortunately, I haven't had time to read any of them yet).

I had another pair of realisations this morning:

  1. It would help to reconsider my data types: I could use floats (I'm not sure that I need the precision of doubles) which means a 50% reduction in data size). I could also use an int8_t: +/- 100, expressed as a percentage. Not ideal, but I could make it work.
  2. It had been an unspoken assumption in my mind that the grid would be centimetre resolution. But, does it need to be? By scaling down by a factor of 10, e.g. decimetre scale, the grid now takes 1% of the space. Considering that the robot's chassis has a footprint of roughly 29 x 15.5 cm, that means the error is less than the width of the robot. Given that I have cheap sensors and an inexpensive IMU, that seems pretty reasonable. In fact, I think that provides a good buffer space for avoiding things in my house :).

Still, we're hitting pretty tight memory constraints for the Uno. I'm still trying to figure out how to power the Redboard Turbo I have with my current setup. My power distribution board would fix some of these issues, but I also want to build a general purpose navboard.

The first version of this will probably be an Arduino shield that provides a seat for an MPU-9250 IMU and BME280 atmospheric sensor, some connections for a number of HC-SR04s, and possibly a GPS; at first, I would just do everything on this.

However, I still like the idea of a navboard. Ideally this would be exported as an I2C or SPI device; this way, I could swing a serial GPS and the nav system could be set up as standardish peripheral. I've never build an I2C slave or SPI device, and I have only a little experience working with SPI. I'm still thinking about interfaces:

  • If I built this as a Redboard Turbo-based ROS node attached to a Raspberry Pi, I could just constantly send a bunch of messages with sensor data. It kind of breaks some of my ideas about wanting to componentize everything, but it'd be useful.
  • Maybe it'd be possible to keep the worldview on the navboard. How would the robot interact with the grid? SD cards export a file system, this could provide some sort of memory interface that lets the robot look at things that way. Maybe? Right now, processors read some data from the SD card into memory, but that means the data is duplicated twice. I don't have any good ideas about that, except that maybe it's not a bad thing. I could support reads and what not, and maybe allow the robot to incorporate some other knowledge to update the map. But then the two need to be kept in sync.

So how big of a grid can I fit on the Redboard Turbo? I'll try to ballpark it, playing fast and loose with the numbers and erring on the conservative side. The Redboard Turbo has 32K of memory; if 50% of that is allocated to the grid, that leaves space for 4,096 floats. That's one 64x64 grid. A pair of 40x40 grids (current and next) takes 12,800 bytes, which is just about 40% of the total memory available, leaving 19968 bytes. Is that enough to do a Kalman filtering, too? The IMU will need at least 36 bytes (9 float measurements), plus possibly overhead for calibration data. Let's be generous and say 128B for any data structure usage. What about the GPS? In the featherlib project, I defined a GPS position structure that takes up 17 bytes. Let's round up to 32B to account for some private data, and add 80 to account for the NMEA sentence storage. That's another 112B. The BME280 needs floats for altitude, pressure, and temperature, and 9 configuration bytes. So that's 21 bytes, let's call it 32B. I also want to support 8x HC-SR04, which adds roughly 10B per sensor, so 80B total for all sensors.

Object Memory Total
Grids 12800 12800
IMU 128 12928
GPS 112 13040
BME280 32 13072
HCSR04 80 13152

Adding all of that up brings the total to still under half the memory usage; an overhead of 3232B brings the memory usage up to 50%. Which again leaves a lot of room to wiggle. The IMU could keep a history of states, which might be useful. Okay, this seems tenable - granted I don't know what I'm doing yet.

I debated the GPS, but I think it'd be useful for providing an absolute position for something like A*, combined with the IMU. Most of them support a standby mode that could be activated when it's not being used, so it shouldn't be too big of a drain on the battery.

I need to read a lot more on this. There's a ton of stuff and it kind of makes me wish I had stayed in school. Another thing is that I was reading up on some other stuff, and I think the ideas I had about Out of Control style robotics are represented by the idea of a subsumption architecture (though MIBE sounds similar too). The point is, there's a lot of people doing stuff like this and there's a lot of stuff I could learn from reading and applying them to what I'm building [2].

[2]If I ever find the time.