Interval-Related Talks at the Second SC-COSMIC Student Conference, El Paso, TX, October 25-27, 1996

On October 25-27, 1996, the Second SC-COSMIC Student Conference on Computational Sciences was held in El Paso, Texas. This conference was sponsored by the National Science Foundation (NSF), by the Center for Research on Parallel Computation (CRPC) at Rice University, NASA Pan-American Center for Earth and Environmental Studies (PACES), the University of Texas at El Paso (UTEP), and UTEP Center for Theoretical Research and its Applications in Computer Science (TRACS). Short abstracts of the student papers were published.

This conference included the Student Symposium on Computations in Astronomy, Space, and Earth sciences (CASE'96). We were lucky to have as a keynote speaker France Cordova who has recently finished her tenure as NASA's Chief Scientist to join the University of California at Santa Barbara as Vice Chancellor of Research. Dr. Cordova gave an exciting overview of the major directions of NASA research, including Exobiology (search for life and intelligence outside Earth), Mission to Planet Earth (use of spaceships to monitor processes on Earth), and Cosmology. Her emphasis on the need for new computational techniques was emphasized by another keynote talk, by Dr. Scott Starks, the Director of the NASA PACES Center, who said that only 1 to 10% of the data collected from the space missions are actually processed. This is partly caused by the fact that most of the collected bits are useless, because they represent the measurement results below the noise level. From this viewpoint, interval methods, that can automatically filter such useless measurements, can be of great help.


The highlighted talk was given by David Morales, one of the student designers of the award-winning interval-using robot. He briefly described the award-winning robot software, and then elaborated on the project that the group is working on right now. The original robot was planned to move in a competition environment, where it was assumed that the corridors were not completely blocked, and that therefore, a robot was always able to navigate towards its goal location. In real-life world, especially in future space applications, it is quite possible that the paths will be temporarily or permanently blocked. If the paths are blocked, then it is desirable not to waste the precious battery energy for futile repeated attempts to find a way, it is better to think up a new path or simply to wait until the path clears. The problem is how to check whether the robot is stuck (especially if the motor is running, but the robot is not moving anywhere). If all the sensors were precise, then "stuck" would mean that the sensor's reading in the current moment of time would be identical to its reading in the previous moment of time. Real-life sensors (sonars and infrared) are rather inaccurate, so the actual reading may change even if the robot stalls. To take this inaccuracy into consideration, the robot considers, instead of the actual sensor readings Xi that may differ from the actual values, the intervals [xi]=[Xi-Di,Xi+Di] of possible actual values, and considers itself stalled if for each sensor i, the intervals [xi(k)] and [xi(k+1)] that correspond to two sequential moments of time k and k+1 have a non-zero intersection.

The talk was followed by a demonstration of the new algorithm. When we moved around a robot, it desperately (and, most often, successfully) avoided the obstacles (i.e., us) and continued moving. When we stood motionless around it, the robot sensed being stalled and stopped "to think" (the robot was only once cheated by the steep surface).

Signal Processing

An interval-related signal processing problem was handled in a talk by Richard Coronado, J. Anderson, Jorge Lopez, Raul Armendariz, and Jaime Morales from NASA/Caltech Jet Propulsion Laboratory and UTEP. They try to detect periodicities within a signal collected from the Pioneer 10 spaceship in 1988 and 1993. Part of the interest is that these periodicities may correspond to gravitational waves.

Several techniques can be used to trace these periodicities. The main computational problem is: if we apply these techniques to the measured signal and they uncover some periodicities, we would like to know whether these periodicities are real, or whether they are noise-related artifacts on top of non-periodic real signals. For interval-valued errors, this problems becomes interval-related. The easiest thing is to show that some periodicities are not for real: for that, it is sufficient to show that within the error-induced intervals [x](t)=[X(t)-D,X(t)+D] there are signals x(t) that have no periodic component with the supposedly observed frequency. This was actually shown for the 1993 data. For the 1988 data, so far, all attempts to find such aperiodic functions $x(t)$ have failed, which may be an indication that these periodicities are real (although their amplitudes and frequency exclude the possibility of them being caused by gravitational waves).

This is still work in progress, made extremely complicated by the fact that part of the noise is of a clearly statistical nature.

Structural chemistry

The third interesting interval-related talk, by Adriana Beltran and James Salvador, was related to structural chemistry and its possible applications in exobiology. The existing techniques of chemical analysis enable us to describe what atoms a molecule consists of, and what are the links between different atoms, but the exact spatial structure of complicated organic molecules is difficult to describe (such techniques were described in another talk, by Stephanie Ann Hoogendoorn, from the University of Houston-Downtown and the Los Alamos National Laboratory). So, often, the only information that we have to identify an unknown substance is a graph in which atoms are nodes and links are edges. Identification means that must, among the graphs stored in the computer memory, find a one that is isomorphic to the one that we are observing.

Unfortunately, checking whether two given graphs are isomorphic is known to be a hard problem (conjectured to be NP-hard, i.e., computationally intractable). To solve this problem, the authors use a result (based on a theorem proven by S. Ulam's) according to which two graphs are isomorphic if and only if certain real numbers constructed from these graphs coincide. If we have to compute these numbers with unlimited accuracy, then we run into the same computational problems as before. If we use standard (approximate) computer arithmetic to compute these numbers, then sometimes two different graphs will be assigned the same number, and sometimes, due to computer roundings, two isomorphic graphs can be assigned different numbers. The authors' algorithm uses the appropriate directed roundings and thus (as the authors claim), eliminates the second problem. The first problem remains, but intensive computer simulation shows that for graphs of reasonable size (with 30 to 40 atoms) only 1/100,000 of all possible graphs have non-isomorphic ``twins'' with the same values of the index. Hence, the rounding-spoiled fast identification algorithm works correctly in 99.999% of all cases.

Reported by Ann Q. Gates, Chenyi Hu, and Vladik Kreinovich.