Online Algorithms For Searching Targets In An Unknown Region

Online searching problem is a research hotspot in computational geometry, robtics and algorithms. It not only involves dynamic search, optimal path planning, algorithm design and analysis, but also has a wide range of applications in emergency evacuation, robot searching and exploration. The research of the algorithm for online searching has both theoretical significance and application value.Although many efficient online searching algorithms have been proposed in recent years, there are still a lot of classic open questions. Also, some of the algorithms are not optimal, or need to set some restrictions in advance. Under this circumstance, this dissertation studies three specific problems in the field of online searching. And the contributions are listed as follows.Firstly, the problem of evacuating from an unknown affected area is considered in two cases:one agent and n(n?3) agents evacuation. In the former case, a 13.812-competitive logarithmic spiral algorithm is proposed. It is proved to be optimal among all monotone and periodic algorithms by showing a matching lower bound. Moreover, a 21-competitive spiral algorithm is proposed in grid network analogously. In the latter case, a new equiangular evacuation algorithm (EES) is proposed. The performance of EES is adjusted to be more efficient by optimizing the number of the groups of the evacuees.Secondly, the problem of walking in streets with minimal sensing is considered. A new 9-competitive online algorithm is proposed. It is proved to be optimal by showing a matching lower bound. This algorithm not only improves the competitive ratio from 11 to 9, but also removes the restriction that the robot needs to take a pebble to mark some positions, and the data structure S-GNT should be used for turning back.Thirdly, the problem of exploring an unknown simple polygon is considered. A new 6.7-competitive online exploration algorithm is proposed. In the process of designing and analyzing, the polygon exploration problem is reduced to the subproblems of exploring two different types of reflex vertices, the (?)-approximation algorithm is implemented online, the structure angle hull is used to analyze the performance of this algorithm. With above new ideas, the competitive ratio is improved from 26.5 to 6.7. This gives a significant improvement upon the previously known algorithm.The algorithms proposed in this dissertation are optimal by far. They not only solve some theoretical problems in the field of online searching, but also have a wide range of applications in emergency evacuation, robot searching and exploration.