|
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.
|
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.
|
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.)
|
|
|
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.
|
|