A unified framework for two-guard street walk problems

摘要

Imagine that two robots collaborate to search in a street area, which has an entrance and an exit. At an abstract level, this is the well-known two-guard street walk problem. In essence, given a simple polygon <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i> with two distinct vertices s and <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">g</i> on its boundary and two guards (robots), the general street walk problem asks whether the two guards can move on the boundary of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i> from s to <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">g</i> in the opposite directions such that they always maintain their mutual visibility. The other variations, i.e., straight street walk, counter street walk, straight counter street walk, have also been studied. In this paper, we propose a simple unified framework for characterizing walkable streets under these variations.