The Location Stack: Design, Implementation, and Use of Probabilistic Multi-sensor Location Systems

April 29, 2004
Jeffrey Hightower | University of Washington

Many emerging mobile computing applications need to know the physical location of things so that they can record them and report them to us: Where did I take these photographs? Is anyone on my buddy-list nearby? What is the best route to the restaurant given current traffic? Answering these and similar questions has inspired development of many systems to locate people, devices, and other objects. Because each system solves a slightly different problem or supports different applications, they vary in many parameters including the physical phenomena used to determine location, form factor of the sensing apparatus, power requirements, infrastructure versus portable elements, cost, and resolution in time and space. Not surprisingly, no approach produces error-free location measurements or is ideal in all situations. For example, current GPS receivers are ineffective indoors while infrared proximity badge systems, which do work well indoors, use infrastructure too cumbersome to deploy ubiquitously. What is needed is a software design framework allowing multiple sensing technologies to exist under a single Location Programming Interface and probabilistic algorithms to capture and operate on uncertain sensor information. My thesis work, The Location Stack, addresses both needs.

In this talk, I begin with a survey and taxonomy of location systems that led to The Location Stack, a six-layer software abstraction for building location-enhanced computing systems. The Location Stack has made a significant impact in the community including research adoption by Place Lab, commercial adoption by Intel, and community adoption through a probabilistic
location-estimation library which has been downloaded over 200 times. In studies of these external adoptions, the Location Stack has been shown to partition research and development problems appropriately, standardize vocabulary, and promote reuse of hardware and software. The second part of this talk presents empirical analyses showing the benefits of a probabilistic approach to location-estimation. Specifically, I show that Bayesian filtering techniques like particle filters are an accurate, flexible, and practical tool to manage measurement uncertainty, perform multi-sensor fusion, and support a rich location programming interface on heterogeneous devices. In addition, colleagues and I developed extensions to increase performance of particle
filters using learned motion structure and we realized a solution to the previously challenging goal of fusing anonymous and ID location sensors. I conclude with my future interests including fundamental algorithmic work to improve performance of sampling algorithms, public adoption of
location-enhanced computing, a “place” abstraction on coordinates, and the challenge of inferring human activity from sensor data.

Speaker Details

Jeffrey is a doctoral candidate at the University of Washington Department of Computer Science and Engineering. He holds an MS from the same and a BS from the University of Colorado, Boulder. His research area is ubiquitous computing: employing devices, services, sensors, and algorithms so computing calmly fades into the background of daily life. Jeffrey spent summers 1999 and 2000 at Xerox PARC working on ad hoc wireless location sensing and was a 2000-2002 Microsoft Research Fellow. He is currently working with Intel Research Seattle on the Place Lab initiative to make location-enhanced computing simple and ubiquitous.