In the terminology of expert systems configuration systems are a subclass of design systems, whose task is to synthesise a set of objects that satisfy a given set of problem specific constraints [1]. Examples of configuration problems are computer equipment configuration (XCON [2]), software configuration, timetables generation and scheduling.
A configuration task is generally rather complex since it involves coping with many and interacting design decisions, whose consequences cannot readily be assessed, and constraints of different nature. Configuration problems are therefore a challenging domain for expert system technologies.
For simpler configuration tasks we can envision interactive configuration assistants which operate by guiding the user step by step through the available design decisions by exploiting their knowledge of the domain constraints and of the constraints deriving from previous choices. Configuration tasks that are amenable to this simplified vision are for example plan of study compilation or shopping for a coherent system built from a catalogue of components, like a complex piece of furniture (a kitchen furniture for instance) or a personal computer.
Important advantages of having a configuration assistant of this kind on the Web are wide availability and the possibility of remote access and use. The system does not need to be installed on the users computer in order to be used and portability issues do not arise. This is also a clear example in which a Java solution has obvious advantages over a solution where the configuration assistant runs on the server and the client interacts via a CGI interface: all the job of the configuration assistant can be done locally at the client’s side by downloading the necessary Java code; communication with the server can be reduced to tasks such as user validation, statistics gathering or archiving.
In this paper we describe the main ideas behind a general tool for developing specific configuration assistants running on the Web: the configuration application is generated starting from a high level description of the basic components and the constraints expressed in a declarative form. More specifically, the HTML files for user guidance and the Java code for constraints checking are automatically generated from this high level description.
In order to demonstrate the use of the general tool we will describe the generation and use of a Web assistant for plan of study compilation and submission (CompAss) which has been developed for the Faculty of Letters and Philosophy of the University of Pisa.
We will conclude by discussing limitations of the current system and plans for future developments.
The Web page of a configuration assistant is vertically divided in two parts. The right part contains the navigation frame with related title bar and navigation buttons, the help frame, and the documentation frame. The left part contains the configuration frame and an application specific tool bar (see figure 1).
Figure 1.
The navigation frame is a HTML frame displaying a normal hypertextual document with hyperlinks to other related pages; it displays the available choices together with any informative text deemed useful to guide the user to do the right choices during the configuration process. Hyperlinks are associated to configurations items and, when clicked, make a description associated to the item appear in the documentation frame.
Special icons associated to choice points and to items are used to perform configuration actions: intermediate choices or item selections; when these icons are selected they send messages to the configuration program, the validator, which is a Java Applet associated to the configuration frame. One difficult technical problem was to allow interaction between HTML pages and the Java applet which collects and stores the plan. An HTML page was the appropriate way to describe the course and provide documentation and guidance to the student in filling the plan. It would have been nice to allow the user to pick up a course (through its title or an icon representing it) and drop it in the plan. Drag-and-drop operations are not currently supported between HTML and applets. Therefore we had to resort to clicking on the icon of a course in order to select it. However filling a page with dozens of Java applets (one for each course) would have been unfeasible, bogging the browser. The solution has been to use JavaScript to post the events of icon selection to the configuration applet. With this solution the interface can exploit all the power of the HTML language and standard browsing capabilities1, while still allowing user interaction with the Java programme.
The configuration frame on the left contains the Java applet which manages the configuration. The applet receives input by direct interaction in its client area, handled through events in the AWT, or by selection of special icons in other frames (the navigation frame and the tool bar frame). Whenever a configuration action is performed the applet reacts by checking the current partial configuration, accepting the change or prompting the user if any configuration constraints is violated.
Tool icons in the toolbar denote general utility or application specific actions available to operate on the partial configuration displayed in the configuration frame (i.e. item deletion, final configuration validation, abortion of the configuration process, printing or submission of the final configuration).
Figure 2.
A configuration it built from a set of basic items that the user can choose. A configuration is a subset of the basic items, and a set of intermediate user choices, that match a given set of constraints. Basic constraints are represented in a directed acyclic graph called choice graph; each node of the graph defines a set of items required for the node; its successors correspond to alternative choices in the configuration process. A configuration is valid only if the user choices define a path from the root to a leaf, and the selected items match all the constraints associated to the nodes in the path.
To build the configuration application we have developed a declarative language for defining the various aspects of the configuration. The application is generated by using a compiler for this language; the output of the compiler is a data structure to be used by the Java applet.
The Java applet depends on the configuration domain only for the item structure and the custom constraints functions; this elements are Java classes generated by the compiler and later combined with the rest of the applet. The applet also uses the items database and a binary representation of the configuration constraints.
The compiler is divided in two modules: C1 and C2. The first module is needed for generating Java code and constructing the items data base. The second module of the compiler generates a Java representation of the constraints and the HTML files for navigation.
The various components needed to build a configuration application and the associated process are described in detail below.
3.1 Item structure, item database, and custom constraint functions
Three data files, in human readable form, are given as input to the component C1, and depend on the configuration domain: the item structure, the items database, and the custom constraints functions.
The item structure file contains an item definition that is very much like the
struct of the language C. At least two fields are required in an item definition: the code field and the name field. The code field is a fixed size field which plays the role of an access key for the item and is fundamental for passing parameters. The name field is a variable size description of the item to be used by the applet at runtime in communicating with the user. The applet uses only data contained in the items database and so the applet code is independent from the configuration domain.The items database is constructed by C1 from a text file where each item is described according to the defined item structure. Each item also contains a description in HTML that is displayed in the documentation frame on user’s request.
For the definition and enforcement of domain specific constraints the user can define special custom functions, in addition to the constraints resulting from the constraint file described below; these functions are boolean tests on the current configuration state and are defined in the custom constraints file. Function definitions can refer to fields defined in the item structure. The functions are defined as
String f(S, n) where n is an integer parameter and S is the current state. The return value of the function can be a null string if the result is positive, can be a string that starts with ‘&’ if the result is a warning or another string if the result is an error.3.2 Constraint file
The constraint file is the heart of the configuration application; in fact the validator module of the application interprets the constraints defined in this file to check the configuration. The constraints are defined in a special declarative language designed for this purpose.
We have defined a valid configuration using the graph of choices: the language reflects the structure of the graph for easy definition of constraints. The language support two types of blocks: a list block and a choice block. A choice block corresponds to a node in the choice graph and defines the various constraints. A list block is only a way to refer by name to a group of items. All blocks have names but only names for choice blocks survive in the binary version of constraints file. A choice block has the following structure:
Name of the block {
item needed1,
item needed2,
...,
[item pres1, item pres2, ..., item presn]->
[item needed n+1, ..., item needed n+h], /* 1 */
[item choice1, ..., item choice k, #reference](7), /* 2 */
[#ref1, #ref2](2+), /* 3 */
[#ref3, item choice k+1](1-) /* 4 */
CHOICE(Block 1, ..., Block m) /* 5 */
} f1(32), f2(31); /* 6 */
In a block description, the items that are necessarily needed for the block are listed first. Items that are needed depending on the configuration state, i.e. the presence of other items, are included with a conditional construct. For example line
1 says that the items on the right of the ‘->’ operator are to included in the block only if the items on the left are present in the current configuration. Line 2 is an example of a construct that allows the selection of a number of items out of a list of items; in particular the example says that exactly seven items of the configuration must be selected from the given list. Lines 3 and 4 are similar with different number restrictions: in the first case two or more items are required, in the second case at most 1 item is accepted. Line 5 defines the children of the current node in the choice graph, i.e. the available choices at this level. The operator ‘#’ refers to a list block, that is a named block of the formblock name[item 1, #item 2, ..., item n]
The choice block defines the items required for the node in the configuration. The type of control that is generated only checks for admissibility of an item in a given configuration, i.e. answers the question "is it correct that this item is in the current configuration"? If other kinds of constraints are needed, such as "The cost of the configuration must be at most XXX$", one must use constraints functions, which are typically application dependent, and can be custom defined or supplied in a library. Constraints functions appear at the end of a choice block (like in line number 6 above) and apply to all items in the block.
The nodes are first checked for inconsistency among items starting from the root of the graph to a leaf. Functions are checked next. Any problem is signalled to the user.
3.3 The compiler
The module C1 of the compiler takes as input the three files described above and produces three files as output: a Java program, information about the items and the binary version of the items database. As shown in Figure 2, these three files are used in the second step of the compilation process. The Java code includes two types of code: the item Java class and the custom constraints functions Java classes. The item class is the class that describes the format of the items database and offers to the configuration applet a set of methods for reading, writing and accessing item components. The custom constraints functions classes are a Java version of custom constraints functions. These classes are registered by a Java class called Function Manager that maps the function calls to the proper functions. All the Java code must be compiled and the output classes must be joined to the rest of the configuration applet2.
The component C2 of the compiler takes as input the constraints file, the items information and the items database. It generates HTML files and the binary version of the constraints.
The HTML files generated are to be used in the navigation frame and in the documentation frame. In particular a set of HTML skeleton files are generated out of the choice graph: for each node in the graph a file is generated with selection icons for the items in the node and hypertextual links to the items descriptions. The file also contains a few lines of text which synthetically describe the node constraints (for example "Choose at least three items out of the following:"). In addition the file contains choice icons and hyperlinks to other HTML files in correspondence of available choices.
The skeleton HTML files needed for the application are all automatically generated by the compiler; the only thing that the configuration builder must do is to provide additional text (if necessary) to guide the user through the configuration process.
A compact binary representation of the choice graph is also generated by C2 and it is the primary data structure used by the applet for checking the validity of a configuration.
One of the major problems in the use of Java applets for building applications on the Web is the Security Manager. The Security Manager is the Java class that defines security policies for Java. In particular for browsers like Netscape Navigator or Microsoft Internet Explorer3, this class prevents the applets from doing I/O on the client local disc and allows opening sockets only with the Web host from which the applet has been loaded.
These limitations make very difficult to write applications that use persistent data. Our solution is to use a special server on the Web host that listens to a given TCP port: the applets open sockets to this server on the specified port and use the server for saving data. This architecture is a little more complex and introduces new problems for implementing the server. Because Java is a multithreaded language designed for the Web it is natural to use it for writing the server. Java has convenient facilities for communicating via sockets and Object serialisation which is useful for sending Java objects across the Web.
Our configuration application system uses a server written in Java that allows different kinds of clients: configuration clients but also server console clients. The configuration clients are the applets running in a configuration application. The server console clients are Java standalone applications that allow remote monitoring of the server. Through the server console the user can monitor in real-time configuration clients, displaying the Internet hosts with open configuration connections, and save statistics on the use of the system.
If the configuration application requires printing capabilities the server can also generate and send back a HTML page with the data provided by the client in an appropriate format and the user can print the content of the generated page with the regular print button of its browser. The server can also store these data in a database for later use.
CompAss (COMPilazione ASSistita di piani di studio) is a system which assists students in the task of producing a plan of study. CompAss and its associated support tools have been developed in the context of a pilot project for the Faculty of Letters and Philosophy of the University of Pisa. The interface of CompAss is shown in figure 1.
Plans of study approval is a time consuming job for all the courses of study in the faculty, due to the high number of submissions each year (around 3000) and the high rate of incorrect submissions. One of the requirements was that students could use any computer located in the various departments of the faculty to compile plans of study; data had to be collected in one single place for archival. The Java solution was the obvious choice and offers additional advantages such as the possibility of using the system from home.
In this configuration application the basic items are all the courses offered by the faculty; the constraint file implements the rules for plan of study formation; it includes a choice graph where nodes correspond to choices such as the course of study, the orientation, the field of specialisation and so on, together with the necessary constraints. A configuration is a legitimate plan of study, i.e. a list of courses which a student plans to take, fulfilling all the requirements imposed by the faculty.
The official submission of the plan must be done on paper because it requires a signature by the student. Our current solution is that the plan is printed locally, after completion and verification by CompAss, and automatically sent to the server and registered in a temporary area. When the student submits the plan to the secretary office, the plan is retrieved and transferred to the archives of submitted plans. CompAss saves a lot of work for secretaries who previously had to type in the plans from the paper forms submitted by students and eliminates most of the work of the faculty committees which had to verify and approve the plans.
The plan of study manager running on the server accepts communications from several CompAss clients, receives data from plans of study, generates HTML pages, stores data in a database, and gathers statistics on the number of users and on the pattern of use of the system.
CompAss can be seen at the Web address "http://omega.di.unipi.it/local/Compass/start.html".
We have described a general tool for generating configuration assistants; the strategy works well in the specific configuration domain of plan of study compilation, but we believe that other configuration applications are amenable to this simple paradigm. More experimentation is however needed to exactly define the range of applications and to come out with a general enough configuration language.
Moreover we plan to enhance the configuration language by including a language-level specification for the display of items both in the applet and in the HTML files. The specification for the applet determines in which manner items are displayed in the configuration frame, since the topology of the configuration partially depends on the application domain. The HTML specification permits to create references in the navigation frame to allow for easier navigation through the configuration choices.
When the browser HotJava, provided by Sun, will be released, we will be able to exploit a new method for communication between HTML and the Java applet. We also plan to write a new interface that uses the Netscape live-connect system for the same purpose.
We are grateful to the Faculty of Letters and Philosophy of the University of Pisa, and prof. Mirko Tavoni in particular, for sponsoring the project, to the CISIAU (the computing centre of the Faculty) and its technical director dr. Paolo Pisanti for providing the necessary technical support and to the people who helped us to understand the rules for plans of study (prof. Letta and prof. Scalfati). The student Alessandro Pelosi also contributed in early stages of the project.