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 th