This One Time, 71

This one time I was working on evaluating algorithms for solving mazes. On one hand it seems kind of useless and abstracted, and frankly it is, but there are a lot of real world problems that can be treated as mazes — assuming you have a good maze-solving strategy you can apply. Also, this is where my department gets the grant money, and my position specifically (for the next eight months), so, at the very bottom, a job is a job. And if it eventually helps somebody, that’s cool.

A popular old standby is the strategy referred to as “the half-blind leaky rat”, wherein a rat (or a cheap digital cursor representing said rat) follows, say, the left wall, leaving a trail of urine so it can tell if it finds a loop. It is slow, and thorough, and fails on particular kinds of mazes with loops and disconnects. Actual rats are quite a bit smarter, and an upgrade to this algorithm is to just build a physical model of the maze, put the rat at one end, a smear of peanut butter at the other, have the undergrads run fifty trials over the weekend while you go camping, then come back Monday and see what the rat does.

There are all sorts of AI learning systems that save us the trouble of building physical mazes and exercising and feeding otherwise bored and hungry rats, but that’s another project entirely and I don’t get to work on that one. I just got to read their papers and evaluate their results.

And then there are amoebas. Individually, pound for pound, they’re the most vicious predator on earth, stalking through little puddles and streams and flows, engulfing their prey whole and taking them apart for, well, parts. And chemical fuel. But when resources run low, they all Voltron together and form a slime mold, with the ability to ooze around en mass, with distinct tissues and vessel structures for transporting food and waste and reproductive fruiting bodies for distributing spores and — well, it’s all massively creepy. Its like you could dissolve a rat in water and have all the cells go off on their merry hunting ways, but when the water dries up again you get the rat back. Or maybe a handful of smaller rats, if they all ended up split up into separate smaller puddles before things dried up.

And if you take a slime mold and drop on it several pieces of food, each representing by mass the number of people in different towns or neighborhoods, you end up with a network of vessels that would be the perfect, most efficient network of roads or rails or whatever to build for a transportation system. Amoebas are a bit tougher to model because we don’t really understand the Voltroning process at the necessary depth, but trust me when I say people are working on it. Furiously.

But organic systems are creepy and slimy and smelly. Even their digital models. I like the solutions that depend on physical systems and modeling them. For instance, if you build a model maze, watertight except for the entrance and exit, fill it with water, add a little pressure until you get a good flow going, and then inject some dye — all you have to do is look at it and see which way the dye goes.

If modeling a zillion water molecules and pressures and flows sounds about as complex as building an intelligent rat from scratch, you’d be pretty close to right. But the kicker is modeling a single water molecule is pretty simple. Its getting time on a supercomputer that can model a zillion simultaneously that’s the expensive part. Fortunately a number of commercial HVAC companies that built ventilation systems for skyscrapers have some money to spread around to model and test their setups before they spend fifty times the amount to actually build and install the damned things, so the code actually exists. And what counts as a supercomputer these days is getting cheaper and cheaper. In fact, in the basement of my building is a room full of second-hand home game consoles all connected together, and that setup makes a first-generation Cray look like a pocket calculator. For that matter, so does a modern cellphone, but I’m sure you understand what I’m getting at.

It turns out that voltage is even more clever than pressurized water. If you build the actual model, fill it with an easily ionized gas, give the entrance and exit a hefty electrical potential difference, turn off the lights and hit the switch, all the paths that work will glow, with the shortest and best path glowing the brightest. Modeling that is no tougher than modeling water or air flow, assuming you adequately understand the physical and chemical principles of ionization and fluorescence. That’s less useful to the HVAC people, since they also care about side eddies and diffusion and trying to keep carbon dioxide and heat from pooling up and putting workers to sleep in their little cubicles in the afternoons. Or at least the good ones do. But anyway.

As for the problems that you can solve like mazes? That’s most of them. Every choice is a choice of paths to take through a maze, with a starting condition and a desired outcome that would represent the maze’s exit. Everything, at that level, is a series of mazes connected end to end, with the starting condition being where we are now and the end where we’d like to be, from getting a particular candidate elected to survival of the species if particular crises were to crop up. Each choice is a step in a particular direction, and even if it overtly looks like you’re going in the wrong direction, you want to take all the steps that get you to the place where you need to be to get onto the right path out.

But people are rats at worst and amoebas at best, in scenarios like this, and the universe is keyed to work like the mazes that lightning solves best, paths from past to future solved in parallel, with the viable paths determined by a quantum-mechanical sum-over-histories approach, where every possible path is the right path, or at least a right path. And if we’re to survive long term, its a race between those two algorithms.

Our current strategies are working in the short term, but in the long term my money’s on the lightning.


March 12, 2011 · by xalieri · Posted in This One Time  


Leave a Reply