×

Sensor network localization on the group of three-dimensional displacements. (English) Zbl 1330.90016

Summary: We consider the problem of estimating relative configurations of nodes in a sensor network based on noisy measurements. By exploiting the cyclic constraints induced by the sensing topology to the network, we derive a constrained optimization on \(\mathrm{SE}(3)^n\). For the case of a network with a single cyclic constraint, we present a closed-form solution. We show that, in certain cases, namely restriction to pure rotation and pure translation, this solution is independent of the particular representation of the constraint function and is the unique, constrained minimizer of an appropriate cost. For sensing topologies represented by a general, weakly connected digraph, we present a solution method which is based on the limits of the solution curves of a continuous-time ordinary differential equation. We show that solutions obtained by our method satisfy all semicycle (generalized cycle) constraints induced by the sensing topology of the network. Further, we show through numerical simulation that for “Gaussian-like” noise models with small variance, our solution achieves noise reduction comparable to that of the least squares estimator for an analogous linear problem.

MSC:

90B10 Deterministic network models in operations research
90C30 Nonlinear programming
Full Text: DOI

References:

[1] R. Abraham, J. E. Marsden, and T. S. Ratiu, {\it Manifolds, Tensor Analysis, and Applications}, Appl. Math. Sci. 75, 2nd ed., Springer-Verlag, New York, 1988. · Zbl 0875.58002
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, {\it Optimization Algorithms on Matrix Manifolds}, Princeton University Press, Princeton, NJ, 2007. · Zbl 1147.65043
[3] P.-A. Absil and J. Malick, {\it Projection-like retractions on matrix manifolds}, SIAM J. Optim., 22 (2012), pp. 135-158. · Zbl 1248.49055
[4] R. L. Adler, J. P. Dedieu, J. Y. Margulies, M. Martens, and M. Shub, {\it Newton’s method on Riemannian manifolds and a geometric model for the human spine}, IMA J. Numer. Anal., 22 (2002), pp. 359-390. · Zbl 1056.92002
[5] C. Altafini, {\it The De Casteljau algorithm on SE(3)}, in Nonlinear Control in the Year 2000, A. Isidori, F. Lamnabhi-Lagarrigue, and W. Respondek, eds., Springer, London, 2001, pp. 23-34. · Zbl 1239.70013
[6] E. Amaldi, L. Liberti, and F. Maffioli, {\it Algorithms for finding minimum fundamental cycle bases in graphs}, Electron. Notes Discrete Math., 17 (2004), pp. 29-33. · Zbl 1152.05370
[7] J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. Belhumeur, {\it A theory of network localization}, IEEE Trans. Mobile Comput., 5 (2006), pp. 1663-1678.
[8] P. Barooah and J. P. Hespanha, {\it Estimation from relative measurements: Algorithms and scaling laws}, IEEE Control Syst. Mag., 27 (2007), pp. 57-74.
[9] P. Barooah and J. P. Hespanha, {\it Error scaling laws for linear optimal estimation from relative measurements}, IEEE Trans. Inform. Theory, 55 (2009), pp. 5661-5673. · Zbl 1367.94078
[10] N. Boumal, A. Singer, P.-A. Absil, and V. D. Blondel, {\it Cramér-Rao bounds for synchronization of rotations}, Inf. Inference, 3 (2014), pp. 1-39. · Zbl 1308.94041
[11] P. Brida, J. Duha, and M. Krasnovsky, {\it On the accuracy of weighted proximity based localization in wireless sensor networks}, in Personal Wireless Communications, IFIP–The International Federation for Information Processing 245, R. Bestak, B. Simak, and E. Kozlowska, eds., Springer, Boston, 2007, pp. 423-432.
[12] F. Bullo and A. D. Lewis, {\it Geometric Control of Mechanical Systems. Modeling, Analysis, and Design for Simple Mechanical Control Systems}, Springer-Verlag, New York, Heidelberg, Berlin, 2004. · Zbl 1066.70002
[13] F. Bullo and R. M. Murray, {\it Proportional Derivative (PD) Control on the Euclidean Group}, Technical Report Caltech/CDS 95-010, California Institute of Technology, Pasadena, CA, 1995; available online at http://resolver.caltech.edu/CaltechCDSTR:1995.CIT-CDS-95-010.
[14] M. Cao, B. D. O. Anderson, and A. S. Morse, {\it Sensor network localization with imprecise distance measurements}, Systems Control Lett., 55 (2006), pp. 887-893. · Zbl 1111.68003
[15] K. Daniilidis, {\it Hand-eye calibration using dual quaternions}, Internat. J. Robotics Res., 18 (1999), pp. 286-298.
[16] L. Doherty, K. S. J. Pister, and L. El Ghaoui, {\it Convex position estimation in wireless sensor networks}, in Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, AK, 2001, pp. 1655-1663.
[17] G. Dubbelman, P. Hansen, B. Browning, and M. B. Dias, {\it Orientation only loop-closing with closed-form trajectory bending}, in Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, 2012, pp. 815-821.
[18] S. Esquivel, F. Woelk, and R. Koch, {\it Calibration of a multi-camera rig from non-overlapping views}, in Pattern Recognition, F. A. Hamprecht, C. Schnörr, and B. Jähne, eds., Springer-Verlag, Berlin, Heidelberg, 2007, pp. 82-91.
[19] P. T. Fletcher, {\it Geodesic regression and the theory of least squares on Riemannian manifolds}, Int. J. Comput. Vis., 105 (2013), pp. 171-185. · Zbl 1304.62092
[20] L. R. Foulds, {\it Graph Theory Applications}, Universitext, Springer-Verlag, New York, 1995. · Zbl 0747.05001
[21] G. Galbiati and E. Amaldi, {\it On the approximability of the minimum fundamental cycle basis problem}, in Approximation and Online Algorithms, Lecture Notes in Comput. Sci. 2909, Springer, Berlin, 2004, pp. 151-164. · Zbl 1173.68862
[22] C. Gramkow, {\it On averaging rotations}, J. Math. Imaging Vision, 15 (2001), pp. 7-16. · Zbl 1012.68209
[23] V. Guillemin and A. Pollack, {\it Differential Topology}, AMS, Providence, RI, 2010. · Zbl 1420.57001
[24] R. Hartley, J. Trumpf, Y. Dai, and H. Li, {\it Rotation averaging}, Int. J. Comput. Vis., 103 (2013), pp. 1-39. · Zbl 1270.68346
[25] R. Horaud and F. Dornaika, {\it Hand-eye calibration}, Internat. J. Robotics Res., 14 (1995), pp. 195-210.
[26] D. Q. Huynh, {\it Metrics for \textup3D rotations: Comparison and analysis}, J. Math. Imaging Vision, 35 (2009), pp. 155-164. · Zbl 1490.68249
[27] T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, and K. A. Zweig, {\it Cycle bases in graphs characterization, algorithms, complexity, and applications}, Comput. Sci. Rev., 3 (2009), pp. 199-243. · Zbl 1301.05195
[28] G. Mao, B. Fidan, and B. D. O. Anderson, {\it Wireless sensor network localization techniques}, Comput. Netw., 51 (2007), pp. 2529-2553. · Zbl 1120.68021
[29] D. Moore, J. Leonard, D. Rus, and S. Teller, {\it Robust distributed network localization with noisy range measurements}, in Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, ACM, New York, 2004, pp. 50-61.
[30] R. M. Murray, Z. Li, and S. S. Sastry, {\it A Mathematical Introduction to Robotic Manipulation}, CRC Press, Boca Raton, FL, 1994. · Zbl 0858.70001
[31] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, R. L. Moses, and N. S. Correal, {\it Locating the nodes: Cooperative localization in wireless sensor networks}, IEEE Signal Processing Mag., 22 (2005), pp. 54-69.
[32] N. Patwari, A. O. Hero, and M. Perkins, {\it Relative location estimation in wireless sensor networks}, IEEE Trans. Signal Process., 51 (2003), pp. 2137-2148.
[33] G. Piovan, I. Shames, B. Fidan, F. Bullo, and B. D. O. Anderson, {\it On frame and orientation localization for relative sensing networks}, Automatica J. IFAC, 49 (2013), pp. 206-213. · Zbl 1258.93012
[34] S. I. Roumeliotis and G. A. Bekey, {\it Distributed multirobot localization}, IEEE Trans. Robot. Autom., 18 (2002), pp. 781-795.
[35] G. C. Sharp, S. W. Lee, and D. K. Wehe, {\it Multiview registration of \textup3D scenes by minimizing error between coordinate frames}, IEEE Trans. Pattern Anal. Mach. Intell., 26 (2004), pp. 1037-1050.
[36] K. H. Strobl and G. Hirzinger, {\it Optimal hand-eye calibration}, in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, 2006, pp. 4647-4653.
[37] M. M. Sysło, {\it On cycle bases of a graph}, Networks, 9 (1979), pp. 123-132. · Zbl 0418.05047
[38] R. Tron and R. Vidal, {\it Distributed 3-D localization of camera sensor networks from 2-D image measurements}, IEEE Trans. Automat. Control, 59 (2014), pp. 3325-3340. · Zbl 1360.94048
[39] J. Wang, R. K. Ghosh, and S. K. Das, {\it A survey on sensor localization}, J. Control Theory Appl., 8 (2010), pp. 2-11. · Zbl 1240.68006
[40] Y. Xu, Y. Ouyang, Z. Le, J. Ford, and F. Makedon, {\it Mobile anchor-free localization for wireless sensor networks}, in Distributed Computing in Sensor Systems, Lecture Notes in Comput. Sci. 4549, J. Aspnes, C. Scheideler, A. Arora, and S. Madden, eds., Springer-Verlag, Berlin, Heidelberg, 2007, pp. 96-109.
[41] M. Žefran, V. Kumar, and C. Croke, {\it On the generation of smooth three-dimensional rigid body motions}, IEEE Trans. Robot. Autom., 14 (1998), pp. 576-589.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.