Immune evolutionary algorithms with domain knowledge for simultaneous localization and mapping

Abstract

Immune evolutionary algorithms with domain knowledge were presented to solve the problem of simultaneous localization and mapping for a mobile robot in unknown environments. Two operators with domain knowledge were designed in algorithms, where the feature of parallel line segments without the problem of data association was used to construct a vaccination operator, and the characters of convex vertices in polygonal obstacle were extended to develop a pulling operator of key point grid. The experimental results of a real mobile robot show that the computational expensiveness of algorithms designed is less than other evolutionary algorithms for simultaneous localization and mapping and the maps obtained are very accurate. Because immune evolutionary algorithms with domain knowledge have some advantages, the convergence rate of designed algorithms is about 44% higher than those of other algorithms.

Keywords

immune evolutionary algorithms / simultaneous localization and mapping / domain knowledge

References

[1] DissanayakeG, NewmanP, ClarkS, et al.. A solution to the simultaneous localization and map building (SLAM) problem[J]. Transactions on Robotics and Automation, 2001, 17(3): 229-241

[2] LeonardJ J, Durrant-WhyteH FDirected sonar sensing for mobile robot navigation[M], 1992, Dordrecht, Kluwer Academic Publishers

[3] ThrunSRobotic mapping: a survey[R], 2002, Pittsburgh, School of Computer Science, Carnegie Mellon University

[4] WangLu, CaiZi-xing. Progress of CML for mobile robots in unknown environments[J]. Robot, 2004, 26(4): 380-384(in Chinese)

[5] Montemerlo M, Thrun S, Koller D, et al. Fast SLAM: a factored solution to the simultaneous localization and mapping problem[C]//Kortenkamp D, Bonasso R P, Murphy R. Proceedings of the AAAI National Conference on Artificial Intelligence. Edmonton, 2002: 593–598.

[6] SmithR C, CheesemanP. On the representation and estimation of spatial uncertainty [J]. International Journal of Robotics Research, 1986, 5(4): 56-68

[7] SmithR, SelfM, CheesemanPWilfongG T, CoxI J. Estimating uncertain spatial relationships in robotics [C]. Autonomous Robot Vehicles, 1990, Changsha, Central South University of Technology: 167-193

[8] Duckett T. A genetic algorithm for simultaneous localization and mapping[C]// Proceedings of the IEEE International Conference on Robotics and Automation. Taipei, 2003: 434–439.

[9] JiaoLi-chen, WangLei. A novel genetic algorithm based on immunity[J]. IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 2000, 30(5): 552-561

[10] de CastroL N, vov ZubenF J. Learning and optimization using the clonal selection principle [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(3): 239-251

[11] MoravecH, ElfesA. High resolution maps from wide angle sonar[C]. Proceedings of the IEEE International Conference on Robotics and Automation, 1985, Changsha, ASME: 116-121

[12] DrumhellerM. Mobile robot localization using sonar [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(2): 323-332

[13] MichalewiczZGenetic algorithms+data structure=evolutionary programming [M], 1996, Berlin, Central South University of Technology

[14] SiadatA, KaskeA, KlausmanSAlbertosP. An optimized segmentation method for a 2d laser-scanner applied to mobile robot navigation[C]. Proceedings of the 3rd IFAC Symposium on Intelligent Components and Instruments for Control Applications, 1997, Annecy, Université de Savoie: 153-158

[15] SchieleB, CrowleyJ L. A comparison of position estimation techniques using occupancy grids[J]. IEEE Transaction on Robotics and Automation, 1994, 12(3): 1628-1634

[16] ZhengJing-hua, XiaoSong-qing, PengGui-hua. A useful model of knowledge base[J]. Journal of Xiangtan University: Natural Science, 1999, 21(3): 104-106(in Chinese)