{"596480":{"#nid":"596480","#data":{"type":"news","title":"Finding a Novel Approach: Merrick Furst Wins Classic Paper Award for Graph Planning","body":[{"value":"\u003Cp\u003EWhy is it so difficult for computers to plan? This was the question Georgia Institute of Technology Professor \u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/people\/merrick-furst\u0022\u003EMerrick Furst\u003C\/a\u003E\u003C\/strong\u003E and Carnegie Mellon University (CMU) Professor\u003Cstrong\u003E \u003Ca href=\u0022http:\/\/www.cs.cmu.edu\/~avrim\/\u0022\u003EAvrim Blum\u003C\/a\u003E\u003C\/strong\u003E set out to answer in 1997.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETheir research eventually led to the influential paper \u003Cem\u003E\u003Ca href=\u0022https:\/\/www.cs.cmu.edu\/~avrim\/Papers\/graphplan.pdf\u0022\u003EFast Planning Through Planning Graph Analysis\u003C\/a\u003E\u003C\/em\u003E, which won a 2017 Classic Paper Award from the \u003Ca href=\u0022http:\/\/aij.ijcai.org\/\u0022\u003EArtificial Intelligence Journal\u003C\/a\u003E this August. The award recognizes papers with exceptional significance and impact published at least 15 years prior, noting that their work \u0026ldquo;changed the perspective on classic planning algorithms.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETwo decades ago, Furst \u0026ndash; then a CMU computer science professor \u0026ndash;\u0026nbsp;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\u0026rsquo;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 \u0026mdash; a very inefficient method.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFurst and Blum weren\u0026rsquo;t the first researchers to tackle this planning problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESince 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EInstead, Furst and Blum realized the solution was not planning how humans do, but matching between each step in the AI\u0026rsquo;s algorithm. \u0026ldquo;We were matching up the truth of the worlds, matching up what\u0026rsquo;s true now to what will be true in the next step,\u0026rdquo; Furst said.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDrawing out these matches enabled the researchers to create a \u0026ldquo;planning graph\u0026rdquo; 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;They said, \u0026lsquo;Oh, but you\u0026rsquo;re not allowed to do it that way,\u0026rsquo;\u0026rdquo; Furst said. \u0026ldquo;Often, what limits you from solving problems is that you may have \u0026nbsp;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, \u0026lsquo;Let\u0026rsquo;s not decide how the solution is going to work; let\u0026rsquo;s ask how you might be able to solve planning problem at all.\u0026rsquo; That opened up a lot of possibilities.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFurst\u0026rsquo;s \u0026ldquo;out of the box\u0026rdquo; 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 \u003Ca href=\u0022http:\/\/flashpoint.gatech.edu\/\u0022\u003EFlashpoint\u003C\/a\u003E, an approach to innovation that disrupts many of our assumptions about how it should happen.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAlthough the specific algorithm from their original paper isn\u0026rsquo;t in use anymore, the concept of planning graphs is still the basis for the newest planning algorithms. Furst\u0026rsquo;s largest contribution to AI might have been in the approach to solving the problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;The biggest breakthroughs in artificial intelligence have often come when we don\u0026rsquo;t try to solve problems exactly the same way human beings would,\u0026rdquo; Furst said.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Professor Merrick Furst\u0027s influential graph planning wins an award for its impact."}],"uid":"34541","created_gmt":"2017-09-26 13:43:54","changed_gmt":"2017-09-26 14:45:30","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2017-09-26T00:00:00-04:00","iso_date":"2017-09-26T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"50624":{"id":"50624","type":"image","title":"Merrick Furst","body":null,"created":"1449175408","gmt_created":"2015-12-03 20:43:28","changed":"1475894463","gmt_changed":"2016-10-08 02:41:03","alt":"Merrick Furst","file":{"fid":"128759","name":"merrick-furst.jpg","image_path":"\/sites\/default\/files\/images\/merrick-furst_1.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/merrick-furst_1.jpg","mime":"image\/jpeg","size":12010,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/merrick-furst_1.jpg?itok=7iSOl3k9"}}},"media_ids":["50624"],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[],"core_research_areas":[{"id":"39521","name":"Robotics"}],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022mailto: tess.malone@cc.gatech.edu\u0022\u003Etess.malone@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["tess.malone@cc.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}