UC Berkeley

The advancement of computing technology has enabled the practical development of intelligent autonomous systems. Intelligent autonomous systems can be used to perform difficult sensing tasks. One such sensing task is to search for and track targets over large geographic areas. Searching for and tracking targets over geographic areas has important applications. These applications include search and rescue, boarder patrol, and reconnaissance. Inherent in applications such as these is the need for high accuracy of observation while performing repetitive, mundane tasks. Additionally, in many of these applications is inherent danger. Fortunately, computers are excellent at performing repetitive, mundane tasks. Also, no loss of life is threatened if intelligent autonomous systems are used for these applications. It is then important to develop computational methods for performing autonomous search and tracking of targets over geographic areas.

In order to perform autonomous search and tracking, intelligent autonomous systems often consist of a team of agents with sensors for making observations. Examples of agents include ground robots, unmanned aerial vehicles, unmanned underwater vehicles, and unmanned spacecraft. The current state-of-the-art approach to accomplish search and tracking decomposes the problem into two parts. The first part is target location estimation. The second part is agent path planning based on the target estimation. As the number of targets increases, the estimation space increases. And when the number of targets is unknown, the dimension of the estimation space is unknown. For the case of general non-parametric estimation, path planning over such a space then becomes a difficult task.

The focus of this dissertation is to develop an alternative approach for autonomous search and tracking. This alternative approach simplifies agent path planning when the number of targets is unknown. This simplification is accomplished in two steps. The first step is to reduce the space over which path planning is performed. This is done by transforming the target location estimation into a target density distribution. The target density distribution is defined over the space of the geographic area. So, the dimension of the target density distribution is potentially much lower than the dimension of the target location estimation space. The second step is to change the objective of search and tracking. In state-of-the-art search and tracking, the objective is to search for and track targets. When the number of targets is unknown, this objective becomes difficult to define. However, over the geographic area, it is possible to define a finite set of regions that change with time. These regions are defined by analyzing the target density distribution. Given this finite set of regions, the objective is then changed to search for and track these regions. By doing this, the objective is shifted from searching and tracking an unknown number of targets to searching and tracking a known number of regions.

Four types of regions are identified in this dissertation. These types of regions are 1) exploration regions, 2) searching regions, 3) tracking regions, and 4) target nullity regions. Exploration regions are those regions over which little information is available, such as regions with uniform distribution of target density. Searching regions are those regions over which significant information is available to guide a search effort. Tracking regions are those regions over which the information available is very certain, specifying near exact target location. Target nullity regions are those regions that have been searched and in which no targets have been observed. In this dissertation, a method for classifying these regions through time is presented. This method is called time-evolving partition classification. Methods are also presented to optimize agent paths over these types of regions.

The search and tracking approach developed in this dissertation was tested for the case when agents are fixed wing aircraft. This approach was tested thoroughly in simulations. Additionally, several components of this approach were tested in experiments. These results are presented. Based on these results, the approach developed in this dissertation performs better than state-of-the-art approaches. This increase in performance applies to the case when the number of targets is unknown and target estimation is general and non-parametric.