Story posted July 24, 2006
Stephen Majercik has a problem. A big problem. It is so difficult, in fact, it belongs to an actual class of complexity. In computer sciencespeak it is what's known as PSPACE-complete. That translates, roughly, as "impossible," laughs Majercik, assistant professor of computer science. "I've been working on it for a long time; it's extremely, extremely difficult."
Problems are the stuff of computer programming, and like most problems that ultimately relate to artificial intelligence, Majercik's computation is an attempt to mathematically codify certain aspects of human behavior and reasoning.
In this case, Majercik - and student research assistant Mark McGranaghan '09 - are working on a probabilistic planning problem. They are trying to come up with a program that could help robots make planning decisions in an environment in which there are uncertainties.
"A robot has limited sensors, it never has a complete picture of its world," notes Majercik. "And, being a mechanical agent in the real world, a robot also has limited accuracy in its actions. We're trying to come up with a plan that would allow the agent, given its knowledge of what the possible outcomes of its action are, to come up with a universal plan for every possible contingency in its environment.
"You want to know, if this happens I should do this, if that happens, I should do something else. You want to plan for all the possible contingencies. The answer is a tree - you take an action, then there is a set of possible actions depending on what is sensed after you take that action, then another set of observations and actions for each of those actions, and so on. The size of the tree can grow very quickly."
The exponentially increasing time required to solve such a problem becomes unreasonable quickly, as can the amount of computer-memory space needed to store the solution tree. Therefore, Majercik and McGranaghan are looking at a subset of these problems to try to find an efficient algorithm for at least a useful subclass of these problems.
"I'm devising various algorithms and testing them on different problems," says McGranaghan. "I started with a classic tree-based approach; it's simple but it tends to take unmanageably long to run. So we decided to look at variations on that algorithm and to apply them to different versions of the problem. For example, we tried an algorithm that saves time by trying to approximate the answer instead of finding it exactly. We had modest success with that."
Majercik is philosophical about the daunting nature of the challenge. It is, he says, emblematic of research in artificial intelligence.
"The problems people look at in artificial intelligence are ridiculously hard, but we try to find ways to solve them," notes Majercik. "The tantalizing thing is, we know that, in many cases, they are solvable because they are things that people do without a second thought. Now we have computers that can play chess at the same level as a chess grandmaster, but things that a child can do - walk into a room and recognize things and understand what's going on - getting a robot to do that ... well, let's just say, we're working on it."