{"id":11519,"date":"2017-02-08T08:55:52","date_gmt":"2017-02-08T08:55:52","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=11519"},"modified":"2017-02-08T08:58:04","modified_gmt":"2017-02-08T08:58:04","slug":"researchers-add-human-intuition-planning-algorithms","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/researchers-add-human-intuition-planning-algorithms\/","title":{"rendered":"Researchers add human intuition to planning algorithms"},"content":{"rendered":"

Incorporating strategies from skilled human planners improves automatic planners\u2019 performance.<\/strong><\/em><\/span><\/p>\n

\"\"
Researchers from MIT\u2019s Computer Science and Artificial Intelligence Laboratory are trying to improve automated planners by giving them the benefit of human intuition. By encoding the strategies of high-performing human planners in a machine-readable form, they were able to improve the performance of competition-winning planning algorithms by between 10 and 15 percent on a challenging set of problems.
Image: Jose-Luis Olivares\/MIT<\/figcaption><\/figure>\n

Every other year, the International Conference on Automated Planning and Scheduling hosts a competition in which computer systems designed by conference participants try to find the best solution to a planning problem, such as scheduling flights or coordinating tasks for teams of autonomous satellites.<\/span><\/p>\n

On all but the most straightforward problems, however, even the best planning algorithms still aren\u2019t as effective as human beings with a particular aptitude for problem-solving \u2014 such as MIT students.<\/span><\/p>\n

Researchers from MIT\u2019s Computer Science and Artificial Intelligence Laboratory are trying to improve automated planners by giving them the benefit of human intuition. By encoding the strategies of high-performing human planners in a machine-readable form, they were able to improve the performance of competition-winning planning algorithms by 10 to 15 percent on a challenging set of problems.<\/span><\/p>\n

The researchers are presenting their results this week at the Association for the Advancement of Artificial Intelligence\u2019s annual conference.<\/span><\/p>\n

\u201cIn the lab, in other investigations, we\u2019ve seen that for things like planning and scheduling and optimization, there\u2019s usually a small set of people who are truly outstanding at it,\u201d says Julie Shah, an assistant professor of aeronautics and astronautics at MIT. \u201cCan we take the insights and the high-level strategies from the few people who are truly excellent at it and allow a machine to make use of that to be better at problem-solving than the vast majority of the population?\u201d<\/span><\/p>\n

The first author on the conference paper is Joseph Kim, a graduate student in aeronautics and astronautics. He\u2019s joined by Shah and Christopher Banks, an undergraduate at Norfolk State University who was a research intern in Shah\u2019s lab in the summer of 2016.<\/span><\/p>\n

The human factor<\/strong><\/span><\/p>\n

Algorithms entered in the automated-planning competition \u2014 called the International Planning Competition, or IPC \u2014 are given related problems with different degrees of difficulty. The easiest problems require satisfaction of a few rigid constraints: For instance, given a certain number of airports, a certain number of planes, and a certain number of people at each airport with particular destinations, is it possible to plan planes\u2019 flight routes such that all passengers reach their destinations but no plane ever flies empty?<\/span><\/p>\n

A more complex class of problems \u2014 numerical problems \u2014 adds some flexible numerical parameters: Can you find a set of flight plans that meets the constraints of the original problem but also minimizes planes\u2019 flight time and fuel consumption?<\/span><\/p>\n

Finally, the most complex problems \u2014 temporal problems \u2014 add temporal constraints to the numerical problems: Can you minimize flight time and fuel consumption while also ensuring that planes arrive and depart at specific times?<\/span><\/p>\n

For each problem, an algorithm has a half-hour to generate a plan. The quality of the plans is measured according to some \u201ccost function,\u201d such as an equation that combines total flight time and total fuel consumption.<\/span><\/p>\n

Shah, Kim, and Banks recruited 36 MIT undergraduate and graduate students and posed each of them the planning problems from two different competitions, one that focused on plane routing and one that focused on satellite positioning. Like the automatic planners, the students had a half-hour to solve each problem.<\/span><\/p>\n

\u201cBy choosing MIT students, we\u2019re basically choosing the world experts in problem solving,\u201d Shah says. \u201cLikely, they\u2019re going to be better at it than most of the population.\u201d<\/span><\/p>\n

Encoding strategies<\/strong><\/span><\/p>\n

Certainly, they were better than the automatic planners. After the students had submitted their solutions, Kim interviewed them about the general strategies they had used to solve the problems. Their answers included things like \u201cPlanes should visit each city at most once,\u201d and \u201cFor each satellite, find routes in three turns or less.\u201d<\/span><\/p>\n

The researchers discovered that the large majority of the students\u2019 strategies could be described using a formal language called linear temporal logic, which in turn could be used to add constraints to the problem specifications. Because different strategies could cancel each other out, the researchers tested each student\u2019s strategies separately, using the planning algorithms that had won their respective competitions. The results varied, but only slightly. On the numerical problems, the average improvement was 13 percent and 16 percent, respectively, on the flight-planning and satellite-positioning problems; and on the temporal problems, the improvement was 12 percent and 10 percent.<\/span><\/p>\n

\u201cThe plan that the planner came up with looked more like the human-generated plan when it used these high-level strategies from the person,\u201d Shah says. \u201cThere is maybe this bridge to taking a user\u2019s high-level strategy and making that useful for the machine, and by making it useful for the machine, maybe it makes it more interpretable to the person.\u201d<\/span><\/p>\n

In ongoing work, Kim and Shah are using natural-language-processing techniques to make the system fully automatic, so that it will convert users\u2019 free-form descriptions of their high-level strategies into linear temporal logic without human intervention.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Incorporating strategies from skilled human planners improves automatic planners\u2019 performance. Every other year, the International Conference on Automated Planning and Scheduling hosts a competition in which computer systems designed by conference participants try to find the best solution to a planning problem, such as scheduling flights or coordinating tasks for teams of autonomous satellites. On […]<\/p>\n","protected":false},"author":6,"featured_media":11520,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,17],"tags":[],"class_list":["post-11519","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/02\/MIT-Interactive-Plan_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Computer Science<\/a> Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/11519","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=11519"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/11519\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/11520"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=11519"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=11519"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=11519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}