Wishful Coding

Didn't you ever wish your
computer understood you?

EV3 Sumo Robot

After a long period of silence, I finally made some things with my EV3. Last time the tools where not really ready, but now everything works great.

I used ev3dev and python-ev3 to build this bulldozer. Watching sumo matches at LEGO World, I saw a few things that do and don’t work.

A lot of people seem to go for blades and hammers, but unless you actually want to destroy the robot, they are useless. Treads sound like a good idea, but wheels have more grip in practice. Make sure the wheels don’t fall off. Encased wheels are the best.

The goal is to push the other robot off the table, so the more powered rubber the better. Four wheel drive is better than rear wheel drive, but rear wheel drive is still much better than front wheel drive.

It’s all about pushing. The only useful thing besides pushing forward is pushing up or sideways. Pushing up is the easiest, because you have the floor to back you up. It also pushes the opponent’s wheels off the ground. This lead me to the following design.

[gallery columns=”2” ids=”534,532,533,535”]

I used two pairs of driven rear wheels on a pivot, so even if I’m lifted, all four remain in contact with the ground. They are geared down, which means I’m slow, but powerful. All the weight of the motors and EV3 is directly above the wheel, for maximum grip.

On the front there is a lift arm, using a worm wheel and a very solid construction. I went through several iterations, improving the strength each time. On the first iteration, it was to weak, but its wedge shape still lifted my opponent a little.

The code is quite simple. Push forward. When you reach the edge, turn around. When something hits the bumper, raise the arm.

from ev3 import lego
import time
import select
import os

# Utility for waiting on the motor.
p = select.poll()
callbacks = {}

def poll():
    for fd, mask in p.poll(0):
        os.lseek(fd, 0, os.SEEK_SET)
        state = os.read(fd, 16)
        if state == "idle\n":
            p.unregister(fd)
            os.close(fd)
            callbacks.pop(fd)()

def on_completion(motor, callback):
    fd = os.open(motor.sys_path + '/state', os.O_RDONLY)
    callbacks[fd] = callback
    os.read(fd, 16)
    p.register(fd, select.POLLPRI)

# Initiate all sensors and motors
l = lego.LargeMotor("A")
r = lego.LargeMotor("D")
lift = lego.MediumMotor()

dist = lego.InfraredSensor()
line = lego.ColorSensor()
touch = lego.TouchSensor()

# reset the motors
l.reset()
r.reset()
lift.reset()

try:
    # run forwards
    l.run_forever(100, regulation_mode=False)
    r.run_forever(100, regulation_mode=False)
    # main loop
    while True:
        poll()
        if touch.is_pushed and lift.state == "idle":
            # we hit something, raise the arm!
            lift.run_position_limited(-3000, 1000)
            on_completion(lift, lambda: lift.run_position_limited(0, 1000))
        elif line.reflect < 20 and l.duty_cycle > 0 and r.duty_cycle > 0:
            # we reached the edge, back up and scan for opponent
            l.run_time_limited(1000, -100)
            on_completion(l, lambda: l.run_forever(100))
            r.run_forever(-100)
        elif dist.prox < 50:
            # found opponent, charge!!!
            r.run_forever(100)
            l.run_forever(100)
finally:
    # stop motors and lower arm
    l.stop()
    r.stop()
    lift.run_position_limited(0, 1000)

Constraint Driven Development

I was reflecting on all the fun I’m having with my Arduino GPS system, and found something interesting.

I could have used a Raspi, and have some actual RAM, storage and screen. But by constraining myself to the bare minimum, I created all sorts of wonderful algorithms and hacks.

This is maybe a known thing, but it bears repeating: constraints foster creativity. Writing “a story” is much harder than wiritng “a story about the first brick of the city hall of Amsterdam”. By narrowing down the search space, your brain can do a much more exhaustive search.

An example that comes to mind is LuaJIT. Lua is found in all sorts of places, so a small binary size is a virtue. Someone told me it fits on a floppy, which I found is true.

LuaJIT on a floppy

Consequently, it contains wonderful things like this.

[A recursive backpropagation algorithm with backtracking, employing skip-list lookup and round-robin caching, emitting stack operations on-the-fly for a stack-based interpreter – and all of that in a meager kilobyte? Yep, compilers are a great treasure chest. Throw away your textbooks and read the codebase of a compiler today!]

Once upon a time, Guy Steele set a high tax on special forms (syn-tax, ha, ha…), and consequently invented Scheme. Later, John Shutt thought that wasn’t enough, and invented Kernel. Clojure on the onther hand, is only constrained to be practical.

What is your favourite piece of constrained software? How do you set constraints for yourself?

Published on

Open Hardware GPS Navigator

Arduino GPS

I stumbled upon Open Street Map a few times, and it seemed like a good idea, but when I actually need a map, I reach for Google Maps.

Until it occurred to me it would be great to have GPS navigation on my bicycle. There are a few companies like Garmin that make them, but from what I understand they are not tailored for cyclists.

I thought this would be a fun Arduino project. Buy parts, download map, write code, profit… right? The buying part was easy.

I choose the Mega because it has 8K of SRAM instead of 2K in the Uno. My research showed I’d need it. I did not get the GPS shield because the pins conflict with the TFT shield.

Downloading the map was also easy, but several GB of XML and a few KB of SRAM is not a good match. I decided the right thing to do is to convert the XML to an R-tree and store it in a binary file on the SD card on the back of the TFT shield.

I spent a lot of time learning Rust and R-trees at the same time.

R-trees are fairly intuitive on the surface. It is a tree of rectangles that contain smaller rectangles. So to find nodes within a certain rectangle, you just have to descend in the rectangles that overlap with your query.

To insert a node, you just descend in the node that is the best fit, enlarging it if needed. But at some point the node is full and needs to be split.

Splitting nodes is the hard part, and there are several ways to do it, of varying cost, complexity, and efficiency. How you spit determines how good your tree is. Mine is fairly dumb.

After I had a basic R-tree working, I used Osmosis to load my map data into Postgres, from where I loaded it into my R-tree.

I recursively wrote the bounding box and offsets to child nodes to a file and put it on the SD card in the Mega.

This was an interesting moment where I was developing C and Rust in parallel. The C development had much less friction, a lot of hacks, and many occasions where I drew random pieces of memory to the screen.

After some more hacking and debugging, I had my first map on the screen! Only it took a few minutes to draw.

Studying my code and SdFat revealed a few things:

There where a lot of nodes where it would read each subnode from disk, check its bounds, and backtrack. I figured that if I stored the bounding rectangles on the parent node, I’d have to read a lot less.

SD cards read in blocks of 512 bytes. I made no particular effort to align my nodes. I think this could save some buffering.

So I formatted the SD card (mistake!) and adjusted the file format so that nodes are aligned at 512 blocks and contain the rectangles of their children. The result: It’s even slower! What happened?

I put some millis() in my code, and it turned out that seek() calls where taking over 3 seconds. I googled around and found that most operating systems suck at formatting SD cards.

I reformatted the card with the official utility and seek times magically went down to 500ms. Better, but not good enough.

It turns out that the reason is that at the edge of every cluster(4KB), it needs to read the FAT header where the next cluster is, in case the file is fragmented. (Now you know why defragmenting speeds up your PC)

But knowing that my file is contiguous, I could use a low-level function to read raw blocks. This was a major improvement, and allows maps at low zoom levels to be drawn in under a second.

The current status is that it can draw a map based on your location, show your speed and some other metrics, and zoom in and out. Source code lives here

Published on