This article is published in the January 2006 issue.

Computing Research at SRI International

By: William S. MarkIn: /

Computer science at SRI International includes many firsts, from the first electronic banking system to invention of the computer mouse. SRI innovations have created new industries, billions of dollars in market value, and lasting benefits to society.

  • Personal Computing. The personal computer revolution was launched when SRI invented the computer mouse in 1964, and in 1968 demonstrated the concept of windows, hypertext, and videoconferencing.
  • Internet. In 1969, SRI received the first logon on the ARPANET, which was the first connection over a broad-area packet-switched computer network. In 1976, SRI also established the first transmission across dissimilar networks, bridging the wired ARPANET and the wireless, mobile PRNET packet radio network located in a van. The digital link was the beginning of internetworked computing that became the Internet.
  • Wireless Communication. In 1977, SRI sent the first wireless packetized voice message over its packet radio network and across the ARPANET. This technology was the precursor to today’s Voice-over-Internet Protocol (VoIP) technology.

Since its founding in 1946 as Stanford Research Institute, and becoming SRI International in 1977, SRI has collaborated with leading universities, and responded to research and development needs of government agencies (including DARPA, NSF, NASA and NIH) and corporations. The Information and Computing Sciences (ICS) Division pushes the boundaries of computing through programs emphasizing artificial intelligence, computer science, and speech research.

Artificial Intelligence

Since 1966, SRI International has been at the forefront in developing computer capabilities for intelligent behavior in complex situations.

  • Robotics. From Shakey, the first autonomous mobile robot that could reason about its own surroundings in 1972, to the Centibots, one of the first and largest teams of coordinated robots in 2004, SRI has pioneered advanced robotics demonstrating adaptation to new tasks, team organization, scalability, map building, and fault-tolerant communication.
  • Computer Vision. SRI is advancing techniques for three-dimensional object recognition, location, tracking, and change detection from a range of sensors. Recent work includes real-time visual odometry from stereo and recognition of people and vehicles from very short video clips taken from unmanned aerial vehicles.
  • Automated Reasoning. SRI researchers have been responsible for major developments in resolution theorem proving (PTTP and SNARK systems) and its application to reasoning by abduction in natural-language interpretation, to software synthesis and, more recently, to the composition of web services.
  • Planning and Control. SRI pioneered the development of generative planning (with STRIPS, QA4 and NOAH systems) and reactive planning (with PRS). It is currently leading the development of integrated human-machine planning and execution monitoring methods based on the advice paradigm.
  • Knowledge Acquisition. SRI is developing techniques that allow domain experts to enter into a knowledge base information rich enough to allow a system using it to answer questions as difficult as those found in standard achievement tests, using declarative inference and simulation.
  • Integrated Learning. SRI is leading a group of more than 20 universities and companies in the CALO project, whose objective is to integrate learning with sensing, reasoning and action, and to evaluate it in an intelligent assistant system that learns “in the wild.” At the end of its second year, the CALO system demonstrated significant improvement in its performance due to learning in a test modeled on a standard achievement test.
  • Structured Argumentation. SRI has developed and fielded a set of tools allowing intelligence analysts to collaborate on the design of analysis methods, to define complex patterns for searching databases, and to brainstorm solutions.
  • Bioinformatics. SRI is building and distributing pathway genome databases for more than 140 organisms, along with development and visualization tools. Novel machine learning algorithms predict the metabolic pathway complement of an organism from its genome. New methods based on rewriting logic are being used for the modeling and analysis of signal transduction and metabolic networks in mammalian cells.

Computer Science

SRI International’s contributions to computer science began in the early 1950s with the development of the first banking industry computer, the Electronic Recording Method of Accounting (ERMA).

  • Cyber Security. Pioneering novel methods of network intrusion detection, protocol development and evaluation, and distributed transaction processing, SRI develops trustworthy, secure solutions to reliable business and personal communication needs. Since 1983, the Intrusion Detection Expert System (IDES), Next-Generation IDES (NIDES), and EMERALD have performed real-time monitoring of user activity on multiple target systems.

In the 1970s and 1980s, SRI pioneered security work such as PSOS (described below), the formal methods used to analyze the Kernelized Secure Operating System, and SeaView (a multilevel-secure database management system). SRI is developing advanced networking with privacy controls for collaboration over secure virtual subnets, and runs the Department of Homeland Security’s Cyber Security Research and Development Center. Ongoing research projects address large-scale network security, wireless security, supervisory control and data acquisition (SCADA) system security, and privacy-enhancing technologies.

  • Advanced Computing. SRI pushes the boundaries of computing through new methods for distributed information processing, computational logic, and formal verification of computer systems, studying the logical foundations of scalable systems beyond the scope of traditional testing and simulation, and building efficient tools for rigorous mechanical analysis.

With the software-implemented fault-tolerant (SIFT) avionics computer in the 1970s, SRI invented the modern approach to fault tolerance, based on Byzantine fault models and state machine replication. In the same period, SRI’s Provably Secure Operating System (PSOS) pioneered modern approaches to security, leading to the concepts of noninterference and separation kernels. Both SIFT and PSOS benefited from mechanically assisted formal verification using the Hierarchical Development Methodology (HDM), which was one of the first formal specification languages with theorem proving support.

SRI continues to develop tools for formal verification, and is the only group with state-of-the-art capabilities in mechanized theorem proving (PVS verification system), model checking (SAL suite of model checkers), and embedded deduction (ICS solver for SAT, MaxSAT, and SMT problems). SRI and external users of these tools apply them to challenging problems in assurance for dependable automotive and avionics systems and for Multiple Independent Level Security (MILS) systems, and to other applications requiring high assurance. These tools have recently been applied to molecular and whole-organism systems biology.

Speech Research

SRI International is a recognized leader in advanced research in speech technologies. SRI develops and licenses speech recognition engines and tools packaged as software development toolkits, which developers incorporate into their products and services.

  • Speech Recognition. In the 1990s, SRI spun off market leader Nuance Communications, Inc. (Nas:NUAN) to exploit its speech recognition technology for automated access to information and services over the telephone, as first used by Charles Schwab & Co., Inc. for stock quotes in 1996. Customers of Nuance are using it today for travel reservations, product ordering, and banking. U.S. soldiers use SRI spoken translation technology overseas. EduSpeak® software brings speaker-independent voice recognition to education and training software. DynaSpeak® speech recognition technology is licensed for products requiring a small footprint, such as mobile and embedded platforms.
  • Speaker ID. SRI is a pioneer in modeling speaking “style,” or behavioral aspects of how a person talks, and integrating this information with conventional features modeling voice characteristics. SRI’s state-of-the-art speaker recognition uses short-term spectral features, and high-level features estimated from patterns of prosodic events. The SRI system has been ranked as one of the best systems on text-independent tasks by the National Institute of Standards and Technology for the past three years.
  • Prosody. SRI pioneered the use of “direct modeling” of prosody (intonation, duration, energy, voice quality), using information automatically extracted from speech audio based on the output of automatic speech recognition. Successful applications have included automatic punctuation and topic detection, emotion recognition, dialog act modeling, detection of deceptive speech, and automatic speaker verification.

Distinguished Information and Computing Sciences Staff at SRI

The 170-person professional staff of SRI International’s ICS Division includes many noted contributors to advancements that have an impact throughout the computing world, including Fellows of the Institute of Electrical and Electronics Engineers (IEEE), Association for Computing Machinery (ACM), American Association for the Advancement of Science (AAAS), and American Association for Artificial Intelligence (AAAI).

Other distinctions include the 2002 National Computer System Security Award, the 2002 Herbrand Award for contributions to Automated Reasoning, and the 2005 ACM SIGSAC Outstanding Contributions Award.

Commercialization

Bringing a new product or service to the marketplace requires a collaborative, disciplined approach. SRI develops ideas into compelling solutions to create new value for clients. We start by understanding their important needs to form just the right team. Together, we determine an approach to maximize return on investment.

Government agencies, commercial businesses, and private foundations turn to SRI for solutions to important problems. SRI offers each client flexible working relationships to meet its specialized needs. We respond to client-sponsored research and development, technologies for license, strategic partnerships, and new spin-off ventures. Our clients capitalize on SRI’s experience at all stages of the value chain: basic and applied research, technology development, prototyping, and product commercialization.

Dr. Mark (william.mark [at] sri.com) is Vice President, Information and Computing Sciences, at SRI International (http://www.sri.com).

Computing Research at SRI International