Alexander G. Gray's Systems Page

We show a novel compiler optimization method for automatically speeding up virtually any program that uses pointer-based data structures (like linked lists, trees, graphs, and dynamically-allocated arrays) using statistical prediction of memory accesses from clock-cycle profiles, building on the SUIF software, in (Jensen and Gray, Profetching: Profile-based Prefetching for Pointer-Based Data Accesses, CMU course report 2001). Though I think we showed some promising experimental results, our attention to this project fizzled before we got to the point of making a general tool.

Stochastic Routing

Fiber-optic cable We introduced two concepts to practical Internet routing, the graph-theoretic notion of maximum flow, and the novel idea of statistical routing, which can be seen to be the direct analog of the foundational idea of statistical multiplexing. We demonstrated that these ideas lead to significant performance improvements in detailed simulations of a real Internet backbone, in (Agrawal, Gray, Konemann, and Schroeder, StatMax: A Novel Scheme for Dynamic Routing with Automatic Load Balancing, CMU course report 2001). Unfortunately, the simulation software we relied on proved to be quite unweildy, and no one really took on the continuation of this project as their primary interest.

Quantum Circuit Design

Given a function one wishes to implement as a quantum circuit, one must represent the function in terms of more primitive quantum circuits, or gates. Finding the most efficient combination of gates is an intractable combinatorial problem. We created a system in Mathematica which performed these optimizations much more efficiently than exhaustive search, using a kind of population search tailored for quantum circuits which can be thought of as a form of `genetic programming'. At the time we knew of no other non-exhaustive system for this task. (Williams and Gray, Automated Design of Quantum Circuits, in Lecture Notes in Computer Science, Special Issue on Quantum Computing and Quantum Communications, 1998.) This project broke my usual rule about working on realistic problems -- unfortunately, quantum circuits don't exist! (At least not yet.)

Advanced Systems

I like to approach all of my research problems the way systems-building research is usually approached: All of the actual constraints of the problem must be treated, all simultaneously -- otherwise the resulting system will be revealed to have little value when it is tested in a realistic setting. Even if you fail, this kind of merciless evaluation makes you work harder and achieve more, I believe.

Autonomous Mars Rover Teams

Intelligent robotics is necessary for planetary exploration, where human presence is costly or impossible. Multiple rovers operating simultaneously in a coordinated fashion can potentially achieve higher efficiency and robustness to malfunctions, but make the problem more complex. We developed a prototype system, the Multi-Rover Intgrated Science Understanding System (MISUS) which provides a framework for autonomously generating and achieving planetary science goals. This system integrates techniques from machine learning with planning and scheduling to enable autonomous multi-rover behavior for analyzing science data, evaluating what new science observations to perform, and deciding what steps should be taken to perform them. These techniques are also integrated with a simulation environment that can model different planetary terrains and science data within a terrain.

Science data analysis in MISUS is performed using machine learning clustering methods, which use image and spectral mineralogical features to help classify different planetary rock types. Specifically, the clustering methods employed look for similarity classes of visible, rock image regions within individual spectral images and across multiple images. These clusters can then be used to help evaluate scientific hypotheses and also to prioritize visible surfaces for further observation based on their ``scientific interest.'' As the clusterer builds a model of the rock type distribution, it continuously assembles a new set of observation goals for a team of rovers to collect from different terrain locations. Thus, the clusterer drives the science process by analyzing the current data set and then deciding what new and interesting observations should be made. Clustering in MISUS is performed by a novel distributed EM algorithm where each rover alternates between independently performing learning computations using its local data and updating the system-wide model through communication among rovers. A planning and scheduling component is used to determine the necessary rover activities required to achieve science goals requested by the learning system. Planning activities are distributed among the individual rovers where each rover is responsible for planning for its own activities. A central planning system is responsible for dividing up the goals among the individual rovers in a fashion that minimizes the total traversing time of all rovers.

Hydrothermal systems were chosen as the main test case, due to the high level of volcanic activity that once took place on Mars. Using geophysical modeling systems such as the USGS's HYDROTHERM, extended by modeling of the distribution of mineral-rich ejecta on the surface of Mars after a meteorite impact, we began testing whether MISUS (in simulation) could reconstruct sub-surface mineral stratigraphy in candidate areas to determine possible extent (temporally and spatially) of hydrothermal activity. (Estlin, Mann, Gray, Rabideau, Castano, Chien, and Mjolsness An Integrated System for Multi-Rover Scientific Exploration, AAAI 1999. Davies, Mjolsness, Gray, Mann, Castano, Estlin, and Saunders, Hypothesis-driven Active Data Analysis of Geological Phenomena Using Semi-Autonomous Rovers: Exploring Simulations of Martian Hydrothermal Deposits, American Geophysical Union Meeting 1999.) I'm not sure what became of this ambitious project since 1999.

???