View planning with combined view and travel cost

In this thesis, motivated by robotic applications, the problem of view planning with combined view and travel costs (Traveling VPP) is addressed. It refers to planning a sequence of viewpoints to fully inspect the objects of interest and a path to realize these viewpoints, while minimizing the combined view and travel cost. Travel cost is the cumulative time and energy consumption due to the robot movements and thus is proportional to the total robot traveling distance. View cost corresponds to the image processing, image registration and geometric model construction after each view is taken and is proportional to the number of viewpoint planned. First, we assume that the viewpoints are given, the geometries of the object, and the graph encoding the robot paths are known. We give an LP based approximation algorithm. We show that the algorithmic approximation ratio is in the order of the frequency parameter, defined as the maximum number of viewpoints that see a single surface patch of the object. Together with the poly-logarithmic approximation ratio provided by an existing LP based randomized algorithm, the best known approximation ratio to Traveling VPP is the minimum of a constant times frequency and the poly-logarithmic of the input size, which matches the existing hardness result for the Group Steiner Tree problem. Then we introduce the Watchman Route Problem with Discrete View Cost (GWRP), which refers to planning a continuous robot tour inside a polygon and a number of discrete viewpoints on it with the minimum combined view and travel cost, such that every polygon boundary point is visible from at least one planned viewpoint. We propose a novel sampling method to reduce the problem to Traveling VPP with a bounded number of viewpoints. We show that the optimal cost of the GWRP is within a constant ratio of the optimal cost of the reduced Traveling VPP. Thus, we have an approximation algorithm to the GWRP. We implement our approximation algorithm for the GWRP for realistic environment. We present some preliminary experimental results that show the power of the algorithm.