Incremental Map Decomposition And Coverage Path Planning For Mobile Robots

Path planning is an important field of mobile robotics research,and complete coverage path planning has important applications in service robots and mapping robots,which has become an important branch of path planning.Traditional boustrophedon complete coverage path planning algorithm is only applicable to a limited range of environment,typically expressed as simple polygons.This thesis proposes a novel incremental segmentation strategy,develops a complete coverage algorithm based on Boustrophedon A Star(BA*),making use of LiDAR sensor's perceived range which is larger than robot's size.The algorithm breaks the limitation of complete coverage path planning and is proved effective in simulated and real environment.This thesis mainly completes the following work:1)To solve the application environment limitations of traditional boustrophedon,this thesis propose a novel incremental segmentation strategy.The strategy makes use of the measuring property of the sensors,segments map dynamically by the perception of robot's own posture through its movement.It breaks the limitations of traditional boustrophedon in complicated environment,so as to completes the tasks of coverage path planning better.2)A new BA*complete coverage path algorithm is implemented based on dynamic region segmentation.It can perform the complete coverage path planning in real-time:carrying out boustrophedon path inside sub-regions and finding a shortest path between regions by the A*algorithm.It overcomes the inapplicability of the original BA*in real complex environment,optimizes the coverage path direction inside regions,and achieves minimal length of the path.3)The relation between the complexity of complete coverage path and the spatial environment of the map is theoretically analyzed.At the same time,the factors that affect the coverage efficiency of mobile robot is studied through simulated and real environment,which includes length of coverage path,coverage area,the number of sub-regions,the energy consumed and the time cost of covering the same area.Finally,the practicability and correctness of the algorithm are proved through comparison of experimental data of the algorithms.The efficiency of the complete coverage path can be improved under practical application scenarios.