Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-20T18:30:00.086Z Has data issue: false hasContentIssue false
  • English
  • Français

A closed-form algorithm for the least-squares trilateration problem

Published online by Cambridge University Press:  20 May 2010

Yu Zhou
Yu Zhou*
Affiliation:
Department of Mechanical Engineering, State University of New York at Stony Brook, Stony Brook, NY 11794, USA
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Trilateration is the most adopted external reference-based localization technique for mobile robots, given the correspondence of external references. The nonlinear least-squares trilateration formulation provides an optimal position estimate from a general number (greater than or equal to the dimension of the environment) of reference points and corresponding distance measurements. This paper presents a novel closed-form solution to the nonlinear least-squares trilateration problem. The performance of the proposed algorithm in dealing with erroneous inputs of reference points and distance measurements has been analyzed through representative examples. The proposed trilateration algorithm has low computational complexity, high operational robustness, and reduced systematic error and uncertainty in position estimation. The effectiveness of the proposed algorithm has been further verified through an experimental test.

Keywords

LocalizationTrilaterationMobile robot
Type
Article
Information
Robotica , Volume 29 , Issue 3 , May 2011 , pp. 375 - 389
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Borenstein, J., Everett, H. R., Feng, L. and Wehe, D., “Mobile robot positioning: Sensors and techniques,” J. Robot. Syst. 14 (4), 231–249 (1997).3.0.CO;2-R>CrossRefGoogle Scholar
2. “Multilateration,” Wikimedia Foundation, Inc. [Online]. Available http://en.wikipedia.org/wiki/Multilateration.Google Scholar
3.El-Rabbany, A., Introduction to GPS: The Global Positioning System (Artech House, Norwood, MA, 2002).Google Scholar
4.Ashkenazi, V., Park, D. and Dumville, M., “Robot positioning and the global navigation satellite system,” Ind. Robot 27 (6), 419–426 (2000).CrossRefGoogle Scholar
5.Folster, F. and Rohling, H., “Data association and tracking for automotive radar networks,” IEEE Trans. Intell. Transp. Syst. 6 (4), 370–377 (2005).Google Scholar
6.Ward, A., Jones, A. and Hopper, A., “A new location technique for the active office,” IEEE Pers. Commun. 4 (5), 42–47 (1997).Google Scholar
7.Bahl, P. and Padmanabhan, V. N., “User Location and Tracking in an In-building Radio Network,” Microsoft Research Technical Report MSR-TR-99-12, Redmond, WA, Microsoft Corporation (1999).Google Scholar
8.Hightower, J., Borriello, G. and Want, R., “SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength,” UW CSE Technical Report 2000-02-02 (University of Washington, Seattle, WA, 2000).Google Scholar
9.Priyantha, N. B., Chakraborty, A. and Balakrishnan, H., “The Cricket Location-Support System,” Sixth ACM/IEEE International Conference on Mobile Computing and Networking, Boston, MA (2000), pp. 32–43.Google Scholar
10.Harter, A., Hopper, A., Steggles, P., Ward, A. and Webster, P., “The anatomy of a context-aware application,” Wirel. Netw. 1, 1–16 (2001).Google Scholar
11.Ahmad, F. and Amin, M. G., “Noncoherent approach to through-the-wall radar localization,” IEEE Trans. Aerosp. Electron. Syst. 42 (4), 1405–1419 (2006).Google Scholar
12.Zhou, Y., Liu, W. and Huang, P., “Laser-Activated RFID-Based Indoor Localization System for Mobile Robots,” Proceedings of 2007 IEEE International Conference on Robotics and Automation, Roma, Italy (2007) pp. 4600–4605.CrossRefGoogle Scholar
13.Manolakis, D. E., “Efficient solution and performance analysis of 3-D position estimation by trilateration,” IEEE Trans. Aerosp. Electron. Syst. 32 (4), 1239–1248 (1996).Google Scholar
14.Fang, B., “Trilateration and extension to global positioning system navigation,” J. Guid. 9 (6), 715–717 (1986).CrossRefGoogle Scholar
15.Ziegert, J. and Mize, C. D., “The laser ball bar: a new instrument for machine tool metrology,” Precis. Eng. 16 (4), 259–267 (1994).Google Scholar
16.Rao, S. K., “Comments on “efficient solution and performance analysis of 3-D position estimation by trilateration,” IEEE Trans. Aerosp. Electron. Syst. 34 (2), 681 (1998).Google Scholar
17.Thomas, F. and Ros, L., “Revisiting trilateration for robot localization,” IEEE Trans. Robot. 21 (1), 93–101 (2005).Google Scholar
18.Coope, I. D., “Reliable computation of the points of intersection of n spheres in Rn,” Aust. N.Z. Ind. Appl. Math. J. 42 (E), C461–C477 (2000).Google Scholar
19.Foy, W. H., “Position-location solutions by Taylor-series estimation,” IEEE Trans. Aerosp. Electron. Syst. AES-12 (2), 187–194 (1976).CrossRefGoogle Scholar
20.Navidi, W., Murphy, W. S. Jr. and Hereman, W., “Statistical methods in surveying by trilateration,” Comput. Stat. Data Anal. 27, 209–217 (1998).Google Scholar
21.Hu, W. C. and Tang, W. H., “Automated least-squares adjustment of triangulation-trilateration figures,” J. Surv. Eng. 133–142 (2001).CrossRefGoogle Scholar
22.Pent, M., Spirito, M. A. and Turco, E., “Method for positioning GSM mobile stations using absolute time delay measurements,” Electron. Lett. 33 (24), 2019–2020 (1997).Google Scholar
23.Spall, J. C., Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Hoboken, NJ (John Wiley & Sons, 2005).Google Scholar
24.Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P., “Optimization by simulated annealing,” Science 220 (4598), 671–680 (1983).Google Scholar
25.Coley, D. A., An Introduction to Genetic Algorithms for Scientists and Engineers (World Scientific, Singapore, 1999).Google Scholar
26.Zhou, Y., “An efficient Least-Squares Trilateration Algorithm for Mobile Robot Localization,” Proceedings of 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (St. Louis, MO, 2009).Google Scholar
27.Golub, G. H. and Van Loan, C. F., Matrix Computations, 3rd ed. (The Johns Hopkins University Press, Baltimore, MD, 1996).Google Scholar
28.Kreyszig, E., Advanced Engineering Mathematics, 8th ed. (John Wiley & Sons, New York, 1999).Google Scholar
29.Weinmann, A., Uncertain Models and Robust Control (Springer-Verlag, Wien, New York, 1991).CrossRefGoogle Scholar
30.Urena, J., Hernandez, A., Jimenez, A., Villadangos, J. M., Mazo, M., Garcia, J. C., Garcia, J. J., Alvarez, F. J., De Marziani, C., Perez, M. C., Jimenez, J. A., Jimenez, A. R. and Seco, F., “Advanced sensorial system for an acoustic LPS,” Microprocess. Microsyst. 31, 393–401 (2007).CrossRefGoogle Scholar
31.Cheng, X., Shu, H., Liang, Q. and Du, D. H., “Silent positioning in underwater acoustic sensor networks,” IEEE Trans. Veh. Technol. 57 (3), 1756–1766 (2008).CrossRefGoogle Scholar