XCON (R1) expert system: Expert systems go into production

The narrow claim: a configurer that went to work

In January 1980, Digital Equipment Corporation (DEC) began using a rule-based program called R1 to check and lay out orders for its VAX-11/780 computers. John McDermott had built it at Carnegie-Mellon University, starting in December 1978. His first conference account, R1: An Expert in the Computer Systems Domain, presented at the first national AAAI conference in 1980, describes a program whose input was a customer's order and whose output was a set of diagrams showing how the roughly 90 components of a typical system should be physically arranged, with missing parts added where the order was incomplete. As of June 1980 it held 772 rules and was used on a regular basis by DEC's manufacturing organization.

The name needs a note. The same paper records that the program was called XCON during its first months; it was published as R1, while inside DEC it was, as a 1984 review by its developers put it, called R1 by some and XCON by others. This report uses both names for the same system.

The documented claim is modest: a program built by hand from expert knowledge performed a recurring industrial task every working day inside a large company, for years. It reasoned about nothing but DEC hardware, and it did not learn. Its importance lies elsewhere. R1 became the standard proof that expert systems could earn their keep, and its builders documented, unusually candidly, what it cost to keep such a system correct while the world it described kept changing. Both halves of that record matter for placing it in AI history.

Why every VAX order was a puzzle

DEC's problem came from its sales strategy. As McDermott explained in R1: The Formative Years, the company did not market a few standard systems; it sold processors with many options and let customers tailor them, so most systems it shipped were one of a kind. Each order posed its own problem: which cabinets, backplanes, controllers and cables were needed, where each module should sit, and whether the order was even complete. Several attempts to automate the task with conventional programs had failed, which McDermott attributed to how knowledge-intensive it was.

The human version of the job belonged to technical editors. According to Bachant and McDermott's four-year review, an editor examined each order, typically the day before the system was assembled, decided whether constraints required additional or different components, and specified some relationships among them. Even at that fairly abstract level an order seldom took less than 5 or 10 minutes, and complex orders took much longer. Stephen Polit of DEC, in an account of AI technology transfer at the company, described the process as a bottleneck: some orders combined parts that would not work together, and others lacked essential components.

The bridge to the university was both personal and historical. Polit notes that DEC had been the main hardware vendor to academic AI in the 1970s, when the two major LISP dialects were developed on its DECsystem-10 and DECsystem-20 machines. Sam Fuller, a Carnegie-Mellon computer scientist who joined DEC early in 1978, suggested that autumn that a knowledge-based approach might work, and brought the university's production-system group together with Herb Shanzer, the DEC manager responsible for configuration. Shanzer would not fund the work at first, so McDermott offered a quick prototype. The team chose the VAX-11/780 over the PDP-11 line, which McDermott later called fortunate: PDP-11 systems supported more than ten times as many components under looser constraints ( The Formative Years).

From a three-month prototype to the factory floor

McDermott spent several days at DEC in December 1978 learning the task from Dick Caruso, an engineer who had already broken it into subtasks. The prototype, written in OPS4, a production-system language developed at Carnegie-Mellon with DARPA support, had about 250 rules and took about three man-months. Shown to about 60 people at DEC in April 1979, it met what McDermott called guarded enthusiasm, and DEC agreed to support further work, with Dennis O'Connor of systems manufacturing as sponsor.

The next phase became a commitment to deliver, by the end of September 1979, a program that could correctly configure at least 75 percent of orders and be easily extended for the rest; the team made it with a day and a half to spare. Knowledge grew by what became the standard expert-system method: R1 configured orders, experts criticized the output, and each criticism produced new rules or split an old one. The rule count roughly tripled, to about 750, and handling special situations turned out to take about twice as much knowledge as the basic task. In parallel, DEC engineers spent about three man-months describing the 420 components then supported on the VAX-11/780, because no single DEC source held the facts the program needed.

In October and November 1979, DEC ran a formal validation. Six experts examined R1's output on the 50 most recently booked orders, spending from about one to eight hours per order. They found 12 errors, all easily fixed, and all but two concerned detail below the level at which human configurers worked at all ( The Formative Years). The 1980 paper adds that R1 fired an average of 1,056 rules and used about 2.5 minutes of processor time per order on a DEC PDP-10. Regular use began in January 1980, with the former VAX technical editor as R1's supervisor, and that year the program spread to all of DEC's final assembly and test plants in the United States. By 1981, a paper by McDermott and Barbara Steele reported that R1 configured almost all VAX-11 systems DEC shipped, maintained by a DEC group of 15 people.

How R1 decided without searching

R1 was a production system. As the 1980 paper describes it, OPS4 kept permanent knowledge as rules in a production memory and the evolving configuration as data in a working memory; on each recognize-act cycle the interpreter found every rule whose conditions matched and executed one. R1 added a third store, the component database, holding a description of each part. Rules were grouped by subtask, so each could assume a context. One published rule, translated into English, says in effect: if the context is putting UNIBUS modules into backplanes, the next module is a multiplexer terminal interface without panel space, and a suitable backplane has enough free slots, then turn to verifying panel space for that multiplexer. When several rules matched, OPS preferred the more specific one, a strategy R1 relied on heavily.

The technically interesting claim concerns method. R1 differed from earlier domain-specific systems chiefly in using what Allen Newell had called Match rather than generate-and-test. Where DENDRAL proposed candidate molecular structures and then tested them, R1's knowledge at each step was enough to recognize an extension that lay on a solution path. False paths were never generated, so backtracking was unnecessary and the test rules McDermott had planned proved superfluous ( The Formative Years). In the 1980 paper's figures, each rule could be preceded or followed, on average, by three others, so the space of possible firing sequences was large, yet a configuration without backtracking followed a single path of about 800 steps. The one exception was choosing an acceptable order for modules on the UNIBUS, where R1 occasionally generated a few candidate sequences.

The design explains both R1's fast development and its later troubles. Because each rule carried its own description of when it applied, new knowledge could usually be added as another rule without rewriting the rest, and the paper notes that OPS4's cycle time was essentially independent of the size of both memories, citing Charles Forgy's Rete matching algorithm. But nothing in the language recorded why rules belonged together or in what order they were meant to fire. That absence did not matter at 772 rules. It mattered at several thousand. The fullest technical account, a fifty-page article titled R1: A Rule-Based Configurer of Computer Systems, appeared in the journal Artificial Intelligence in September 1982, by which time the system it described had already been reimplemented and substantially extended.

The numbers, and why they disagree

Rule counts for R1 vary from source to source, and the variation is itself informative. The June 1980 paper gives 772 rules, of which only 480 were configuration rules, the rest being more general knowledge needed to apply them. McDermott's 1981 history gives about 750 for September 1979, and the 1984 review lists 777 for the initial version. Then, in 1980, the system was rewritten in the newer OPS5 language, a four-man-month effort that produced a more capable program of about 500 rules: about 100 test rules and 50 database-access rules disappeared, and about 150 more went by finding generalizations and cutting redundancy ( The Formative Years). New capabilities pushed the count to about 850 by December 1980.

Growth then accelerated. The 1984 review records about 2,000 rules by mid-1982, when R1 could also configure the VAX-11/730 and PDP-11/23+, and about 3,300 by November 1983, when it covered every system DEC sold in significant volume. Its database had grown to about 5,500 component descriptions, out of more than 100,000 parts that could appear on an order. A rule count is therefore a snapshot of a system that was continually rewritten, merged and extended, not the size of a fixed program.

Accuracy figures need the same care. From May to December 1980, plant staff filed problem reports on about 40 percent of orders, split fairly evenly among bad database entries, wrong or missing rules, input errors and mistaken reports. Many at DEC were disturbed, having expected at least 90 percent correct soon after validation. The 1984 review says reaching the 90 to 95 percent target took three years, and that by then fewer than one order in a thousand was misconfigured because of missing or incorrect rules, after more than 80,000 orders. The authors criticized their own yardstick, since the percentage of totally correct orders could not distinguish a gross error from a trivial one. In one quarter of 1983, bogus reports, where a human reviewer wrongly flagged a correct configuration, ran at double the number of real rule errors. Processing time also moved: about 2.5 minutes per order on the PDP-10, about 15 after a move to a VAX-11/780 in August 1980, and about 1.67 on the VAX by 1984.

The expert that was never finished

The central lesson of R1, stated repeatedly by the people who built it, is that it was never done. In 1981 McDermott described how one plant manager's complaint in July 1980 reshaped the program: plants did not want missing components added to the roughly 20 percent of orders that arrived incomplete, so R1 was changed to configure such orders twice, the second time leaving aside parts with missing prerequisites. Capabilities for customer-specific guidelines and room floor layouts followed, and knowledge grew at least as much in that period as in any earlier one. His closing worry was that DEC still treated R1 as a program rather than an expert. Finished programs have no bugs, he observed, but "When experts are finished, on the other hand, they're dead" ( The Formative Years).

The 1984 review turned the worry into data. Its authors had expected R1 to settle eventually into a maintenance mode of minor additions; four years in, they doubted it would ever be finished, because DEC kept introducing products and users kept asking for one more capability. Adding knowledge consumed about four worker-years a year. A July 1982 change to how components were categorized, made so that other DEC systems could share a common database, forced changes to nearly all of the roughly 2,000 rules, several hundred of which took considerable thought. Newcomers took ever longer to become productive ( Bachant and McDermott). Polit drew the managerial conclusion: the DEC engineers who took over maintenance, mostly without AI expertise, needed about a year and much help from Carnegie-Mellon, which taught the company that maintenance, probably an expert system's largest cost, required specially trained staff ( Polit).

By 1987 the problem had a name. Soloway, Bachant and Jensen reported that XCON had grown to about 6,200 rules drawing on a database of about 20,000 parts, and that about 50 percent of the rules changed every year. Performance was satisfactory; maintainability was not. Rules fired in unintended situations as different programmers added to them, developers extended the system by copying rules for a similar device without knowing why every action was there, and each had private tricks for forcing rules to fire in order: a "degradation in integrity," in the software-engineering phrase the authors borrowed. DEC's response was RIME, a language that made explicit what OPS5 left implicit, with 40 named problem spaces, standard problem-solving methods and rule templates, in which a successor, XCON-in-RIME, was being written. Their evidence for it came from interviews with eight rotating developers, and they said plainly this was not a controlled study.

The showcase of a boom

Inside DEC, Polit wrote, R1's success legitimized AI as an industrial subject and gave the company an image as a leading practitioner. XSEL helped salespeople tailor an order and passed it to XCON for configuration, XSITE helped prepare customers' sites, and other projects covered chip design and fault diagnosis. DEC formed a knowledge-engineering group, then an AI Technology Center, and a training program of a fourteen-week course followed by a nine-month apprenticeship ( Polit). By 1984 the group responsible for R1 had grown from five people with no AI background to 77 people responsible for eight knowledge-based systems ( Bachant and McDermott).

Outside DEC, R1 became the reference case. Polit dates the publicity wave to about 1982, when the popular press covered AI widely, Japan made it the focus of its fifth-generation computing effort, and many American corporations took an interest. The historian Thomas Haigh, in How the AI Boom Went Bust, describes XCON as the apparent proof that expert systems could save money in practice, retold in almost every textbook and magazine treatment of the subject, and notes that McDermott himself founded a company, the Carnegie Group. By March 1988, Harvard Business Review was introducing expert systems to executives through XCON and a drilling-mud advisor, explaining them as chains of if-then rules. Haigh also notes that DEC publicized large annual savings from XCON and a related system; the technical papers consulted here state no savings number, so none is repeated.

The dependence on one example was visible at the time. At a panel on "The Dark Ages of AI" at AAAI-84, published in AI Magazine in 1985, an audience member asked for operational successes besides R1, which he said was fast becoming ancient history. John McDermott, a panelist, restated it as why there was at most one successful AI system, then named others, including DEC's sales assistant, while conceding he could not vouch for how heavily most were used. Academic recognition came later: in 1999 AAAI gave its Classic Paper Award to McDermott's 1980 paper. Copies of papers on R1, XCON and XSEL, with an XSEL demonstration booklet, are preserved in a folder in the Computer History Museum's collections.

What the bust looked like from inside the rule base

The same 1984 panel put a name to the fear. Drew McDermott of Yale sketched a worst case in which the Strategic Computing Initiative and Japan's program collapsed, startups failed and funding dried up, a condition he said some were calling the "AI Winter" ( The Dark Ages of AI). He judged it unlikely. Haigh argues that by the end of the decade it had largely happened, and that this, rather than the 1970s retrenchment often labelled the first AI winter, began AI's real two-decade slump. That periodization is his argument, not a consensus, but his account of the market is specific.

Haigh's explanation connects directly to XCON's maintenance history. The market for expert-system software proved unsustainable, he writes, because most companies could not build the in-house skills to use it: systems designed to automate expertise required them to hire new experts to maintain them. His illustration is DEC itself. Citing DEC's own retrospective on a decade of its configuration systems, he reports that by 1989 the company had 59 technical staff assigned to maintaining the infrastructure and rule bases of its internal expert systems ( Haigh). Few companies could afford that, especially while a shortage of AI specialists drove up salaries.

This is the precise sense in which XCON foreshadowed the bust. It did not fail. By its operators' accounts it worked well enough that DEC kept investing for a decade, and the 1987 paper is explicit that the redesign was about maintainability, not accuracy ( Soloway, Bachant and Jensen). What XCON exposed was the cost structure behind the success: a large, well-funded team, a close university partnership, and years of tolerance for imperfect output in a domain that never stopped changing. Its own developers wrote that had R1 faced thousands of orders a month in its first two years, rather than a few tens a week, its use would probably have been discontinued ( Bachant and McDermott). Few firms buying expert-system tools in the mid-1980s could match those conditions, which is Haigh's point.

How to place XCON in AI history

XCON was not a conceptual breakthrough. The idea that encoded specialist knowledge could drive expert performance came from Stanford's DENDRAL and its successors, and the production-system machinery from Carnegie-Mellon. What R1 added was proof of sustained industrial use, a demonstration that Match could replace search in a constructive design task, and an unusually detailed public record of a knowledge base after deployment. Its contemporary claims, such as the validation and accuracy statistics, are documented almost entirely by its builders and DEC staff, not independent evaluators. Its larger role, as the boom's showcase and an early warning of the bust, is a retrospective reading supported by later historians and DEC's own staffing numbers.

Two threads lead outward. The first is its central limitation: the rule base learned nothing on its own, every fact entering by hand through an expert and a programmer, the gap that data-driven methods such as learning by backpropagation approached from a different direction. The second is the lesson that outlived the technology. Its builders' conclusion, that a system serving a changing domain must be treated as a permanent apprentice under continuous development rather than a finished product, remains the most durable part of XCON's record, though how far it transfers to systems that learn from data is a question this history cannot settle.

References

• John McDermott, AAAI (1980). R1: An Expert in the Computer Systems Domain.
• John McDermott, AI Magazine (1981). R1: The Formative Years.
• John McDermott and Barbara Steele, IJCAI (1981). Extending a Knowledge-Based System to Deal with Ad Hoc Constraints.
• John McDermott, Artificial Intelligence (1982). R1: A Rule-Based Configurer of Computer Systems.
• Judith Bachant and John McDermott, AI Magazine (1984). R1 Revisited: Four Years in the Trenches.
• Stephen Polit, AI Magazine (1984). R1 and Beyond: AI Technology Transfer at Digital Equipment Corporation.
• Drew McDermott, M. Mitchell Waldrop, B. Chandrasekaran, John McDermott and Roger Schank, AI Magazine (1985). The Dark Ages of AI: A Panel Discussion at AAAI-84.
• Elliot Soloway, Judy Bachant and Keith Jensen, AAAI (1987). Assessing the Maintainability of XCON-in-RIME: Coping with the Problems of a VERY Large Rule-Base.
• Dorothy Leonard-Barton and John J. Sviokla, Harvard Business Review (1988). Putting Expert Systems to Work.
• Virginia E. Barker, Dennis E. O'Connor, Judith Bachant and Elliot Soloway, Communications of the ACM (1989). Expert Systems for Configuration at Digital: XCON and Beyond.
• Association for the Advancement of Artificial Intelligence (1999). AAAI Classic Paper Award.
• Thomas Haigh, Communications of the ACM (2024). How the AI Boom Went Bust.
• Computer History Museum (1980). Assorted papers on R1, XCON, XSEL.