Diagnosis, parsimony, and genetic algorithms

ABSTRACT

The Communication Alarm Processor Expert System (CAP), developed at Oak Ridge National Laboratory for the Bonneville Power Administration, is a near real-time system that aids microwave communication system operators with interpreting the cause of large communication system problems [Purucker89]. Problems in the communications network are indicated by the real-time arrival of alarms at the central control site. CAP receives and processes these alarms, then presents the operator with a sorted list indicating the most probable cause (and location) generating the alarms. However, to achieve multiple problem diagnosis a diagnostic strategy is needed that: 1) satisfies the previously defined near real-time processing constraints, 2) “scales up” easily to handle large real-world applications (i.e., applications with more than 50 problems/components), and 3) gives the operator highly reliable information on the current status of the communications network. This paper describes recent successful results of our efforts to develop a general multiple problem (fault) diagnostic strategy that meets these requirements. The CAP system is currently being upgraded to incorporate this new strategy.

REFERENCES

• Chandrasekaran83: Chandrasekaran, B., and S. Mittal, "Deep versus Compiled Knowledge Approaches to Diagnostic Problem Solving," in International Journal of Man- Machine Studies, Vol. 19, No. 5, pp. 425-436, November 1983.
• Davis84: Randall Davis, Diagnostic reasoning based on structure and behavior, Artificial Intelligence, v.24 n.1-3, p.347-410, Dec. 1984 [doi>10.1016/0004-3702(84)90042-0]
• Edmonds62: Edmonds, J., "Covers and Packings in a Family of Sets," in Bulletin of the American Mathematics Society, Vol. 68, pp. 494-499, 1962.
• Fink87: Fink, P.K., and J.C. Lusth, "Expert Systems and Diagnostic Expertise in the Mechanical and Electrical Domains," in IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-17, No. 3, pp. 340-349, May/June 1987.
• Garey79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Genesereth84: Michael R. Genesereth, The use of design descriptions in automated diagnosis, Artificial Intelligence, v.24 n.1-3, p.411-436, Dec. 1984 [doi>10.1016/0004-3702(84)90043-2]
• Goldberg89: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• Holland75: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• Holtzblatt88: Holtzblatt, L.J., "Diagnosing Multiple Failures Using Knowledge of Component States," in Proceedings of the Fourth Conference on Artificial Intelligence Applications, pp. 139-143, San Diego, CA, March 1988.
• Josephson87: Josephson, J., B. Chandrasekaran, J. Smith, and M. Tanner, "A Mechanism For Forming Composite Explanatory Hypotheses," in IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-17, No. 3, pp. 445-454, May/June 1987.
• deKleer87: J de Kleer , B C Williams, Diagnosing multiple faults, Artificial Intelligence, v.32 n.1, p.97-130, April 1987 [doi>10.1016/0004-3702(87)90063-4]
• Liepins89: Liepins, G.E., M.R. Hilliard, j. Richardson, and M. Palmer, "Genetic Algorithm Applications to Set Coveting and Traveling Salesman Problems," in OR/AI: The Integration of Problem Solving Strategies, (Brown, ed.) 1989.
• Peng87a: Y. Peng , J. A. Reggia, A probabilistic causal model for diagnostic problem solving, part one: integrating symbolic causal inference with numeric probabilistic inference, IEEE Transactions on Systems, Man and Cybernetics, v.17 n.2, p.146-162, March/April 1987 [doi>10.1109/TSMC.1987.4309027]
• Peng87b: Peng, Y., and J.A. Reggia, "A Probabilistic Causal Model for Diagnostic Problem Solving, Part II: Diagnostic Strategy," in IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-17, No. 3, pp. 395-406, May/June 1987.
• Peng89: Peng, Y., and J.A. Reggia, "A Connectionist Model for Diagnostic Problem Solving," in IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC- 19, No. 2, pp. 285-298, March/April 1989.
• Pipitone86: Frank Pipitone, The FIS electronics troubleshooting system, Computer, v.19 n.7, p.68-76, July 1986 [doi>10.1109/MC.1986.1663281]
• Potter90: Potter, W.D., J.A. Miller, and O.R. Weyrich, "A Comparison of Methods for Diagnostic Decision Making," in Expert Systems with Applications: An International Journal, 1990. (to appear)
• Purucker89: Pumcker, S.L., et. al., "Design and Operation of the Communication Alarm Processor Expert System," in Proceedings of the Power Systems and Expert Systems Conference, Seattle, WA, July, 1989.
• Reggia83: Reggia, J.A., D. Nau, and P. Wang, "Diagnostic Expert Systems Based on a Set Covering Model," in International Journal of Man-Machine Studies, Vol. 19, No. 5, pp. 437-460, November, 1983.
• Reiter87: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Industrial automation
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Real time

General Terms:
Algorithms, Design, Performance, Reliability