MIT Technology Review

Wednesday, August 18, 2010

Finding Our Way with Digital Bread Crumbs

A Microsoft research project explores whether sensors in mobile devices could help us navigate without GPS.

In the classic tale by the Brothers Grimm, Hansel and Gretel leave a trail of bread crumbs from their home so as not to get lost in the forest, but the plan fails when birds eat the crumbs. In the modern world, a GPS device could assist the fabled siblings. But what if they wandered into a place without GPS signals?

With that kind of problem in mind, a team of researchers at Microsoft set out to create a mobile device that could forge a trail of "digital bread crumbs." The device would collect the trail data while the user walked indoors, underground, or in other spaces where GPS signals are unavailable or weak--such as multilevel parking garages that can baffle people who forget where they parked.

The resulting Microsoft Research device, a prototype phone called Menlo, packs a suite of sensors: an accelerometer to detect movement, a side-mounted compass to determine direction, and a barometric pressure sensor to track changes in altitude.

While existing phones contain some of these sensors, what's new about Menlo is an app called Greenfield, which aims to solve the Hansel and Gretel problem by harnessing the data from the sensors. The goal is to count a user's sequence of steps, gauge direction changes, and even calculate how many floors the user has traversed by stairs or an elevator. The app stores the trail data so that a user can later retrace his path precisely.

The researchers call Greenfield an example of "activity-based navigation." In a paper to be presented at the MobileHCI conference in Lisbon, Portugal, next month, the Microsoft team positions Greenfield as an ideal method of navigation in places where maps haven't been constructed or aren't accessible. For the paper, computer scientist A.J. Brush and her team conducted a trial in which people had to retrieve an object from a colleague's parked car in a large garage, using the coworker's trail data to navigate the way.

"I knew this was possible, but I was wondering when someone would put all the pieces together," says Jeff Fischbach, a forensic technologist with SecondWave Information Systems, a consulting firm in Chatsworth, CA. Fischbach often serves as an expert witness in criminal trials in which GPS data is used as evidence. He says that trail data from an app like Greenfield could help determine whether a murder suspect is truthfully stating an alibi. "This kind of data is terrific for convicting people and terrific at exonerating people."

But since such trail data can be retrieved, transmitted to the Internet, and even subpoenaed by the government, this raises the most extreme sort of privacy issues. "How can you control who has access to the data?" Fischbach says. And would employers use it to keep close track of their workers?

The potential applications are numerous. Greenfield could be used for new kinds of urban street games, to recover lost items, to find friends at a stadium, or to rescue hikers and mountain climbers. The researchers cite a 2002 book, Inner Navigation, by engineer Erik Jonnson, who argues that everyone struggles with creating "cognitive maps." Even those who have an excellent sense of direction can be tricked by their own recall, sometimes remembering landscapes in precisely opposite layouts. "I think people have an inner compass," Jonnson says, "and when it goes wrong, the most amazing things happen."

In their test at two different parking garages--one with GPS signals and one without--the Microsoft team started subjects in an adjacent office building and handed each of them a piece of paper listing the color, make, model, and license plate number of a colleague's car. (This kind of problem was familiar to most of the study's participants; one said that losing track of a car in a garage is "catastrophic.") The subjects were given a Menlo device running Greenfield, which had recorded an activity trail, for use in retracing the way back. In some cases, the trail data was enhanced by photographs taken along the route.

Every participant in the study found every car, at least eventually. But since several configurations of bread-crumb data were tested, there was wide variation in how long it took each subject, depending on what kind of information was displayed. Even when they were told what garage floor and quadrant the car was on, subjects often forgot and had to rely on the device for direction.