[back]

Path-Planning for Feature-Recognition and Classification using Information Theoretic Methods
Tim Chung, Joel Burdick, Richard Murray

Abstract. This project investigates the role of information-theoretic techniques in cooperative multi-agent systems. These techniques are used to govern the path planning of agents to optimally classify features of interest by improving the quality of the measurements. Sensor measurements are assumed to be in the presence of noise. We consider issues associated with distributed systems such as sensor fusion of information and formation control of relative vehicle locations. The objective is to articulate the theory underlying the relationship between sensing tasks and cooperative control.

Project Summary. As computational and technological advances allow for sensor networks to implement mobile sensing elements, the integration of cooperative control in multi-vehicle systems and sensor-based path-planning strategies becomes essential. This interface yields many interesting areas of research, such as cooperative decision-making for achieving distributed sensing objectives.

Applications range widely in variety, such as exploratory tasks in dangerous environments as in search-and-rescue operations, where the ability of mobile agents to reliably classify a target as human may lead to rescue. Another use involves military target classification, where measurements determine whether targets are friendly, neutral or foe. As a simplified illustration, we examine the latter case where three tracking vehicles are tasked to classify a single entity vehicle as friendly or foe by measuring the entity position.

For classification tasks in general, a set of features taken from measurements (e.g. color, velocity, shape, markings, etc.) is used to categorize the subject. Given that these measurements are corrupted by noise, the classification must be examined in a probabilistic context. The uncertainty in measurements is thus assumed to be Gaussian, and the sensor(s) used are characterized with specified uncertainty profiles. For our example, we use range-finding sensors such as sonar, which have noise present in range and bearing measurements. We construct the sensor to have a “sweet spot” in the range sensing, i.e. an optimal range from the target where measurements have minimum uncertainty. There is assumed to be no preferential bearing angle, i.e. uncertainty in bearing is independent of the orientation of the target. Such uncertainty profiles are shown in Figure 7, where minimum range uncertainty occurs when the target is ~6m away, and bearing uncertainty with respect to target orientation is constant.

Figure 7. Uncertainty Profiles of Range and Bearing Measurements

The goal in path-planning is to develop a trajectory of the vehicle which allows measurements to be taken with minimum uncertainty. In this context, we examine a quantity called mutual information, which is the information contained in one random variable about another random variable. Specifically, we are interested in the relationship between the measurements taken by the sensors of some subject and the classification of that subject into discrete categories.

Given the sensor profile, the mutual information can be computed locally, and used by the vehicles to determine the path which maximizes the mutual information, that is, the path along which measurements taken will yield more information about the class of the target. The mutual information surface for our sample uncertainty profiles is given by Figure 8. By applying simple gradient ascent techniques, the path that maximizes the mutual information is one that adjusts the range to ~6m without any bearing preference, as expected.

Figure 8. Mutual Information for the Specified Uncertainty Profile

Simple simulation envisages the three vehicles attempting to track and classify a single entity. Initial work supplies the proof-of-concept for the applicability of mutual information as a guiding tool, as seen in Figure 9.

Figure 9. Simulation of Motion-Planning Using Mutual Information

An obvious extension to this research is the incorporation of cooperative methods amongst the tracking vehicles to collectively achieve the maximal mutual information, and hence to generate trajectories for each vehicle towards a global, rather than local, optimal solution. Sensor fusion algorithms may also be implemented at different levels – measurement, classification, or decision-making – to examine decentralization issues associated with this classification problem. Further, entity motion, such as adversarial behavior to avoid detection, is of interest in the application of friend-foe scenarios. Future work includes these extensions, as well as a generalization of the underlying theory in classification and decision theory.

References
T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 1991.

B. Grocholsky. “Information-Theoretic Control of Multiple Sensor Platforms.” The University of Sydney, Ph.D Thesis, 2002.

D. Erdogmus, J. Principe and R. Thogulua. “Information Theoretic Organization Principles for Autonomous Multiple-Agents.” In Cooperative Control and Optimization. Kluwer Academic, 2003.

A. Logothetis, A. Isaksson and R. Evans. “An Information Theoretic Approach to Observer Path Design for Bearings-Only Tracking.” Proc. of the 36th Conference on Decision and Control. 1997. pp. 3132-3137