Sub-optimal 3D volume convergence with time and fuel constraints
Dan O. Popa, Shaminder Singh, John Ting-Yung Wen, Robert J. Szczerba · 2003
We consider the problem of detecting objects in a 3D region of space, using a mobile vehicle equipped with proximity sensors. A particular application is searching an area of the ocean for submarines using helicopters equipped with a dipping sonar. The vehicle can travel between any arbitrary points in the 3D space (a "move") and can decide to stop, collect, and process sensory data to determine the location of the objects (a "ping"). We assume that the only known a priori information are the probability distribution map of objects' location, and the 3D coverage region from each point in space. Each move and ping operation takes a certain amount of time and fuel. The objective is to find the sequence of moves and pings (a "bath") which maximize the expected value of detecting the objects given additional time and fuel constraints. Usually, the search space is very large and the search time is very small, such that it is not possible to exhaustively perform detect operations from each point. Using a discrete cubic cell decomposition of the search space, we pose the problem in both a discrete optimal control and a combinatorial optimization framework. We then investigate the numerical feasibility of several sub-optimal, polynomial type algorithms in solving the problem.