Autolacing Back to the Future shoes

In Back to the Future 2, we were promised autolacing shoes by 2015. I figured I’d do my part and help make it happen.

rsz_1img_9127This video gives a quick demonstration:

And this video goes over it in more detail:


Build your own

Here are the parts that I used:

Nike Air Mag shoes
5v Arduino Pro Mini
USB LiPo charger
Force sense resistor
Motor mount
Motor driver
Shaft coupler
Rotary encoder
The power supply I designed can be found here, but if you don’t want to build that, you can buy something like this which should also work.


Assembly is pretty straightforward. I’m not going to replicate the documentation of each of the components, but basically, you want to use an Xacto knife to carve out a notch in the shoe strap to install the motor, shaft coupler, and encoder. I used 40 lb test fishing line connected from the shoe strap to the motor shaft. This seems to be a good tradeoff between strength and thickness/rigidity of the fishing line. The elastic I used I got from Hobby Lobby, but other craft stores probably have it. I used 3M double sided foam tape to hold all the components down and a little RTV over the wire connections from the button and pressure sensor socket since the 32 gauge wire I used there was getting torn off sometimes. I found that both superglue and 2 part epoxy actually didn’t stick very well to the inside surface of the straps. The rotary encoder is pretty bouncy, and the code does a pretty good job of debouncing, but if you want extra protection, you can add a small low pass filter by putting an RC filter on the input of the encoder to the Arduino.

You can download the Arduino code here.

Commission a pair

If you want a pair of these yourself, the best option is to build your own. However, depending on interest, I might make a few pairs for people who want to just buy a preassembled pair. If you’re interested, fill out this form.

The DSP Behind Bat Echolocation

A couple weeks ago, Dr. Bruce Patterson (the curator of mammals at The Field Museum in Chicago) was kind enough to send me some very high quality recordings of bat vocalizations captured during his recent expedition to Kenya. Bats use a lot of the same DSP techniques that sonar and radar use, and I thought it would be interesting to take a closer look.

Having the original recordings is really useful for doing analysis because I know that they haven’t been shifted down into the human hearing range and they haven’t been resampled or compressed, so all of the original data is there. Bats produce sounds that are anywhere from 14 kHz to over 100 kHz, so that means to collect bat recordings, you need a microphone with a good frequency response at those frequencies and you need to be sampling fast enough to accurately capture it. The files I analyzed were captured at 384 kHz, which means they should be able to unambiguously represent frequencies up to 192 kHz. The files were all uncompressed WAVs and were recorded with microphones that were capable of capturing ultrasonic frequencies.

A note on bat biology

Not all bats echolocate. There are two classes (the correct taxonomic term would be suborders) of bats: microbats and megabats. Microbats (suborder Microchiroptera) are usually the smaller of the two, but there are exceptions. Microbats all use echolocation and have a few morphological differences from megabats, the most important for this discussion being larger ears for their size and smaller eyes. Megabats (suborder Megachiroptera, family Pteropodidae), don’t echolocate, with the exception of one species, Rousettus aegyptiacus.

The bats I got recordings of were Cardioderma cor (the Heart-Nosed bat), Lavia frons (the Yellow Winged bat), Nycteris thebaica (the Egyptian Slit-Faced bat), Rhinolophus clivosus (Geoffroy’s Horseshoe bat), and Rhinolopgus eloquens (the Eloquent Horseshoe bat). Not all bat vocalizations are purely for hunting or localization. There are also social calls, and it’s possible some of the calls seen here have a social component to them, but I focused mainly on hunting and localization calls.

Echolocation in the frequency domain

A naive way to do active sonar is to simply send out a flat, single tone for a fixed amount of time, and then stop transmitting, start counting, and listen for a reflection. Because we know the speed of sound and when we started and stopped transmitting, figuring out the distance is just the speed of sound multiplied by the time the signal took to come back, divided by two. But if we’re clever about the kind of signal we initially transmit, we can significantly improve performance. Bats do this in several ways. For example, different bats use different frequencies depending on their prey and environment. Euderma maculatum chirps at about 12.7 kHz, which is low enough that cannot be heard by moths. To see other examples, let’s dig into some real signals. First, we’ll look at the Heart-Nosed bat. Here’s what it looks like:


These guys have really tall ears that almost look like rabbit ears. Here’s what they sound like when shifted into the human hearing range:

Here’s what their sound looks like:


This spectrogram was generated using Baudline. The Y axis is time and the X axis is frequency. This plot spans about 6 seconds. The calls start off fairly far apart, and then rapidly get close together in what is know as the “terminal buzz”.

Side note: this could also be explained by a Doppler shift, if the bat were flying toward the microphone and chirping at a steady rate. I don’t think that’s what’s happening here though, because the footage I saw of the researchers recording calls all had the bats flying away from them, and the speed needed to achieve a Doppler shift to produce a fake terminal buzz is faster than any bat can fly. There is undoubtedly some Doppler shift in these recordings caused by the movement of the bat relative to the microphone, but it shouldn’t matter much for our purposes.

When a bat approaches an object or prey, it starts sending out calls much faster to help improve accuracy at the expense of range. Also notice that the intensity of the sound decreases a little at the end of this recording. By adjusting how loud each chirp is, the bat can effectively set a limit on how far away he wants to “look”. However, I’m not sure if the intensity decrease here is due to the bat adjusting his volume or the microphone getting further away. To prove to you that it does happen though, listen to this YouTube recording of a bat (unshifted, you’re just hearing the part of his chirps that is below 20 kHz). Listen for the change in volume as well as the terminal buzz:

Let’s go back to our original recording and zoom in a bit:



Notice the spectrum plot at the bottom. The call has quite a large bandwidth of about 76 kHz. For reference, the human voice has a bandwidth of about 3 kHz, and that’s not even the continuous bandwidth.

There’s an interesting artifact in the Heart-Nosed bat call if we take a note from CSI and ZOOM! ENHANCE! If we set the equalization to to an X-curve and adjust the level to -40 dB, as well as use a Kaiser window with beta=5.31, here’s what we see:

zoomed and cleaned


If you look carefully, you can see what looks like a twisting pattern in these signals. Here it is a little closer:


At first, I thought I might be seeing a Doppler shift as the bat flew away from the microphone, but these nulls in the signal move backwards over the course of only a few milliseconds. The resulting speed you get if you do the math is about 25.5 m/s, which is faster than any bat I could find. My other guess was that it may be a feature of the larynx or some other biological structure within the bat that is resonating. But I think it’s actually frequency modulation. To me, it looks like there are three frequency ranges that are shifted downward in the course of about 3 milliseconds. So perhaps the biological structure that produces these vibrations resonates at those three frequencies or there are three different structures that almost overlap, but leave a tiny hole between each range. Frequency modulation like this, where a tone is swept over a range, is known as a chirp. It’s a very specific mathematical definition, and here’s what one sounds like:

As you can see, the Heart-Nosed bat sends out a relatively large bandwidth chirp that lasts for about 3 to 5 milliseconds. The bat then changes how often it sends this chirp out based on how close it thinks it is to its prey or an obstacle. This way, the bat gets more frequent updates on the location and characterization of the object. By sending such a large bandwidth signal, it may be able to identify different insects and objects by listening to how the frequency changes when the echo returns. Some objects may resonate at a particular frequency, causing that frequency to be attenuated in the reflection. By knowing what objects and insects attenuate which frequencies, the bat may be able to identify them.


Taken from “The physics of bat echolocation: Signal processing techniques” by Denny

The plots above show the results of a simulation of echos off of an insect. Each of the four plots represents an insect with different body and wing proportions. You can see that the spectrum changes a lot, even for small physical dimension changes. Bats can use this information to help classify targets. This may also be aided by using simple amplitude return information. For example, a baffle like the leaves of tree may disperse the sound, resulting in a weaker echo. A flat, hard object like the side of a building will reflect really well and return something much closer to the original amplitude.

Let’s look at another bat: the Yellow Winged bat. Here’s what he looks like:


Here’s what he sounds like in the human hearing range:

And here’s what his sound looks like:

buzz again

Recognize the terminal buzz? The Yellow Winged bat has different frequency characteristics than his Heart-Nosed relative, however. The Yellow Winged bat has a bandwidth of about 55 kHz that spans from ~33 kHz to ~88 kHz in this recording. The Heart-Nosed bat has a bandwidth of about 74 kHz that spans from ~38.5 kHz to ~112.5 kHz. The chirps on both bats last for about the same amount of time, 5 ms. As far as we know, all bats of the same species have the same chirps, and most species have their own chirps, but you can’t always identify a bat based solely on its chirps. The Yellow Winged bat chirp has a lot in common with the Heart-Nosed bat though. Both signals have a large bandwidth and don’t appear to change bands over time. Let’s look at one more bat that has this same structure, the Egyptian Slit-Nosed bat:


That’s a rather dramatic picture, but his sounds look familiar:


Notice that the chirps are shifted up from the Yellow Winged bat and closer to the Heart-Nosed bat. These chirps span from 64 kHz to 186 kHz, and are 122 kHz wide (although there are components that go up even higher until they’re limited at 192 kHz because of the sample rate). This bat’s chirps also have the same unusual frequency shifting artifacts:


Alright, now let’s look at my favorite bat chirps from the Rhinolophus family. First, Geoffroy’s Horseshoe bat.



Their sounds look totally different!


This bat is using two techniques. First of all, notice that the chirps are produced in groups, rather than one at a time. In each chirp, there is one fundamental frequency at about 100 kHz, then another one at about 50 kHz, and two more above it at 150 kHz and 182 kHz. Let’s look at the structure more closely.

Untitled presentation (1)

First, a frequency modulated signal is produced, followed by a continuous frequency, and then another frequency modulated signal. A single, continuous frequency helps the bat determine the velocity of the object it’s tracking, as well as whether or not the object has wings. If a moth is flying away from the bat, the echos that reflect off of it will be Doppler shifted down, meanings that the bat will hear his call echo back at a lower pitch. Additionally, the fluttering wings of moths and other insects will cause small amplitude changes and Doppler shifts that the bat can use to help identify the object. 0If a bat is tracking a particularly fast moving object, the resulting Doppler shift may be so large that it lands outside of the bat’s hearing range. To combat this, bats that use continuous frequencies are able to change the pitch their initial chirp to ensure that the shifted returning echo stays within their hearing range. The other advantage to using continuous frequencies is increased range. Notice that the duration of continuous frequency calls are much longer than the frequency modulated calls. A longer duration followed by a longer listening period means that there is more time for echos from further away objects to come back. If the initial chirp was frequency modulated, the returning Doppler shifted echo might overlap the transmitting frequencies, but if all the energy of the call is concentrated in a single narrow band, there’s a lower chance that the returning echo will overlap the initial frequency. Because the continuous frequency technique is ideal for greater range, bats tend to use it when they are flying or perching in open, clutter free environments.

A frequency modulated signal has its own advantages. Because the bat can correlate frequency as well as simple reflection time, the spacial resolution is much better than simple continuous frequency methods. One experiment showed that bats using frequency modulation can distinguish two objects as close together as half a millimeter! Additional harmonics in the call can improve this even further. One disadvantage of frequency modulation is that the effective range of detectable objects is much shorter. This is in part because the energy of the call is spread out over a larger frequency range.

There are some bats that use only continuous frequency, and some that use only frequency modulation, but bats in the Rhinolophus family like Geoffrey’s Horseshoe bat use both. This is one of the most complex biosonars that we know of.

Let’s look at another species of Rhinolophus, the Eloquent Horseshoe bat.




You can see that this species uses more harmonics than Geoffrey’s Horseshoe bat, and the primary frequencies are different. There are some other interesting artifacts if we zoom in closer.

fm 2

This is the spectrum for the CF part of the call, and here’s the spectrum for the first FM chirp:

top spec


And here’s the spectrum for the bottom FM call:

bottom spec
The waveform looks like it’s got lots of other continuous frequency harmonics. I’m not sure what those are from. It may have something to do with the resonating properties of the biological mechanism that creates these sounds. They don’t look strong enough to be used for improving localization, but I could be wrong. I spotted another unusual artifact in this same species:


Here you can see harmonics more clearly as well as shorter, weaker, and more periodic CF pulses. For comparison, here’s what a clean chirp from this species looks like:

less weird, less top fm

Signal Processing Anatomy

Most bat ears have fairly similar anatomy to human ears. There are a few special differences though. Some species have muscles in their inner ear that tighten during chirping to decouple the eardrum, preventing the bat from damaging its own ears. Bats in the Rhinolophus family, like the last two bats we looked at, have different structures for handling the continuous frequency part of their calls.The basilar membrane is a thin structure that runs along the cochlea and resonates with incident sound waves. Human ears have this membrane too, and it’s part of what determines which frequencies we are most sensitive too. Rhinolophus bats have a basilar membrane that is much larger in areas that correspond to about 83 kHz, which is the frequency at which the bat calls.

The auditory cortex of the bat brain is highly sensitive to time. Bats can distinguish sounds that are as close as 500 ns apart. The neurons in this part of the brain retain their sensitivity to time even as the intensity of the signal changes, a behavior that is not seen in non-echolocating animals. This is possible because the interneurons in the auditory cortex will only fire one or two action potentials when stimulated. They also have a very low activation threshold, meaning they can continue to function even the presence of weak signals. Bats with FM calls have neurons that are tuned for specific frequencies within the frequency shift. What’s really cool is that those neurons are mapped to a grid within the bat’s brain. Each row is a frequency and each column in a time (see Nobuo Suga’s work if you want more detail on this). This same structure also exists in bats that use continuous frequency calls.

A mathematical perspective

A number of biologists believe that bats may use a technique called coherent cross-correlation. If correct, it would mean that bats use the phase of the sound waves to continually compare the signal they are hearing with the signal they are creating. The latest research suggests that bats don’t use coherence, but they do use cross-correlation. To see how this works, let’s first examine the FM chirp in eloquens and clivosas, the two Horseshoe bats. These chirps use hyperbolic frequency modulation. It can be modeled as:


where Q is the inverse of the fractional bandwidth. So why don’t bats use linear frequency modulation? Because a Doppler shifted hyperbolic frequency modulated signal has the same form as the original (this isn’t true for linear FM). This makes cross-correlation much easier.


Taken from “The physics of bat echolocation: Signal processing techniques” by Denny

Plot “a” shows the time domain waveform of an original chirp. Plot “b” shows the time domain echo after being Doppler shifted. Plot “c” shows the frequency domain version of the original linear FM signal and the echo. Notice how the echo has been delayed and the slope has changed. Plot “d’ shows the frequency domain of a hyperbolic FM signal along with the echo. The signal is shifted again, but this time it’s shifted along the same curve, which makes cross-correlation much more effective.

Cross-correlation is defined as


If that reminds you of convolution, there’s a reason for that. Convolution is defined as


Wikipedia has a nice diagram visually explaining these two functions.


Both of these functions are essentially summing up the area under the intersection of two functions as they slide by each other. In the case of cross-correlation, when the two functions match, the cross-correlation is maximized. That’s why it’s so important that the echo of the original signal have a similar structure to the original, hence the use of hyperbolic FM.

Echolocation Jamming

Believe it or not, echolocation countermeasures are practiced in the wild. One species of Tiger moth, Bertholdia trigona, produces its own ultrasonic clicks in the same band as its predator, preventing the bat from discerning between echos and tones generated by the moth. Here’s what it looks like:


Taken from “How do tiger moths jam bat sonar?” by Corcoran et al.

This same technique has been used in electronic countermeasure systems for radar and sonar. Other moths simply produce ultrasonic tones as a sort of sonic equivalent to bright markings on their wings, designed to warn their bat predators that they won’t taste very good. But just as in warfare, electronic counter-countermeasures exist, which are designed to resist jamming attempts. Some species of bats can shift their chirping frequency in response to noise. This switch can take place almost instantly. Despite these countermeasures, Bertholdia trigona has been shown to have an almost 10x higher survival rate than other moths, proving how effective even simple jamming techniques can be.

Bat Beamsteering

Bats can use interference patterns and multipath effects to determine elevation. If you’d like a deeper look at the math, I highly recommend The Physics of Bat Echolocation. Additionally, many bats appear to be able to focus their ultrasonic emissions using complex baffles on their faces.


These shapes have a beamforming effect and are thought to increase the ability of the bat to resolve prey. Some work has been done in 3D modeling and simulating the effect of these baffles, but there is still a lot of interesting work to be done. There is a huge amount of diversity in bats, and that includes the various ear and nose shapes. Here’s a selection of different bat ears and noses:




And here are the various -3 dB contour maps for some different ears. Frequency is encoded by shading: lower frequencies are darker.




These images are from this paper, which I recommend if you’d like more detail.

Bats are amazing

There are people who spend their entire career doing this kind of analysis, and this is just the tip of the iceberg. There’s so much we have to learn about life on our planet. If you want to dig into more detail, check out the links below. They give a lot more information about both the biological side of things and the mathematical/signal processing side of things. I’m grateful to Dr. Patterson and Dr. Webala for collecting and sending me the bat vocalization recordings that got me into all of this. And thanks to The Field Museum and Emily Graslie for setting up the Bats of Kenya event in the first place!

Further Reading

University of Oregon echolocation notes

MIT Lincoln Lab echolocation/sonar report

The physics of bat echolocation: Signal processing techniques

How do tiger moths jam bat sonar?

Bat Species Identification

How to tell if your UI sucks

There’s a really quick, fairly objective way to tell if your UI sucks. Google:

win7 win8

It’s clear that more people are having trouble with more fundamental problems in Windows 8 than in Windows 7. Closing apps, shutting down, and finding programs are pretty central tasks in day to day computer. Over time, these autocomplete suggetions will change, but for now it’s clear that a lot of people using Windows 8 don’t know how to do the tasks they are familiar with in Windows 7.

Tiny Parts

I made a quick video last week about some 01005 resistors I got. I was able to make a little “adapter” by soldering a 1/4 watt resistor lead to each side of the 01005 part. This video is mostly interesting if you’ve never seen parts this small before.

Your Game of Life

John Conway made up the rules for the game of life by fiddling around until it looked good. Why not make your own game of life and change the rules?

Your Game of Life

For the unfamiliar, Conway’s Game of Life is a cellular automaton. It’s pretty neat and you should read the Wikipedia article on it. The original game has 4 very specific rules that were formulated by John Conway. After watching the video above, I wondered what it would look like if you changed those rules. My implementation was forked from steelerose. I pretty much just stripped it down and added the ability to adjust the constants that govern behavior. If you want to mess with it, you can check out the code here.

A friend of mine linked me to this neat article on the edge of chaos which I think is relevant.

Interesting Technical PDF Roulette

I read a lot, but I don’t always have time to read an article or paper as soon as I come across it. Instead, I add it to a folder in my Dropbox called “To Read”. Once I read something that’s in there, I move it to my “Already Read” folder, in case I want to search for it again. One trick I like to use is instead of bookmarking a site that I want to read later, I print it to a PDF and save it in my “To Read” folder for later. That way if the site goes offline or gets buried in a pile of bookmarks, I won’t lose it. Last night I thought it would be fun to make Interesting Technical PDF Roulette. I moved all of the PDFs in my “Already Read” and “To Read” folders into a directory on my server and wrote a simple page to serve you a random PDF from that directory. If you want to check it out, it’s here. I’ll be updating the list as time goes on. I also didn’t read protect the directory that they’re in, so if you want to wget them all, that’s fine, but if the bandwidth is really terrible, that probably means someone else is doing the same thing, so please be kind and try again later.

What a Soviet spacecraft on Venus can teach you about failure

The 1960’s and 70’s were a frenzied time for spacecraft engineering. It was a field that had just been invented, and putting machines into a new extremely harsh environment required new methods, materials, and tools, and no one had very much experience. The Space Race was in full swing as the US and USSR rushed to get things launched both to assert their country’s dominance, and as a reaction to the possibility that the other might be developing a space warfare capability. [Read more]


What would it take to build a “Pacific Rim” robot?

Disclaimer: I don’t work for any company involved in Pacific Rim, I just think robots are cool.

If you haven’t seen the trailer for Pacific Rim, check it out here:

My friend John wanted to know a little more about what it would take to make one for real.


So what would it take to build one for real? Well, according to these stats, the robots in the movie are around 250-280 feet tall. The closest real life analog to that is probably a Virginia class nuclear submarine. A nuclear submarine is slightly longer, but it’s got a similar density of material and technical sophistication that a giant robot might have. This should give you an idea of the scale (those are people standing on the top there):


According to the released “schematics” from the movie studio, the robots are powered with a nuclear vortex turbine and the actuators are hydraulic. I’m not sure what a nuclear vortex turbine is, but driving hydraulic actuators with a nuclear reactor isn’t totally implausible. One of the tricks in building a humanoid robot is having REALLY powerful actuators, specifically a large amount of torque. With robots at this scale, limbs will be very heavy and need a lot of torque just to hold still, let alone fight giant monsters. A Virginia class submarine costs $2.6 billion to build (in 2012 dollars). I think a Pacific Rim robot would cost slightly less because it’s a bit smaller and has a smaller armament. Most other things would be surprisingly similar though. It would have similar armor, radar, and communications equipment. And of course, it would have a similar compact nuclear reactor. The S9G reactor onboard a Virginia class submarine can output 29.8 MW and deliver 40,000 shaft horsepower, which would probably be enough to power a Pacific Rim robot.

Now, we’re getting pretty good at building humanoid robots, but it’s very hard to do. Some of humanity’s best humanoid robots so far include Hubo, Petman, Asimo, and the recently revealed Atlas. Walking is hard. It’s not until you’ve tried to make a robot walk that you realize how good humans are at it. I experienced this while working on the DARPA Virtual Robotics Challenge at Georgia Tech. Georgia Tech also has a real humanoid robot performing the DRC tasks (which include turning a valve, smashing down a wall, clearing rubble, using a drill, driving a car, opening a door, and lots of other hard tasks). Unfortunately, I can’t talk about the work being done just yet. Anyway, there are a couple of ways to make a robot walk. One way is using something called ZMP walking. ZMP stands for zero moment point. To make a robot stand up, its center of mass must be within its polygon of support, which is an imaginary 2D plane that ensures there robot remains statically stable. Once the robot starts moving, the challenge is to find a set of trajectories that keeps the robot from losing its balance and falling over. A similar problem in this space is the inverted pendulum problem. The zero moment point is the point where the foot hitting the ground does not produce any horizontal moment and the sum of the vertical inertia and gravity is zero. This is only part of the problem though: you also have to have a path planner that decides where the feet should attempt to land and thus what direction it should walk as well as inverse kinematics (either numeric or analytical) to figure out how to position the actuators in the leg to get the foot to that point. You also will typically have lots of sensors and a feedback loop to be able to take into account external disturbances to the system like an uneven ground or something hitting your robot. After all of that, you end up with a ZMP walk that looks something like this:

You’ll notice his walking looks extremely, well, robotic. Compare it to another form of robot walking, passive dynamic walking:

That looks much more human. While terribly named, passive dynamic walking can be done without active power. In the video, the robot is being pushed by the engineer which provides it with the energy to walk. Theo Jansen’s Strandbeests are another example of a passive dynamic walker. Real human walking has a component of this to it, as the leg swings rather than remain continuously driven by muscles. However, ZMP walking can look pretty lifelike, as PETMAN shows.

The walking in Pacific Rim looks pretty human like, and we’re meant to believe that walking is teleoperated by the drivers in the head of the robot. Teleoperating the robot with haptic feedback is a pretty cool idea and it’s been done before. However, directly controlling walking like they show in the movie wouldn’t work because the polygon of support and ZMP would be different for a person and the robot since they’re different sizes and densities and have limbs of different lengths. However, there’s still a way it could work. If the teleoperation rig in the head of the robot was only using the human’s legs to determine relative parameters of the ZMP walking algorithm, you would get a similar effect to directly controlling the legs. A ZMP walking algorithm can take in parameters like stride length, duration, and height. By mapping those relative parameters from the operator to the robot, the robot would walk in sync with the operator. According to the movie, there is a brain interface to the robot which is too heavy for a single person, so there are two pilots, one for each brain hemisphere. There’s a great article over at IEEE on how that might work.

To actually construct a Pacific Rim robot, the Vehicle Assembly Building at Kennedy Space Center would be a good spot to put it together. It’s plenty large enough (maybe even big enough for a couple) and has all the necessary cranes and scaffolding as well as doors big enough to get it out once it’s put together.


How long would it take to build? Well, a Virginia class submarine takes 9 million man hours to build over 6 years. It also takes 134 people to crew it and control all of the complicated systems to make the submarine function. I think it’s likely that a Pacific Rim robot would require a mission control of a couple people to watch and control other vital systems that the two pilots of the robot couldn’t.

Cost: $1.8 billion
Total construction time: 5 years
Crew: 2 pilots, 5 remote mission controllers