Unsupervised 3D Scene Understanding and Prediction to Enable Adaptable Solutions to the Art Gallery Problem and Watchman Route Problem

摘要

The art gallery problem (AGP) asks the question: "How can we place a small set of sensors to provide maximum coverage of an observed environment?" The watchman route problem (WRP) operates in conjunction with the AGP by asking the question "How do we create the shortest route between AGP-solving positions?" The objective of this work is to provide a means of assessing where to place both static and mobile sensors in order to solve the AGP and WRP, respectively, while adapting subsequent AGP/WRP-solutions in anticipation of future events. We can fulfill this objective by 1) extracting a 3D point cloud representation of the item of interest (IOI) to be surveiled in a video frame, 2) determine highest probability anticipated behavior by the IOI based upon training data and 3) incorporate the information gained from items 1 and 2 in order to obtain approximate solutions to the AGP and WRP using the respective Sensor Placement Optimization via Queries (SPOQ) and the Photon-mapping-informed active-Contour Route Designator (PICRD) algorithms. In this paper, we show how to obtain the requirements embodied in items 1, 2 and 3 and thus fulfill our objective.