MIT uses 4D maps to help robot teams navigate moving obstacles

A new algorithm incorporates time as a fourth mapping dimension

It's one thing to keep robots from crashing into fixed obstacles like walls or furniture, but preventing collisions with other moving things is a much tougher challenge. Targeting teams of robots working together, MIT on Thursday announced a new algorithm that helps robots avoid moving objects.

Planning algorithms for robot teams can be centralized, in which a single computer makes decisions for the whole team, or decentralized, in which each robot makes its own decisions. The latter approach is much better in terms of incorporating local observations, but it's also much trickier, since each robot must essentially guess what the others are going to do.

MIT's new algorithm takes a decentralized approach and factors in not just stationary obstacles but also moving ones. Each robot uses its own observations to map out an obstacle-free region in its immediate environment. It then passes that map to its nearest neighbors. When a robot receives a map from a neighbor, it calculates the intersection of that map with its own and passes that on to other neighbors.

Because each robot communicates only with its close neighbors, the bandwidth required for communications is greatly reduced, particularly when there are a lot of robots. And each robot ends up with a map that reflects all of the obstacles detected by the whole team.

The algorithm accounts for obstacles in motion by including time as a fourth mapping dimension. With that dimension included, it describes how a three-dimensional map would have to change to accommodate the obstacle’s change of location over a span of a few seconds.

In simulations involving squadrons of mini helicopters, the algorithm came up with the same flight plans that a centralized version did but allowed for small variations as conditions required.

“It’s a really exciting result, because it combines so many challenging goals,” said Daniela Rus, a professor in MIT’s Department of Electrical Engineering and Computer Science and director of the Computer Science and Artificial Intelligence Laboratory.

“Your group of robots has a local goal, which is to stay in formation, and a global goal, which is where they want to go or the trajectory along which you want them to move," Rus explained. "You allow them to operate in a world with static obstacles but also unexpected dynamic obstacles, and you have a guarantee that they are going to retain their local and global objectives.”

Each robot updates its map several times per second, calculating the trajectory that will maximize both local and global objectives.

To simulate environments in which humans and robots work together, the researchers are also testing a version of their algorithm on wheeled robots whose goal is to collectively carry an object across a room where humans are also moving.

They'll present their algorithm next month at the International Conference on Robotics and Automation.

Join the Good Gear Guide newsletter!

Error: Please check your email address.

Tags robotsMIT

Our Back to Business guide highlights the best products for you to boost your productivity at home, on the road, at the office, or in the classroom.

Keep up with the latest tech news, reviews and previews by subscribing to the Good Gear Guide newsletter.

Katherine Noyes

IDG News Service
Show Comments

Most Popular Reviews

Latest News Articles

Resources

PCW Evaluation Team

Azadeh Williams

HP OfficeJet Pro 8730

A smarter way to print for busy small business owners, combining speedy printing with scanning and copying, making it easier to produce high quality documents and images at a touch of a button.

Andrew Grant

HP OfficeJet Pro 8730

I've had a multifunction printer in the office going on 10 years now. It was a neat bit of kit back in the day -- print, copy, scan, fax -- when printing over WiFi felt a bit like magic. It’s seen better days though and an upgrade’s well overdue. This HP OfficeJet Pro 8730 looks like it ticks all the same boxes: print, copy, scan, and fax. (Really? Does anyone fax anything any more? I guess it's good to know the facility’s there, just in case.) Printing over WiFi is more-or- less standard these days.

Ed Dawson

HP OfficeJet Pro 8730

As a freelance writer who is always on the go, I like my technology to be both efficient and effective so I can do my job well. The HP OfficeJet Pro 8730 Inkjet Printer ticks all the boxes in terms of form factor, performance and user interface.

Michael Hargreaves

Windows 10 for Business / Dell XPS 13

I’d happily recommend this touchscreen laptop and Windows 10 as a great way to get serious work done at a desk or on the road.

Aysha Strobbe

Windows 10 / HP Spectre x360

Ultimately, I think the Windows 10 environment is excellent for me as it caters for so many different uses. The inclusion of the Xbox app is also great for when you need some downtime too!

Mark Escubio

Windows 10 / Lenovo Yoga 910

For me, the Xbox Play Anywhere is a great new feature as it allows you to play your current Xbox games with higher resolutions and better graphics without forking out extra cash for another copy. Although available titles are still scarce, but I’m sure it will grow in time.

Featured Content

Latest Jobs

Don’t have an account? Sign up here

Don't have an account? Sign up now

Forgot password?