{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:62533"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:62533","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Robust real-time locolization and mapping in single and multi-robot systems","abstract":"The thesis addresses several aspects of the mobile autonomous navigation in the single and multi-robot systems. We presented novel solutions to the single robot localization and simultaneous localization and mapping (SLAM) problems for both the single and multi-robot cases. Our global localization algorithm is an instance of the known Monte-Carlo localization technique, which represents the hypotheses about the real robot pose as a set of weighted samples, which are then refined during the localization process. The weights of the samples are the probabilities that a given sample represents the real robot pose. The computation of the sample weights depends heavily on the perception sensor model used in the localization method. Our approach was to represent the data acquired by the perception sensor of a robot in a hierarchical way using the multi-resolution analysis, which made it possible to dramatically (by an order of magnitude) reduce the dimensionality of the data without loosing their expressive power. We also introduced a probabilistic model for this hierarchical representation of the perception sensor data, which led to an order of magnitude reduction in the overall localization time of a robot in comparison to the existing techniques known from the literature. Based on the mentioned hierarchical perception sensor model, we developed a heuristics for solving one of the most challenging problems in mobile robotics – the \"kidnapped\" robot problem. The method performed very well in practice letting a robot detect a kidnap in about 5-10 seconds. We presented a new approach to the solution of the robotic SLAM problem. The approach is based on the so called Rao-Blackwellized particle filters, which is a new technique in the context of the robotic SLAM problem. In contrast to the FastSLAM algorithm – the best known implementation of Rao-Blackwellized particle filters, our approach neither represents hypotheses about maps explicitly, nor assumes any prior distribution of robot poses or maps. Instead, the approach is based on localizing a robot in its own local sub-maps, which can be computed by retrieving the previously stored perception data the robot has registered at earlier stages. The storage and retrieval is done using an efficient data structure based on kd-trees and by matching the current and previous perception data. This way we avoid an explicit representation of map hypotheses in our approach and generate them on demand from the stored perception sensor data. As mentioned our implementation does not make the restrictive assumptions about the used probability models, such as linearity in the perception and control data and Gaussian distribution and, therefore, can be used to map any complex environment in contrast to the existing algorithms. The results of the experiments have shown that our algorithm is capable of mapping an environment at robot speeds up to 1m/s, which is several times faster than in the existing approaches. We also extended our single robot localization and mapping algorithms to the multi-robot case. The main idea was to determine the relative poses of robots by localizing them in sub-maps of each other. This was done in the same way as in the case of the single robot SLAM by matching the perception data, but in this case of one robot with those of another. After the estimation of the relative poses of the robots with respect to each other it is possible to refine a sample set representing the set of hypotheses about the global pose of one robot by better estimated sample sets of other robots. In the case of mapping the simple fusion of the occupancy grid-maps of the robots can be done. The estimation of the relative poses has shown itself to be robust and quite precise, however there was a relatively high ratio of false positives, which can be explained by the symmetry of environments and inherently low expressive power of 2-dimensional laser range-scans used as perception information. Still, the number of false positives could be considerably reduced by detecting them by an efficient heuristics for the \"kidnapped\" robot problem, which we presented in the context of the single robot localization. The experimental results have shown that the method performs satisfactorily well.","abstract_html":"The thesis addresses several aspects of the mobile autonomous navigation in the single and multi-robot systems. We presented novel solutions to the single robot localization and simultaneous localization and mapping (SLAM) problems for both the single and multi-robot cases. Our global localization algorithm is an instance of the known Monte-Carlo localization technique, which represents the hypotheses about the real robot pose as a set of weighted samples, which are then refined during the localization process. The weights of the samples are the probabilities that a given sample represents the real robot pose. The computation of the sample weights depends heavily on the perception sensor model used in the localization method. Our approach was to represent the data acquired by the perception sensor of a robot in a hierarchical way using the multi-resolution analysis, which made it possible to dramatically (by an order of magnitude) reduce the dimensionality of the data without loosing their expressive power. We also introduced a probabilistic model for this hierarchical representation of the perception sensor data, which led to an order of magnitude reduction in the overall localization time of a robot in comparison to the existing techniques known from the literature. Based on the mentioned hierarchical perception sensor model, we developed a heuristics for solving one of the most challenging problems in mobile robotics – the "kidnapped" robot problem. The method performed very well in practice letting a robot detect a kidnap in about 5-10 seconds. We presented a new approach to the solution of the robotic SLAM problem. The approach is based on the so called Rao-Blackwellized particle filters, which is a new technique in the context of the robotic SLAM problem. In contrast to the FastSLAM algorithm – the best known implementation of Rao-Blackwellized particle filters, our approach neither represents hypotheses about maps explicitly, nor assumes any prior distribution of robot poses or maps. Instead, the approach is based on localizing a robot in its own local sub-maps, which can be computed by retrieving the previously stored perception data the robot has registered at earlier stages. The storage and retrieval is done using an efficient data structure based on kd-trees and by matching the current and previous perception data. This way we avoid an explicit representation of map hypotheses in our approach and generate them on demand from the stored perception sensor data. As mentioned our implementation does not make the restrictive assumptions about the used probability models, such as linearity in the perception and control data and Gaussian distribution and, therefore, can be used to map any complex environment in contrast to the existing algorithms. The results of the experiments have shown that our algorithm is capable of mapping an environment at robot speeds up to 1m/s, which is several times faster than in the existing approaches. We also extended our single robot localization and mapping algorithms to the multi-robot case. The main idea was to determine the relative poses of robots by localizing them in sub-maps of each other. This was done in the same way as in the case of the single robot SLAM by matching the perception data, but in this case of one robot with those of another. After the estimation of the relative poses of the robots with respect to each other it is possible to refine a sample set representing the set of hypotheses about the global pose of one robot by better estimated sample sets of other robots. In the case of mapping the simple fusion of the occupancy grid-maps of the robots can be done. The estimation of the relative poses has shown itself to be robust and quite precise, however there was a relatively high ratio of false positives, which can be explained by the symmetry of environments and inherently low expressive power of 2-dimensional laser range-scans used as perception information. Still, the number of false positives could be considerably reduced by detecting them by an efficient heuristics for the "kidnapped" robot problem, which we presented in the context of the single robot localization. The experimental results have shown that the method performs satisfactorily well.","abstract_has_math":false,"creators":["Amiranashvili, Vazha"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Lakemeyer, Gerhard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-30T19:43:28Z","subjects":["info:eu-repo/classification/ddc/004","Informatik","Robotik","Monte-Carlo-Lokalisierung","Kartenbau","SLAM","Monte-Carlo localization","mapping","kidnapped robot problem","Rao-Blackwellized particle filters"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124097%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124097%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124097%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/62533","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lakemeyer, Gerhard"]},{"key":"dc:creator","label":"Author","values":["Amiranashvili, Vazha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-18289"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Informatik","Robotik","Monte-Carlo-Lokalisierung","Kartenbau","SLAM","Monte-Carlo localization","mapping","kidnapped robot problem","Rao-Blackwellized particle filters"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/62533","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124097%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis addresses several aspects of the mobile autonomous navigation in the single and multi-robot systems. We presented novel solutions to the single robot localization and simultaneous localization and mapping (SLAM) problems for both the single and multi-robot cases. Our global localization algorithm is an instance of the known Monte-Carlo localization technique, which represents the hypotheses about the real robot pose as a set of weighted samples, which are then refined during the localization process. The weights of the samples are the probabilities that a given sample represents the real robot pose. The computation of the sample weights depends heavily on the perception sensor model used in the localization method. Our approach was to represent the data acquired by the perception sensor of a robot in a hierarchical way using the multi-resolution analysis, which made it possible to dramatically (by an order of magnitude) reduce the dimensionality of the data without loosing their expressive power. We also introduced a probabilistic model for this hierarchical representation of the perception sensor data, which led to an order of magnitude reduction in the overall localization time of a robot in comparison to the existing techniques known from the literature. Based on the mentioned hierarchical perception sensor model, we developed a heuristics for solving one of the most challenging problems in mobile robotics – the \"kidnapped\" robot problem. The method performed very well in practice letting a robot detect a kidnap in about 5-10 seconds. We presented a new approach to the solution of the robotic SLAM problem. The approach is based on the so called Rao-Blackwellized particle filters, which is a new technique in the context of the robotic SLAM problem. In contrast to the FastSLAM algorithm – the best known implementation of Rao-Blackwellized particle filters, our approach neither represents hypotheses about maps explicitly, nor assumes any prior distribution of robot poses or maps. Instead, the approach is based on localizing a robot in its own local sub-maps, which can be computed by retrieving the previously stored perception data the robot has registered at earlier stages. The storage and retrieval is done using an efficient data structure based on kd-trees and by matching the current and previous perception data. This way we avoid an explicit representation of map hypotheses in our approach and generate them on demand from the stored perception sensor data. As mentioned our implementation does not make the restrictive assumptions about the used probability models, such as linearity in the perception and control data and Gaussian distribution and, therefore, can be used to map any complex environment in contrast to the existing algorithms. The results of the experiments have shown that our algorithm is capable of mapping an environment at robot speeds up to 1m/s, which is several times faster than in the existing approaches. We also extended our single robot localization and mapping algorithms to the multi-robot case. The main idea was to determine the relative poses of robots by localizing them in sub-maps of each other. This was done in the same way as in the case of the single robot SLAM by matching the perception data, but in this case of one robot with those of another. After the estimation of the relative poses of the robots with respect to each other it is possible to refine a sample set representing the set of hypotheses about the global pose of one robot by better estimated sample sets of other robots. In the case of mapping the simple fusion of the occupancy grid-maps of the robots can be done. The estimation of the relative poses has shown itself to be robust and quite precise, however there was a relatively high ratio of false positives, which can be explained by the symmetry of environments and inherently low expressive power of 2-dimensional laser range-scans used as perception information. Still, the number of false positives could be considerably reduced by detecting them by an efficient heuristics for the \"kidnapped\" robot problem, which we presented in the context of the single robot localization. The experimental results have shown that the method performs satisfactorily well."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University V, 105 S. : graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"]},{"key":"dc:title","label":"Title","values":["Robust real-time locolization and mapping in single and multi-robot systems"]}]}],"canonical_facts":{"dc:contributor":["Lakemeyer, Gerhard"],"dc:coverage":["DE"],"dc:creator":["Amiranashvili, Vazha"],"dc:date":["2007"],"dc:description":["The thesis addresses several aspects of the mobile autonomous navigation in the single and multi-robot systems. We presented novel solutions to the single robot localization and simultaneous localization and mapping (SLAM) problems for both the single and multi-robot cases. Our global localization algorithm is an instance of the known Monte-Carlo localization technique, which represents the hypotheses about the real robot pose as a set of weighted samples, which are then refined during the localization process. The weights of the samples are the probabilities that a given sample represents the real robot pose. The computation of the sample weights depends heavily on the perception sensor model used in the localization method. Our approach was to represent the data acquired by the perception sensor of a robot in a hierarchical way using the multi-resolution analysis, which made it possible to dramatically (by an order of magnitude) reduce the dimensionality of the data without loosing their expressive power. We also introduced a probabilistic model for this hierarchical representation of the perception sensor data, which led to an order of magnitude reduction in the overall localization time of a robot in comparison to the existing techniques known from the literature. Based on the mentioned hierarchical perception sensor model, we developed a heuristics for solving one of the most challenging problems in mobile robotics – the \"kidnapped\" robot problem. The method performed very well in practice letting a robot detect a kidnap in about 5-10 seconds. We presented a new approach to the solution of the robotic SLAM problem. The approach is based on the so called Rao-Blackwellized particle filters, which is a new technique in the context of the robotic SLAM problem. In contrast to the FastSLAM algorithm – the best known implementation of Rao-Blackwellized particle filters, our approach neither represents hypotheses about maps explicitly, nor assumes any prior distribution of robot poses or maps. Instead, the approach is based on localizing a robot in its own local sub-maps, which can be computed by retrieving the previously stored perception data the robot has registered at earlier stages. The storage and retrieval is done using an efficient data structure based on kd-trees and by matching the current and previous perception data. This way we avoid an explicit representation of map hypotheses in our approach and generate them on demand from the stored perception sensor data. As mentioned our implementation does not make the restrictive assumptions about the used probability models, such as linearity in the perception and control data and Gaussian distribution and, therefore, can be used to map any complex environment in contrast to the existing algorithms. The results of the experiments have shown that our algorithm is capable of mapping an environment at robot speeds up to 1m/s, which is several times faster than in the existing approaches. We also extended our single robot localization and mapping algorithms to the multi-robot case. The main idea was to determine the relative poses of robots by localizing them in sub-maps of each other. This was done in the same way as in the case of the single robot SLAM by matching the perception data, but in this case of one robot with those of another. After the estimation of the relative poses of the robots with respect to each other it is possible to refine a sample set representing the set of hypotheses about the global pose of one robot by better estimated sample sets of other robots. In the case of mapping the simple fusion of the occupancy grid-maps of the robots can be done. The estimation of the relative poses has shown itself to be robust and quite precise, however there was a relatively high ratio of false positives, which can be explained by the symmetry of environments and inherently low expressive power of 2-dimensional laser range-scans used as perception information. Still, the number of false positives could be considerably reduced by detecting them by an efficient heuristics for the \"kidnapped\" robot problem, which we presented in the context of the single robot localization. The experimental results have shown that the method performs satisfactorily well."],"dc:identifier":["https://publications.rwth-aachen.de/record/62533","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124097%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-18289"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University V, 105 S. : graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"],"dc:subject":["info:eu-repo/classification/ddc/004","Informatik","Robotik","Monte-Carlo-Lokalisierung","Kartenbau","SLAM","Monte-Carlo localization","mapping","kidnapped robot problem","Rao-Blackwellized particle filters"],"dc:title":["Robust real-time locolization and mapping in single and multi-robot systems"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:43:28Z"}