Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2000-06-02
2004-05-25
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S013000, C706S014000
Reexamination Certificate
active
06741974
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains to systems and methods that incorporate machine learning and automatic adaptation to respond to changing environmental conditions. More particularly, the invention pertains to such systems and methods that incorporate genetic algorithms, learning classifier systems and agent technology in the realization of a complex adaptive system.
BACKGROUND OF THE INVENTION
Information systems have grown to comprise such a large number of subsystems that direct centralized control is often very difficult, if not impossible. In actual use, the systems change, new situations develop in the system environment, various new components are added, and the relationships between existing components may change. This is typical of a real-world system, and such a system is called a complex adaptive system, or CAS.
Structured and object-oriented software techniques provide many useful paradigms for software development in a CAS. However, agent-based systems are superior in that system intelligence is contained in locally encapsulated software entities, or agents, and is thus portable and dedicated to given tasks. Individual agents can adapt without changing the rest of the system. An agent is a self-contained entity in a CAS. Each agent is able to accomplish given tasks within a software environment.
The use of multiple agents allows interaction and parallel execution of multiple tasks in diverse locations throughout the system. The intrinsic parallelism provides enhanced system robustness.
Because a CAS is continually changing, it is necessary to provide the agents with a form of learning, to allow them to adapt on-line to the changing environment. Using the principles of evolution, the agents can learn to accomplish their tasks, and continually work to improve their performance, and hence their fitness, to better survive in the current environment. Various solutions are built and tested, and the better solutions are kept and combined with other good solutions to attempt to continually improve the performance.
One known approach, a learning classifier-system, was a machine-learning technology that attempted to learn optimum job performance in a given environment. This was a rule-based system containing multiple rules, and was capable of generating new rules as needed. This type of system was capable of creating rule-chains, by allowing time-delayed rewards to influence the fitness of earlier rules in the chain, and by passing part of the reward earlier in the chain. It incorporated a genetic algorithm, to create new rules, and to evolve the existing rules through rule crossover and mutation techniques.
The rules contained in the known system consisted of fixed-length strings of binary digits, requiring external interpretation to express their meaning. Through the use of binary digits, with the addition of a wild card symbol, hierarchies of rules could be evolved, where one rule could be applicable in multiple situations. Because the known system was constrained to operate on binary strings, it was difficult to add new information into the system. The interpretation of each of the binary digits in the string would have to be modified to accommodate the new information, and the string length would change, all increasing complexity.
Genetic programming evolved to create more text-based evolved solutions to problems. Instead of using a binary string, genetic programming combined functions and terminals, which are represented by words, into a string that is genetically evolved. The functions and terminals can be combined in a type of Lisp or tree expression. As known, genetic programming determines only a single solution from the evolutionary process. In contrast, learning classifier systems need multiple actions to be maintained in the knowledge base.
Thus, there is a need to combine properties of learning classifier systems and genetic programming to create an adaptable system that automatically learns optimum behavior. Preferably such a system would use the terms and operations of the actual environment to make up its rules, while maintaining a diverse rule base.
It would be preferred if it would be unnecessary to code software manually based on learned information. Preferably, such systems would incorporate online adaptation and response to environmental changes. Such adaptation would minimize down time or sub-optimal functioning while awaiting new software.
It would also be preferred if manual software changes would be unnecessary to modify system behavior or to respond to changes in the environment or the system being controlled. In this regard, distributed processing as opposed centralized control minimizes problems due to losses of portions of the system resident at remote nodes. It would also be preferable if it would be unnecessary to have a human maintain and update the software manually. This avoids ongoing needs to understand the software, modify tests and integrate the modified software.
SUMMARY OF THE INVENTION
A system which embodies this invention enables a plurality of intelligent agents to learn to accomplish tasks in their environment and to adapt to changes in the environment. The agents each have a substantially similar structure and incorporate a plurality of pre-stored rules.
Each rule has an associated fitness or success measure. This measure can be dynamically increased and decreased in response to effectiveness in carrying out a function.
Agents incorporate an internal message list. This list can be accessed by the rules. The messages can be allocated by, for example, an auction process.
Agents also have access to an external message list at each site. Messages are received and auctioned to the agent population. Funds are collected from successful bidders and distributed, at least in part, to the agent or agents which contributed the auctioned messages.
In one embodiment, the intelligent agents exist in an artificial economy where information is bought and sold. The fitness of agents for a certain task is based upon virtual funds they have accumulated over time.
The funds a certain agent possesses are related to how well it performed jobs that is has attempted. Rewards are provided in an ongoing manner as jobs progress, allowing an agent to learn which actions to take to accomplish each job.
Agents that perform the jobs correctly and efficiently are rewarded more than agents that do not. Agents that accumulate more funds or fitness indicia are used to populate the environment, through cloning, and evolutionary techniques such as simulated sexual reproduction. In this simulation process, new agents are created from two parent agents with the parent agents being selected by their level of fitness.
In another embodiment, the environment can contain multiple sites where agents can execute their commands, communicate with other agents, and interface to the outside world. Each site is a location on a computer that supports the existence and operation of agents. The site contains message boards that are available for use by the agents. A site serves as an address for agents to be used when agents traverse the network.
Sites are interconnected, such that agents can be dispatched from one site, traverse the network, and reappear at another site. Sites may be located on the same computer, or distributed geographically to distant locations connected through a digital communications system. The conglomeration of all sites and agents that exist at those sites is called the environment.
Sites can contain an interface agent that provides a vehicle for agents to communicate with software systems that are external to the agent site. These external software systems may consist of databases, messaging/communication systems for human users, or other pre-existing software applications.
Instead of using binary strings, in another aspect, strings of high-level computer language words that are sequenced under syntax rules and structured in the form of IF-THEN statements. Irrespective of language, the present rules have a two part structure wherein anteceden
Harrison Gregory A.
Hollister Keith
Worden Eric
Davis George B.
Lockheed Martin Corporation
Welsh & Katz Ltd.
LandOfFree
Genetically programmed learning classifier system for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Genetically programmed learning classifier system for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Genetically programmed learning classifier system for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3264663