Research Abstracts - 2007

Optimal Exploration for Optimizing Map Fidelity

Optimal exploration is the process of selecting a sequence of sensing actions that maximizes information utility. Optimal exploration has many real world applications where the objective is to maximize the overall awareness of a survey area. For example, we may wish to measure the ocean depth using an autonomous underwater vehicle (AUV). In this example, an optimal exploration strategy requires a sequence of measurements that maximizes map accuracy. Sensor mapping strategies exist which seek to efficiently cover an area of interest. However, these strategies do not directly optimize the plan for creating the most accurate map possible.

Application

We address the specific problem of autonomous bathymetric mapping. Bathymetry is the study of underwater depth. A bathymetric map shows seafloor terrain. We can collect bathymetric sonar data using an AUV. This sensing platform is integral to the undersea data network planned for Monterey Bay; the first state-of-the-art power and communications highway into the deep sea. The AUV, to be used as our sensing platform, needs to operate reliably in an uncertain environment. This includes uncertainty over the sensor data which we expect to collect. This is best achieved by planning for uncertain outcomes and reacting to them as they occur. For example, we start with a low fidelity map of our sensing area. We then generate a plan and begin collecting data over this area. When our new data is consistent with our prior knowledge, our certainty increases substantially. However, if our new data conflicts with our prior belief, our certainty is challenged. Consequently, these areas require more attention, and our plan is adapted accordingly. This is the essence of adaptive undersea bathymetric sampling. That is, we direct sensor resources to areas where they are most useful. Utility is measured in terms of uncertainty reduction. The ultimate goal is to build a map of the environment that maximizes map fidelity and the solution is an ordered set of sensing actions which achieve this goal.

Model

We model the environment as a discrete grid, just like a typical bathymetric map. Our actions consist of the locations at which to make sensor measurements. Our actions are selected solely to maximize information gain, and thus map accuracy. We model this problem as a continuous belief-space Markov process where the current state is our belief about the map at each grid location. Our transition function is the probability of getting a particular sensor sample as the result of a given sensing action. The next belief-state is implicitly defined by a Bayesian update given that sample.

Approach

While the optimal selection of sensing actions is essential for success in a wide variety of real world applications, existing approaches are computationally complex and time consuming. Our research goal is to improve upon current algorithms for computing an optimal set of sensing actions. In general, the solution techniques applied to the optimal exploration problem involve search, greedy information gain and application specific mathematical methods. In contrast, we are exploring reinforcement learning approaches such as William's REINFORCE and approximate dynamic programming. Our William's REINFORCE approach uses agents to learn the optimal action set given our current state. Our approximate dynamic programming approach combines dynamic programming and function approximation to learn a policy over our entire state space. Both take and information theoretic approache to maximizing total map accuracy.