Mobile Robots Navigation, Mapping, and Localization Part II

Lee Gim Hee (DSO National Laboratories, Singapore) and Marcelo H. Ang Jr. (National University of Singapore, Singapore)
DOI: 10.4018/978-1-59904-849-9.ch159

Abstract

In addition to the capability to navigate from a point of origin to a given goal and avoiding all static and dynamic obstacles, a mobile robot must posses another two competencies: map building and localization in order to be useful. A mobile robot acquires information of its environment via the process of map building. Map building for mobile robots are commonly divided into occupancy grid and topological maps. Occupancy-grid maps seek to represent the geometric properties of the environment. Occupancy-grid mapping was first suggested by Elfes in 1987 and the idea was published in his Ph.D. thesis (A. Elfes, 1989) in 1989. Topological mapping was first introduced in 1985 as an alternative to the occupancy- grid mapping by R. Chatila and J.-P. Laumond (R. Chatila, & J.-P. Laumond, 1985). Topological maps describe the connectivity of different locations in the environment. The pose of a mobile robot must be known at all times for it to navigation and build a map accurately. This is the problem of localization and it was first described in the late 1980’s by R. Smith et al (R. Smith et al, 1980). Some key algorithms for map building and localization will be discussed in this article.
Chapter Preview
Top

Map Building

As seen from the integrated algorithm from part I of the article, a mobile robot must be able to acquire maps of an unknown environment to achieve higher level of autonomy. Map building is the process where sensory information of the surrounding is made comprehensive to a mobile robot. In this section, two key approaches for map building: occupancy-grid and topological mapping are discussed.

Key Terms in this Chapter

Odometry: A method to do position estimation for a wheeled vehicle during navigation by counting the number of revolutions taken by the wheels that are in contact with the ground.

Recursive Algorithm: It refers to a type of computer function that is applied within its own definition. The extended Kalman filter and particle filter are recursive algorithms because the outputs from the filters at the current time step are used as inputs in the next time step.

Curse of Dimensionality: This term was first used by Richard Bellman. It refers to the problem of exponential increase in volume associated with adding extra dimensions to a mathematical space.

Jacobians: The Jacobian is a first-order partial derivatives of a function. Its importance lies in the fact that it represents the best linear approximation to a differentiable function near a given point.

Gaussian Distribution: It is also known as normal distribution. It is a family of continuous probability distributions where each member of the family is described by two parameters: mean and variance. This form of distribution is used by the localization with extended Kalman filter algorithm to describe the posterior belief distribution of the robot pose.

Predicted Belief: It is also known as the prior belief. It refers to the probability distribution of the robot pose estimate interpreted from the known control data and in the absence of the sensor measurement data.

Posterior Belief: It refers to the probability distribution of the robot pose estimate conditioned upon information such as control and sensor measurement data. The extended Kalman filter and particle filter are two different methods for computing the posterior belief.

Complete Chapter List

Search this Book:
Reset
Chapter 1
Jun Jiang, Horace H.S. Ip
\$37.50
Chapter 2
M. L. Gavrilova
\$37.50
Chapter 3
Zbigniew Michalewicz
\$37.50
Chapter 4
\$37.50
Chapter 5
Larbi Esmahi, Kristian Williamson, Elarbi Badidi
\$37.50
Chapter 6
João José Neto
\$37.50
Chapter 7
J. Álvaro Fernández
\$37.50
Chapter 8
Zaiyong Tang, Xiaoyu Huang, Kallol Bagchi
\$37.50
Chapter 9
Lester Ingber
\$37.50
Chapter 10
Amira Djebbari, Aedín C. Culhane, Alice J. Armstrong, John Quackenbush
\$37.50
Chapter 11
José D. Martín-Guerrero, Emilio Soria-Olivas, Paulo J.G. Lisboa, Antonio J. Serrano-López
\$37.50
Chapter 12
Vasudha Bhatnagar, Anamika Gupta, Naveen Kumar
\$37.50
Chapter 13
Ambient Intelligence  (pages 85-91)
\$37.50
Chapter 14
Carlos Ramos
\$37.50
Chapter 15
Shourya Roy, L. Venkata Subramaniam
\$37.50
Chapter 16
L. Venkata Subramaniam, Shourya Roy
\$37.50
Chapter 17
Francisco J. Nóvoa, Alberto Curra, M. Gloria López, Virginia Mato
\$37.50
Chapter 18
Juan L. Pérez, Mª Isabel Martínez, Manuel F. Herrador
\$37.50
Chapter 19
Daniel Rivero, Juan Rabuñal
\$37.50
Chapter 20
Matthieu Voiry, Véronique Amarger, Joel Bernier, Kurosh Madani
\$37.50
Chapter 21
Eduardo Sánchez, Manuel Lama
\$37.50
Chapter 22
Gregorio Iglesias Rodriguez, Alberte Castro Ponte, Rodrigo Carballo Sanchez, Miguel Ángel Losada Rodriguez
\$37.50
\$37.50
Chapter 24
Paulo Eduardo Ambrósio
\$37.50
Chapter 25
Amanda J.C. Sharkey
\$37.50
Chapter 26
Ana Belén Porto Pazos, Alberto Alvarellos González, Félix Montañés Pazos
\$37.50
Chapter 27
Association Rule Mining  (pages 172-178)
Vasudha Bhatnagar, Sarabjeet Kochhar
\$37.50
Chapter 28
Automated Cryptanalysis  (pages 179-185)
Otokar Grošek, Pavol Zajac
\$37.50
Chapter 29
Otokar Grošek, Pavol Zajac
\$37.50
Chapter 30
\$37.50
Chapter 31
\$37.50
Chapter 32
Girolamo Fornarelli, Antonio Giaquinto
\$37.50
Chapter 33
Girolamo Fornarelli, Antonio Giaquinto
\$37.50
Chapter 34
J. Álvaro Fernández
\$37.50
Chapter 35
\$37.50
Chapter 36
María José Castro-Bleda, Slavador España-Boquera, Francisco Zamora-Martínez
\$37.50
Chapter 37
José Antonio Seoane Fernández, Mónica Miguélez Rico
\$37.50
Chapter 38
José Antonio Seoane Fernández, Mónica Miguélez Rico
\$37.50
Chapter 39
Roberto A. Vazquez, Humberto Sossa
\$37.50
Chapter 40
Manuel G. Bedia, Juan M. Corchado, Luis F. Castillo
\$37.50
Chapter 41
Marcos Faundez-Zanuy
\$37.50
Chapter 42
Miguel A. Ferrer, Aday Tejera Santana
\$37.50
Chapter 43
Chaotic Neural Networks  (pages 275-281)
Emilio Del-Moral-Hernandez
\$37.50
Chapter 44
Óscar Pérez, Manuel Sánchez-Montañés
\$37.50
Chapter 45
Alan Wee-Chung Liew, Ngai-Fong Law, Hong Yan
\$37.50
Chapter 46
Yu-Chen Song, Hai-Dong Meng
\$37.50
Chapter 47
Atiq Islam, Khan M. Iftekharuddin, E. Olusegun George, David J. Russomanno
\$37.50
Chapter 48
Atiq Islam, Khan M. Iftekharuddin, E. Olusegun George, David J. Russomanno
\$37.50
Chapter 49
Lei Xu, Shun-ichi Amari
\$37.50
Chapter 50
Phillip Ein-Dor
\$37.50
Chapter 51
Phillip Ein-Dor
\$37.50
Chapter 52
Shaista Rashid, Dimitris Rigas
\$37.50
Chapter 53
José Fernando Díaz Martín, Jesús M. Riaño Sierra
\$37.50
Chapter 54
Jirí Kroc, Peter M.A. Sloot
\$37.50
Chapter 55
Tohru Nitta
\$37.50
Chapter 56
Oscar Déniz Suárez, Gloria Bueno García
\$37.50
Chapter 57
Michele Piana
\$37.50
Chapter 58
Enrique Fernández-Blanco, Julián Dorado de la Calle
\$37.50
Chapter 59
Óscar Ibáñez, Juan Ramón Rabuñal Dopico
\$37.50
Chapter 60
Antonio Eleuteri, Azzam Taktak, Bertil Damato, Angela Douglas, Sarah Coupland
\$37.50
Chapter 61
Configuration  (pages 396-403)
Luca Anselma, Diego Magro
\$37.50
Chapter 62
Constraint Processing  (pages 404-409)
Roman Barták
\$37.50
Chapter 63
Wei-Chiang Samuelson Hong
\$37.50
Chapter 64
John Wang, Qiyang Chen, James Yao
\$37.50
Chapter 65
James Yao, John Wang
\$37.50
Chapter 66
Mats Danielson, Love Ekenberg
\$37.50
Chapter 67
Man Wai Lee, Kyriacos Chrysostomou, Sherry Y. Chen, Xiaohui Liu
\$37.50
Chapter 68
Malcolm J. Beynon
\$37.50
Chapter 69
Ruket Çakici
\$37.50
\$37.50
Chapter 71
Developmental Robotics  (pages 464-470)
Max Lungarella, Gabriel Gómez
\$37.50
Chapter 72
Valeriu Beiu, Walid Ibrahim, Sanja Lazarova-Molnar
\$37.50
Chapter 73
José M. Cadenas, Ma Carmen Garrido, Enrique Muñoz, Carlos Cruz-Corona, David A. Pelta, José L. Verdegay
\$37.50
Chapter 74
Janez Brest
\$37.50
Chapter 75
Vikram Sorathia, Anutosh Maitra
\$37.50
Chapter 76
Disk-Based Search  (pages 501-506)
Stefan Edelkamp, Shahid Jabbar
\$37.50
Chapter 77
Marius C. Silaghi, Makoto Yokoo
\$37.50
\$37.50
Chapter 79
Gilles Lebrun, Olivier Lezoray, Christopher Charrier, Hubert Cardot
\$37.50
Chapter 80
Juan L. Pérez, Belén González-Fonteboa, Fernando Martínez-Abella
\$37.50
Chapter 81
Nieves Pedreira, José Ramón Méndez Salgueiro, Manuel Martínez Carballo
\$37.50
Chapter 82
Darryl N. Davis, Paul M. Chapman
\$37.50
Chapter 83
Ignasi Iriondo, Santiago Planet, Francesc Alías, Joan-Claudi Socoró, Elisa Martínez
\$37.50
Chapter 84
Gloria Bueno García, Antonio Martínez, Roberto González, Manuel Torres
\$37.50
Chapter 85
M. Paz Sesmero Lorente, Juan Manuel Alonso-Weber, Germán Gutiérrez Sánchez, Agapito Ledezma Espino, Araceli Sanchis de Miguel
\$37.50
Chapter 86
Ángela Blanco, Manuel Martín-Merino
\$37.50
Chapter 87
Bohumil Sulc, David Klimanek
\$37.50
Chapter 88
Antonia Azzini, Andrea G.B. Tettamanzi
\$37.50
Chapter 89
\$37.50
Chapter 90
Prayag Narula, Sudip Misra, Sanjay Kumar Dhurandher
\$37.50
Chapter 91
Ernesto Rodrigues, Heitor Silvério Lopes
\$37.50
Chapter 92
Evolutionary Robotics  (pages 603-608)
J. A. Becerra, R. J. Duro
\$37.50
Chapter 93
Laurentiu Ionescu, Alin Mazare, Gheorghe Serban, Emil Sofron
\$37.50
Chapter 94
Daniel Rivero, David Periscal
\$37.50
Chapter 95
\$37.50
Chapter 96
Feature Selection  (pages 632-638)
Noelia Sánchez-Maroño, Amparo Alonso-Betanzos
\$37.50
Chapter 97
Lluís A. Belanche Muñoz
\$37.50
Chapter 98
Marcos Gestal, Mari Paz Gómez-Carracedo
\$37.50
Chapter 99
László Kovács, Domonkos Tikk
\$37.50
Chapter 100
Tuomas Kärnä, Amaury Lendasse
\$37.50
Chapter 101
Functional Networks  (pages 667-676)
Oscar Fontenla-Romero, Bertha Guijarro-Berdiñas, Beatriz Pérez-Sánchez
\$37.50
Chapter 102
\$37.50
Chapter 103
Guanrong Chen, Young Hoon Joo
\$37.50
Chapter 104
Fuzzy Decision Trees  (pages 696-703)
Malcolm J. Beynon
\$37.50
Chapter 105
Leonid S. Bershtein, Alexander V. Bozhenyuk
\$37.50
Chapter 106
Alfonso Castro, Bernardino Arcay
\$37.50
Chapter 107
Rosa Maria Alsina Pagès, Clàudia Mateo Segura, Joan-Claudi Socoró Carrié
\$37.50
Chapter 108
Fuzzy Rule Interpolation  (pages 728-733)
Szilveszter Kovács
\$37.50
Chapter 109
Young Hoon Joo, Guanrong Chen
\$37.50
Chapter 110
Enrique Fernandez-Blanco, J. Andrés Serantes
\$37.50
\$37.50
Chapter 112
João H. Kleinschmidt
\$37.50
Chapter 113
Óscar Ibáñez, Alberte Castro
\$37.50
Chapter 114
Daniel Manrique, Juan Ríos, Alfonso Rodríguez-Patón
\$37.50
Chapter 115
Granular Computing  (pages 774-780)
Georg Peters
\$37.50
Chapter 116
\$37.50
Chapter 117
Lluís Formiga, Francesc Alías
\$37.50
Chapter 118
Roy Gelbard, Avichai Meged
\$37.50
Chapter 119
Zong Woo Geem
\$37.50
Chapter 120
Marley Vellasco, Marco Pacheco, Karla Figueiredo, Flavio Souza
\$37.50
Chapter 121
Marley Vellasco, Marco Pacheco, Karla Figueiredo, Flavio Souza
\$37.50
Chapter 122
Carlos Diuk, Michael Littman
\$37.50
Chapter 123
Nouma Izeboudjen, Ahcene Farah, Hamid Bessalah, Ahmed Bouridene, Nassim Chikhi
\$37.50
Chapter 124
Stefano Cagnoni, Monica Mordonini, Luca Mussi, Giovanni Adorni
\$37.50
Chapter 125
Stefano Cagnoni, Monica Mordonini, Luca Mussi, Giovanni Adorni
\$37.50
Chapter 126
\$37.50
Chapter 127
Carlos Alberto Reyes-García, Ramon Zatarain, Lucia Barron, Orion Fausto Reyes-Galaviz
\$37.50
Chapter 128
Carlos Alberto Reyes-García, Sandra E. Barajas, Esteban Tlelo-Cuautle, Orion Fausto Reyes-Galaviz
\$37.50
Chapter 129
Antonio Seoane, Alberto Jaspe
\$37.50
Chapter 130
Liwei Fan, Kim Leng Poh
\$37.50
Chapter 131
Lior Rokach
\$37.50
Chapter 132
Independent Subspaces  (pages 892-901)
Lei Xu
\$37.50
Chapter 133
Deniz Erdogmus, Jose C. Principe
\$37.50
Chapter 134
O. Valenzuela, I. Rojas, F. Rojas, A. Guillen, L. J. Herrera, F. J. Rojas, M. Cepero
\$37.50
Chapter 135
G. Nicolás Marichal, Evelio J. González
\$37.50
Chapter 136
Safiye Turgay, Fahrettin Yaman
\$37.50
Chapter 137
Raúl Vicen Bueno, Manuel Rosa Zurera, María Pilar Jarabo Amores, Roberto Gil Pita, David de la Mata Moya
\$37.50
Chapter 138
\$37.50
Chapter 139
\$37.50
Chapter 140
Mario Jankovic-Romano, Milan Stankovic, Uroš Krcadinac
\$37.50
Chapter 141
Raúl Vicen Bueno, Elena Torijano Gordo, Antonio García González, Manuel Rosa Zurera, Roberto Gil Pita
\$37.50
Chapter 142
Qiyang Chen, John Wang
\$37.50
Chapter 143
Ioannis K. Vlachos, George D. Sergiadis
\$37.50
Chapter 144
Javier Andrade, Santiago Rodríguez, María Seoane, Sonia Suárez
\$37.50
Chapter 145
Juan Ares, Rafael García, María Seoane, Sonia Suárez
\$37.50
Chapter 146
Knowledge-Based Systems  (pages 989-995)
\$37.50
Chapter 147
Marie-Thérèse Boyer-Xambeu, Ghislain Deleplace, Patrice Gaubert, Lucien Gillard
\$37.50
Chapter 148
Lluís A. Belanche Muñoz
\$37.50
Chapter 149
Lluís A. Belanche Muñoz
\$37.50
Chapter 150
Alfredo Garro
\$37.50
Chapter 151
Learning-Based Planning  (pages 1024-1028)
Sergio Jiménez Celorrio, Tomás de la Rosa Turbides
\$37.50
Chapter 152
Patrick Rousset, Jean-Francois Giret
\$37.50
Chapter 153
Qiyang Chen, John Wang
\$37.50
Chapter 154
Francesco di Pierro, Soon-Thiam Khu, Dragan A. Savic
\$37.50
Chapter 155
Yi Zhao, Wolfgang A. Halang
\$37.50
Chapter 156
\$37.50
Chapter 157
Juan M. Gómez, Ricardo Colomo, Marcos Ruano, Ángel García
\$37.50
Chapter 158
Lee Gim Hee, Marcelo H. Ang Jr.
\$37.50
Chapter 159
Lee Gim Hee, Marcelo H. Ang Jr.
\$37.50
Chapter 160
Nikolay V. Shilov, Natalia Garanina
\$37.50
Chapter 161
Ricardo Téllez, Cecilio Angulo
\$37.50
Chapter 162
Jose Crespo
\$37.50
Chapter 163
Enrique Mérida-Casermeiro, Domingo López-Rodríguez, Juan M. Ortiz-de-Lazcano-Lobato
\$37.50
Chapter 164
Ivan N. Silva, Rogerio A. Flauzino
\$37.50
Chapter 165
László Kovács, Tanja Sieber
\$37.50
Chapter 166
P. A. Gutiérrez, C. Hervás, F. J. Martínez-Estudillo, M. Carbonero
\$37.50
Chapter 167
Sanjoy Das, Bijaya K. Panigrahi
\$37.50
Chapter 168
M. P. Cuéllar, Miguel Delgado, M. C. Pegalajar
\$37.50
Chapter 169
Gian Piero Zarri
\$37.50
Chapter 170
Gian Piero Zarri
\$37.50
Chapter 171
Gemma Bel Enguix, M. Dolores Jiménez López
\$37.50
Chapter 172
Vasile Rus, Philip M. McCarthy, Danielle S. McNamara, Arthur C. Graesser
\$37.50
Chapter 173
Matthew Szenher
\$37.50
Chapter 174
Sanjoy Das
\$37.50
Chapter 175
Francisco García-Córdova, Antonio Guerrero-González, Fulgencio Marín-García
\$37.50
Chapter 176
Enrique Romero, Julio J. Valdés, Alan J. Barton
\$37.50
Chapter 177
Juergen Perl
\$37.50
Chapter 178
\$37.50
Chapter 179
Juan J. González De la Rosa, Carlos G. Puntonet, A. Moreno-Muñoz
\$37.50
Chapter 180
J. Francisco Vargas, Miguel A. Ferrer
\$37.50
Chapter 181
Vassilis G. Kaburlasos
\$37.50
Chapter 182
Tien Ho-Phuoc, Anne Guerin-Dugue
\$37.50
Chapter 183
Chutima Boonthum-Denecke, Irwin B. Levinstein, Danielle S. McNamara, Joseph P. Magliano, Keith K. Millis
\$37.50
Chapter 184
Carlos M. Travieso González, Aythami Morales Moreno
\$37.50
Chapter 185
Jesús Bernardino Alonso Hernández, Patricia Henríquez Rodríguez
\$37.50
Chapter 186
Mónica Miguélez Rico, José Antonio Seoane Fernández, Julián Dorado de la Calle
\$37.50
Chapter 187
Manuel Lama, Eduardo Sánchez
\$37.50
Chapter 188
Ontology Alignment Overview  (pages 1283-1289)
José Manuel Vázquez Naya, Marcos Martínez Romero, Javier Pereira Loureiro, Alejandro Pazos Sierra
\$37.50
Chapter 189
Marcos Martínez Romero, José Manuel Vázquez Naya, Javier Pereira Loureiro, Norberto Ezquerra
\$37.50
Chapter 190
V. Romero-García, E. Fuster-Garcia, J. V. Sánchez-Pérez, L. M. Garcia-Raffi, X. Blasco, J. M. Herrero, J. Sanchis
\$37.50
Chapter 191
Stefano Cagnoni, Monica Mordonini
\$37.50
Chapter 192
Neal Shambaugh
\$37.50
Chapter 193
Javier Bajo, Dante I. Tapia, Sara Rodríguez, Juan M. Corchado
\$37.50
Chapter 194
\$37.50
Chapter 195
Somasheker Akkaladevi, Ajay K. Katangur, Xin Luo
\$37.50
Chapter 196
Frank-M. Schleif, Thomas Villmann, Barbara Hammer
\$37.50
Chapter 197
Randomized Hough Transform  (pages 1343-1350)
Lei Xu, Erkki Oja
\$37.50
Chapter 198
Ranking Functions  (pages 1351-1355)
Franz Huber
\$37.50
Chapter 199
Robert Lukomski, Kazimierz Wilkosz
\$37.50
Chapter 200
José García-Rodríguez, Francisco Flórez-Revuelta, Juan Manuel García-Chamizo
\$37.50
Chapter 201
Fernando Zacarías Flores, Dionicio Zacarías Flores, Rosalba Cuapa Canto, Luis Miguel Guzmán Muñoz
\$37.50
Chapter 202
Carlos Herrera, Tom Ziemke, Thomas M. McGinnity
\$37.50
Chapter 203
Robots in Education  (pages 1383-1388)
\$37.50
Chapter 204
Andrzej Rusiecki
\$37.50
Chapter 205
Kai Keng Ang, Chai Quek
\$37.50
Chapter 206
Agostino Poggi, Michele Tomaiuolo
\$37.50
Chapter 207
Chun-Cheng Peng, George D. Magoulas
\$37.50
Chapter 208
Ioanna Roussaki, Ioannis Papaioannou, Miltiades Anagnostou
\$37.50
Chapter 209
Fernando Zacarías Flores, Dionicio Zacarías Flores, Rosalba Cuapa Canto, Luis Miguel Guzmán Muñoz
\$37.50
Chapter 210
Fatih Onur Hocaoglu, Ömer Nezih Gerek, Mehmet Kurban
\$37.50
Chapter 211
Jesús Bernardino Alonso Hernández, Patricia Henríquez Rodríguez
\$37.50
Chapter 212
Carlos M. Travieso González, Carlos F. Romero
\$37.50
Chapter 213
Yan Yan, Yu-Jin Zhang
\$37.50
Chapter 214
Arturo Berrones, Dexmont Peña, Ricardo Sánchez
\$37.50
Chapter 215
Mirjam Sepesy Maucec, Zdravko Kacic
\$37.50
Chapter 216
Snorre Aunet, Hans Kristian Otnes Berge
\$37.50
\$37.50
Chapter 218
M. Martínez-Zarzuela, F. J. Díaz Pernas, D. González Ortega, J. F. Díez Higuera, M. Antón Rodríguez
\$37.50
Chapter 219
M. Martínez-Zarzuela, F. J. Díaz Pernas, D. González Ortega, J. F. Díez Higuera, M. Antón Rodríguez
\$37.50
Chapter 220
Pi-Sheng Deng
\$37.50
Chapter 221
\$37.50
Chapter 222
Support Vector Machines  (pages 1518-1523)
Cecilio Angulo, Luis Gonzalez-Abril
\$37.50
Chapter 223
Ioannis Papaioannou, Ioanna Roussaki, Miltiades Anagnostou
\$37.50
Chapter 224
Prayag Narula, Sudip Misra, Sanjay Kumar Dhurandher
\$37.50
Chapter 225
Swarm Robotics  (pages 1537-1542)
Amanda J.C. Sharkey
\$37.50
Chapter 226
Symbol Grounding Problem  (pages 1543-1548)
Angelo Loula, João Queiroz
\$37.50
Chapter 227
Symbolic Search  (pages 1549-1554)
Stefan Edelkamp
\$37.50
Chapter 228
Snorre Aunet
\$37.50
Chapter 229
Raymond Chiong
\$37.50
Chapter 230
T. T. Wong, C. W. Leung
\$37.50
Chapter 231
Fernando Mateo, Ramón J. Aliaga, Jorge D. Martínez, José Ma Monzó, Rafael Gadea
\$37.50
Chapter 232
Pablo Mesejo, Enrique Fernández-Blanco, Diego Martínez-Feijóo, Francisco J. Blanco
\$37.50
Chapter 233
Julio J. Valdés, Alan J. Barton
\$37.50
Chapter 234