Why is it so difficult for computers to plan? This was the question Georgia Institute of Technology Professor Merrick Furst and Carnegie Mellon University (CMU) Professor Avrim Blum set out to answer in 1997.
Their research eventually led to the influential paper Fast Planning Through Planning Graph Analysis, which won a 2017 Classic Paper Award from the Artificial Intelligence Journal this August. The award recognizes papers with exceptional significance and impact published at least 15 years prior, noting that their work “changed the perspective on classic planning algorithms.”
Two decades ago, Furst – then a CMU computer science professor – and Blum set out to use their theoretical computer science expertise to collaborate with artificial intelligence (AI) researchers at CMU. They wanted to know what was the biggest problem the researchers encountered at the time: why robots couldn’t plan the way humans did. For example, if you were to program a robot to build block towers, the robot would explore all combinations to find the right one — a very inefficient method.
Furst and Blum weren’t the first researchers to tackle this planning problem.
Since the 1960s, researchers had used either a logical approach or tried to emulate how humans plan. The CMU researchers tried the latter, programming robots to solve problems using human rationale (e.g. to build something new, do not undo previous work). They hoped Furst and Blum could make this approach more effective.
Instead, Furst and Blum realized the solution was not planning how humans do, but matching between each step in the AI’s algorithm. “We were matching up the truth of the worlds, matching up what’s true now to what will be true in the next step,” Furst said.
Drawing out these matches enabled the researchers to create a “planning graph” of steps. This graph was much smaller than the graph of all world states that AI researchers would normally use. Instead of an exponential size graph for the AI to analyze and explore, there was a polynomial size graph, allowing the algorithm to run much more efficiently. Even better, because of the way the planning graph was structured, the algorithm always found the shortest plan possible.
The planning graph approach was instantly successful, finding solutions for previously unsolvable problems. Academics took note and wrote expository descriptions of the paper shortly after the researchers first took it to a conference. But when Furst and Blum brought their solution back to the CMU scientists they were collaborating with, they were surprised by the response.
“They said, ‘Oh, but you’re not allowed to do it that way,’” Furst said. “Often, what limits you from solving problems is that you may have already decided, incorrectly, how a solution is going to work. Avrim Blum and I took a really out of the box approach: We said to ourselves, ‘Let’s not decide how the solution is going to work; let’s ask how you might be able to solve planning problem at all.’ That opened up a lot of possibilities.”
Furst’s “out of the box” thinking not only solved this problem, but it has followed him throughout his career at Georgia Tech. The Threads approach to the undergraduate curriculum in the College of Computing owes much to his unique perspective. Today he is the director of the Center for Startup Engineering and created and runs Flashpoint, an approach to innovation that disrupts many of our assumptions about how it should happen.
Although the specific algorithm from their original paper isn’t in use anymore, the concept of planning graphs is still the basis for the newest planning algorithms. Furst’s largest contribution to AI might have been in the approach to solving the problem.
“The biggest breakthroughs in artificial intelligence have often come when we don’t try to solve problems exactly the same way human beings would,” Furst said.