Algorithms for Optimizing Search Schedules in a Polygon

computational geometry;visibility;Computer Science

Bahun, Stephen

University of Waterloo

关键词: computational geometry;    visibility;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3964/1/BahunThesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In the area of motion planning, considerable work has been done on guardingproblems, where ;;guards;;, modelled as points, must guard a polygonalspace from ;;intruders;;. Different variantsof this problem involve varying a number of factors. The guards performing the search may vary in terms of their number, their mobility, and theirrange of vision. The model of intruders may or may not allow them to move. The polygon being searched may have a specified starting point,a specified ending point, or neither of these. The typical question askedabout one of these problems is whether or not certain polygons can besearched under a particular guarding paradigm defined by the typesof guards and intruders.In this thesis, we focus on two cases of a chain of guards searchinga room (polygon with a specific starting point) for mobile intruders.The intruders must never be allowed to escape through the door undetected.In the case of the two guard problem, the guards must start at the door point and move in opposite directions along the boundary of the polygon, never crossing the door point. At all times, theguards must be able to see each other. The search is complete once bothguards occupy the same spot elsewhere on the polygon. In the case ofa chain of three guards, consecutive guards in the chain must alwaysbe visible. Again, the search starts at the door point, and the outerguards of the chain must move from the door in opposite directions. These outer guards must always remain on the boundary of the polygon.The search is complete once the chain lies entirely on a portion of the polygon boundary not containing the door point.Determining whether a polygon can be searched is a problem in the area of visibility in polygons; further to that, our work is relatedto the area of planning algorithms. We look for ways to find optimal schedules that minimizethe distance or time required to complete the search. This is doneby finding shortest paths in visibility diagrams that indicate valid positions for the guards. In the case ofthe two-guard room search, we are able to find the shortest distanceschedule and the quickest schedule. The shortest distance scheduleis found in O(n^2) time by solving an L_1 shortest path problem among curved obstacles in two dimensions. The quickest search schedule is found in O(n^4) time by solving an L_infinity shortest pathproblem among curved obstacles in two dimensions.For the chain of three guards, a search schedule minimizing the totaldistance travelled by the outer guards is found in O(n^6) time bysolving an L_1 shortest path problem among curved obstacles in two dimensions.