View planning with time constraints: an adaptive sampling approach

Planning for object search requires the generation and sequencing of views in a continuous space. These generated plans need to consider the effect of overlapping views, and there is typically a limit imposed on the time taken to compute and execute the plans. We formulate this challenging problem of view planning in the presence of overlapping views and time constraints as an Orienteering Problem with history-dependent rewards. In this paper, we focus on the aspect of the problem in which the plan execution time is constrained, but not the planning time. We abstract away the unreliability of perception, and present a sampling-based view planner that simultaneously selects a set of views and a route through them, and incorporates a prior over object locations. We show that our approach outperforms the state of the art methods for the orienteering problem. All algorithms are evaluated in four environments that vary in size and complexity, using a robot simulator that includes a realistic model of robot dynamics. We also demonstrate the robustness of our approach through long-term robot deployment in a real-world environment.