Research On Map Preprocessing Method For Path Planning

Autonomous navigation is one of the core functions of mobile robot and also an important topic in the field of robotics,including environment modeling,positioning,map processing,path planning,and end control.In the process of path planning,the planning algorithm will consume a lot of running time and storage space in the search of invalid path,and the map preprocessing technology can effectively reduce the complexity of the robot's workspace,so as to improve the overall efficiency of path planning process.Traditional map preprocessing techniques include manual marking,multi-resolution grid map,navigation mesh,and topology abstraction,etc.However,these methods generally lack flexibility in dealing with the concave obstacle in grid map,and in the preprocessed maps,planning algorithms cannot avoid searching such areas.To solve the problem of concave obstacles,this paper proposes a fast marking algorithm for filling concave areas.The main work is as follows:Firstly,this paper proposes a general solution,the FC(Filling the Container)algorithm.This algorithm simulates the properties of water flow under gravity and fills any unstructured concave area effectively by traversing the map several times.The definition of the concave area and the proof that there is no optimal path for this type of area are given.The filling process of single concave region and compound concave region is described in detail,and the pseudocode and rigorous analysis is given.In the experiment,several test maps show the effectiveness of this method,and compare the performance difference of the path planning algorithm before and after filling the concave area.Secondly,block decomposition algorithm is proposed for the scenario of mobile robot repeating path planning on the same map.By constructing the index table of the filling blocks to establish the linking relation between the blocks,eliminating the filling blocks that block the starting point and the target point by decomposition method,the regional connectivity in the robot workspace is restored,and the purpose of reusing the filling processing map is achieved.It solves the problem that in the space of the filled concave area map,where the reset point or target point is randomly located in a filled block,the repeated execution of the FC algorithm caused by canceling all the filling processes generates a lot of time-consuming problems.This method has a limited impact on the performance of the original algorithm,but it can avoid the repeated running of the FC algorithm.Finally,the paper discusses the incompleteness of the concave area filling of the FC algorithm in detail,and explains the reason and necessity of incomplete filling.The existence of the optimal path solution in the map processed by the FC algorithm and the block decomposition algorithm was proved.