Genetically programmed learning classifier system for complex adaptive system processing with agent-based architecture

• US 6,741,974 B1
• Filed: 06/02/2000
• Issued: 05/25/2004
• Est. Priority Date: 06/02/2000
• Status: Expired due to Term

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Harrison, Gregory A., Hollister, Keith, Worden, Eric
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/586,456
• Time in Patent Office: 1,453 Days
• Field of Search: 706/47, 706/14, 706/13
• US Class Current: 706/47
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

A system and a method enabling a software agent to learn about its environment, and learn how to perform jobs and tasks. Novel information is assimilated and used in an adaptive manner by the genetically evolving rule set of the agent. The agent learning system communicates with the external environment in an artificial economy through on-line auctions. Internal information also passes through message auctions, that provide chaining of rule execution. The agent continually attempts to automatically improve its performance with respect to fitness for a job.

Claims

1. An adaptive system comprising:

a plurality of agents wherein at least some of the agents exhibit a substantially similar structure with a selected function defined, at least in part, by a plurality of pre-stored rules and wherein each of the rules includes one or more antecedent conditions automatically selected from a class which includes external messages, agent characteristics, environmental detecting primitives, internal messages and internal state-detecting primitives and each includes a variable performance indicium with respective indicia being selectively altered in response to increased effectiveness in carrying out the selected function.

2. An adaptive system as in claim 1 wherein each rule includes one or more consequent actions selected automatically from a class which includes external messages, environmental altering primitives, internal messages and internal state changing primitives.

3. A system as in claim 2 wherein at least some of the agents each include a rule modification system.

4. A system as in claim 3 wherein the respective pluralities of rules include relatively newly created, evolving rules and imported rules received from a different agent.

5. A system as in claim 4 wherein members of a selected plurality of rules attempt to acquire intra-agent messages from a local plurality by successfully bidding therefore.

6. A system as in claim 2 wherein at least some of the agents each include an indicium indicative of the respective agent'"'"'s overall performance.

7. A system as in claim 2 wherein some of the agents reside at different sites than others and wherein agents can be transmitted between sites via an interconnecting network.

8. A system as in claim 7 wherein multiple agents can be resident at a selected site.

9. A system as in claim 8 wherein at least some of the agents communicate with respective, locally resident application software.

10. A system as in claim 9 wherein agents are coupled to selected respective pluralities of messages.

11. A system as in claim 10 wherein a plurality of agents can forward messages to and receive messages from a selected collection of messages.

12. A system as in claim 11 wherein the collection of messages maintains a running indicium, which is altered when messages are acquired by a selected agent and altered in a different way when acquired messages are received from other agents.

13. A system as in claim 2 wherein at least some of the agents are implemented in software executable at an associated processor and wherein at least some of such agents include software for creating new rules based, in part, on existing rules.

14. A system as in claim 13 wherein such agents also include software for evaluating rule performance and for replacing at least one rule with a new rule in accordance with a determined criterion.

15. A system as in claim 14 wherein the evaluating software replaces rules in a manner that promotes diversity.

16. A system as in claim 1 which includes at least one simulator for training at least one of the agents.

17. An adaptive system comprising:

a plurality of agents wherein at least some of the agents exhibit a substantially similar structure with a selected function defined, at least in part, by a plurality of pre-stored rules and wherein each of the rules includes a variable performance indicium with a greater indicium being indicative of increased effectiveness of carrying out the selected function; and

a collection of interagent messages wherein agents can forward messages to and receive messages from the collection.

18. A system as in claim 17 wherein at least some of the agents each include a rule modification system.

19. A system as in claim 18 wherein the respective pluralities of rules include relatively newly created, evolving rules and imported rules received from a different agent.

20. A system as in claim 17 wherein at least some of the agents each include a total performance indicium indicative of the respective agent'"'"'s overall performance.

21. A system as in claim 17 wherein some of the agents reside at different sites than others and wherein agents can be transmitted between sites via an interconnecting network.

22. A system as in claim 21 wherein multiple agents can be resident at a selected site.

23. A system as in claim 22 wherein agents communicate with locally resident application software.

24. A system as in claim 23 wherein agents are coupled to selected respective pluralities of messages;

and

wherein agents can forward messages to and receive messages from a selected plurality of agents.

25. A system as in claim 17 wherein members of a selected plurality of rules attempt to acquire intra-agent messages from a local plurality by successfully bidding therefore.

26. A system as in claim 17 wherein at least some of the rules each have an antecedent and a consequence which follows only if the requirements of the antecedent have been met.

27. A system as in claim 17 wherein at least some of the rules include one or more antecedent conditions automatically selected from a class which includes external messages, agent characteristics, environmental detecting primitives, internal messages and internal state-detecting primitives and each includes a variable performance indicium with respective indicia being selectively altered in response to increased effectives in carrying out the selected function.

28. An adaptive system as in claim 17 wherein each rule includes one or more consequent actions selected automatically from a class which includes external messages, environmental altering primitives, internal messages and internal state changing primitives.

29. A system, implemented as a set of programs, some of which can be transferred via a medium between sites of a network, comprising:

a plurality of diverse agents for implementing at least two different processes wherein the respective agents include a plurality of rules with each rule having at least one antecedent and at least one consequent; and

an evaluator wherein a selected agent is not activated unless specified antecedents are met and unless the selected agent has met a predetermined performance criterion.

30. A system as in claim 29 which includes at least one agent training simulator.

31. A system as in claim 30 wherein at least some of the agents are implemented as a processing portion and an interface portion.

32. A system as in claim 31 wherein the processing portion is linked to the simulator for training.

33. A system as in claim 29 wherein at least some of the agents include a state machine for evaluating antecedents.

34. A multiple site system comprising:

a diverse group of entities wherein each of the entities incorporates a plurality of rules, wherein each rule has associated therewith an effectiveness indicium, and wherein the rules are implemented in at least a two-part, variable condition format; and

an information compilation having discrete information segments, wherein segments can be received from various of the entities and added to the compilation and including executable instructions for auctioning at least some of the segments to members of the entity population wherein entities acquire auctioned segments in exchange for value indicating indicia and including software for transferring at least a portion of the indicia received for a segment to the entity contributing that segment.

35. A system as in claim 34 which includes a simulator for automatically training at least some of the entities.

36. A system as in claim 34 wherein the entities are located at and p executed on a plurality of spaced apart processors on a network.

37. A system as in claim 36 which includes executable instructions for transferring entities between different processors.

38. A virtual society comprising:

a plurality of diverse, software implemented agents each of which maintains a variable effectiveness indicium; and

a software implemented message collection wherein agents contribute messages and wherein messages are allocated to respective agents in response to each respective agent satisfying an indicium based criterion and wherein message contributing agents are rewarded for an allocated message.

39. A society as in claim 38 wherein each of the agents includes a plurality of software based, multi-part, function implementing rules.

40. A society as in claim 39 which includes a software reproduction process wherein an offspring rule is created from at least one selected rule in accordance with a predetermined criterion.

41. A society as in claim 40 wherein agents include software wherein an existing rule of an agent is replaced by an offspring rule in accordance with a predetermined criterion to promote improved effectiveness of the respective agent as measured by a selected criterion.

42. A society as in claim 41 wherein agents include software which promotes diversity among rules.

43. A society as in claim 42 wherein the diversity software includes array processing for evaluating structural similarities between two different rules.

44. A society as in claim 42 wherein the diversity software includes oscillating sigma truncation.

45. A society as in claim 39 which includes software for covering messages which were not allocated from the message collection.

46. A society as in claim 39 which includes software for creating new rules which incorporate new information from an external environment.

47. A society as in claim 38 wherein agents are displaced from one another at different sites on a network and wherein at least one of the sites includes software for transmitting an agent to a different site for execution thereat.

48. A society as in claim 38 which includes a plurality of networked processors, wherein, some of the agents reside at different processors and wherein agents contribute messages to and receive messages from message collections implemented at different, interconnected processors.

49. An adaptive system comprising:

a plurality of agents wherein at least some of the agents exhibit a substantially similar structure with a selected function defined, at least in part, by a plurality of pre-stored rules and wherein each of the rules includes a variable performance indicium with respective indicia being selectively altered in response to increased effectiveness in carrying out the selected function, and executable instructions for automatically created new rules.

50. A system as in claim 49 wherein the respective pluralities of rules include evolving rules and imported rules received from a different agent.

51. A system as in claim 49 wherein agents are coupled to selected respective pluralities of messages.

52. A system as in claim 51 wherein a plurality of agents can forward messages to and receive messages from a selected collection of messages.

53. A system as in claim 52 wherein the collection of messages maintains a running indicium which is altered when messages are acquired by a selected agent and altered in a different way when acquired messages are received from other agents.

54. A system as in claim 53 wherein agents also include software for evaluating rule performance and for replacing at least one rule with a new rule in accordance with a redetermined criterion.

55. A system as in claim 54 wherein the evaluating software replaces rules so as to promote diversity.

56. An adaptive system comprising:

a plurality of agents wherein at least some of the agents exhibit a substantially similar structure with a selected function defined, at least in part, by a plurality of pre-stored rules and wherein at least some of the rules have a non-string like antecedent/consequent structure; and

including software for automatically creating at least some of the rules.

57. A system as in claim 56 which includes software for receiving and evaluating bids from rules for messages.

58. A system as in claim 57 wherein the respective pluralities of rules include relatively newly created, evolving rules and imported rules received from a different agent.

59. A system as in claim 57 wherein agents are coupled to selected respective pluralities of messages.

60. A system as in claim 59 wherein a plurality of agents can forward messages to and receive messages from a selected collection of messages.

61. A system as in claim 60 wherein the collection of messages maintains a running indicium, which is altered when messages are acquired by a selected agent and altered in a different way when acquired messages are received from other agents.

62. A system as in claim 56 wherein at least some of the agents each include an indicium indicative of the respective ages overall performance.

63. A system as in claim 56 wherein members of a selected plurality of rules attempt to acquire intra-agent messages from a local plurality by successfully bidding therefore.

64. A system as in claim 56 wherein such agents also include software for evaluating rule performance and for replacing at least one rule with a new rule in accordance with a determined criterion.

65. A system as in claim 64 wherein the evaluating software replaces rules in a manner that promotes diversity.

66. A system as in claim 56 wherein at least some of the rules each include a variable performance indicium with the indicia being selectively altered in response to increased performance in carrying out the selected function.

67. A method comprising:

providing a plurality of multi-part rules, each having an antecedent portion and a consequent portion;

matching requirements of at least one antecedent portion of a selected rule prior to permitting the rule to carry out the consequent portion where matching includes attempting to acquire at least one of an external message from an external message list and an internal message from an internal message list in response to an indicium of a selected message falling within a predetermined range;

responsive to the results of the matching, carrying out the consequent portion.

68. A method as in claim 67 which includes, carrying out the consequent portion by posting at least one consequent message for use by other rules.

69. A method as in claim 68 which includes providing a reward to at least one rule that has been able to execute its consequent portion.

70. A method as in claim 67 which includes matching antecedent requirements of a plurality of rules by comparing an indicium of a selected available message to an acceptability range of the respective rule.

71. A method as in claim 70 which includes permitting those rules that have fulfilled their antecedent requirements to try to execute their consequent portions.

72. A method as in claim 71 which includes permitting those rules that successfully executed their consequent portions to make messages available for acquisition by other rules.

73. A method as in claim 67 which includes promoting diversity among newly created rules.

74. A method as in claim 73 which includes evaluating effectiveness of a plurality of rules and modulating an effectiveness indicium so as to promote diversity of rules.

75. A method as in claim 67 where a rule acquires a message by offering resources in a bidding process.

76. A method as in claim 75 where a rule acquires a plurality of messages in satisfying its antecedent portion.

77. A method as in claim 76 where messages are acquired by bidding against other rules.

78. Software recorded on a computer readable medium comprising:

first software for maintenance of a plurality of agents;

second software for attempting to carry out a plurality of agent related multi-part rules, second software including additional software to evaluate a first part of the rules by evaluating if an indicium of a message, sought by a respective rule, falls into a predetermined rule related range;

third software for automatically generating additional rules where diversity is promoted among the additional rules.

79. Software as in claim 78 which includes software enabling a respective rule to bid against other rules for a selected message.

80. Software as in claim 79 including additional software enabling agents to move between sites of a computer based network.

81. Software as in claim 79 which includes additional software for evaluating a second part of a respective rule, responsive to successfully evaluating a first part of that rule where evaluating the first part has led to at least one message related bid.