{"id":4572,"date":"2015-06-04T05:27:33","date_gmt":"2015-06-04T05:27:33","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=4572"},"modified":"2015-06-04T05:27:33","modified_gmt":"2015-06-04T05:27:33","slug":"helping-robots-handle-uncertainty","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/helping-robots-handle-uncertainty\/","title":{"rendered":"Helping robots handle uncertainty"},"content":{"rendered":"

Algorithm for planning multirobot collaborations makes complex models practical.<\/strong><\/em><\/span><\/p>\n

\"Researchers<\/a>
Researchers are using a small group of robotic helicopters to address the problem of drone package delivery. The scenario includes base stations (marked with a “B”) and destinations (marked with a “D”). The colored lines represent the planned paths of the 4 helicopters.
Image: Shayegan Omidshafiei and Shih-Yuan Liu<\/figcaption><\/figure>\n

CAMBRIDGE, Mass. —\u00a0Decentralized partially observable Markov decision processes are a way to model autonomous robots\u2019 behavior in circumstances where neither their communication with each other nor their judgments about the outside world are perfect.<\/span><\/p>\n

The problem with Dec-POMDPs (as they\u2019re abbreviated) is that they\u2019re as complicated as their name. They provide the most rigorous mathematical models of multiagent systems \u2014 not just robots, but any autonomous networked devices \u2014under uncertainty. But for all but the simplest cases, they\u2019ve been prohibitively time-consuming to solve.<\/span><\/p>\n

Last summer, MIT researchers presented a paper that made Dec-POMDPs\u00a0much more practical<\/span><\/a>\u00a0for real-world robotic systems. They showed that Dec-POMDPs could determine the optimal way to stitch together existing, lower-level robotic control systems to accomplish collective tasks. By sparing Dec-POMDPs the nitty-gritty details, the approach made them computationally tractable.<\/span><\/p>\n

At this year\u2019s International Conference on Robotics and Automation, another team of MIT researchers takes this approach a step further. Their new system can actually generate the lower-level control systems from scratch, while still solving Dec-POMDP models in a reasonable amount of time.<\/span><\/p>\n

The researchers have also tested their system on a small group of robotic helicopters, in a scenario mimicking the type of\u00a0drone package delivery<\/span><\/a>\u00a0envisioned by Amazon and\u00a0Google<\/span><\/a>, but with the added constraint that the robots can\u2019t communicate with each other.<\/span><\/p>\n

\u201cThere\u2019s an offline planning phase where the agents can figure out a policy together that says, \u2018If I take this set of actions, given that I\u2019ve made these observations during online execution, and you take these other sets of actions, given that you\u2019ve made these observations, then we can all agree that the whole set of actions that we take is pretty close to optimal,\u2019\u201d says Shayegan Omidshafiei, an MIT graduate student in aeronautics and astronautics and first author on the new paper. \u201cThere\u2019s no point during the online phase where the agents stop and say, \u2018This is my belief. This is your belief. Let\u2019s come up with a consensus on the best overall belief and replan.\u2019 Each one just does its own thing.\u201d<\/span><\/p>\n

What makes Dec-POMDPs so complicated is that they explicitly factor in uncertainty. An autonomous robot out in the world may depend on its sensor readings to determine its location. But its sensors will probably be slightly error-prone, so any given reading should be interpreted as defining a probability distribution surrounding the actual measurement.<\/span><\/p>\n

Even an accurate measurement, however, may be open to interpretation, so the robot would need to build a probability distribution of possible locations on top of the probability distribution of sensor readings. Then it has to choose a course of action, but its possible actions will have their own probabilities of success. And if the robot is participating in a collaborative task, it also has to factor in the probable locations of other robots and their consequent probabilities of taking particular actions.<\/span><\/p>\n

Since a probability distribution consists of a range of possible values \u2014 in principle, an infinite number of values \u2014 solving a problem with probabilities heaped on probabilities is much harder than solving a problem involving discrete values.<\/span><\/p>\n

To make it easier to solve a Dec-POMDP, Omidshafiei and his co-authors \u2014 his thesis advisor, Maclaurin Professor of Aeronautics and Astronautics Jonathan How; Ali-akbar Agha-mohammadi, a former postdoc in MIT\u2019s Laboratory for Information and Decision Systems who is now at Qualcomm Research; and Christopher Amato, who led the earlier work on Dec-POMDPs as a postdoc in MIT\u2019s Computer Science and Artificial Intelligence Laboratory and has just joined the faculty of the University of New Hampshire \u2014 decompose it into two problems, both of which involve\u00a0graphs<\/span><\/a>.<\/span><\/p>\n

A graph is data representation consisting of nodes, usually depicted as circles, and edges, usually depicted as lines connecting the circles. Network diagrams and family trees are familiar examples.<\/span><\/p>\n

The researchers\u2019 algorithm first constructs a graph in which each node represents a \u201cbelief state,\u201d meaning a probabilistic estimate of an agent\u2019s own state and the state of the world. The algorithm then creates a set of control procedures \u2014 the edges of the graph \u2014 that can move the agent between belief states.<\/span><\/p>\n

The researchers refer to these control procedures as \u201cmacro-actions.\u201d Because a single macro-action can accommodate a range of belief states at both its origin and its destination, the planning algorithm has removed some of the problem\u2019s complexity before passing it on to the next stage.<\/span><\/p>\n

\"This<\/a>
This diagram shows the various destinations and obstacles in the researchers’ scenario.
Image: Shayegan Omidshafiei<\/figcaption><\/figure>\n

For each agent, the algorithm then constructs a second graph, in which the nodes represent macro-actions defined in the previous step, and the edges represent transitions between macro-actions, in light of observations. In the experiments reported in the new paper, the researchers then ran a host of simulations of the task the agents were intended to perform, with agents assuming different, random states at the beginning of each run. On the basis of how well the agents executed their tasks each time through, the planning algorithm assigned different weights to the macro-actions at the nodes of the graph and to the transitions between nodes.<\/span><\/p>\n

The result was a graph capturing the probability that an agent should perform a particular macro-action given both its past actions and its observations of the world around it. Although those probabilities were based on simulations, in principle, autonomous agents could build the same type of graph through physical exploration of their environments.<\/span><\/p>\n

Finally, the algorithm selects the macro-actions and transitions with the highest weights. That yields a deterministic plan that the individual agents can follow: After performing macro-action A, if you make measurement B, execute macro-action C.<\/span><\/p>\n

The work was funded by Boeing.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Algorithm for planning multirobot collaborations makes complex models practical. CAMBRIDGE, Mass. —\u00a0Decentralized partially observable Markov decision processes are a way to model autonomous robots\u2019 behavior in circumstances where neither their communication with each other nor their judgments about the outside world are perfect. The problem with Dec-POMDPs (as they\u2019re abbreviated) is that they\u2019re as complicated […]<\/p>\n","protected":false},"author":6,"featured_media":4573,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14,17],"tags":[],"class_list":["post-4572","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-innovation","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/06\/MIT-MultiRobot-Planner-01.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Innovation<\/a> Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/4572","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=4572"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/4572\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/4573"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=4572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=4572"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=4572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}