Researches On Online Algorithm Of Exploring Grid Area Based On Visual Range Maximization

It is a classic problem of computational geometry and robotics to explore the polygonal area online by robot.This paper studies the online exploration problem of grid polygons on the plane.The goal of the study is to find the optimal path that traverses all the grids in the given polygonal area and returns to the starting point with a limited visual range robot.In addition,the given polygonal area is a grid polygon which boundary information is unknown.In other words,the exploration process is online exploration.This problem is not only a deformation of the polygon searching problem,but also an abstract model that uses robot to completely search the specific area in bad environment,such as path planning of sweeping robot,the search and rescue of robot in disaster area,etc.Since the visual range of robots are often limited,this paper studies the grid exploration problem of the robot traversing a given area with the maximum visual range.This study not only has great theoretical value,but also can provide effective solutions for some practical problems.This paper proposes an optimal local exploration strategy based on the analysis of existing research results.This strategy combines the SmartDFS algorithm,and ensures that the robot's visible range is bounded in the unit grid of the given polygon.It defines special cells by distinguishing the type of grid.According to the priority level of robot traversing cells,corresponding exploration strategies were designed respectively to dynamically determine the traversal route of robot.SmartDFS-OPT algorithm is proposed to improve the competitive ratio of the online exploration algorithm for grid polygon from 5/4 to 7/6,which reaches the lower bound of the theoretical analysis results.In order to verify the effectiveness of SmartDFS-OPT algorithm,this paper designs the corresponding data structure and implements it by programming.With the randomly generated different types of grid polygons,the performance of the algorithm is tested.Experimental results show that the algorithm proposed in this paper is correct and effective.