XCON (R1)

What it was

R1 — known inside Digital Equipment Corporation (DEC) as XCON, short for Expert Configurer — was a production-rule-based expert system written in OPS5 by John P. McDermott of Carnegie Mellon University in 1978^[1]. Its task was narrow and concrete: to assist in ordering DEC's VAX computer systems by automatically selecting components based on customer requirements^[1].

Why it was needed

A computer order is not one object but a long list of parts that have to fit together. Before XCON, ordering a VAX meant that every cable, connection and piece of software had to be ordered separately^[1]. A salesperson therefore had to know, or look up, which parts could be combined with which — work that scales badly as a product line grows.

How it worked

XCON interacted with the salesperson, asking critical questions before printing out a coherent and workable system specification or order slip^[1]. McDermott's AAAI-80 paper, R1: An Expert in the Computer Systems Domain, describes R1 as a rule-based system that has much in common with other domain-specific systems developed over the past several years^[2]. The difference, the paper says, is primarily in its use of Match rather than Generate-and-Test as its central problem-solving method, exploiting its knowledge of its task domain to generate a single acceptable solution^[2]. In plain terms, the system does not enumerate candidate configurations and test them one by one; its rules match against the current description of the order and extend that description step by step until it is a complete, workable machine.

The knowledge base was organized around the components themselves. The paper says OPS4's two memories were augmented for this application with a third, a database containing descriptions of each of the 420 components currently supported for the VAX^[2]. Each database entry consists of the name of a component and a set of eight or so attribute-value pairs indicating the properties relevant for the configuration task^[2]. Some of the encoded knowledge is about the machine architecture itself: the paper notes that the VAX-11/780 is the first implementation of DEC's VAX-11 architecture and uses a high-speed synchronous bus, the sbi, as its primary interconnect^[2]. Facts of that kind are what let the rules decide which boards and cables may coexist.

Building it, and putting it to work

McDermott drew on experts from both DEC's PDP/11 and VAX systems groups, who sometimes disagreed about the optimal configuration^[1]. XCON first went into use in 1980 at DEC's plant in Salem, New Hampshire^[1].

Growth and maintenance

It eventually had about 2500 rules, and by 1986 had processed 80,000 orders with 95–98% accuracy^[1]. It was estimated to be saving DEC $25M a year by reducing free replacement components, speeding assembly and increasing customer satisfaction^[1]. The system kept growing: by 1987 XCON had grown to 6200 rules and had become difficult to maintain, as about 50% of the rules changed every year^[1]. In 1989 Digital's XCON alone included 10,129 rules and was described as saving tens of millions of dollars each year^[1].

What it led to

XCON's success led DEC to rewrite it as XSEL for use by the salesforce, and a further system, XSITE, handled location problems^[1].

Why it is remembered

XCON is a standard case for anyone learning how knowledge-based systems work, because both sides of the story are documented. On one side, a rule-based program took over a genuinely intricate ordering task, processed 80,000 orders at 95–98% accuracy by 1986 and was credited with savings in the tens of millions of dollars a year^[1]. On the other, the rule base grew from about 2500 rules to 10,129 rules, and with roughly half of the rules changing every year, maintenance became the limiting problem^[1]. The system also shows how domain knowledge gets captured: from experts in two different DEC groups who did not always agree, and in a structured database of component attributes that the rules could match against^[1][2].