Engineering (Mechanical)
Elevator Design
VT
Mid 80’s
Sandra Marcus, Jeffrey Stout, John McDermott
OPS5
VAX 11/780, 20MB RAM
VT was used by Westinghouse Elevator engineers to design elevator systems to customer specifications. It could run virtually autonomously or allow user interaction.
EL is a similar expert system. It analyzes electric circuits by guessing the current at a particular node and applies rules to propose values for other parts of the circuit. It builds a dependency network and backtracks when constraints are violated, but the backtracking strategy is domain independent.
The GARI (Descotte and Latombe 1985) expert system which builds plans for machining parts uses domain-dependent backtracking, but by applying weights instead of revision rules as VT does.
AIR/CYL (Brown 1985) and PRIDE (Mittal
and Araya 1986) also use knowledge-based revision techniques. AIR/CYL has
failure handlers that call for redesigns of particular parts to handle
constraint violations.
1.
Customer requirements forms for the elevator:
Performance specifications,
carrying capacity, speed, product selection (like
light fixtures, etc.)
2.
Architectural and structural design of the
building
Wall-to-wall dimensions in the
elevator shaft (hoistway), locations of rail supports, etc.
3.
Architectural design of the elevator cabs,
entrances and fixtures.
4. Knowledge about pieces of equipment and machinery that must be configured (supplied in read-only database).
The data provided to the system could be incomplete. The output elevator design is complete.
Constructive problem solving, domain-dependent backtracking.
The system endeavors to leverage domain-dependent knowledge while constructing a solution for a well-defined task to quickly arrive at the best elevator design given the criteria. It is contended that interdependencies between the many design features necessitates this approach. The method of construction, using domain-dependent backtracking, is implied to work on any domain with a fixed set of design parameters, a high degree of interrelation amongst the parameters, and a limited up-front knowledge.
VT is a simulation at a cognitive level, in that when engineers are faced with a design problem, they apply the knowledge they have and the rules they know to constructively build a solution.
The system has been fully implemented.
The system was (and may still be) used by Westinghouse Elevator engineers.
Took between 7 and 22 minutes to complete
test runs that modeled normal usage.
Aside from solution construction, domain-dependent backtracking is used to resolve constraint violations, and a dependency network is used to identify contributors to a violated constraint and the value it constrains.
This system does not simulate any procedure or analysis.
The architecture used domain-dependent knowledge that falls in three categories for the purpose of developing a design. The knowledge is used to build up a design, express constraints on the design parameters, and propose fixes to the design. A dependency network is built in the design phase to identify contributors to violated constraints and the value it constrains. The dependency network is also used to contain information used later to explain the design.
The types of knowledge are:
Used for forward-chaining to build up a design given design parameters.
Express required limitation on one or more design parameters, given the state of a specific design parameter. This is used by “demons” to test the validity of a design built through forward-chaining.
Describe how to resolve a constraint violation. This is the core of the domain-dependent backtracking feature.
Information about the features of particular elevator parts are stored in a read-only database.
Design rules build up a design. Constraint rules express the interrelation between design parameters. Revision rules resolve constraint violations.
The knowledge is “deep” in the sense the system contains a great deal of domain-dependent knowledge, including domain-dependent knowledge geared specifically for resolving issues that result from executing design rules. It is “surface” knowledge in the sense that there is no real qualitative simulation that is taking place.
The set of all combinations of elevator design parameters. There are hundreds of parameters, and most parameter can have many values (many of which are numerical values). This is a large space.
The search space is traversed by forward-chaining through a set of design rules, which guide the process of setting design parameters. Invalid combinations of elevator design parameters (constraint violations) are pruned by a combination of expertly chosen design rules (determined by system implementer) and the application of revision rules.
The control strategy seems to model what might be done by a
human engineer developing the problem. Humans also apply design rules, and test
their design by applying constraints. Humans also often have a standard
approach to dealing with a particular aspect of a design problem (revision
rules).
The technique is a form of generate and test. A design is
built up through a process of executing forward-chaining rules. This is the generate stage. Then, the result is tested for constraint violations using
constraint rules.
Search control is very much knowledge-based, augmented with domain-dependent backtracking.
If only some design constraints are specified at the beginning of a design, default values are used in place of actual data, and a complete elevator design is presented as the final output. If more design specifications are introduced later, they can be applied to the same problem and result in a modified design. So in a sense, partial solutions are allowed.
Search control knowledge is built into the design rules and
revision rules. The search is tracked by maintaining a dependency network to
identify contributors to violated constraints and the value it constrains.
The search control is very strong. It is based very much on domain-dependent knowledge in each of the design, test and revision phases.
Domain-dependent knowledge in the form of revision rules are used to resolve all design parameter constraint violations. The rules will alter a parameter that had already been specified by a design rule to resolve the constraint. Forward-chaining of the design rules from the point of the change forward is done to assure consistency of the design.
Rules are considered to be certain.
When the specifications for the elevator to be designed are input by the user of VT, a certainty value can be specified.
A solution to a subproblem is not known to be certain until the elevator is completely designed or deemed to be impossible. Problems are detected by violations of constraints.
Revision rules do have a numeric value of preference that express what is the most desirable way to resolve constraint violations.
Certainty values for specification input by the user of the system can be used to determine if it’s permissible to change a value, or how desirable it is to change a value specified by the user when resolving constraints when the system is running.
There is no time-dependent data in this problem.
Domain-dependent knowledge is stored as rules.
Domain-dependent knowledge is collected through a generic knowledge acquisition utility called SALT.
Knowledge (expressed in rules) derived from SALT, a rule interpreter and a user-interface can be combined to form an expert system similar to VT that uses a propose-and-revise strategy of design. A database can also be introduced to represent fixed data, such as the parameters of available parts.
Design rules and fix rules are linked together through a dependency network. SALT analyzes this network to find trouble-spots. This corresponds to the domain in that it dramatically reduces an otherwise extremely large search space of potential design solutions.
Alternative representation of knowledge are not used in this system.
The only manner in which alternative solution methods are used to arrive at the same solution is that there are may be many revision rules for a particular constraint violation.
The system produces a very good answer almost always. This is because the problem-solving technique is similar to what a true expert would do to reduce the search space of potential solutions. However, I think that the algorithm described for traversing through potential fixes can lead to non-optimal solutions. The only way to determine if there is a better solution is to compare it to the solution of another expert, or to generate all possible combinations of elevator design parameter and test to see how well they minimize cost and meet the customer’s design criteria.
Only one result is given.
Interaction is through a command line. Customer requirement are specified, then the system proceeds to use its knowledge to design the elevator. If the system is running in interactive mode, it will as the user to verify all design revisions that are suggested to resolve constraint violations.
The system does not require all data initially, as default values can be used in their stead. However, default values are likely to be overwritten by the user of the system as the customer requirements are further specified.
Data is specified in screens on information in tabular text and graphical form.
Domain-dependent knowledge is collected through a generic knowledge acquisition utility called SALT. The categories of this knowledge are design rules, constraint rules and revision rules. SALT also identifies trouble-spots in the knowledge-base that can lead to infinite looping or premature search termination (without a solution). Trouble-spots in VT can be dealt with by adding new fix rules or tweaking existing rules.
This system does not perform better with successive runs with the same information, so in that sense, it does not learn.
The explanation facility allows for a declarative explanation of why every decision was made to achieve the resulting design. The user is allowed to see the ramifications of an individual suggestion for the change to the final design. The user is also allowed to ask why a certain feature was not implemented in the final design