Computer implemented machine learning and control system

• US 5,946,673 A
• Filed: 07/12/1996
• Issued: 08/31/1999
• Est. Priority Date: 07/12/1996
• Status: Expired due to Term

• Current Assignee: Frank D. Francone, Peter Nordin, Wolfgang Banzhaf
• Original Assignee: Frank D. Francone, Peter Nordin, Wolfgang Banzhaf
• Inventors: Nordin, Peter, Banzhaf, Wolfgang, Francone, Frank D.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/679,555
• Time in Patent Office: 1,145 Days
• Field of Search: 395/13, 395/22, 395/81, 701/210, 701/301, 706/13
• US Class Current: 706/13
• CPC Class Codes: B25J 9/163 learning, adaptive, model based, rule based expert control
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

In a computer implemented learning and/or process control system, a computer model is constituted by the most currently fit entity in a population of computer program entities. The computer model defines fitness as a function of inputs and outputs. A computing unit accesses the model with a set of inputs, and determines a set of outputs for which the fitness is highest. This associates a sensory-motor (input-output) state with a fitness in a manner that might be termed "feeling". The learning and/or control system preferably utilizes a compiling Genetic Programming system (CGPS) in which one or more machine code entities such as functions are created which represent solutions to a problem and are directly executable by a computer. The programs are created and altered by a program in a higher level language such as "C" which is not directly executable, but requires translation into executable machine code through compilation, interpretation, translation, etc. The entities are initially created as an integer array that can be altered by the program as data, and are executed by the program by recasting a pointer to the array as a function type. The entities are evaluated by executing them with training data as inputs, and calculating fitnesses based on a predetermined criterion. The entities are then altered based on their fitnesses using a genetic machine learning algorithm by recasting the pointer to the array as a data (e.g. integer) type. This process is iteratively repeated until an end criterion is reached.

Claims

1. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses; and

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion;

in which the computer model defines fitness as a function of input and output;

further comprising a learning unit configured to derive the computer model;

in which the learning unit is configured to derive the computer model using empirical fitness of input and output.

2. A system as in claim 1, in which the learning unit is configured to derive the computer model using a learning algorithm.

3. A system as in claim 1, in which the learning unit is configured to derive the computer model using regression.

4. A system as in claim 1, in which the learning unit is configured to derive the computer model using symbolic regression.

5. A system as in claim 1, in which the learning unit is configured to derive the computer model using a machine learning system.

6. A system as in claim 1, in which the learning unit is configured to derive the computer model using a fitting algorithm applied to training data.

7. A system as in claim 1, in which the computing unit is configured to receive applied inputs serially.

8. A system as in claim 1, in which the computing unit is configured to receive applied inputs periodically.

9. A system as in claim 1, in which the learning unit and the computing unit operate independently and interact intermittently.

10. A system as in claim 9, in which said intermittent interaction comprises the computing unit periodically accessing the learning unit to obtain the computer model.

11. A system as in claim 1, in which the learning unit is configured to derive the computer model by altering a single entity.

12. A system as in claim 11, in which the entity comprises a computer program.

13. A system as in claim 1, in which the learning unit is configured to derive the computer model by altering a plurality of a population of entities.

14. A system as in claim 13, in which the entities comprise computer programs.

15. A system as in claim 1, in which the learning unit is configured to derive different computer models at different times.

16. A system as in claim 1, in which:

the computer model defines fitness as a function of input and output; and

the computing unit is configured to calculate, using the computer model, for an applied input and at least a plurality of outputs, corresponding fitnesses, and select the output for which the corresponding fitness is best according to a predetermined criterion.

17. A system as in claim 1, in which the learning unit includes an entity which defines fitness as a function of input and output.

18. A system as in claim 17, in which the entity comprises a computer program.

19. A system as in claim 17, in which the learning unit is configured to derive the computer model by an algorithm that includes the step of altering the entity.

20. A system as in claim 1, in which the learning unit includes a population of entities which define fitness as a function of input and output.

21. A system as in claim 20, in which the entities include computer programs.

22. A system as in claim 20, in which the learning unit is configured to derive the computer model by an algorithm which includes the step of altering a plurality of the entities.

23. A system as in claim 1, further comprising an autonomous agent, in which:

the computing unit is configured to apply said output to control the autonomous agent; and

the applied input represents a parameter relating to the autonomous agent.

24. A system as in claim 23, further comprising a sensor configured to sense said parameter and apply said input to the computing unit.

25. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses;

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion; and

a learning unit configured to derive the computer model;

using a compiling genetic programming system.

26. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses; and

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion;

in which the computing unit is configured to use the output determined by the computing unit to control a real-time process.

27. A system as in claim 26, in which at least one applied input represents a parameter relating to the real-time process.

28. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses;

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion;

a learning unit configured to derive the computer model; and

a fitness calculation module, which is configured to calculate the empirical fitness of an output previously determined by the computing unit in response to an applied input.

29. A system as in claim 28, in which the learning unit is configured to use at least one evaluation of empirical fitness by the fitness calculation module to derive the computer model.

30. A system as in claim 28, in which the learning unit is configured to use at least one evaluation of empirical fitness by the fitness calculation module to improve the computer model.

31. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses; and

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion;

in which the computer model defines fitness as including a "pain" component and a "pleasure" component.

32. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses;

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion; and

a learning unit which includes;

a memory for storing a plurality of vectors, each of which includes an input, an output, and a corresponding fitness; and

a derivation unit configured to derive the computer model using the vectors as a training set.

33. A system as in claim 32, in which:

the fitness in at least one of the vectors is an empirical fitness; and

the fitness defined by computer model is a predicted fitness.

34. A system as in claim 32, in which the learning unit is further configured to prevent at least one of the vectors stored in memory from being removed.

35. A system as in claim 32, in which the learning unit is further configured to temporarily prevent at least one of the vectors stored in memory from being removed according to a predetermined criterion.

36. A system as in claim 32, in which the learning unit is further configured to make at least one of the vectors stored in memory more difficult to remove than at least one other vector stored in memory.

37. A system as in claim 32, in which the derivation unit is configured to alter, using an algorithm, a population of entities, at least one of which defines fitness as an alterable function of input and output.

38. A system as in claim 32, in which the computing unit is further configured to calculate, using the computer model, for an applied input and at least a plurality of outputs, corresponding fitnesses, and to select the output for which the corresponding fitness is best according to a predetermined criterion.

39. A system as in claim 32, in which the derivation unit and the computing unit operate independently and interact intermittently.

40. A system as in claim 32, in which the system further comprises a fitness calculation module, which is configured to calculate the empirical fitness of an output previously determined by the computing unit in response to an applied input.

41. A system as in claim 40, in which the learning unit is configured to use said evaluation of empirical fitness to derive the computer model.

42. A system as in claim 40, in which the learning unit is configured to use said evaluation of empirical fitness to improve the computer model.

43. A system as in claim 32, in which at least one of the vectors is determined empirically.

44. A system as in claim 32, in which at least one of the vectors is determined from past experience.

45. A system as in claim 32, in which at least one of the vectors is preset.

46. A system as in claim 32, in which each vector further includes a state variable.

47. A system as in claim 32, in which each input includes at least one sensed parameter.

48. A system as in claim 32, in which the learning unit is further configured to periodically store new vectors in the memory.

49. A system as in claim 48, in which the learning unit is further configured to prevent at least one of the vectors which was first stored in the memory from being replaced.

50. A system as in claim 32, in which:

the computer model includes an entity which defines fitness as a function of input and output; and

the computing unit is configured to calculate, using the entity, for an applied input and at least a plurality of outputs, corresponding fitnesses, and select the output for which the corresponding fitness is best according to a predetermined criterion.

51. A system as in claim 32, in which the derivation unit is configured to alter, using an algorithm, a population of computer entities, each of which defines fitness as an alterable function of an input and an output, and produce the computer model as the entity which best fits the vectors according to a predetermined criterion.

52. A system as in claim 51, in which:

the fitnesses included in the vectors are empirical fitnesses; and

the fitnesses defined by the entities are predicted fitnesses.

53. A system as in claim 51, in which the algorithm includes genetic alteration.

54. A system as in claim 51, in which the algorithm includes tournament selection.

55. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses;

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion; and

an autonomous agent, in which;

the computing unit is configured to apply said output to control the autonomous agent; and

said fitness includes a "pain" component and a "pleasure" component.

56. A system as in claim 55, in which:

the "pain" component increases as the behavior of the autonomous agent becomes less desirable; and

the "pleasure" component increases as the behavior of the autonomous agent becomes more desirable.

57. A computer implemented system, comprising:

a computer model which defines a relationship between inputs, outputs, and corresponding fitnesses;

a computing unit for accessing the computer model to determine, in response to an applied input, an output for which a corresponding fitness meets a predetermined criterion;

an autonomous agent, in which the computing unit is configured to apply said output to the autonomous agent; and

the applied input represents a parameter relating to the autonomous agent; and

a learning unit which includes;

a memory for storing a plurality of vectors, each of which includes an input, an output, and a corresponding fitness; and

a derivation unit configured to derive the computer model using the vectors as a training set.

58. A system as in claim 57, in which the derivation unit and the autonomous agent operate independently and interact intermittently.

59. A system as in claim 57, in which:

the fitnesses included in the vectors are empirical fitnesses; and

the fitness defined by the computer model is a predicted fitness.

60. A system as in claim 57, in which the learning unit is further configured to wait until a predetermined event occurs after the computing unit applies an output corresponding to a previous applied input to the autonomous agent, receive a new applied input, calculate an empirical fitness as a predetermined function of said new applied input and said output, and store said previous applied input, said output, and said empirical fitness as a vector in the memory.

61. A system as in claim 60, in which the predetermined event is a lapse of a predetermined length of time.

62. A system as in claim 60, in which the system further comprises a sensor configured to sense said parameter and apply said input to the computing unit.

63. A system as in claim 60, in which said predetermined function includes a "pain" component and a "pleasure" component.

64. A system as in claim 57, in which:

the autonomous agent is a propelled object;

the input represents proximity of the propelled object to external objects; and

the output represents a propulsion control parameter for the propelled object.

65. A system as in claim 64, in which the fitnesses included in the vectors each include a "pain" component and a "pleasure" component.

66. A system as in claim 65, in which:

the "pain" component increases with proximity to external objects; and

the "pleasure" component increases with at least one of propulsion speed and straightness of movement.

67. A system as in claim 64, in which:

the propelled object comprises a propulsion motor and a plurality of proximity sensors;

the input comprises a vector including outputs of the proximity sensors; and

the output comprises a speed control value for the propulsion motor.

68. A system as in claim 64, in which the propelled object is a robot.