Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection

We introduce a new route-finding problem which considers perception and travel costs simultaneously. Specifi- cally, we consider the problem of finding the shortest tour such that all objects of interest can be detected successfully. To rep- resent a viable detection region for each object, we propose to use an entropy-based viewing score that generates a diameter- bounded region as a viewing neighborhood. We formulate the detection-based trajectory planning problem as a stochastic traveling salesperson problem with neighborhoods and propose a center-visit method that obtains an approximation ratio of O( Dmax Dmin ) for disjoint regions. For non-disjoint regions, our method provides a novel finite detour in 3D, which utilizes the region’s minimum curvature property. Finally, we show that our method can generate efficient trajectories compared to a baseline method in a photo-realistic simulation environment.