Using Angle of Arrival (Bearing) Information for Localization in Robot Networks

In this paper, we consider using angle of arrival information (bearing) for localization in robot networks. The essential property we require in this paper is that a node can infer heading information from its neighbors. We address the uniqueness of network localization solutions by the theory of globally rigid graphs. We show that while the parallel rigidity problem for formations with bearings is isomorphic to the distance case, the global rigidity of the formation is simpler (in fact identical to the simpler rigidity case) for a network with bearings, compared to formations with distances. We provide the conditions of localization for networks in which the neighbor relationship is not necessarily symmetric.

Using Angle of Arrival (Bearing) Information for Localization in Robot Networks

In this paper, we consider using angle of arrival information (bearing) for localization in robot networks. The essential property we require in this paper is that a node can infer heading information from its neighbors. We address the uniqueness of network localization solutions by the theory of globally rigid graphs. We show that while the parallel rigidity problem for formations with bearings is isomorphic to the distance case, the global rigidity of the formation is simpler (in fact identical to the simpler rigidity case) for a network with bearings, compared to formations with distances. We provide the conditions of localization for networks in which the neighbor relationship is not necessarily symmetric.

___

  • T. He, C. Huang, B. Blum, J. Stankovic, T. Abdelzaher, “Range-free localization schemes in large scale sensor networks,” Univ. of Virginia, Tech. Rep. CS-TR2003-06, 2003. [Online]. Available: http://citeseer.nj.nec.com/he03rangefree.html
  • D. Moore, J. Leonard, D. Rus, S. Teller, “Robust distributed network localization with noisy range measure- ments,” in Proceeding of the Second ACMConference on Embedded Networked Sensor Systems, November 2004.
  • A. Das, J. Spletzer, V. Kumar, C. Taylor, “Ad hoc for localization and control,” in Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, 2002. B. Karp, H. T. Kung, “GPSR:Greedy perimeter stateless routing for wireless net- works,” in Proceedings of Mobicom , Boston, MA, August Online]. Available: http://www.acm.org/pubs/contents/proceedings/comm/345910/
  • M. Weiser, “Some computer science problems in ubiquitous computing,” Communications of ACM, July 1993.
  • B. Hofmann-Wellenhof, H. Lichtenegger, J. Collins, Global Positioning System: Theory and Practice. Springer- Verlag, 1997.
  • J. Aspnes, T. Eren, D. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson, P. N. Belhumeur, “A theory of network localization,” IEEE Transactions on Mobile Computing, vol. 5, no. 12, pp. 1663–1678, December 2006.
  • R. Olfati-Saber, R. Murray, “Distributed structural stabilization and tracking for formations of dynamic multi- agents,” in Proceedings of the 41st IEEE Conference on Decision and Control, vol. 1, Las Vegas, NV, December , pp. 209–215. J. Baillieul, A. Suri, “Information patterns and hedging Brockett’s theorem in controlling vehicle formations,” in Proceedings of the 42nd IEEE Conference on Decision and Control, vol. 1, Maui, Hawaii, December 2003, pp. – 563.
  • P. Tabuada, G. Pappas, P. Lima, “Feasible formations of multi-agent systems,” in Proceedings of the American Control Conference, 2001, pp. 56–61.
  • H. G. Tanner, G. J. Pappas, V. Kumar, “Leader-to-formation stability,” IEEE Transactions on Robotics and Automation, vol. 20, no. 3, pp. 443–455, June 2004.
  • D. Niculescu, B. Nath, “Ad hoc positioning system (APS) using AoA,” in Proceedings of IEEE INFOCOM’03, vol. 3, San Francisco, CA, April 2003, pp. 1734– 1743.
  • W. Whiteley, “Matroids from discrete geometry,” in Matroid Theory, J. E. Bonin, J. G. Oxley, B. Servatius, Eds. American Mathematical Society, Contemporary Mathematics, 1996, vol. 197, pp. 171–313.
  • T. Eren, W. Whiteley, A. S. Morse, P. N. Belhumeur, B. D. O. Anderson, “Sensor and network topologies of formations with direction, bearing and angle information between agents,” in Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, Hawaii, December 2003, pp. 3064–3069.
  • T. Eren, W. Whiteley, P. N. Belhumeur, “Using angle of arrival (bearing) information in network localization,” in Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, California, December 2006.
  • N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, R. L. Moses, N. S. Correal, “Locating the nodes:cooperative localization in wireless sensor networks,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 54–69, July 2005.
  • J. Ash, L. Potter, “Sensor network localization via received signal strength measurements with directional anten- nas,” Proceedings of the Forty-Second Annual Allerton Conference on Communication, Control, and Computing, pp. 1861–1870, Champaign-Urbana , IL, Sep 2004.
  • F. Zhang, B. Grocholsky, V. Kumar, “Formations for localization of robot networks,” in Proceedings of the 2004
  • IEEE International Conference on Robotics and Automation, vol. 3, April 2004, pp. 3369– 3374.
  • T. Eren, P. Belhumeur, A. Morse, “Closing ranks in vehicle formations based on rigidity,” in Proceedings of the st IEEE Conference on Decision and Control, December 2002, pp. 2959–2964.
  • T. Eren, P. Belhumeur, B. Anderson, A. Morse, “A framework for maintaining formations based on rigidity,” in Proceedings of the 15th IFAC World Congress, Barcelona, Spain, July 2002, pp. 2752–2757.
  • T. Eren, W. Whiteley, B. D. O. Anderson, A. S. Morse, P. N. Belhumeur, “Information structures to secure control of rigid formations with leader-follower architecture,” in Proceedings of the American Control Conference, Portland, Oregon, June 2005, pp. 2966–2971.
  • T. Eren, W. Whiteley, P. Belhumeur, “Rigid formations with leader-follower architeture,” Columbia University, Tech. Rep. CUCS-010-05, March 2005. [Online]. Available:http://www1.cs.columbia.edu/∼library/
  • ——, “Rigid formations with leader-follower architeture,” Columbia University, Tech. Rep. CUCS-008-06, December 2005. [Online]. Available:http://www1.cs.columbia.edu/∼library/
  • J. M. Hendrickx, B.D.O. Anderson, V. D. Blondel, “Rigidity and persistence of directed graphs,” in Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, Seville, Spain, December 2005, pp. 2176–2181.
  • C. Yu, B. Fidan, B. D. O. Anderson, “Persistence acquisition and maintenance for autonomous formations,” in Proceedings of Workshop on Unmanned Aerial Vehicles, 2nd International Conference on Intelligent Sensors, Melbourne, Australia, December 2005, pp. 379–384.
  • B. Fidan, C.Yu, B. D. O. Anderson, “Acquiring and maintaining persistence of autonomous multi-vehicle formations,” IET Control Theory and Applications, vol. 1, no. 2, pp. 452–460, March 2007.
  • J. Blum, M. Ding, A. Thaeler, X. Cheng, “Connected dominating set in sensor networks and MANETs,” in Handbook of Combinatorial Optimization, D.-Z. Du, P. Pardalos, Eds. –369. Kluwer Academic Publishers, 2004, pp.
  • P. Gober, A. Ziviani, P. Todorova, M. D. de Amorim, P. Hueneberg, S. Fdida, “Topology control and localization in wireless ad-hoc and sensor networks,” Ad Hoc & Sensor Wireless Networks: An International Journal, vol. 1, no. 2, pp. 301–321, March 2005.
  • R. Connelly, “Generic global rigidity,” Discrete Comput. Geom., vol. 33, no. 4, pp. 549–563, April 2005.
  • W. Whiteley, “Rigidity and scene analysis,” in Handbook of Discrete and Computational Geometry, J. Goodman, J. O’Rourke, Eds. CRC Press, 1997, pp. 893–916.
  • B. Servatius, W. Whiteley, “Constraining plane conŞgurations in Computer Aided Design: Combinatorics of directions and lengths,” SIAMJournal of Discrete Mathematics, vol. 12, pp. 136–153, 1999.
  • W. Whiteley, “Parallel redrawing of conŞgurations in 3-space,” 1986, preprint.
  • ——, “A matroid on hypergraphs, with applications to scene analysis and geometry,” Discrete and Computa- tional Geometry, vol. 4, pp. 75–95, 1988.
  • ——, “Constraining plane conŞgurations in CAD:geometry of lengths and directions,” 1997, preprint.
  • B. Servatius, W. Whiteley, “Constraining plane conŞgurations in Computer Aided Design: Combinatorics of directions and lengths,” 1995, preprint, York University, North York, Ontario.