Monday, March 3, 2008

Good Enough For Government Work

This might be a surprise if you've read my post on pragmatism, The Attitude of the Knife, but I'm actually an idealist. I don't want things to be good enough; I want them to be perfect, or at least as perfect as pragmatically possible. I use the attitude of the knife to temper my idealism.

Of course, there is tension between idealism and pragmatism when encountering very difficult problems. I don't just mean, "you'll have to be really smart to solve this problem." I mean, "it's mathematically impossible to solve this problem using the computer you have access to." The idealist wants 100% and the pragmatist wants 99% or even just 90%.

The classic example of a mathematically difficult problem is the Traveling Salesman Problem. If you're not familiar with the problem, it works like this: Suppose you have a salesman who wants to visit every city in a certain area exactly once, and he knows the distance between each pair of cities. What's the minimum distance he'll have to travel to visit all the cities and how do you determine it?

Mathematicians have been studying this problem for almost 200 years now. It turns out that determining the perfect solution is really, really hard, but it's possible. Worst case you can just check every possible ordering of cities. That worst case is unbelievably bad, however. If the salesman had 30 cities to visit and a computer could test one trillion options per second (current no single computer exists that is this fast), testing all these options would take much longer than the current age of the universe. Most of the studying mathematicians have done on this problem revolves around ways to get a "pretty good" answer without spending billions of years to do so.

I say I'm an idealist, which means I want things to be perfect. But I'm also ruthlessly pragmatic. These contrasting ideals intersect on the definition of perfect. If it takes 1 trillion years to find the traveling salesman route that takes 38 days but 1 hour to find the route that takes 42 days, then the 38 day solution isn't perfect. It's really 1 trillion years plus 38 days, which is definitively worse than 42 days, 1 hour. A "perfect" solution must take into account the constraints surrounding the problem and not just the problem itself. The mathematically optimal solution is not the perfect solution expressly because it's not practical enough to use.

What does this have to do with Artificial Intelligence, and specifically item pickup? Deciding what items to pickup is very similar to solving the traveling salesman problem, and that's bad news for me as the AI designer! If there are 20 items on a level, a bot wants to pickup between 0 and 20 different items on the way to its final destination. That's similar to a traveling salesman wanting to visit exactly 20 different cities. And since BrainWorks bots can't spend several trillion years to decide what items they're going to pickup, their item pickup code cuts a lot of corners to get a pretty good solution in a reasonable amount of time. This isn't the mathematically optimal solution, but it is a better choice overall.

Here are some of the tricks BrainWorks uses to reduce the computation time:
  • Nearby items are grouped into a single cluster. Bots consider picking up the entire cluster at once. This reduces the effective number of things to consider.
  • Bots do not consider picking up more than four items at once before going to their final goal.
  • Bots only consider picking up the dozen or so items that are relatively near their current position, or not far off the path to their destination.
  • When the bot is very near an item (less than a second away), it automatically picks it up rather than doing a full computation.
These changes have a profound effect on the size of the search. Suppose a level with 40 items gets bound into 25 clusters and the bots never consider more than 4 total pickups from the 12 nearest items. Each item pickup decision require testing at most 800 options, rather than more possibilities than there are people on planet Earth.

It's rare that thinking 10 item pickups ahead would really help the bot more than the first two or three choices. And usually the bot doesn't want to travel halfway across the map to pickup some random item. Only the nearby items are worth considering. For the one or two items that really might be that good, the bot specifically notes these items and includes them in the list of possible pickups, no matter how far away they might be. And as it turns out, these results are still "very good". Often the theoretically best solution isn't the best for the problem at hand. If you idealize the results and not the method, being idealistic involves selecting the most pragmatic solution.

2 comments:

Anonymous said...

Not a coder myself, just a mapper, but I love reading your stuff. Explains everything in simple terms. Keep it up.

Ted Vessenes said...

Glad you appreciate it. It's hard work explaining such complicated concepts to such a wide audience, and it's great to hear that it's worth it.