New indoor navigation system works where GPS can't reach
In the age of GPS and Google Maps, being “lost” may seem like a distant memory. However, navigating in unexplored indoor environments without GPS remains a significant challenge, often with serious implications. For example, quickly locating a firefighter in danger in a large burning building is extremely challenging if no one knows the layout of the building.
Humans are not the only ones that would benefit from navigation aids; in fact autonomous systems often struggle to navigate in environments that we find intuitive. While they can rely on GPS outdoors in the same way that we can, they are often confounded by the complexity of indoor environments, especially those that are unmapped, changing, and full of people.
Peregrine is a system that helps users navigate in indoor environments where GPS is not available, reliable, or sufficiently accurate. Peregrine isn't the first system to attempt to create an "indoor GPS," but it is the first to combine cooperative localization with optimal measurement selection, whereby users exchange signals and information to figure out where they are in relation to one another. Other systems require a building to be outfitted with transponders that can be used as reference points; in comparison, the cooperative localization technique can significantly reduce infrastructure costs, improve localization accuracy, and extend coverage.
In practice, cooperative localization is more complicated than simply allowing users to measure the distance between themselves and other users. Processing these measurements creates a complex, but powerful, network that must be effectively managed to operate efficiently. To do this, Peregrine measures only optimal links between users at any given time, as opposed to linking all users all of the time. This novel navigation framework, named Network Localization and Navigation (NLN), forms a blueprint that can be applied to many domains where GPS is not available.
"The unique piece that Peregrine does is it lets users collaborate with one another from a localization perspective," said Bryan Teague of the Advanced Concepts and Technologies Group at MIT Lincoln Laboratory who spearheaded the development of the Peregrine system. "As we add users to the environment, they can help one another find out where they are.”
Peregrine is composed of two parts: the network navigation framework (NLN) and the Peregrine devices that host it. NLN is the software that selects which links to measure and processes the resulting information to determine users' locations. The algorithm selects the best links based on their signal quality and the relative geometry of the devices; it doesn't measure all the links at once. The Peregrine devices, meanwhile, each consist of a transponder for communication and ranging, a battery, and a low-power processor to run the network navigation software. They are small enough to be used as portable handheld devices or they can be placed at known locations. The Peregrine devices collect the data for NLN to process to determine users' locations.
To understand the potential of Peregrine, picture it this way: six firefighters enter an unfamiliar building. As they enter, they place a Peregrine device by the door, a known location. As they move deeper, they place a few more, by a stairwell, perhaps, or in an atrium. Then, the firefighters split up, and their handheld devices take measurements of the distance between each other as well as between themselves and the deployed devices. NLN uses these measurements to determine each firefighter's location. Peregrine is designed to be a distributed system, meaning that each user is able to calculate and display both their own and nearby users’ positions, either on the screen of a cell phone or in a heads-up display in their helmet. Although things like the name of the room would likely remain unknown, a firefighter would be able to garner much more important information; for instance the relative position of the exit and the location of the other five firefighters.
Teague developed Peregrine under the guidance of Professor Moe Win of the Laboratory for Information and Decision Systems at MIT. At the time, Teague was a graduate student supported by the Lincoln Scholars program, which helps Lincoln Laboratory employees to attend graduate school while continuing to work at the Laboratory. He took the theoretical concepts that researchers and students, including MIT postdoctoral researcher Florian Meyer, had developed and built a functioning prototype. "Working with students from MIT and Lincoln Laboratory was very synergetic," Meyer said. "While at MIT, we established algorithms that are involved from a theoretical point; engineers at Lincoln Laboratory have the capabilities to develop a working platform, based on these rather theoretical results, in record time."
In 2018, the Peregrine system was honored with an R&D 100 Award for the originality of its network navigation framework. This award is given annually by R&D Magazine to 100 technologies judged to be the year's most innovative. Peregrine was one of ten R&D 100 Awards winners from Lincoln Laboratory.
Researchers at Lincoln Laboratory picture a number of future applications of the technology that Peregrine demonstrated, particularly in the area of autonomy. The navigation framework in Peregrine is generalized so that a "user" can be a person, a static device, or a mobile autonomous system. This generalization provides a blueprint that can help people, swarms of robots, and even mixed teams of humans and autonomous systems navigate. Teague and his team at Lincoln Laboratory envision a number of improvements for the next system, including algorithm enhancements, increased range, fusion with additional sensors, and improved battery life. “The novelty is not necessarily solving localization indoors," Teague said. "It’s the ability to link users in an effective and scalable way for the purposes of localization and navigation."