Research On Online Exploration Algorithms For Simple Grid Polygons

Online exploration of unknown polygonal regions is a hot research problem in computational geometry and robotics.In this thesis,the visual area of the robot is limited to the adjacent square cells or hexagonal cells.The exploration area is divided by the cells,so that the region exploration problem of planar polygon is transformed into the polygon exploration problem of grid.For the online exploration of simple square grids and hexagonal grid polygons,the academia has not yet provided the optimal exploration strategy.This thesis focuses on the optimal exploration algorithm for this problem,and gives the efficiency analysis of the algorithm.It has good theoretical significance and practical application value.Combined with the actual situation,this thesis introduces the limitation of sight distance through cells,and the robot can only see the cells adjacent to it.The robot can enter any adjacent free cell(i.e.cells not blocked by obstacles)from its current position.Entering a cell,the robot knows the status of its adj acent cells.The robot's task is to visit every free cell in the given environment and return to the starting point.For square grid polygons,two improvements are made on the basis of SmartDFS algorithm,one is to identify split cells earlier,and the other is to identify and efficiently process corridor structures with a width of 3.A competition ratio of 7/6 online exploration algorithm,NewSmartDFS,is proposed,which matches the lower bound and achieves the optimal algorithm.For the hexagonal grid polygon,combined with the geometric characteristics of the hexagonal model and the improvement of the SmartDFS algorithm in the square grid polygon,an online exploration algorithm H-NewSmartDFS is given,which reduces the competition ratio from 4/3 to 11/9,and further improves the efficiency of the algorithm.The two algorithms proposed in this thesis are the optimal solutions to the corresponding problems so far.The transportation network of most cities is presented as a square grid.Hexagonal grids are common in game maps and better simulate robots equipped with circular tools.This thesis studies the online exploration of square and hexagonal grid areas,which not only solves the theoretical problems in the field of computational geometry,but also can be applied to practical problems such as exploration of dangerous areas,patrolling,and monitoring.