PRESS-NEWS.org - Press Release Distribution
PRESS RELEASES DISTRIBUTION

Helping robots handle uncertainty

Algorithm for planning multirobot collaborations makes complex models practical

2015-06-03
(Press-News.org) Decentralized partially observable Markov decision processes are a way to model autonomous robots' 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're abbreviated) is that they're as complicated as their name. They provide the most rigorous mathematical models of multiagent systems -- not just robots, but any autonomous networked devices --under uncertainty. But for all but the simplest cases, they've been prohibitively time-consuming to solve.

Last summer, MIT researchers presented a paper that made Dec-POMDPs much more practical for 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.

At this year's 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.

The researchers have also tested their system on a small group of robotic helicopters, in a scenario mimicking the type of drone package delivery envisioned by Amazon and Google, but with the added constraint that the robots can't communicate with each other.

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

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.

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.

Since a probability distribution consists of a range of possible values -- in principle, an infinite number of values -- solving a problem with probabilities heaped on probabilities is much harder than solving a problem involving discrete values.

To make it easier to solve a Dec-POMDP, Omidshafiei and his co-authors -- his thesis advisor, Maclaurin Professor of Aeronautics and Astronautics Jonathan How; Ali-akbar Agha-mohammadi, a former postdoc in MIT's 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's Computer Science and Artificial Intelligence Laboratory and has just joined the faculty of the University of New Hampshire -- decompose it into two problems, both of which involve graphs.

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.

The researchers' algorithm first constructs a graph in which each node represents a "belief state," meaning a probabilistic estimate of an agent's own state and the state of the world. The algorithm then creates a set of control procedures -- the edges of the graph -- that can move the agent between belief states.

The researchers refer to these control procedures as "macro-actions." 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's complexity before passing it on to the next stage.

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.

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.

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.

INFORMATION:

The work was funded by Boeing.

Related links

ARCHIVE: Delivery by drone https://newsoffice.mit.edu/2014/algorithm-monitors-delivery-drones-0821

ARCHIVE: Herding robots http://newsoffice.mit.edu/2014/herding-robots-0212



ELSE PRESS RELEASES FROM THIS DATE:

How a box jellyfish catches fish

2015-06-03
The first feeding study of tropical Australia's Irukandji box jellyfish has found that they actively fish. They attract larval fish by twitching their extended tentacles, highlighting their nematocyst clusters (stinging structures) and using them as lures. It's an impressive feat by any standards, but particularly so for an animal that doesn't have a defined brain. The laboratory-based study of Carukia barnesi, the tiny but deadly Irukandji jellyfish, was conducted at James Cook University (JCU) in Cairns, Australia, and has been published in the online journal PLOS ONE. ...

Cyberbullying less emotionally harmful to kids than traditional in-person harassment, study finds

2015-06-03
WASHINGTON - Contrary to popular belief, cyberbullying that starts and stays online is no more emotionally harmful to youngsters than harassment that only occurs in-person and may actually be less disturbing because it's likelier to be of shorter duration and not involve significant power imbalances, according to a study published by the American Psychological Association. Researchers at the University of New Hampshire analyzed data from the Technology Harassment Victimization Study, funded by the National Institute of Justice. They focused on telephone interviews conducted ...

Arterial thrombosis: Cloaking of collagen frees up the flow

2015-06-03
Blood clots often form when lipid-rich plaques on the inner surface of arteries rupture and platelets aggregate at the site of injury. Cardiologists from Ludwig-Maximilians-Universitaet (LMU) in Munich have now compared the effects of two new platelet aggregation inhibitors. Blood clots that form in arteries - so-called arterial thrombosis -are among the most common causes of heart attack and stroke. They are particularly prone to develop when 'atherosclerotic plaques', fatty deposits that build up within the inner lining of major arteries, fracture and break. Circulating ...

New treatment for polycystic kidney disease

2015-06-03
Published in the Journal of the American Society of Nephrology, the treatment, which involves targeting tiny blood and lymphatic vessels inside the kidneys, is shown to improve renal function and slow progression of disease in mice. Polycystic kidney disease (PKD) is a genetic disorder where fluid filled cysts grow in kidneys and destroy normal renal tissue. It is the world's most common inherited kidney disease, affecting between 1 in 400 and 1 in 1000 people worldwide - around 12.5 million individuals. A rarer form of the disease, which occurs in about one in every ...

In search of memory storage

2015-06-03
The hippocampus plays a crucial role in memory formation. However, it is not yet fully understood in what way that brain structure's individual regions are involved in the formation of memories. Neuroscientists at the Collaborative Research Center 874 at RUB have recreated this process with the aid of computer simulations. Their findings challenge the model of memory forming in the hippocampus established to date. Their results have been published in the journal PLOS Computational Biology. Unique anatomy of the hippocampus The hippocampus' importance for memory forming ...

Study supports IDH gene as prognostic marker in anaplastic astrocytoma

2015-06-03
COLUMBUS, Ohio - New findings suggest that a gene called IDH1 might be prognostic marker for a rare form of brain cancer. Patients in this study who had a mutated IDH gene lived an average of 7.9 years after diagnosis versus 2.8 years for patients with unaltered IDH. The IDH study was done as part of the phase III clinical trial RTOG 9813, which involved 301 patients with anaplastic astrocytoma. The duel-arm trial evaluated the effectiveness of radiation therapy plus either of two chemotherapy drugs: temozolomide and nitrosourea. "We found that IDH status is not only ...

Re-inflating balloon after carotid stenting appears to double risk of stroke and death

2015-06-03
After reviewing outcomes from thousands of cases, researchers at Johns Hopkins report that patients with blocked neck arteries who undergo carotid stenting to prop open the narrowed blood vessels fare decidedly worse if their surgeons re-inflate a tiny balloon in the vessel after the mesh stent is in place. Although the overall risk of stroke and death is low in patients who undergo carotid stenting, the common practice of "ballooning" the vessel after the wire mesh is inserted can double the risk of death and stroke during or shortly after the procedure, according to ...

The Lancet: Middle East respiratory syndrome (MERS) Seminar

2015-06-03
Middle East respiratory syndrome (MERS) has recently returned to the headlines as new cases have been exported to Korea and China. Experts are concerned that MERS cases continued to be detected in Saudi Arabia throughout the past year, and there appears to be little reduction in the number of cases since its first discovery three years ago. As the month of Ramadan approaches, with 1 million pilgrims expected to arrive in Saudi Arabia in June and July 2015, MERS remains a threat to global health security. The Lancet today publishes a new Seminar on MERS, outlining the current ...

Intravenous nutrition source could reduce side effects of chemotherapy

2015-06-03
PITTSBURGH -- A single dose of an FDA-approved intravenous nutrition source may be able to significantly reduce the toxicity and increase the bioavailability of platinum-based cancer drugs, according to a study by Carnegie Mellon University biologists published in Scientific Reports. Platinum-based drugs, including cisplatin, carboplatin and oxyplatin, have been used to treat cancer for more than 35 years. While they remain among the most prescribed and most potent chemotherapy drugs, they also cause serious side effects, including kidney damage. Many of the side effects ...

Cooking up cognition

2015-06-03
These days, cooking dinner requires no more thought than turning a knob on a stovetop, but for early humans the notion that - simply by applying heat or fire - foods could be transformed into something both tastier and easier to digest demanded huge cognitive insight - insights often believed to be limited to humans. New evidence, however, suggests that, when it comes to cooking, humans may need to make more room at the table. A new study, co-authored by Felix Warneken, the John L. Loeb Associate Professor of the Social Sciences, and Alexandra Rosati '05, currently ...

LAST 30 PRESS RELEASES:

“Molecular bodyguard” helps infections persist

Japan’s first nationwide survey highlights gaps in patient engagement for allergy research

World’s first pig-to-human liver xenotransplant in a living recipient reported in the Journal of Hepatology

The Lancet: Tens of thousands of children aged under five suffering acute malnutrition in Gaza, recent estimates suggest

Prostate testing may not target those most likely to benefit, warn experts

Global analysis shows hidden damage from men’s alcohol use

DRI recognizes Ashley Cornish as the 2025 Peter B. Wagner Memorial Award Winner for Women in Atmospheric Sciences

Unlocking the blueprint for a powerful plant-based drug

Bringing modern science to vitamin biology: Isha Jain wins NIH Transformative Research Award

University of Houston scientists learn that rare bacterium ‘plays dead’ to survive

Introduced animals change how island plants spread, new global study finds

Mayo Clinic researchers discover ‘traffic controller’ protein that protects DNA, and may help kill cancer cells

Protein sidekick exhibits dual roles in stress granule assembly and disassembly

New hope for MS

Kennesaw State professor receives grant to study cancer origins

Pain and antidepressant drug combo linked to increased seizure risk in older adults

Cancer researchers shape new strategies for immunotherapy

Physical exercise can ‘train’ the immune system

Calm red brocket deer can learn to "Come" and other commands - but the flightiest, most restless individuals struggle

China, the world's largest tea producer, is predicted to experience increases in land suitable for tea-growing under climate change, with the overall range shifting northwards, per AI modeling study

Composing crews for Mars missions

Early humans butchered elephants using small tools and made big tools from their bones

1,000-year-old gut microbiome revealed for young man who lived in pre-Hispanic Mexico

Bears and pandas in captivity develop significantly different gut microbiomes compared to their wild counterparts, and giant pandas in particular have less diverse microbiomes than their wild counterp

Prenatal and postnatal support apps might not work

Dancing dust devils trace raging winds on Mars

Raging winds on Mars

Real-time biopsies uncover hidden response to glioblastoma therapy

Repeated brain tumor sampling uncovers treatment response in patients with glioblastoma

Novel immunotherapy combination destroys colorectal liver metastases

[Press-News.org] Helping robots handle uncertainty
Algorithm for planning multirobot collaborations makes complex models practical