By Rob Knies
January 25, 2010 11:00 AM PT
You’re planning a party and want to make it easy for your guests to get there. Not a problem, you think: You’ll just send them a map they can use to find their way.
But that can be more challenging than it seems. Because guests are coming from all directions, a map with sufficient context would have too little detail available near the destination. And a map that shows the last few turns to the destination would cover too small an area to get people to the neighborhood. All of a sudden, you have a problem.
Now, though, thanks to work by Johannes Kopf and Michael Cohen of Microsoft Research Redmond and their colleagues, a solution is at hand. In fact, their work, called Destination Maps, has been incorporated as an application plug-in, part of an array of enhancements newly available through Bing Maps: Simply click the Map Apps button at the bottom of the Bing Maps page and select the “Destination maps” app.
Destination Maps are automatically generated to enable anybody within a region to be able to navigate to a specific location. The technology simplifies the details necessary to navigate to your intended destination by highlighting only those highways, main streets, and side roads necessary to get to where you’re going. At the same time, the neighborhood around the destination is enlarged in context.
“Say you want to send a digital map with directions to your home,” says Cohen, a principal researcher in the Interactive Visual Media Group (IVM). “People might be coming from many places. You could take a normal map and just put a dot on the location, but, typically, the little roads near the destination are virtually invisible, because in a map of a large region, you can’t see all the little roads.
“What you’d like to have is a map that creatively expands the area around the destination while leaving some of the outer areas alone, putting more detail near the destination and less detail away from the destination. Ideally, it would be a single map that could tell anybody within the region how to get to that destination.”
Of course, you could attempt to draw your own map, but that is likely to become challenging as you try to include major highways within the region and the appropriate arterial routes to approach the location, then add sufficient neighborhood detail to direct visitors to the proper address. The Bing Maps plug-in takes care of all this for you.
“If I ask you to draw a map of Seattle and the surrounding area and indicate where you live and the roads, you probably have a mental model,” Cohen explains. “You know that one highway runs north and south and that another runs east and west, and that some streets are of a certain size. We would like the map, as much as possible, to conform to that mental model, to end up with something very much like you would draw it.”
To do so, the Destination Maps project provides a generalization of an actual map, with each gradation of road size, from highway to specific small streets, given equal emphasis. Instead of an actual map rendered at scale, the smaller segments are increased in size for legibility, and irrelevant areas are removed to reduce clutter and to make it simple for you to navigate to your desired location.
“You could say, ‘Take the highway for 10 miles, take a right and drive for a mile, then take a left and drive 100 meters,” Cohen says. “Each of these pieces is getting shorter, but, in some ways, each piece carries equal weight.
“We can get you not only from point A to point B, but from anywhere to point B.”
The technology is based on design principles used by mapmakers and uses novel algorithms for selecting the most important roads, based on a non-linear optimization procedure.
“When you have an intersection,” says Kopf, an IVM researcher, “we try to preserve the angles of the streets. But, at the same time, we try to make sure every road segment is long enough so that you can read its label. These are constraints that are fighting against each other, so we have a complicated optimization that tries to meet all these goals at the same time.”
That is something that hasn’t been accomplished before.
“Nobody has ever solved the problem,” Cohen says. “The problem is to encode what we usually think of as a human mental operation, where you have a sense of what it means to get somewhere and what you need to do to communicate to somebody else how to get there. These things are typically very difficult to encode in an algorithm.
“The many parts of that algorithm range from how to select which roads you want to include and to do the proper balancing of being complete yet not cluttered. And the most difficult part is the layout. How do you decide to push a road over a little bit to make some room so you can expand a local region while balancing that against making the map unrecognizable compared to a normal map? Those are the technical challenges.”
To surmount those difficulties, the researchers devised a set of design principles to make the process work.
“One thing, for example,” Kopf says, “is we create rings of roads around the destination that increase from small to larger roads, and connect those to the destination.”
The Destination Maps user specifies a destination by identifying an address on a normal digital map. Once that is complete, the user presses a Continue button that generates a bounding box for the region, which can be adjusted to the desired size, say, a section of a city that contains the major highways one would use to approach the destination.
When the bounding box is defined, pressing Continue again prompts the technology to analyze the small roads surrounding the destination, then look outward to the ring for a set of larger nearby roads, and then outward again to the ring of nearby highways. Those three sets of road segments are identified as the collection of potential roads to be included in the map.
Then Destination Maps identifies routes from the highways to the desired location, crossing each of the three rings, to determine the final set of roads to be included. Once that road selection is complete, then the plug-in determines how to lay them out, expanding the smaller ones for legibility without unduly distorting the rest.
“The assumption,” Kopf notes, “is that you always know how to get to one of the big roads. We don’t need to show you how to get to the big road that leads to the destination, just to show you how to get from that big road to close to your destination, and then all the way to your destination.”
This cartographic generalization, using distortion, simplification, and abstraction, is the key to the technology. The resultant Destination Map might not be really to scale, but then again, even mapmakers attempting to provide as accurate a representation as possible sometimes deploy distortion to include each road segment within a region. Otherwise, some short stretches would never be able to be included at all.
The rendering of Destination Maps helps make it clear that they are not designed to be precisely accurate at scale, but rather as navigational aids. The maps that users see might have a certain hand-drawn look to them, making it easier for people to understand that they are more of an explanatory sketch.
“We select the roads that are important for getting to the location,” Kopf says. “It’s much simpler: If you start here, you know you have to take these roads, and you can read the labels.”
Further steps are taken to make the Destination Maps more user-friendly. An overview of the system:
“We take all the water features—lakes, rivers, wharves—and make them fit the map,” Cohen says. “We put labels on all the streets. And we render it in one of four different styles.”
The rendering styles can be selected to fit the user’s preference. One looks hand-drawn. A European style uses fat roads in which the labels are inserted. An American style inserts the label alongside the road. And a fourth style is designed to resemble a treasure map.
The project has its origins in a Microsoft Research project from 2001 by Maneesh Agrawala, now an associate professor in Electrical Engineering and Computer Sciences at the University of California, Berkeley. His Stanford University Ph.D. dissertation, Visualizing Route Maps, essayed a similar technique applied from a single origin to a single destination. Agrawala and colleagues had begun to consider the more general Destination Maps problem after his dissertation and while he was with Microsoft Research Redmond. Kopf and Cohen recently contacted Agrawala and began to investigate ways to broaden the capabilities of the earlier work. They asked if he would like to consult on completing the ideas.
Since then, Kopf and Cohen have applied Destination Maps to dozens of locations across more than a dozen cities. They’ve also evaluated the effectiveness of their approach.
“We generated a large number of maps and tried to look at them to see what’s going on,” Kopf says. “We also ran some tests to automatically figure out how many roads are too small to be able to read the labels and produce any false turns.”
The proof of their success is indicated by its adoption as one of the initial plug-in applications for the Bing Maps platform. But that doesn’t mean their work is complete.
“What really needs to be done,” Kopf says, “is to evaluate this with users.”
The Bing Maps release will enable that.
“We feel good about getting things right almost all the time,” Cohen says. “But we’re looking forward to getting some user feedback.”
One direction they’re interested in pursuing is user personalization.
“We’ve thought about allowing the user to make changes to the map,” Kopf says, “because people know the best way to get to their house, and sometimes, this is not the way that comes out of an automatic routing algorithm.
“It’s very hard for the algorithm to know about local things, such as how many traffic lights there are or how long it really takes to get there. It would be nice to allow the user to make those changes to the map.”
Another area of ongoing research interest is user annotation.
“If you were going to get married and you create a wedding map,” Cohen says, “you might want to clip out a picture of the church and insert it into the map. Or you might want to help people who want to see the sites, so you could put a well-known landmark in its location.”
Both researchers say that the Destination Maps has been a fascinating project to pursue, doubly so now that it is being made available to the public.
“I have this great job at Microsoft Research where I get to pick and pursue the projects I’m interested in,” Cohen says, “and this one is really interesting, both at the technical level and at the algorithmic level of figuring out how to do it.
“Bing Maps’ app plug-in platform has opened up the world of maps and applications related to maps. It’s been relatively straightforward to build something using Bing Maps as the backdrop. This is a very different model, and I’m pretty excited about seeing what other people do.”
For Kopf, too, the process has proved rewarding.
“It’s really exciting that we can put this online in Bing Maps and everybody is able to user our maps,” Kopf concludes. “I very much like how this came out, how the maps look. In the beginning, we didn’t really know how these maps should look, and I think we got interesting results.”