Monday, November 30, 2009

AI for real life: The perfect is the enemy of the good

I have seen that searching for a perfect solution is much harder than searching for a good solution. My experience is based on AI planning. You have to find a path from a start to a goal there. A perfect solution would find the shortest path.

If you need the shortest path, you have to examine all promising paths. You cannot skip a path that could be possibly shorter than the currently best known solution.

If a good solution is enough, you have more possibilities how to find the solution. For example, you could stop the search when no promising path would be X-times better. You could also be more realistic about the promising paths. It is OK to over-estimate the length of a path. That would postpone the path for later examination. A good enough solution could be found in the meantime.

The hardness of the search is seen on the International Planning Competition 2008. They have two tracks:

  • The "satisficing track" is for planners searching a good solution.
  • The "optimization track" is for cost-optimal planners. They are searching only for the perfect solution.

The competition uses much larger problems for the satisficing planners. The cost-optimal planners would not be able to solve the same problems in the given time.

It is also interesting that no cost-optimal planner was better than a basic breadth-first search. The breadth-first search was used as the "baseline" for the "optimization track". A planner would need prior knowledge, to carefully estimate the lengths of the paths. Otherwise it is not faster than doing the walk.

Additional reading

The prior knowledge could be, for example, knowledge of solutions to easier problems. You then know that the harder problem will take at least the same number of steps: Hierarchical A*: Searching Abstraction Hierarchies Efficiently

Saturday, November 28, 2009

Face detection that just works

I may be the last man who noticed this. My new camera does face detection when looking at persons. And it just works. You only use AI knowledge to appreciate it.

Friday, November 27, 2009

AI for real life: Optimize team utility

I will write some articles about Artificial Intelligence (AI). Especially, they will be about what I have learned from AI. The first one is about teamwork.

A work in a team is different from a solo work. They are two different problems. When you are working solo, your goal is to maximize the amount of work done by you. In AI, they would say that an agent optimizes its utility function. It is like a score you receive from a finished game.

Inside a team, the goal of the problem is different. The goal is to maximize the amount of work done by the team. You should maximize the sum of the work done by you and your coworkers.

It is a much harder problem to optimize the sum of the utilities. If you are choosing an action, you would like to be able to predict its effects. A good start is to create a model of the internal state of your coworker. We humans call that empathy.

To understand AI:
Universal Intelligence: A Definition of Machine Intelligence

To understand other people:
How to Win Friends & Influence People