A Study Of Algorithms For Searching Mobile Intruders In A Circular Corridor By 1-Searchers

This paper studies the problem of searching mobile intruders in a circular corridor by 1-searchers. A circular corridor is a polygon with one polygonal hole and disjoined each other. The given circular corridor in this paper is limited to have the geometrical property that its inner and outer boundaries are mutually weakly visibile. The so-called 1-searcher is a robot or a man who has a flashlight and can see only along the ray of the flashlight emanating from his position. The 1-searcher always directs its flashlight at inner boundary. The searching problem by 1-searchers in circular corridors is a theoretical model for practical application problems of the search robot. So studying this problem not only has theoretical significance, but also has great application value.Based on the analysis of the geometrical characteristics of circular corridors, related techniques and methods of the Two-guard problem and the search ability of 1-searcher, we put forward concepts of "start phase", "end phase" and "non-separated deadlock" for the circular corridor such that its inner and outer boundaries are mutually weakly visibile. Determinant conditions and methods for the searchable circular corridor by two 1-searchers are studied in detail. A decision algorithm of O(nlogn) time is designed, and a search schedule can be output in the searchable case. Moreover, when the given circular corridor is not searchable by two 1-searchers, there needs no more than three 1-searchers to complete the sweep if its inner and outer boundaries are mutually weakly visibile. Based on this conclusion, a search schedule can be reported in O(m) time, where m(m<n2) denotes walk instructions, n denotes the total number of vertices of P and H.According to the algorithm designed in this paper, we construct test cases and give operation results to verify its correctness and effectiveness.