Adaptive Sampling-based View Planning under Time Constraints

Planning for object search requires the generation and sequencing of views in a continuous space. These plans need to consider the effect of overlapping views and a limit imposed on the time taken to compute and execute the plans. We formulate the problem of view planning in the presence of overlapping views and time constraints as an Orienteering Problem with history-dependent rewards. We consider two variants of this problem—in variant (I) only the plan execution time is constrained, whereas in variant (II) both planning and execution time are constrained. 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 by evaluating all algorithms in four environments that vary in size and complexity.