Researches On Online Exploring Algorithms With Limited Vision Robot In A Polygon

Exploring unknown polygons with a robot is a typical online searching problem.It not only involves theoretical knowledge such as path planning,target search and algorithm design in research fields,but also helps to solve practical application problems such as evacuation from affected areas and exploration of unknown dangerous region.Therefore,the research of online exploring algorithms for polygons has both theoretical significance and application value.Since the robot usually has a limited sensing area,it is a challenging research topic to design an efficient strategy for exploring the given polygons within the robot's search capabilities.The robot model used in this dissertation is assumed as follows.The robot does not have the geometric information such as the shape and boundary of the exploring polygons in advance,but it has a certain memory function,which can recognize and store relevant information.'Under this assumption,this dissertation firstly studies the problem of exploring an unknown rectangular polygon.Using the robot with a circle sensing area,a new 4.47-competitive online exploring algorithm is proposed,which enable the robot to search the boundary of polygon from a given starting point and return to it.With the randomly generated rectangular polygons,the simulation of the algorithm is completed.Secondly,the problem of evacuating from an unknown affected area rapidly is studied.In the case of one agent in the grid network,the evacuees with obstructed vision are required to reach the boundary of the affected area as soon as possible.By optimizing the solution of step size in spiral path,an improved progressional spiral evacuating algorithm is prdposed,which improves the competitive ratio from 17.5 to 17.0 and improves the efficiency of the algorithm.Finally,this dissertation considers the problem of exploring an unknown simple polygon.Combining the strategy of logarithmic spiral,an online algorithm for exploring simple polygons is proposed with a circle sensing area robot.With randomly generated test data,the simulation experiments verify the effectiveness of the algorithm.Experimental results show that the algorithms proposed in this dissertation are correct and efficient.