A New Three Object Triangulation Algorithm for Mobile Robot Positioning

[en] Positioning is a fundamental issue in mobile robot applications. It can be achieved in many ways. Among them, triangulation based on angles measured with the help of beacons is a proven technique. Most of the many triangulation algorithms proposed so far have major limitations. For example, some of them need a particular beacon ordering, have blind spots, or only work within the triangle defined by the three beacons. More reliable methods exist; however, they have an increasing complexity or they require to handle certain spatial arrangements separately. In this paper, we present a simple and new three object triangulation algorithm, named ToTal, that natively works in the whole plane, and for any beacon ordering. We also provide a comprehensive comparison between many algorithms, and show that our algorithm is faster and simpler than comparable algorithms. In addition to its inherent efficiency, our algorithm provides a very useful and unique reliability measure, assessable anywhere in the plane, which can be used to identify pathological cases, or as a validation gate in Kalman filters.

Research Center/Unit :

Telecommunications and Imaging Laboratory (TELIM)
Intelsig

Disciplines :

Electrical & electronics engineering

Author, co-author :

Pierlot, Vincent ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)

Van Droogenbroeck, Marc ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Télécommunications

Language :

English

Title :

A New Three Object Triangulation Algorithm for Mobile Robot Positioning

Publication date :

June 2014

Journal title :

IEEE Transactions on Robotics

ISSN :

1552-3098

eISSN :

1941-0468

Publisher :

IEEE, Piscataway, United States - New Jersey

Volume :

Issue :

Pages :

566-577

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6693716
http://www.telecom.ulg.ac.be/publi/publications/pierlot/Pierlot2014ANewThree/

Name of the research project :

Eurobot

Commentary :

Source code available at http://www.telecom.ulg.ac.be/triangulation See also http://www.telecom.ulg.ac.be/publi/publications/pierlot/Pierlot2014ANewThree/ for an HTML version of the document

Available on ORBi :

since 22 October 2013

Statistics

Number of views

337 (35 by ULiège)

Number of downloads

2128 (17 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Bibliography

D. Avis and H. Imai, "Locating a robot with angle measurements, " J. Symbol. Comput., vol. 10, pp. 311-326, Aug. 1990.
A. Bais, R. Sablatnig, and J. Gu, "Single landmark based self-localization of mobile robots, " in Proc. 3rd Can. Conf. Comput. Robot Vis. (CRV). IEEE Comput. Soc., Jun. 2006.
M. Betke and L. Gurvits, "Mobile robot localization using landmarks, " IEEE Trans. Robot. Autom., vol. 13, no. 2, pp. 251-263, Apr. 1997.
J. Borenstein, H. Everett, and L. Feng, "Where amI? Systems and methods for mobile robot positioning, " Univ. Michigan, Ann Arbor, MI, USA, Tech. Rep., Mar. 1996.
J. Borenstein, H. Everett, L. Feng, and D. Wehe, "Mobile robot positioning-Sensors and techniques, " J. Robot. Syst., vol. 14, no. 4, pp. 231-249, Apr. 1997.
J. Borenstein and L. Feng, "UMBmark: A benchmark test for measuring odometry errors in mobile robots, " in Proc. Soc. Photo-Instrum. Eng., vol. 1001, Philadelphia, PA, USA, Oct. 1995, pp. 113-124.
K. Briechle and U. Hanebeck, "Localization of a mobile robot using relative bearing measurements, " IEEE Trans. Robot. Autom., vol. 20, no. 1, pp. 36-44, Feb. 2004.
M. Brkić, M. Lukić, J. Bajić, B. Dakić, and M. Vukadinović, "Hardware realization of autonomous robot localization system, " in Proc. Int. Conv. Inf. Commun. Technol., Elect. Microelectron., Opatija, Croatia, May 2012, pp. 146-150.
R. Burtch, Three point resection problem, Surveying computations course notes 2005/2006, Ferris State Univ., Big Rapids, MI, USA, 2005, ch. 8, pp. 175-201.
C. Cohen and F. Koss, "A comprehensive study of three object triangula-tion, " in Mobile Robots VII. vol. 1831, Boston, MA, USA: SPIE, Nov. 1992, pp. 95-106.
E. Demaine, A. López-Ortiz, J. Munro, Robot localization without depth perception, Proc. Scandinavian Workshop on Algorithm Theory (SWAT), ser. (Lecture Notes Comput. Sci.), vol. 2368. New York, NY, USA: Springer-Verlag, Jul. 2002, pp. 177-194
A. Easton and S. Cameron, "A gaussian error model for triangulation-based pose estimation using noisy landmarks, " in Proc. IEEE Conf. Robot., Autom. Mechatron., Bangkok, Thailand, Jun. 2006, pp. 1-6.
J.-D. Eiden, G éometrie Analytique Classique. Paris, France: Calvage & Mounet, 2009.
J. Esteves, A. Carvalho, and C. Couto, "Generalized geometric triangula-tion algorithm for mobile robot absolute self-localization, " in Proc. Int. Symp. Ind. Electron., Rio de Janeiro, Brazil, Jun. 2003, vol. 1, pp. 346-351.
J. Esteves, A. Carvalho, and C. Couto, "An improved version of the generalized geometric triangulation algorithm, " presented at the Eur.-Latin-Amer. Workshop Eng. Syst., Porto, Portugal, Jul. 2006.
J. Esteves, A. Carvalho, and C. Couto, "Position and orientation errors in mobile robot absolute self-localization using an improved version of the generalized geometric triangulation algorithm, " in Proc. IEEE Int. Conf. Ind. Technol., Mumbai, India, Dec. 2006, pp. 830-835.
J. Font-Llagunes and J. Batlle, "Mobile robot localization. Revisiting the triangulation methods, " in Proc. IFAC Int. Symp. Robot Control, vol. 8, Santa Cristina Convent, Univ. Bologna, Bologna, Italy, Sep. 2006, pp. 340-345.
J. Font-Llagunes and J. Batlle, "Consistent triangulation for mobile robot localization using discontinuous angular measurements, " Robot. Auton. Syst., vol. 57, no. 9, pp. 931-942, Sep. 2009.
J. Font-Llagunes and J. Batlle, "New method that solves the three-point resection problem using straight lines intersection, " J. Surveying Eng., vol. 135, no. 2, pp. 39-45, May 2009.
H. Hmam, "Mobile platform self-localization, " in Proc. Inf., Decis. Control, Adelaide, Australia, Feb. 2007, pp. 242-247.
H. Hu and D. Gu, "Landmark-based navigation of industrial mobile robots, " Int. J. Ind. Robot, vol. 27, no. 6, pp. 458-467, 2000.
A. Kelly, "Precision dilution in triangulation based mobile robot position estimation, " Intell. Auton. Syst., vol. 8, pp. 1046-1053, 2003.
D. Kortenkamp, "Perception for mobile robot navigation: A survey of the state of the art, " Nat. Aero. Space Admin., Tech. Rep. 19960022619, May 1994.
C. Lee, Y. Chang, G. Park, J. Ryu, S.-G. Jeong, S. Park, J. Park, H. Lee, K.-S. Hong, and M. Lee, "Indoor positioning system based on incident angles of infrared emitters, " in Proc. Conf. IEEE Ind. Electron. Soc, vol. 3, Busan, Korea, Nov. 2004, pp. 2218-222.
M. Ligas, "Simple solution to the three point resection problem, " J. Surveying Eng., vol. 139, no. 3, pp. 120-125, Aug. 2013.
I. Loevsky and I. Shimshoni, "Reliable and efficient landmark-based localization for mobile robots, " Robot. Auton. Syst, vol. 58, no. 5, pp. 520-528, May 2010.
M. Lukic, B. Miodrag, and J. Bajic, "An autonomous robot localization system based on coded infrared beacons, " in Research and Education in Robotics (EUROBOT), vol. 161, Prague, Czech Republic, Springer-Verlag, Jun. 2011, pp. 202-209.
C. Madsen and C. Andersen, "Optimal landmark selection for triangulation of robot position, " Robot. Auton. Syst, vol. 23, no. 4, pp. 277-292, Jul. 1998.
C. Madsen, C. Andersen, and J. Sorensen, "A robustness analysis of triangulation-based robot self-positioning, " in Proc. Int. Symp. Intell. Robot. Syst, Stockholm, Sweden, Jul. 1997, pp. 195-204.
C. McGillem and T. Rappaport, "Infra-red location system for navigation of autonomous vehicles, " in Proc. IEEE Int. Conf. Robot. Autom., vol. 2, Philadelphia, PA, USA, Apr. 1988, pp. 1236-123.
C. McGillem and T. Rappaport, "A beacon navigation method for autonomous vehicles, " IEEE Trans. Veh. Technol., vol. 38, no. 3, pp. 132-139, Aug. 1989.
V. Pierlot and M. Van Droogenbroeck, "A simple and low cost angle measurement system for mobile robot positioning, " in Proc. Worksh. Circuits, Syst. Signal Process., Veldhoven, The Netherlands, Nov. 2009, pp. 251-254.
V. Pierlot, M. Van Droogenbroeck, and M. Urbin-Choffray, A new three object triangulation algorithm based on the power center of three circles, Research and Education in Robotics (EUROBOT), ser. Commun. Com-put. Inf. Sci., vol. 161. New York, NY, USA: Springer-Verlag, 2011, pp. 248-262.
J. Porta and F. Thomas, "Simple solution to the three point resection problem, " J. Surveying Eng., vol. 135, no. 4, pp. 170-172, Nov. 2009.
J. Sanchiz, J. Badenas, and F. Pla, "Control system and laser-based sensor design of an automonous vehicle for industrial environments, " Soc. Photo-Instrum. Eng., vol. 5422, no. 1, pp. 608-615, 2004.
I. Shimshoni, "On mobile robot localization from landmark bearings, " IEEE Trans. Robot. Autom., vol. 18, no. 6, pp. 971-976, Dec. 2002.
S. Shoval and D. Sinriech, "Analysis of landmark configuration for absolute positioning of autonomous vehicles, " J. Manuf. Syst, vol. 20, no. 1, pp. 44-54, 2001.
A. Siadat and S. Vialle, "Robot localization, using p-similar landmarks, optimized triangulation and parallel programming, " presented at the IEEE Int. Symp. Signal Process. Inform. Technol., Marrakesh, Morocco, Dec. 2002.
D. Sinriech and S. Shoval, "Landmark configuration for absolute positioning of autonomous vehicles, " IIE Trans., vol. 32, no. 7, pp. 613-624, Jul. 2000.
H. Sobreira, A. Moreira, and J. Esteves, "Characterization of position and orientation measurement uncertainties in a low-cost mobile platform, " in Proc. Portuguese Conf. Automat. Contr, Coimbra, Portugal, Sep. 2010, pp. 635-640.
H. Sobreira, A. Moreira, and J. Esteves, "Low cost self-localization system with two beacons, " in Proc. Int. Conf. Mobile Robots Competit, Leiria, Portugal, Mar. 2010, pp. 73-77.
O. Tekdas and V. Isler, "Sensor placement algorithms for triangulation based localization, " in Proc. IEEE Int. Conf. Robot. Autom., Rome, Italy, Apr. 2007, pp. 4448-4453.
O. Tekdas and V. Isler, "Sensor placement for triangulation-based localization, " IEEE Trans. Autom. Sci. Eng., vol. 7, no. 3, pp. 681-685, Jul. 2010.
T. Tsukiyama, "Mobile robot localization from landmark bearings, " in World Congr. Fundam. Appl. Metrol., Lisbon, Portugal, Sep. 2009, pp. 2109-211.
E. Zalama, S. Dominguez, J. Gómez, and J. Perán, "A new beacon-based system for the localization of moving objects, " presented at the IEEE Int. Conf. Mechatron. Mach. Vis. Pract., Chiang Mai, Thailand, Sep. 2002.
E. Zalama, S. Dominguez, J. Gómez, and J. Perán, "Microcontroller based system for 2D localisation, " Mechatronics, vol. 15, no. 9, pp. 1109-1126, Nov. 2005.
O. Fuentes, J. Karlsson, W. Meira, R. Rao, T. Riopka, J. Rosca, R. Sarukkai, M. Van Wie, M. Zaki, T. Becker, R. Frank, B. Miller, and C. M. Brown, "Mobile robotics 1994, " Tech. Rep. 588, Comput. Sci. Dept., Univ. Rochester, Rochester, NY, Jun. 1995 (see http://www.cs.cmu.edu/afs/cs.cmu.edu/ Web/People/motionplanning/papers/sbp-papers/integrated2/fuentas-mobile-robots. pdf).
T. Heath, Euclid: The Thirteen Books of The Elements. Dover, 1956.