{"id":7758,"date":"2016-02-17T06:46:46","date_gmt":"2016-02-17T06:46:46","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=7758"},"modified":"2016-02-17T06:46:46","modified_gmt":"2016-02-17T06:46:46","slug":"automatic-contingency-planning","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/automatic-contingency-planning\/","title":{"rendered":"Automatic contingency planning"},"content":{"rendered":"

Algorithm lets planning systems generate backup plans efficiently.<\/strong><\/em><\/span><\/p>\n

\"\u201cThe<\/a>
\u201cThe problem with planning contingencies is that there are so many things that can go wrong, if you generated plans for all possible contingencies, you\u2019d go nuts,\u201d Brian Williams says.
Image: MIT News<\/figcaption><\/figure>\n

CAMBRIDGE, Mass.<\/strong> —\u00a0Planning algorithms are widely used in logistics and control. They can help schedule flights and bus routes, guide autonomous robots, and determine control policies for the power grid, among other things.<\/span><\/p>\n

In recent years, planning algorithms have begun to factor in uncertainty \u2014 variations in travel time, erratic communication between autonomous robots, imperfect sensor data, and the like. That causes the scale of the planning problem to grow exponentially, but researchers have found\u00a0clever ways<\/span><\/a>\u00a0to solve it efficiently.<\/span><\/p>\n

[pullquote]Despite the extra labor imposed by generating contingency plans, the algorithm still provides mathematical guarantees that its plans\u2019 risk of failure falls below some threshold, which the user sets.[\/pullquote]<\/p>\n

Now, researchers at MIT and the Australian National University (ANU) have made the problem even more complex, by developing a planning algorithm that also generates contingency plans, should the initial plan prove too risky. It also identifies the conditions \u2014 say, sensor readings or delays incurred \u2014 that should trigger a switch to a particular contingency plan.<\/span><\/p>\n

Despite the extra labor imposed by generating contingency plans, the algorithm still provides mathematical guarantees that its plans\u2019 risk of failure falls below some threshold, which the user sets.<\/span><\/p>\n

\u201cThe problem with planning contingencies is that there are so many things that can go wrong, if you generated plans for all possible contingencies, you\u2019d go nuts,\u201d says Brian Williams, a professor of aeronautics and astronautics whose group developed the new system. \u201cSo then the question ends up being, \u2018How many contingencies do you generate?\u2019\u201d<\/span><\/p>\n

Pedro Santana, a graduate student in aeronautics and astronautics, is first author on a paper describing the system, which he presented at the annual meeting of the Association for the Advancement of Artificial Intelligence last weekend. He\u2019s joined by Williams and Sylvie Thi\u00e9baux, a professor of computer science at the Australian National University and a researcher with Australia\u2019s National Information Communications Technology Australia (NICTA) research program, which has a partnership with MIT.<\/span><\/p>\n

Probabilistic pruning<\/strong><\/span><\/p>\n

As Williams explains, the range of possible decisions that a planner faces can be represented as a data structure called a\u00a0graph<\/span><\/a>. A graph consists of nodes, which are usually represented as circles, and edges, which are represented as line segments connecting the nodes. Network diagrams and flow charts are familiar examples of a graph.\u00a0<\/span><\/p>\n

In a planning system, each node of the graph represents a decision point, such as, \u201cShould I take the bus or the subway?\u201d A path through the graph can be evaluated according to the rewards it offers \u2014 you reach your destination safely \u2014 and the penalties it imposes \u2014 you\u2019ll be five minutes late. The optimal plan is the one that maximizes reward.<\/span><\/p>\n

Factoring in probabilities makes that type of reward calculation much more complex: The average bus trip might be 15 minutes, but there\u2019s some chance that it will be 35; the average subway trip might be 18 minutes, but it\u2019s almost never more than 24. In that context, for even a relatively simple planning task, canvassing contingency plans can be prohibitively time consuming.<\/span><\/p>\n

To make the problem tractable, the MIT and ANU researchers borrowed a technique from some\u00a0earlier work<\/span><\/a>\u00a0from Williams\u2019 group. Before the planner begins constructing the graph, it asks the user to set risk thresholds. A researcher trying to develop a data-gathering plan for a multimillion-dollar\u00a0underwater robot<\/span><\/a>, for example, might be satisfied with a 90 percent probability that the robot will take all the sensor readings it\u2019s supposed to \u2014 but they might want a 99.9 percent probability that the robot won\u2019t collide with a rock face at high speed.<\/span><\/p>\n

The researchers\u2019 algorithm treats these thresholds as a \u201crisk budget\u201d that it spends as it explores paths through the graph. If the planner determines that a given branch of the graph will exceed the budget, it lops it off.<\/span><\/p>\n

Staying optimistic<\/strong><\/span><\/p>\n

That determination has to be rapid, however. So the researchers use some simple rules of thumb \u2014 or, in computer parlance, heuristics \u2014 to evaluate branches. Every path through a given branch, for instance, might include a different car route between two points, each with its own probability distribution of possible travel times. But if traversing a straight line between the points, at the maximum allowed speed, will still incur intolerable delays, there\u2019s no point in evaluating probabilities for every route. The branch can be eliminated.<\/span><\/p>\n

As long as the heuristics are optimistic \u2014 possibly underestimating risk but never overestimating it \u2014 the planner can lop off branches without compromising the quality of the final plans. Sometimes those heuristics are application-specific, like the one that evaluates routes geometrically. But sometimes they\u2019re not.<\/span><\/p>\n

For instance, one of the reasons that probability distributions add so much complexity to planning calculations is that they\u2019re nonlinear: Their graphs take on shapes that are more complicated than simple lines. In a paper being presented at the International Conference on Automated Planning and Scheduling in June, Santana \u2014 again first author \u2014 Williams, and colleagues at MIT, the University of S\u00e3o Paulo in Brazil, and Caltech describe a way to produce linear approximations of probability distributions that are much easier to work with mathematically.<\/span><\/p>\n

Those approximations are optimistic: They never overestimate risk. But a computer can evaluate them thousands of times faster than it can a nonlinear distribution. Such heuristics offer hope that the researchers\u2019 planning system could update plans on the fly, in light of new information, as well as generating contingency plans in advance.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Researchers at MIT and the Australian National University (ANU) have made the problem even more complex, by developing a planning algorithm that also generates contingency plans, should the initial plan prove too risky.<\/p>\n","protected":false},"author":6,"featured_media":7759,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[],"class_list":["post-7758","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",448,299,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/02\/MIT-Planning-Chance_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/7758","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=7758"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/7758\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/7759"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=7758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=7758"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=7758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}