Robotics-based location sensing using wireless ethernet

ABSTRACT

A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location awareness with RF signals have been severely hampered by non-linearity, noise and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-linear signals is a well-studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.

REFERENCES

• 1: A. A. Argyros, K. E. Bekris, and S. C. Orphanoudakis. Robot homing based on corner tracking in a sequence of a panoramic images. In Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recogntion (CVPR 2001), volume~2, pages 3--10, Kauai, Hawaii, Dec. 2001.
• 2: P. Bahl and V. N. Padmanabhan. Enhancements to the RADAR user location and tracking system. Technical Report MSR-TR-2000 12, Microsoft Research, Feb. 2000.
• 3: P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In Proc. of IEEE Infocom 2000, volume~2, pages 775--784, Tel Aviv, Israel, Mar. 2000.
• 4: Wolfram Burgard , Armin B. Cremers , Dieter Fox , Dirk Hähnel , Gerhard Lakemeyer , Dirk Schulz , Walter Steiner , Sebastian Thrun, The interactive museum tour-guide robot, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.11-18, July 1998, Madison, Wisconsin, United States
• 5: A. Chakraborty. A distributed architecture for mobile, location-dependent applications. Master's thesis, Massachusetts Institute of Technology, May 2000.
• 6: H. Choset and K. Nagatani. Topological simultaneous localization and mapping (SLAM): Toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 17(2):125--137, Apr. 2001.
• 7: T. W. Christ and P. A. Godwin. A prison guard duress alarm location system. In Proc. IEEE International Carnahan Conference on Security Technology, Oct. 1993.
• 8: I. Cox. Blanche - an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Transactions on Robotics and Automation, 7(2):193--204, 1991.
• 9: T. Cutler. Wireless Ethernet and how to use it. The Online Industrial Ethernet Book, Issue 5, 1999.
• 10: A. J. Davison and N. Kita. 3D simultaneous localization and map-building using active vision for a robot moving on undulating terrain. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2001), volume 1, pages 384--391, Kauai, Hawaii, Dec. 2001.
• 11: Gregory Dudek , Michael Jenkin, Computational principles of mobile robotics, Cambridge University Press, New York, NY, 2000
• 12: Federal Communcations Commission Report and Order 96-264: Revision of the commission's rules to ensure compatibility with Enhanced 911 emergency calling systems, July 1996. http://www.fcc.gov/Bureaus/Wireless/Orders/1996/fcc96264.txt.
• 13: Dieter Fox , Wolfram Burgard , Frank Dellaert , Sebastian Thrun, Monte Carlo localization: efficient position estimation for mobile robots, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.343-349, July 18-22, 1999, Orlando, Florida, United States
• 14: Dieter Fox , Wolfram Burgard , Hannes Kruppa , Sebastian Thrun, A Probabilistic Approach to Collaborative Multi-Robot Localization, Autonomous Robots, v.8 n.3, p.325-344, June 2000 [doi>10.1023/A:1008937911390]
• 15: D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, (JAIR), 11:391--427, Nov. 1999.
• 16: J. Guivant and E. Nebot. Optimization of the simultaneous localization and map building algorithm for real time implementation. Journal of Robotics Research, 17(10):565--583, 2000.
• 17: P. Harley. Short distance attenuation measurements at 900MHz and 1.8GHz using low antenna heights for microcells. IEEE Journal on Selected Areas in Communications (JSAC), 7(1):5--11, Jan. 1989.
• 18: Andy Harter , Andy Hopper , Pete Steggles , Andy Ward , Paul Webster, The anatomy of a context-aware application, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.59-68, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313476]
• 19: H. Hashemi. Impulse response modeling of indoor radio propagation channels. IEEE Journal on Selected Areas in Communications (JSAC), 11:967--978, Sept. 1993.
• 20: H. Hashemi. The indoor radio propagation channel. Proc. of the IEEE, 81(7):943--968, July 1993.
• 21: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 22: J. Hightower, R. Want, and G. Borriello. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 00-02-02, University of Washington, Department of Computer Science and Engineering, Seattle, WA, Feb. 2000.
• 23: Institute of Electrical and Electronics Engineers, Inc. ANSI/IEEE Standard 802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.
• 24: Kurt Konolige , Ken Chou, Markov Localization using Correlation, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1154-1159, July 31-August 06, 1999
• 25: John Krumm , Steve Harris , Brian Meyers , Barry Brumitt , Michael Hale , Steve Shafer, Multi-Camera Multi-Person Tracking for EasyLiving, Proceedings of the Third IEEE International Workshop on Visual Surveillance (VS'2000), p.3, July 01-01, 2000
• 26: B. Kuipers and Y. T. Byan. A robot exploration and mapping strategy based on a semantic hierarcy of spatial representations. Journal on Robotics and Automatic Systems, 8:47--63, 1991.
• 27: J. F. Leonard and H. Durrant-Whyte. Mobile robot localization by tracking geometric beacons. IEEE Transactions Robotics and Automations, 7(3):376--382, June 1991.
• 28: T. Liu, P. Bahl, and I. Chlamtac. Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks. IEEE Journal on Selected Areas in Communications, 16(6):922--936, Aug. 1998.
• 29: T. Logsdon. Understanding the Navstar: GPS, GIS and IVHS. Second edition. Van Nostrand Reinhold, New York, 1995.
• 30: Guillaume Marceau, The McGill's RedDogs Legged League System, RoboCup 2000: Robot Soccer World Cup IV, p.627-630, January 2001
• 31: A. Neskovic, N. Nescovic, and G. Paunovic. Modern approaches in modeling of mobile radio systems propagation environment. IEEE Communications Surveys, Third Quarter 2000.
• 32: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 33: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 34: Randall C. Smith , Peter Cheeseman, On the representation and estimation of spatial uncertainly, International Journal of Robotics Research, v.5 n.4, p.56-68, Winter, 1987 [doi>10.1177/027836498600500404]
• 35: S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.
• 36: Sebastian Thrun , Wolfram Burgard , Dieter Fox, A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots, Machine Learning, v.31 n.1-3, p.29-53, April/May/June 1998 [doi>10.1023/A:1007436523611]
• 37: Sebastian Thrun , Dieter Fox , Wolfram Burgard , Frank Dallaert, Robust Monte Carlo localization for mobile robots, Artificial Intelligence, v.128 n.1-2, p.99-141, May 2001 [doi>10.1016/S0004-3702(01)00069-8]
• 38: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 39: A. Ward, A. Jones, and A. Hopper. A new location technique for the active office. IEEE Personal Communications, (5):42--47, Oct. 1997.
• 40: Jay Webr , Colin Lanzl, Designing a positioning systems for finding things and people indoors, IEEE Spectrum, v.35 n.9, p.71-78, Sept. 1998 [doi>10.1109/6.715187]
• 41: R. Yamamoto, H. Matsutani, H. Matsuki, T. Oono, and H. Ohtsuka. Position location technologies using signal strength in cellular systems. In Proc. of the 53rd IEEE Vehicular Technology Conference, May 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Sensors
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Design, Experimentation

Keywords:
802.11, localization, mobile systems, probabilistic analysis, wireless networks