Ant colony optimization
Image Source: Wikipedia
I’ve been looking at ant-algorithms for pathfinding lately. They’re interesting because they are very simple multi-agent search, but some of the benefits that I originally thought it might have (dealing with imperfect last-known-information, dynamic environment, etc.) seem to be negated by the fact that it isn’t terribly great when you don’t have a ton of agents.
I’ll have a more concrete idea of how feasible ant-algorithms are once my implementations are done and I can run simulations. Never hurts to separate the hype from the substance, though.
Update (2011-12-31): We ended up implementing some various pathfinding mechanisms for many-agent movement in a semi-unknown environment. Turns out that ant colony optimization is actually not so great… at least in the classic “pathfinding” sense. Convergence is slow, the actual amount of shared information is weak, etc. The test program is at least pretty, thanks to wxPython. The settings are all at the top of the Python script, and a little arcane, but you can run it with
You can download the program here: sim.py