Autonomous navigation of mobile agents using RFID-enabled space partitions

ABSTRACT

Existing techniques for autonomous indoor navigation are often environment-specific and thus limited in terms of their applicability. In this paper, we take a fundamentally different approach to indoor navigation and propose an active environment based navigation system. We argue that for a versatile navigation system the environment itself should provide spatial information. In our proposed approach, navigation is based on the concept of space partitions where the location of an agent is approximated by the closest partition. We show that Radio Frequency Identification (RFID) technology is a viable option for generating space partitions. We present a cost effective deployment strategy for passive RFID tags to construct a complete partitioning of the environment. A sparse deployment of tags leads to coarse partitioning, which in turn allows an agent to only approximate its position. We introduce a path planning algorithm that enables an agent reach its destination with a small overhead compared to the shortest path algorithm assuming precise information. Our experiments show that the deployment allows efficient path planning even under a large degree of imprecision.

REFERENCES

• 1: P. Bahl and V. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. In INFOCOM, pages 775--784, 2000.
• 2: J. Bresenham. Algorithm for Computer Control of a Digital Plotter. IBM Systems Journal, 4:25--30, 1965.
• 3: H. Chae and K. Han. Combination of RFID and Vision for Mobile Robot Localization. In ISSNIP, pages 75--80, 2005.
• 4: Andrew J. Davison , David W. Murray, Simultaneous Localization and Map-Building Using Active Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.865-880, July 2002 [doi>10.1109/TPAMI.2002.1017615]
• 5: Guilherme N. DeSouza , Avinash C. Kak, Vision for Mobile Robot Navigation: A Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.237-267, February 2002 [doi>10.1109/34.982903]
• 6: D. Hahnel, W. Burgard, D. Fox, K. Fishkin, and M. Philipose. Mapping and Localization with RFID Technology. In ICRA, pages 1015--1020, 2004.
• 7: Taimur Hassan , Samir Chatterjee, A Taxonomy for RFID, Proceedings of the 39th Annual Hawaii International Conference on System Sciences, p.184.2, January 04-07, 2006 [doi>10.1109/HICSS.2006.32]
• 8: Guang-yao Jin , Xiao-yi Lu , Myong-Soon Park, An Indoor Localization Mechanism Using Active RFID Tag, Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing -Vol 1 (SUTC'06), p.40-43, June 05-07, 2006 [doi>10.1109/SUTC.2006.36]
• 9: R. Kershner. The Number of Circles Covering a Set. A. M. J. Math, 61:665--671, 1939.
• 10: O. Kubitz, M. Berger, M. Perlick, and R. Dumoulin. Application of Radio Frequency Identification Devices to Support Navigation of Autonomous Mobile Robots. In VTS, pages 126--130, 1997.
• 11: V. Kulyukin, C. Gharpure, and J. Nicholson. RoboCart: Toward Robot-Assisted Navigation of Grocery Stores by the Visually Impaired. In IROS, pages 2845--2850, 2005.
• 12: X. Liu, M. Corner, and P. Shenoy. Ferret: RFID Localization for Pervasive Multimedia. In Ubicomp, pages 422--440, 2006.
• 13: Joseph F. McCarthy, Active Environments: Sensing and Responding to Groups of People, Personal and Ubiquitous Computing, v.5 n.1, p.75-77, February 2001 [doi>10.1007/s007790170036]
• 14: Muhammad Atif Mehmood , Lars Kulik , Egemen Tanin, Navigation and interaction in physical spaces using RFID enabled spatial sensing, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322304]
• 15: Mohamed F. Mokbel , Walid G. Aref , Ibrahim Kamel, Analysis of Multi-Dimensional Space-Filling Curves, Geoinformatica, v.7 n.3, p.179-209, September 2003 [doi>10.1023/A:1025196714293]
• 16: Y. Murai, H. Tatsumi, S. Tokumasu, and M. Miyakawa. Autonomous Navigation of RFID-Sensing Robots-Information Ensuring for the Visually Impaired. In SMC, pages 3634--3639, 2005.
• 17: Lionel M. Ni , Yunhao Liu , Yiu Cho Lau , Abhishek P. Patil, LANDMARC: indoor location sensing using active RFID, Wireless Networks, v.10 n.6, p.701-710, November 2004 [doi>10.1023/B:WINE.0000044029.06344.dd]
• 18: 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]
• 19: 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]
• 20: S. Schneegans, P. Vorst, and A. Zell. Using RFID Snapshots for Mobile Robot Self-Localization. In ECMR, pages 241--246, 2007.
• 21: T. Schwartz, B. Brandherm, and D. Heckmann. Calculation of the User-Direction in an Always Best Positioned Mobile Localization System. In AIMS, with MobileHCI, 2005.
• 22: J. Tuttle. Traditional and Emerging Technologies and Applications in the Radio Frequency Identification (RFID) Industry. In RFIC Symposium, pages 5--8, 1997.
• 23: 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]
• 24: A. Ward, A. Jones, and A. Hopper. A New Location Technique for the Active Office. Personal Communications, 4(5):42--47, 1997.
• 25: Scooter Willis , Sumi Helal, RFID Information Grid for Blind Navigation and Wayfinding, Proceedings of the Ninth IEEE International Symposium on Wearable Computers, p.34-37, October 18-21, 2005 [doi>10.1109/ISWC.2005.46]
• 26: K. Yamano, K. Tanaka, M. Hirayama, E. Kondo, Y. Kimuro, and M. Matsumoto. Self-localization of Mobile Robots With RFID System by Using Support Vector Machine. In IROS, pages 3756--3761, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Experimentation, Performance