I swear it was a coincidence that I was reading On Trails just at the moment when my dad and I road-tripped a small moving truck from Florida to Colorado (go Penske). But it did make for some interesting connections. While it opens and closes with discussions of the Appalachian Trail and the International AT, this isn’t a “hiking” book. The central thesis (at least to my reading) is that trails act as “social memory” — helping groups from insects to people share knowledge and history.
Moor also ponders the connectedness of trails; continuous journeys through an environment, vs the “nodes and desire lines” of point-to-point travel, typically by air. That certainly registered during the trip with my dad. In a single day I teleported from Seattle through Charlotte (although it could have been anywhere) to Fort Meyers. Over the next four I glided across the United States in one continuous motion, seeing the gradual changes from swamps to horse country and low forests, up and down the Appalachians and onto the prairies. So much prairie! I love driving through the wide open skies and horizons of Kansas. Then suddenly the Rockies just show up out of nowhere, dropping me at the foothills of Boulder.
It never ceases to amaze me that there are continuous ribbons of asphalt that cover thousands and thousands of miles. If I just start driving, I can go from the Pacific to the Atlantic with my tires never touching anything but I-90. There is nothing so awesome as a highway road trip (with adaptive cruise control of course).
Ants
Anyways, let’s do a little nerd stuff. Towards the beginning of the book, On Trails describes stigmergy, a form of self-organization that uses modifications of the physical environment to coordinate individuals.
Ants are a great example. Brave ant souls leave their colony to explore randomly for food. When they find it, they return to the colony, leaving behind a chemical pheromone that serves as a trail for other (less adventurous) ants.
Amazingly, most ants use dead reckoning to remember how to get home — they literally count steps to measure distance and interpret the polarization of sun (or moon) light to remember cardinal direction. Some species supplement these by tracking the velocity of objects in visual range, or sensing changes to the Earth’s magnetic field. Still others leave behind a secondary, weaker pheromone like Hansel and Gretel.
These simple actions — Look for food! Leave a trail! Go home! — add up to some pretty striking colony-level behavior, so I thought it’d be fun to do some simulations. Plenty of folks have done this already, and surely more elegantly than I. But it’s my site and I love to write code, so let’s get nerdy.
AntWorld
My ants and the environment they inhabit are described in AntWorld.java. If you’ve got git, maven and a reasonably up-to-date JDK you can run it yourself:
git clone https://github.com/seanno/shutdownhook.git
cd shutdownhook/toolbox
mvn clean package install
cd ../ants
mvn clean package
java -cp target/ants-1.0-SNAPSHOT.jar com.shutdownhook.ants.App ants 400 config.json ants.htm
All this will result in a file ants.htm on your local machine. Open that file in a browser and you’ll see something like this (not exact because the configuration is set to use a new random seed each time it runs); click the image for an animated view:
- Red represents the ant colony.
- Blue denotes randomly-placed food caches.
- Black ants leave the colony to explore for food.
- Ants that find food return to the colony, leaving behind a trail of green pheromone.
- Ants that hit the edge of the world return to the colony without leaving a trail.
- Pheromone trails decay over time.
- Food is consumed as ants discover it.
In mine, the first cache is found in the eastern part of the environment around cycle 35. Just as that cache is fully consumed, a second is found in the western side — but it gets lost around cycle 150 because the strong “leftover” eastern trail is just too attractive. After that trail decays, the second cache is re-discovered around cycle 200, pulling more ants towards the west. From there they find the third and fourth caches pretty quickly.
Each run provides a new dramatic twist, and tweaking parameters is pretty addictive. For example, a dense colony (100 ants) can obviously flood the environment quickly, but even a sparse colony (just 10 ants) is pretty successful.
The Details: Exploration
Little details make a huge difference in this kind of simulation. Check out the code that handles “exploration” mode. In my first version, explorers really did just pick a random direction with each step. But this didn’t look or feel “real” at all. Eventually I ended up with these rules:
- If there is food directly adjacent to the ant, go there. This makes sense — an ant can certainly see or smell food in their immediate vicinity; they’re not going to randomly turn away from that.
- Travel has “inertia.” An ant moving in one direction isn’t likely to just pull a one-eighty for no reason, so it chooses from previous last direction or one step to either side. For example, an ant that travelled east in the last cycle will choose east, northeast, or southeast.
- The choice of the three directions is weighted by the amount of pheromone in each direction — ants strongly prefer to travel along pheromone trails.
Another dynamic that’s not immediately obvious is “giving up.” Ants in the real world stay within a certain distance from the colony — they don’t just explore infinitely. I was able to approximate this failure mode by detecting collision with the edge of the world.
The Details: Pheromone Trails
The concept here is pretty straightforward: when an ant discovers food, they return to the colony, leaving behind a chemical pheromone trail that other ants use to get to the same food source. But there needs to be some balance between following known trails and breaking new ones. And since food sources are exhausted over time, the pheromone needs to decay, or ants would keep returning to an empty cache forever.
The configuration values “AntReturningPheromone,” “LocationPheromoneMax” and “LocationPheromoneDecay” fine-tune this behavior — this run shows how imbalance (pheromone too strong) can sabotage a colony’s ability to effectively leverage its envoironment.
Another interesting side effect of the current implementation is “exploration spillover.” Watch what happens around cycle 125 of this run. Large numbers of ants are moving back and forth between the colony and the food cache. Eventually the food is depleted, but there are still a bunch of ants travelling along the path. When ants hit the empty food cache, they “spill over” the end of the trail, causing a surge of exploration in the local area.
Does this behavior track the real world? Not really — apparently while frustrated ants do conduct a “brief local search” to be sure there aren’t leftovers to be found, mostly they return back to the colony emptyhanded without dropping pheromone.
I haven’t bothered to fix this — it doesn’t matter for my purposes. But it does illustrate just how complex even the simplest things in the real world, really are.
A Brief Lesson for the Enterprise
This post is about trails and ants, not enterprise software. But it seems like there is always a lesson to be learned, and today that lesson is “honor your history,” aka “everything exists for a reason.” My first implementation of AntWorld was crisp, concise and elegant. But it didn’t work at all. It took a ton of trial and error, multiple literature reviews, parameter tweaks and dead ends before I got to the current state.
The software in your enterprise almost certainly has a similar pedigree. At first glance it seems overly complicated and filled with special cases. But those cases are there for a reason — think really, really hard before starting over with that alluring “clean slate.”
Anyways
That’s plenty for today. A great book, a fun coding challenge and a bunch of neat visualizations to play with. And it’s sunny outside — things don’t get much better than that. Until next time!