mobile robot; positioning; triangulation; resection; survey; source code in C; ToTal; benchmarking; robot
Abstract :
[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
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
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. 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.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
