Robot Path Planning Based On Dual Normal Tracing Medial Axis Extraction Algorithm

With the rapid development of robot related technologies,mobile robots are widely used in various fields of daily life.People have higher and higher requirements for the safety and efficiency of mobile robots,and path planning is the most mobile robot to achieve safe autonomous motion.One of the key technologies.Path planning is not only a pure pursuit of the shortest path,but also needs to make reasonable decisions according to the specific environment and the actual needs of users,so as to plan the optimal feasible path.The mobile robot senses the working environment and the state of the mobile robot itself through the visual sensor,the sonar sensor,etc.,so that the optimal path from the starting position to the target position can be searched in the troubled working environment,and the robot is moving.During this process,all obstacles can be safely bypassed without collision and the path through is the shortest.The path planning based on the dual-normal-tracing medial axis extraction algorithm is to use the relevant characteristics of the medial axis to perform path planning of the robot in a static planar environment.The related concepts of the central axis are introduced in detail,the mathematical model is established,and the central axis extraction algorithm is partially improved.The algorithm uses a dual-normal-tracing algorithm for each sample point to calculate the medial axis point and iteratively performs to calculate the medial axis point for all sample points.Since the dual normal trajectories of each sample point are independent of each other,the algorithm can be parallelized by the GPU of the computer.After the iteration is completed,the generated medial axis point is converted to the medial axis by the topological connectivity of the corresponding sampling points.According to the definition of the medial axis,the external medial axis is a theoretically feasible safety path.After processing the external medial axis according to actual requirements,the shortest path is obtained on the external medial axis,which is the best path.It has been proved by a large number of experiments that a reasonable optimal path can be obtained very effectively,and the method is easy to implement in parallel,which shortens the calculation time and proves the feasibility and effectiveness of the method.The main innovations of this paper are as follows:(1)By dividing the model into grid units,the average number of candidate sample points and candidate edge pairs in each grid unit in parallel computing is reduced,and the time complexity of the algorithm is reduced.(2)The sample points are grouped according to the mid-axis radius.In each round iteration,only the sample points with the mid-axis radius within the current range participate in the mid-axis point calculation,reducing the intersection grid unit of each sample point in parallel calculation The average number increases the efficiency of the algorithm.