llllllllllllllIllIllll||l|l||||l|ll|ll||l|IlllllllllllllllllllllllIllllllll
`US005586218A
`
`United States Patent
`Allen
`
`[19]
`
`5,586,218
`[11] Patent Number:
`[45] Date of Patent: Dec. 17, 1996
`
`
`
`[54] AUTONOMOUS LEARNING AND
`REASONING AGENT
`
`[75]
`
`Inventor: Bradley P. Allen, Hermosa Beach,
`Calif.
`
`[73] Assignee:
`
`Inference Corporation, Novato, Calif.
`
`[21]
`
`[22]
`
`Appl. No.: 518,850
`
`Filed:
`
`Aug. 24, 1995
`
`Related US. Application Data
`
`[63] Continuation of Ser. No. 869,926, Apr. 15, 1992, abandoned,
`which is a continuation—in—part of Ser. No. 664,561, Mar. 4,
`1991, abandoned.
`
`........................... G06F 15/18
`Int. 01.6
`[51]
`[52] US. Cl. ......... 395/10; 395/50; 395/51;
`395/75; 395/77; 395/11; 395/13
`[58] Field of Search .................................. 395110, 50, 51,
`395/75, 77, 11, 13, 600, 934
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3/1987 Johnson et a1. ............. 364/900
`4,648,062
`5/1990 Tan et al.
`364/300
`4,930,071
`
`2/1991 Burkowski et al.
`.
`364/200
`4,991,087
`5/1991 Ogawa ............
`364/900
`5,020,019
`
`.. 364/900
`5,062,074 10/1991 Kleinberger
`364/419
`3/1992 Carlgren et a1.
`.
`5,099,426
`
`.. 395/68
`5,103,498
`4/1992 Lanier et a1.
`
`6/1992 Richards et a1.
`.
`395/157
`5,122,972
`
`8/1992 Koza ................. 395/13
`5,136,686
`
`5,140,692
`8/1992 Morita .
`395/600
`................
`5,168,565
`12/1992 Morita
`395/600
`
`4/1993 Coulter et a1.
`..............
`5,201,048
`395/600
`5,224,206
`6/1993 Simoudis
`...... 395/77
`5,255,386 10/1993 Prager .........
`395/600
`5,287,448
`2/1994 Nicol et a1.
`.
`395/159
`5,301,314
`4/1994 Gifford et a1.
`395/600
`5,303,361
`4/1994 Colwcll et a1. ............. 395/425
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`Riesbeck, C. K.,—“An Interface for Case—Based Knowledge
`Acquisition,” Proc. Workshop on Case—Based Reasoning,
`May 1988, 312—326.
`'
`Shafer, D., “CBR Express: Getting Down to Cases,” Jul./
`Aug. 1991, PCAI, 42—45.
`Integrating Case~Based Reasoning With GenetieAlgo
`rithms; Computational Intelligence, HI; Oppacher et
`211;
`Conference Date 24—28 Sep. 1990; pp. 103—114.
`Combining Case—Based And Rule Based Reasoning: A
`Heuristic Approach; IJCAI 1989; Rissland Et Al; vol. 1; pp.
`524—530.
`Explanation Based Indexing Of Cases; Proc. Of AAAI—88;
`Barletto Et Al; Aug. 1988.
`
`(List continued on next page.)
`
`Primary Examiner—Robert W. Downs
`Attorney, Agent, or Finn—D’Alessandro & Ritchie
`
`[57]
`
`ABSTRACT
`
`A software agent which performs autonomous learning in a
`real—world environment, implemented in a case-based rea-
`soning System and coupled to a sensor for gathering infor-
`mation from, and to an effector for manipulating, its envi-
`ronment. A case base which is tuned in response to an
`evaluation of how well the agent is operating in that envi-
`ronment. A memory of cases, the contents of that memory
`being determined by a genetic technique, including produc-
`ing new cases which may never have been encountered in
`the environment, evaluating cases in response to a history of
`previous matches and in response to an external stimulus,
`and selecting a limited set of cases which provides a
`preferred model of the environment. A selection technique
`based on multiple measures, such as match quality, case
`accuracy, or case utility, which may induce experimentation
`by the autonomous agent, such as by employing arandom or
`pseudorandom efi'ect in selecting cases, and which may also
`distinguish between those actions which solve problems and
`those actions which gather further information so as to better
`solve problems. Multiple autonomous agents may form a
`collective entity and may cooperate to select an action to be
`performed by that collective entity.
`
`0233071
`
`6/1986 European Pat. Off.
`
`........ GUSB 13/02
`
`20 Claims, 5 Drawing Sheets
`
` QUERIES
`
`MOTlVES
`MESSAGE
`MESSAGE
`DATA
`1 17
`
`
`
` 108
`ELEMENT
`1 19
`
`
`
`
`STlMULUS
`FROPRIO-
`
`MESSAGE
`CEPTDRS
`
`104
`/
`
`FEATURES OBJECT
`
`MESSAGE
`"2
`
`RE-
`CEPTORS
`
`109
`
`ACTION
`
`
`MESSAGE
`
`
`
`3+REINFORCEMENT
`
`
` 0,:
`
`COMMANDS
`HUMAN
`REWARD
`115
`{7‘
`MESSAGE
`open/non
`
`
`VS
`MESSAGE
`
`
`
`
`
`
`
`
`
`
`ORACLE EX. 1004 (pg. 1)
`
`ORACLE EX. 1004 (pg. 1)
`
`

`

`5,586,218
`Page 2
`
`OTHER PUBLICATIONS
`
`A Generalized Case Based Reasoning System For Personnel
`Performance Evaluation; Proc. 24th Annual Hawaii Inter.
`Conf. On System Sciences; Chi Et Al; 8«11 Jan. 1991; pp.
`82—89.
`Credit Assignment And The Problem Of Competing Factors
`In Case—Based Reasoning; Proc. Workshop On Case—B ased
`Reasoning; Rissland Et A]; May 10—13, 1988; pp. 327—344.
`Case Based Reasoning For Continuous Control; Proc. Work-
`shop On Case—Based Reasoning; Kopeikina Et Al; May
`10—13, 1988; PP- 250—259.
`Some Experiments With Case—Based Search; Proc. Work-
`shop On Case—Based Reasoning; Bradtke Et Al; May 10—13,
`1988; Pp. 80—93.
`Clavier: A Case Based Autoclave Loading Advisor; David
`Hinkle; Mar. 9, 1990.
`Using A Case Memory To Integrate Case—Based And Causal
`Reasoning; Case~Based Reasoning Workshop; Phyliss
`Koton; Aug. 23, 1988; pp. 74—81.
`Oppacher, et al.; “Integrating Case—Based Reasoning with
`Genetic Algorithms,” in Computational
`Intelligence 111
`(Sep. 24—28, 1990), pp. 103—114.
`Handelman, et al.; “Ingegrating Neural Networks and
`Knowledge—Based Systems for Intelligent Robotic Con—
`trol,” in IEEE Control Systems Magazine (Apr. 30, 1990),
`pp. 77—87.
`Aleksander, et al; ”The Cognitive Challlenge for Neural
`Architectures,” in International Neural Network Conference
`(Jul. 9—13, 1990), pp. 627—630.
`Isik, et al.; “Pilot Level of a Hierarchical Controller for an
`Unmanned Mobile Robot,” in 4:3 IEEE Journal of Robotics
`and Automation (Jun. 1988), pp. 241—255.
`MacNiel, “Capturing Multimedia Design Knowledge Using
`TYRO, the Constraint Based Designer’s Apprentice”, in
`Image Handling And Reproduction Sysems Integration
`(1991) pp. 94—102.
`C. Lee, “Case—based reasoning for robotic assembly cell
`diagnosis”, in Expert Robots For Industrial Use (1988), pp.
`241—246.
`Venta, O. and Kohonen, T., A Content—Addressing Software
`Method for the Emulation of Neural Networks, Helsinki
`University of Technology (1991).
`Allen, B. P. and Lee, S. D., A Knowledge—Based Environ—8
`ment for the Development of Software Parts Composition
`Systems, Proceedings of the 11th International Conference
`on Software Engineering, IEEE, May, 1989.
`Willett, P., Recent Trends in Hierarchic Document Cluster-
`ing: A Critical Review, Information Processing & Manage-
`ment, vol. 24, No. 5, pp. 577—597, 1988.
`(hitting, D. R., Karger, D. R., Pedersen, J. O. and Tukey, I.
`W., Scatter/Gather: A Cluster—based Approach to Browsing
`Large Document Collections, 15th Ann. Int’l SIGIR 1992.
`Can, F. and Ozkarahan, E. A., Dynamic Cluster Mainte-
`nance, Information Processing & Management, vol. 25, No.
`3, pp. 275—291, 1989.
`Parodi, A. and Bonelli, P., The Animat and the Physician, pp.
`50—57, (1991).
`.
`Brooks, R. A., Elephants Don’t Play Chess, Robotics and
`Autonous Systems 6, pp. 3—15, 1990.
`Allen, B. P., Case—Based Reasoning in a Software Informa—
`tion System, Inference (1991).
`Wood, M. and Sommerville, I., An Information Retrieval
`System for Software Components, ACM SIGIR, V01. 22,
`Issue 3, 4, Spring/Summer 1988.
`
`Frakes, W. B. and Nejmeh, B. A., Sofware Reuse Through
`Information Retrieval, Proceedings of IEEE Spring COM-
`PCON ’87, Mar. 1987.
`Stone, H. S., Parallel Querying ofLarge Databases: A Case
`Study, Computer, Oct. 1987.
`Batz, J. C., Chohcn, P. M., Rcdwine, S. T. and Rice, J. R.,
`The Application—Specific Task Area, Computer, Nov. 1983.
`Arnold, S. P. and Stepoway, S. L., The REUSE System:
`Cataloging and Retrieival of Reusable Software, Proceed-
`ings of IEEE Spring COMPCON ’87, Mar. 1987.
`Prieto—Diaz, R. and Freeman, P. Classifling Software for
`Reusability, IEEE Software, vol. 4, No. 1, Jan. 1987.
`Aha, D. W., Kibler, D. and Albert, M. K., InstancewBased
`Learning Algorithms, Machine Learning, vol. 1, No. 1, Jan.
`1991.
`Steinberg, L. I., Design as Refinement Plus Constraint
`Propagation: The Vexed Experience, Proceedings of the
`National Conference on Artificial Intelligence, AAAI, Jul.
`1987.
`Patel-Schneider, P. F., Brachmau, R. J. and Levesque, H. J.
`ARGON: Knowledge Representation meets Information
`Retrieval, Proceedings of the First Conference on Applica-
`tions of Artificial Intelligence, IEEE, Dec. 1984.
`Kolodner, J. L., Simpson, R. L. Jr., and Sycara—Cyranski, K.
`A Process Model of Cased—Based Reasoning in Problem
`Solving, Proceedings of the Ninth International Joint Con-
`ference on Artificial Intelligence, Aug. 1985.
`Yen, J., Neches, R. and DeBellis, M., Specification by
`Reformulation: A Paradigm for Building Integrated User
`Support Environments, Proceedings of the National Confer—
`ence on Artificial Intelligence, AAA], Aug. 1988.
`Fischer, G. and Nieper—Lcmke, H., HELGON: Extending
`the Retrieval by Reformulation Paradigm, Proceedings of
`CHI ’89 Human Factors in Computing Systems ACM,
`Apr—May 1989.
`Frakes, W. B. and Gandel, P. B., Representation Methodsfor
`Software Reuse, Proceedings of TRI—Ada 89, Oct. 1989.
`Harandi, M. T. and Young, F. H., Template Based Specifi-
`cation and Design, Proceedings of the 3rd International
`Workshop on Software Specification and Design, IEEE,
`Aug. 1985.
`Marcus, S., SALT} A Knowledge Acquisition Tools for Pro-
`posemnd—Revise Systems, Automating knowledge Acquisi—
`tion for Expert Systems, Marcus, S., Eds, Kluwer Aca-
`demic, 1988.
`Selby, R. W., Quantitative Studies of Software Reuse, Soft-
`ware Reusability, vol. 2, ACM Press, 1989.
`Lanergan, R. G. and Grasso, C. A., Software Engineering
`with Reusable Designs and Code, Software Reusability, vol.
`2, ACM Press, 1989.
`Yost, G. R. and Newell, A., A Problem Space Approach to
`Expert System Specification, Proceedings of the Eleventh
`IJCAI, Aug. 1989.
`Stottler, R. H., Henke, A. L. and King, J. A., Rapid Retrieval
`Algorithms for Case—Based Reasoning, Proceedings of the
`Eleventh International Joint Conference on Artificial Intel-
`ligence, Aug. 1989.
`Devanbu, P., Selfridge, P. G., Ballard, B. W. and Brachman,
`R. 1., A Knowledge—Based Software Information System,
`Proceeding of the Eleventh International Joint Conference
`on Artificial Intellignece, Aug. 1989.
`Embley, D. W. and Woodfield, S. N., A Knowledge Structure
`for Reusing Abstract Data Types, Proceedings of the 9th
`International Conference on Software Engineering, IEEE,
`Mar—Apr. 1987.
`
`ORACLE EX. 1004 (pg. 2)
`
`ORACLE EX. 1004 (pg. 2)
`
`

`

`5,586,218
`Page 3
`
`Allen, B. P. and Lee, S. D., A Knowledge—Based Environ-
`ment for the Development of Software Parts Composition
`Systems, Proceedings of the 11th International Conference
`on Software Engineering, IEEE, May 1989.
`Bareiss, E. R.
`and Porter, B. W., PROTOS: An
`Exemplar—Based Learning Apprentice, Proceedings of the
`Fourth International Workshop on Machine Learning, Jun.
`1987.
`Kolodner, J. L., Improving Human Decision Making through
`Case—Based Decision Aiding, AI Magazine, vol. 2, No. 2,
`Summer 1991.
`Williams, M. D., What makes RABBIT run“), International
`Journal of Man—Machine Studies, vol. 21, 1984.
`Williams, R. 8., Learning to Program by examining and
`Modifying Cases, Proceedings of the DARPA Workshop on
`Case—Based Reasoning, May 1988.
`Venta, 0. and Kohonen, T., A Content—Addressing Software
`Methodfor the Emulation ofNeural Networks, Proceedings
`of the IEEE International Conference on Neural Networks
`1988, Jul. 1987.
`Williams, M. D., The Process of Retrieval from Very
`Long—Tenn Memory, Cognitive Science 5, 1981.
`Stanfill, C. and Waltz, D. L., The Memory—Based Reasoning
`Paradigm, Proceedings of the DARPA Workshop on
`Case—Based Reasoning, May 1988.
`Koton, Phyllis, Reasoning about Evidence in Causal Expla—
`nations, MIT Laboratory for Computer Science, Procedural
`Workshop on Case—Based Reasoning, pp. 260—270, (May
`13, 1993).
`Risch, T. et al., A Functional Approach to Integrating
`Database and Expert Systems, Communications of the
`ACM, vol. 31, No. 12, pp. 1424—1437, Dec. 1988.
`Subcontract No. 036 Between University of Houston
`Clear-Lake and Inference Corporation, Mar. 1989.
`Subcontract No. 087 Between University of Houston
`Clear—Lake and Inference Corporation, May 1991.
`Sirnoudis, et al., “The Application of CBR to Help Desk
`Applications,”
`Proceedings
`of
`the
`1991 DARPA
`Case—Based Reasoning Workshop, May 1991.
`Kolodner, “Extending Problem Solver Capabilities Through
`Case—Based Inference,” Proc. 4th Annual Inter. Machine
`Learning Workshop, pp. 21—30, 1987.
`Frakes, et al., “Using Expert System Components to Add
`Intelligent Help and Guidance to Software Tools,” AT & T
`Bell Laboratories, Sep. 1989.
`Prager, et al., “REASON An Intelligent User Assistant for
`Interactive Environments,” IBM Systems Journal, vol. 29,
`No. 1, 1990, pp. l41~164.
`Breuker, et al., “A Shell for Intelligent Help Systems,”
`Cognitive Modeling, Dee. 1987, pp, 167—173.
`Skalak, “Options for Controlling Mixed Paradigm Sys-
`terns,” Proc. Workshop on Case Based Reasoning, Jun.
`1989, pp. 318—323.
`Simoudis, et al., “Validated Retrieval in Case—Based AAA
`P90,” Aug. 1990, pp. 310—315.
`Pallatto, “New ART—1M features to aid expert system devel—
`opment,” PC Week, Aug. 27, 1990, 67(2).
`
`Goodman, “Prism: A Case Based Texex Classifier,” Pro.
`Innovative Applications of Artificial Intelligence 2, 1990,
`pp. 25—37.
`Software Product Specification for ESTEEM V1.1, Esteem
`Software, Inc. Released 1991.
`Kamel, et al., “Fuzzy Query Processing Using Clustering
`Techniques," Information Processing & Management, vol.
`26, No. 2, pp. 279—293, 1990.
`Sachs, “An Approach to Associate Retrieval through the
`Theory of Fuzzy Sets,” Journal of the American Society for
`Information Sciences, Mar.—Apr., pp. 85—87, 1976.
`Salton,
`et
`al.,
`“Introduction to Modern Information
`Retrieval,” pp. 59—75 and 421—426, 1983.
`a
`to Realize
`Bender,
`“The Descriptive
`Search
`Knowledge-Based Retrieval of Reusable Project Results,”
`Artificial Intelligence in Real—Time Control, pp. 109—112,
`1988.
`Salton, et al., “Term Weighting Approaches in Automatic
`Text Retrieval,” Information Processing & Management,
`vol. 24, No. 5, pp. 513—523, 1988.
`Maarek, et al., “Full Text Indexing Based on Lexical Rela-
`tions An Application: Software Libraries," Proceedings of
`The International Conference on Research and Development
`in Information Retrieval, pp. 198—205, 1989.
`Kochen, et al., “On the Precision of Adjectives which
`Denote Fuzzy Sets,” Journal of Cybernetics, pp. 49—59,
`1974.
`McNarrnara, “An Application of Cyclomatie Complexity
`Metrics to Microcode,” IBM Technical Report No. 01.A517,
`Mar. 22, 1988.
`Klir, “Is There More to Uncertainty Than Some Probability
`Theorists Might Have Us Believe?,” International Journal of
`General Systems, vol. 15, pp. 347—378, 1989.
`Leung, et al., “Fuzzy Concepts in Expert Systems,” Com—
`puter, pp. 48—56, Sep. 1988.
`Salton,
`et
`al.,
`“Introduction to Modern Information
`Retrieval,” McGraw Hill, Chapter 3 pp. 52415, Chapter 4
`pp. 146—151, Chapter 7 pp. 287—297, Chapter 10 pp.
`421—422, 1983.
`Bookstein, “Fuzzy Requests: An Approach to Weighted
`Boolean Searches,” Journal of the American Society for
`Information Science, pp. 240—247, Jul. 1980,
`Tahani, “A Fuzzy Model of Document Retrieval Systems,”
`Information Processing & Management, vol.
`12, pp.
`177—187, 1976.
`Radecki, “Mathematical Model of Information Retrieval
`system Based on the Concept of Fuzzy Thesaurus,” Infor-
`mation Processing & Management, vol. 12, pp. 313—318,
`1976.
`Miyamoto, et al, “Fuzzy Information Retrieval Based on a
`Fuzzy Pseudothesanrus,” IEEE Transactions on Systems,
`Man and Cybernetics, vol. SMC—16, No. 2, pp. 278—282,
`Man/Apr. 1986.
`Cisler, “Searching for a Better Way: Verity, INC’s Topic
`Software,” Online, pp. 99-102, Nov. 1988.
`Chong, “Feature Software Review: Product: Topic,” Library
`Software Review, pp. 281—284, Sap/Oct, 1989.
`
`ORACLE EX. 1004 (pg. 3)
`
`ORACLE EX. 1004 (pg. 3)
`
`

`

`US. Patent
`
`Dec. 17, 1996
`
`Sheet 1 of 5
`
`5,586,218
`
` \\x\EOmmmOOm—mDw._.<EO._.D<
`
`
`
`szEWOmSZM/Ixor/
`
`v:
`
`szEwOm—OLZEE
`
`
`moz<§Eooomssmm2.32::
`
`
`w0<mmm=2m0<mmm2EOF<mmmO
`a:m:xm:
`
`
`
`m3--mmoHomumm
`
`mo<mmm§
`
`wemmoEmoBFm2
`
`
`
`
`mmEmSOmm>FOE
`
`
`
`m0<wmm=2mmu<wwm§
`
`m:t.—<._.<D
`
`#0.“..memmIDbxm”.
`,or—m:m0<mmm§
`
`
`
`hzw§m4m
`
`wo—
`
`-O_mn_0mn_
`
`meHmm—O
`
`mDJDEPm
`
`m0<mwm=2
`
`ORACLE EX. 1004 (pg. 4)
`
`ORACLE EX. 1004 (pg. 4)
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 17, 1996
`
`Sheet 2 of 5
`
`5,586,218
`
`m0<mmm§
`
`memSG
`
`02.32200
`
`m0<mmm§
`
`m:
`
`FNF
`
`mom
`
`EOFOmem
`
`mom
`
`wMIObfiZ
`
`mmu<wmm=2
`
`mom
`
`how
`
`mm<0
`
`mmm_n=._.2m_n=
`
`
`
`._<>m=m...mmmm<o
`
`
`
`mmm<0>>m_z
`
`NON
`
`mw<mmmz
`
`9a
`
`mm<o
`
`mm<m<k<o
`
`mmm<oWEE:mm<o
`
`NSt
`
`
`
`5N
`
`>IO§ME
`
`MADDOE
`
`wow
`
`N:
`
`o:
`
`m:
`
`mm>:.0_>_
`
`m0<wmm=2
`
`mmm3.2m“.
`
`wmu<wmm=2
`
`DI<>>wI
`
`mw<wmm=2
`
`ORACLE EX. 1004 (pg. 5)
`
`ORACLE EX. 1004 (pg. 5)
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 17, 1996
`
`Sheet 3 of 5
`
`5,586,218
`
`HISTORY
`MESSAGE
`307
`
`113
`REWARD
`MESSAGE
`
`MATCHING
`HISTORY
`
`
`
`
`
`EVALUATION
`MODULE
`
`
`306
`
`308
`
`REPRO-
`
`
`DUCTION
`
`
`MODULE
`
`
`
`
`301 FEATURES ELEMENT
`302 ACTION ELEMENT
`303 EVALUATION
`
`ACCURACY 305
`VALUE
`UTILITY
`VALUE
`
`CASE DATABASE
`
`FIG. 3
`
`301
`302
`303
`
`126
`
`MATCH
`QUALITY 304
`VALUE
`403
`
`305
`
`205
`
`304 305
`
`126
`126
`
`MATCHING
`
`MODULE
`
`401
`
`404
`
`RANDOM~
`IZATION
`MODULE
`
`
`
`ORACLE EX. 1004 (pg. 6)
`
`ORACLE EX. 1004 (pg. 6)
`
`

`

`US. Patent
`
`Dec. 17, 1996
`
`Sheet 4 of 5
`
`5,586,218
`
`KNOBOTS IN DIAGNOSIS AND REPAIR
`
`
`
`DEVICE SENSOR READINGS, USER AND DEALER
`
`COMMANDS
`
`
`
`
`
`
`GOALS ELIMINATE NEED FOR USER INVOLVEMENT IN
`
`MAINTENANACE, ANTICIPATE FAILURES FOR
`
`PREVENTATIVE MAINTENANCE
`
` STIMULI
`
`ACTIONS
`
`DEVICE DRIVER OUTPUTS, DIAGNOSTIC AND REPAIR
`
`
`
`MESSAGES
`,
`
`
`NEGATIVE IF DEVICE FAILS
`REINFORCEMENT
`
`
`GREATLY INCREASED MEAN-TIME-BETWEEN-FAILURE
`
`
`
`
`
`
`BENEFITS
`
`FIG.5
`
`KNOBOTS IN CUSTOMER SERVICE
`
`604
`
`602
`
`0
`
`TELEP]I_-IONE
`SYS EM
`
`DESK
`SYSTEM
`
`GOALS
`
`STIMULI
`
`TOUCH-TONE COMMANDS. VOICE RESPONSE UNIT
`
`MESSAGES
`
`
`VOICE RESPONSE OUTPUT, PBX TRANSFERS
`POSITIVE IF DIALOG COMPLETED, NEGATIVE IF CALLER
`HANGS UP BEFORE PROBLEM RESOLUTION OR TRANSFER
`
`
`HELP
`601%—E3—4——>
` RESPONSIVELY HANDLE CUSTOMER PHONE CALLS AND
`
`
`
`
`AUTOMATICALLY RESOLVE PROBLEM
`
`
`
`
`ACTIONS
`REINFORCEMENT
`
`
`
`BENEFITS
`
`FOCUSED, RESPONSIVE USER INTERFACE THAT ADAPTS
`
`TO USER BEHAVIOR
`.
`
`
`
`
`FIG.6
`
`ORACLE EX. 1004 (pg. 7)
`
`ORACLE EX. 1004 (pg. 7)
`
`

`

`US. Patent
`
`Dec. 17, 1996
`
`Sheet 5 of 5
`
`5,586,218
`
`KNOBOTS IN KNOWLEDGE DISCOVERY
`
`701 \
`
`ACTIONS
`
`
`GOALS
`LEARN USEFUL KNOWLEDGE ABOUT PATTERNS IN DATA
`
`
`
`
`STIMULI
`DATABASE TABLES AND SCHEMA DEFINITIONS
`DATABASE QUERIES AND TRANSACTIONS
`
`
`
`POSITIVE IF USEFUL INFORMATION DISCOVERED
`
`BENEFITS
`IMPROVED ABILITY TO GENERALIZE FROM DATA AND
`
`
`CAPTURE USEFUL REGULARITIES FOR COMPETITIVE
`
`ADVANTAGE
`
`REINFORCEMENT
`
`FIG. 7
`
`ORACLE EX. 1004 (pg. 8)
`
`ORACLE EX. 1004 (pg. 8)
`
`

`

`5,586,218
`
`1
`AUTONOMOUS LEARNING AND
`REASONING AGENT
`
`CROS S—REFERENCE TO RELATED
`APPLICATION
`
`This application is a file-wrapper continuation of patent
`application Ser. No. 07/869,926, filed Apr. 15,1992, now
`abandoned which is a continuation-in-part of application
`Ser. No. 07/664,561, filed Mar. 4, 1991, now abandoned, in
`the name of inventors Bradley P. Allen and S. Daniel Lee
`and titled “CASE-BASED REASONING SYSTEM",
`hereby incorporated by reference as if fully set forth herein.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`This invention relates to case-based reasoning and to a
`case-based reasoning system which performs autonomous
`learning in a real-world environment.
`2. Description of Related Art
`While computers are capable of tremendous processing
`power, their ability to use that processing power for reason-
`ing about complex problems has so far been limited. Gen—
`erally, before a computer can be used to address a complex
`problem, such as one which requires the attention of a
`human expert, it has been necessary to distill the knowledge
`of that expert into a set of inferential rules (a “rule base”)
`which allow an automated processor to reason in a limited
`field of application. While this method has been effective in
`some cases, it has the natural drawback that it often requires
`a substantial amount of time and effort, by both computer
`software engineers and experts in the particular field of
`application, to produce a useful product.
`Moreover, mle—based systems of this type present a
`diflicult programming task. Unlike more prosaic program-
`ming tasks, constructing a rule base is sometimes counter-
`intuitive, and may be beyond the ability of many application
`programmers. And once a rule—based system has been con-
`structed based on the knowledge of a human expert, it may
`be difiicult to accommodate changes in the field of operation
`in which the processor must operate. Such changes might
`comprise advances in knowledge about the application field,
`additional tasks which are intended for the processor, or
`changes in or discoveries about the scope of the application
`field.
`
`One proposed method of the prior art is to build auto—
`mated reasoning systems which operate by reference to a set
`of exemplar cases (a “case base”), to which the facts of a
`particular situation (the “problem”) may be matched. The
`processor may then perform the same action for the problem
`as in the exemplar case. While this proposal has been
`well—received, case—based systems of this type may still
`require a substantial amount of human effort to identify
`exemplar cases and present a processor with sufiicient
`information that cases may be matched and acted upon. For
`example, it may be necessary to deduce or supply extensive
`information about a complex environment so as to determine
`a preferred sct of exemplar cases.
`A parent copending application, Ser. No. 07/664,561, filed
`Mar. 4, 1991, discloses inventions in which a case-based
`reasoning system is smoothly integrated into a rule-based
`reasoning system, and in which an automated reasoning
`system may dynamically adapt a case base to problems
`which it encounters. An aspect of the inventions disclosed in
`that application also includes a technique in which a system
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`2
`may be set to work with a limited case base, and may solicit
`human advice for treatment of new problems which are not
`already well-treated by the case base, thus learning how to
`do its job on a dynamic basis.
`Another application, Ser. No. 07/869,935, now aban—
`doned, filed the same day as this application, discloses
`inventions in which a machine learning system may operate
`in conjunction with a relational database system, and par-
`ticularly in which a machine learning system may operate in
`conjunction with a relational database system with an SQL
`interface. This allows the machine learning system to use
`high-speed searching power of computer systems which
`have been designed for use with relational database systems
`with an SQL interface, and allows the machine learning
`system to be smoothly integrated into computer systems
`which have relational databases, even if those databases
`were not designed to work with learning or reasoning
`systems of any kind.
`It would be advantageous if an automated reasoning
`system could dynamically create its own case base in
`response to problems which it encounters, thus learning how
`to do its job on a dynamic basis and without substantial
`human intervention, or at least with only occasional human
`intervention. Limited intervention would allow an auto-
`mated reasoning system to examine a larger set of cases and
`to determine a preferred set of exemplar cases without an
`external agent, such as a human operator, having to deduce
`or supply extensive information about a complex environ-
`ment.
`
`It would also be advantageous if an automated reasoning
`system could operate autonomously in a complex environ-
`ment, possibly with external intervention such as positive or
`negative reinforcing stimuli. External stimuli might be in
`response to a result of the system’s attempts to manipulate
`its environment, or might be provided by an external agent,
`such as a human operator. Accordingly, it is an object of the
`invention to provide an automated reasoning system which
`does not require intervention for every case.
`
`SUMMARY OF THE INVENTION
`
`The invention provides a software agent which performs
`autonomous learning in a real-world environment. The
`autonomous agent may learn by reinforcement (including
`positive and negative, and delayed and sporadic, reinforce-
`ment), in addition to learning by example and learning by
`being told what
`to do. In a preferred embodiment,
`the
`autonomous agent may be implemented in a case-based
`reasoning system, which may be coupled to a sensor for
`gathering information from, and to an effector for manipu-
`lating, its environment (which may comprise a software
`environment, a physical environment, or some combination
`thereof). In addition to gathering a case base of experience
`in its environment, the autonomous agent may tune that case
`base in response to an evaluation of how well it is operating
`in that environment. The evaluation may be its own, or may
`be in response to a stimulus such as a reward or punishment.
`In addition to taking action on a problem based on its case
`base,
`the autonomous agent may take action to gather
`information so as to determine which cases are most appro-
`priate to that problem.
`In a preferred embodiment, the autonomous agent may
`comprise a memory of cases, the contents of that memory
`being determined by a genetic technique for producing,
`evaluating and selecting cases. New cases may be produced
`by inspection of scenarios from the environment, by muta-
`
`ORACLE EX. 1004 (pg. 9)
`
`ORACLE EX. 1004 (pg. 9)
`
`

`

`5,586,218
`
`3
`tion of old cases, or by combining or selecting features from
`old cases; thus the memory may comprise cases the autono-
`mous agent has never encountered in the environment. The
`stored cases may be evaluated in response to a history of
`previous matches and in response to an external stimulus,
`and evaluations (such as measures of accuracy and utility)
`may be associated with stored cases. The contents of the
`memory may be limited to a set of cases which provides a
`preferred model of the environment, such as those cases
`which have the better evaluations.
`
`In a preferred embodiment, the autonomous agent may
`comprise a selection technique based on multiple factors,
`such as match quality, case accuracy, or case utility. The
`selection technique may also induce experimentation by the
`autonomous agent, such as by employing a random or
`pseudorandom effect in selecting cases. The selection tech-
`nique may also distinguish between those actions which
`solve problems and those actions which gather further
`information so as to better solve problems. Multiple autono-
`mous agents may form a collective entity and may cooperate
`to select an action to be performed by that collective entity.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows a block diagram of an autonomous agent
`embedded in a complex environment.
`FIG. 2 shows a block diagram of a behavior module of an
`autonomous agent.
`FIG. 3 shows a data flow diagram of a genetic technique
`for producing, evaluating and selecting cases.
`FIG. 4 shows a data flow diagram of a technique for
`selecting cases in a memory.
`FIG. 5 shows a block diagram of an intelligent oflice
`equipment device including an autonomous agent.
`FIG. 6 shows a block diagram of a customer service
`system with a help-desk system including an autonomous
`agent.
`FIG. 7 shows a block diagram of a knowledge discovery
`system including an autonomous agent.
`. Appendix A shows an example software environment and
`autonomous agent for distinguishing between classes of
`irises.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`An embodiment of this invention may be used together
`with inventions which are disclosed in a copending appli-
`cation titled “MACHINE LEARNING WITH A RELA-
`TIONAL DATABASE", application Ser. No. 07/869,935,
`filed the same day in the name of the same inventor, hereby
`incorporated by reference as if fully set forth herein.
`FIG. 1 shows a block diagram of an autonomous agent
`embedded in a complex environment.
`A software agent 101 may be embedded in an environ-
`ment 102 so that the agent 101 may receive a stimulus 103
`from the environment 102 by receiving a stimulus message
`104, and may perform an action 105 which affects the
`environment 102 by sending an action message 106. In a
`preferred embodiment, the stimulus message 104 and the
`action message 106 may each comprise a manipulable
`software object 107 and may transmit that software object
`107 from source to destination. Software objects 107 may
`comprise data elements 108 and relations to other software
`objects 107 as is well known in the art. Object-oriented
`systems are more fully described in “Object—Oriented
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`Design With Applications” by Grady Brooch, published by
`Benjamin/Cummings Publishing, Redwood City, Calif.
`(1991), hereby incorporated by reference as if fully set forth
`herein.
`
`In a preferred embodiment, the environment 102 may
`comprise either a software environment or a physical envi—
`ronment, or some combination thereof. For example, the
`environment 102 may comprise a physical room; the agent
`101 may receive a LIGHTS stimulus message 104 telling if
`a set of lights in the room is off or on; and the agent 101 may
`send a LIGHTS-ON action message 106 to turn on the
`lights. Alternatively, the environment 102 may comprise a
`graphic database; the agent 101 may receive a PICTURE
`stimulus message 104 telling about a picture in the database;
`and the agent 101 may send an ADD-PROPERTY action
`message 106 to add a property value (e.g., “auth0r=Ver-
`meer”) to the picture.
`A set of receptors 109 may receive the stimulus message
`104 and generate a features message 110. In a preferred
`embodiment, the receptors 109 may map a set of aspects or
`features 111 of the environment 102 (especially those relat-
`ing to external stimuli) into a set of feature objects 112,
`which may comprise software objects 107 which describe
`the aspects or features 111 of the environment 102. For
`example, the environment 102 may comprise an oil refinery
`and the feature objects 112 may comprise temperature and
`pressure values at various positions in the refinery.
`The set of receptors 109 may also generate a reward
`message 113, which may comprise a scalar-valued rein-
`forcement 114 which measures what success the agent 101
`is having with the environment 102. In a preferred embodi-
`ment, the value of the reinforcement 114 may be determined
`by the receptors 109, or may be externally supplied, such as
`from a human operator 115. For example, the environment
`102 may comprise a loan portfolio database and the rein-
`forcement 114 may measure loan performance, or the envi-
`ronment 102 may comprise a music audio database and the
`reinforcement 114 may be entered by the human operator
`115 after listening to selections made by the agent 101.
`A set of proprioceptors 116 may generate a motives
`message 117, which may comprise software objects 107
`which describe goals or needs of the agent 101. In a
`preferred embodiment, the proprioceptors 116 may map
`aspects or features of the environment 102 (especially those
`relating to internal states of the agent 101 itself) into those
`goals or needs. The goals or needs of the agent 101 itself are
`thus a kind of feature 111 which the agent 101 may consider,
`and are similar to the features 111 which are reported by the
`receptors 109. For example,
`the environment 102 may
`comprise a piece of oflice equipment such as a photocopier
`and the motives message 117 may comprise internally
`generated features 111 such as the need for new ink or paper.
`The proprioceptors 116 may be altered by a designer so as
`to change the essential goals of the agent 101.
`A behavior module 118 may receive the motives message
`117, the features message 110 and the reward message 113,
`and may generate a queries message 119, which may com-
`prise software objects 107 which describe a request 120 by
`the agent 101 for further information, and a commands
`message 121, which may comprise software objects 107
`which describe a command 122 by the agent 101 to affect the
`environment 102. In a preferred embodiment, the behavior
`module 118 may comprise one like that disclosed with FIG.
`2.
`
`A set of effectors 123 may receive the queries message
`119 and the commands message 121 and generate the action
`
`ORACLE EX. 1004 (pg. 10)
`
`ORACLE EX. 1004 (pg. 10)
`
`

`

`5,586,218
`
`5
`message 106. In a preferred embodiment, the action message
`106 may be coupled to the environment 102 (e.g., a physical
`device or another software element) and may cause an eifect
`in the environment 102. For example, the environment 102
`may comprise a chess program and the action message 106
`may direct the chess program to make a particular move on
`behalf of the agent 101.
`In a preferred embodiment; the software agent 101 may be
`implemented with an automated processor 124, which may
`execute a software inference engine 125 for reaso