Featured Research

from universities, journals, and other organizations

Delivery by drone: New algorithm lets drones monitor their own health during long package-delivery missions

Date:
August 21, 2014
Source:
Massachusetts Institute of Technology
Summary:
In the near future, the package that you ordered online may be deposited at your doorstep by a drone: Last December, online retailer Amazon announced plans to explore drone-based delivery, suggesting that fleets of flying robots might serve as autonomous messengers that shuttle packages to customers within 30 minutes of an order. A new algorithm lets drones monitor their own health during long package-delivery missions.

Credit: Illustration: Christine Daniloff/MIT (photograph of quadrotor courtesy of the researchers)

In the near future, the package that you ordered online may be deposited at your doorstep by a drone: Last December, online retailer Amazon announced plans to explore drone-based delivery, suggesting that fleets of flying robots might serve as autonomous messengers that shuttle packages to customers within 30 minutes of an order.

To ensure safe, timely, and accurate delivery, drones would need to deal with a degree of uncertainty in responding to factors such as high winds, sensor measurement errors, or drops in fuel. But such "what-if" planning typically requires massive computation, which can be difficult to perform on the fly.

Now MIT researchers have come up with a two-pronged approach that significantly reduces the computation associated with lengthy delivery missions. The team first developed an algorithm that enables a drone to monitor aspects of its "health" in real time. With the algorithm, a drone can predict its fuel level and the condition of its propellers, cameras, and other sensors throughout a mission, and take proactive measures -- for example, rerouting to a charging station -- if needed.

The researchers also devised a method for a drone to efficiently compute its possible future locations offline, before it takes off. The method simplifies all potential routes a drone may take to reach a destination without colliding with obstacles.

In simulations involving multiple deliveries under various environmental conditions, the researchers found that their drones delivered as many packages as those that lacked health-monitoring algorithms -- but with far fewer failures or breakdowns.

"With something like package delivery, which needs to be done persistently over hours, you need to take into account the health of the system," says Ali-akbar Agha-mohammadi, a postdoc in MIT's Department of Aeronautics and Astronautics. "Interestingly, in our simulations, we found that, even in harsh environments, out of 100 drones, we only had a few failures."

Agha-mohammadi will present details of the group's approach in September at the IEEE/RSJ International Conference on Intelligent Robots and Systems, in Chicago. His co-authors are MIT graduate student Kemal Ure; Jonathan How, the Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics; and John Vian of Boeing.

Tree of possibilities

Planning an autonomous vehicle's course often involves an approach called Markov Decision Process (MDP), a sequential decision-making framework that resembles a "tree" of possible actions. Each node along a tree can branch into several potential actions -- each of which, if taken, may result in even more possibilities. As Agha-mohammadi explains it, MDP is "the process of reasoning about the future" to determine the best sequence of policies to minimize risk.

MDP, he says, works reasonably well in environments with perfect measurements, where the result of one action will be observed perfectly. But in real-life scenarios, where there is uncertainty in measurements, such sequential reasoning is less reliable. For example, even if a command is given to turn 90 degrees, a strong wind may prevent that command from being carried out.

Instead, the researchers chose to work with a more general framework of Partially Observable Markov Decision Processes (POMDP). This approach generates a similar tree of possibilities, although each node represents a probability distribution, or the likelihood of a given outcome. Planning a vehicle's route over any length of time, therefore, can result in an exponential growth of probable outcomes, which can be a monumental task in computing.

Agha-mohammadi chose to simplify the problem by splitting the computation into two parts: vehicle-level planning, such as a vehicle's location at any given time; and mission-level, or health planning, such as the condition of a vehicle's propellers, cameras, and fuel levels.

For vehicle-level planning, he developed a computational approach to POMDP that essentially funnels multiple possible outcomes into a few most-likely outcomes.

"Imagine a huge tree of possibilities, and a large chunk of leaves collapses to one leaf, and you end up with maybe 10 leaves instead of a million leaves," Agha-mohammadi says. "Then you can … let this run offline for say, half an hour, and map a large environment, and accurately predict the collision and failure probabilities on different routes."

He says that planning out a vehicle's possible positions ahead of time frees up a significant amount of computational energy, which can then be spent on mission-level planning in real time. In this regard, he and his colleagues used POMDP to generate a tree of possible health outcomes, including fuel levels and the status of sensors and propellers.

Proactive delivery

The researchers combined the two computational approaches, and ran simulations in which drones were tasked with delivering multiple packages to different addresses under various wind conditions and with limited fuel. They found that drones operating under the two-pronged approach were more proactive in preserving their health, rerouting to a recharge station midmission to keep from running out of fuel. Even with these interruptions, the team found that these drones were able to deliver just as many packages as those that were programmed to simply make deliveries without considering health.

Going forward, the team plans to test the route-planning approach in actual experiments. The researchers have attached electromagnets to small drones, or quadrotors, enabling them to pick up and drop off small parcels. The team has also programmed the drones to land on custom-engineered recharge stations.

"We believe in the near future, in a lab setting, we can show what we're gaining with this framework by delivering as many packages as we can while preserving health," Agha-mohammadi says. "Not only the drone, but the package might be important, and if you fail, it could be a big loss."

This work was supported by Boeing.


Story Source:

The above story is based on materials provided by Massachusetts Institute of Technology. The original article was written by Jennifer Chu. Note: Materials may be edited for content and length.


Cite This Page:

Massachusetts Institute of Technology. "Delivery by drone: New algorithm lets drones monitor their own health during long package-delivery missions." ScienceDaily. ScienceDaily, 21 August 2014. <www.sciencedaily.com/releases/2014/08/140821115834.htm>.
Massachusetts Institute of Technology. (2014, August 21). Delivery by drone: New algorithm lets drones monitor their own health during long package-delivery missions. ScienceDaily. Retrieved October 23, 2014 from www.sciencedaily.com/releases/2014/08/140821115834.htm
Massachusetts Institute of Technology. "Delivery by drone: New algorithm lets drones monitor their own health during long package-delivery missions." ScienceDaily. www.sciencedaily.com/releases/2014/08/140821115834.htm (accessed October 23, 2014).

Share This



More Matter & Energy News

Thursday, October 23, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

3D Printed Instruments Make Sweet Music in Sweden

3D Printed Instruments Make Sweet Music in Sweden

Reuters - Innovations Video Online (Oct. 23, 2014) Students from Lund University's Malmo Academy of Music are believed to be the world's first band to all use 3D printed instruments. The guitar, bass guitar, keyboard and drums were built by Olaf Diegel, professor of product development, who says 3D printing allows musicians to design an instrument to their exact specifications. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Chameleon Camouflage to Give Tanks Cloaking Capabilities

Chameleon Camouflage to Give Tanks Cloaking Capabilities

Reuters - Innovations Video Online (Oct. 22, 2014) Inspired by the way a chameleon changes its colour to disguise itself; scientists in Poland want to replace traditional camouflage paint with thousands of electrochromic plates that will continuously change colour to blend with its surroundings. The first PL-01 concept tank prototype will be tested within a few years, with scientists predicting that a similar technology could even be woven into the fabric of a soldiers' clothing making them virtually invisible to the naked eye. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Jet Sales Lift Boeing Profit 18 Pct.

Jet Sales Lift Boeing Profit 18 Pct.

Reuters - Business Video Online (Oct. 22, 2014) Strong jet demand has pushed Boeing to raise its profit forecast for the third time, but analysts were disappointed by its small cash flow. Fred Katayama reports. Video provided by Reuters
Powered by NewsLook.com
Internet of Things Aims to Smarten Your Life

Internet of Things Aims to Smarten Your Life

AP (Oct. 22, 2014) As more and more Bluetooth-enabled devices are reaching consumers, developers are busy connecting them together as part of the Internet of Things. (Oct. 22) Video provided by AP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins