A Topological Mapping Algorithm Designed For Lightweight Computing

Recent advances in map construction and navigation promote the wide applications of the unmanned system in various industries and fields.However,the current mapping and navigation technologies still highly depend on the on-board computational ability,which is limited by the requirements of the miniaturized equipment in practical applications nowadays.In addition,the traditional metric map performs poorly in abstracting the environment.As a result,it is still difficult for a lightweight unmanned system platform to achieve a higher level of intelligence.To address these problems,this paper starts from the technical route of global topological map,and designs a fast and robust topological mapping algorithm based on multi-hypothesis method.The algorithm contains the following main aspects:1.Aiming at the problem of divergent understanding of loop-closure structures caused by the environment confusion(perception aliasing)during mapping,a framework for deducing the map structure based on the multihypothesis method is designed.A probabilistic map structure evaluation algorithm based on Bayes’ theorem is proposed,applying a method to evaluate loop-closure by the accumulation odometer information on the path in real time.Therefore,the problem of map evaluation can be solved when the number of maps grows with a hyper exponential trend.2.Under the framework of probabilistic evaluation of map,a fast matching method of topological nodes based on geometric hash is proposed.This method not only improves the efficiency of the bottleneck problem in the multi-hypothesis method,but also has the ability to robustly deal with the misrecognition and missing recognition in practical application.Finally,combining with the Bayesian derivation paradigm of the mapping framework,a method for calculating the probability accuracy of node matching is also designed.3.A dual-growth tree data structure,and a high performance algorithm is designed for the construction of the topological map.The algorithm combines the characteristics of multi-hypothesis method and the features of the fast node matching algorithm.The search of the loop structure is conducted efficiently by making full use of the recursive probability calculation method while highly reusing the low-level data from sensors.At last,an algorithm of the reconstruction of the entire map is designed and the idea of lazy evaluation is applied to only selectively construct the necessary global map.Thereby the real-time performance of the algorithm is further improved.4.Finally,we modularly designed the topological map building system framework,and deployed the algorithm based on the ROS architecture and built the graphical UI.An automated simulation environment is developed and large-scale simulations and stress tests were conducted to verify the algorithm in the simulation environment.Finally,the real-time performance of the algorithm was preliminarily verified on a small quadrotor.The results demonstrate that the proposed method is high-efficiency,robust,scalable and can be implemented in real time.