The Research Of Efficient Exploration Strategy In The Plane Grid

The exploration problem of polygons is a typical online exploration problem in the plane grid.This paper mainly studies the exploration problem of grid polygons whose boundary geometric information is unknown in the plane.The research of exploration problem not only involves relevant theoretical knowledge in the fields of computational geometry and mathematics,but also can solve many practical application problems such as evacuation from unknown dangerous areas,search and rescue,game industry,and path planning.Therefore,it has both theoretical and practical research value.The exploration problem of the grid polygon can be described as follows:Given an area of grid in the plane,a polygon P whose boundary information is unknown and the starting cell s which is adjacent to the boundary of P.The robot starts from the cell s,explores all the cells in the polygon,and finally returns to the cell s.The robot completes the exploration of the grid polygon.The goal of research is to find an exploration strategy to optimize the exploration path of the robot and makes the exploration time shorter.The research in this paper is based on the assumption that the robot does not known the geometric information of the exploration area in the initial state,and the robot has a certain memory function,which can store relevant information with the exploration process.This paper first discusses the relevant basic knowledge of grid polygon,such as interior cells,boundary cells,split cells,and the competition ratio of exploration strategy.Then,the depth-first search algorithm and the improved depth-first search algorithm for the grid exploration problem are analyzed.Next,this paper proposes an improved method to solve the problem with the low exploration efficiency because of the long exploration path.an improved method is proposed.The optDFS exploration algorithm is designed and its competition ratio is analyzed.Finally,the optDFS algorithm is implemented using Python,and the grid polygon is randomly generated for test data.The effectiveness of the proposed algorithm is verified by comparing the experimental results with the theoretical analysis results.