Adaptive Applications of Intelligent Agents

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

Adaptive Applications of Intelligent Agents

Ibrahim F. Imam

Department of Computer Science Arab Academy for Science and Technology

Cairo, Egypt

email:

satisfaction. Only the external actions of the agent are ABSTRACT

The paper presents two applications of intelligent agents

to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adaptation is classified into three categories: internal, external and complete. Internal adaptation is concerned with the problem-solving algorithm; however, external adaptation is concerned with changes in the agent environment. The paper presents an automated travel agent that performs adaptive tasks using the AQDT-2 system for learning task-oriented decision structures. The AQDT-2 system can optimize the learning process according to a set of costs. The system allows defining costs for attributes, decisions, cases, and learning criteria. The system offers alternative decisions whenever it is impossible to reach an exact decision. Another application is presented for identification agent. The identification agent is implemented to recognize faces through pictures. The agent utilizes multiple classifiers to speed up the recognition process. The agent uses some of these classifiers to select the best classifier to recognize the given object. Other classifiers are used for identifying the object. The concept of adaptation is illustrated through out the two examples.

Key words: intelligent agent, adaptive behavior, machine learning.

1. Introduction

An agent is a machine or a system that accomplishes something the user needed without knowing how the agent did it, “You call it an agent when you want to treat it as a black box”[9]. An agent should have a set of tasks to perform for the user. These tasks define the scope and limitations of the agent. Intelligent agents utilize inferential or complex computational methodologies to accomplish their tasks. Usually, the methodologies adopted by the agent have no relationship to the user

recognized and may be evaluated by the user.

External actions of an intelligent agent are usually projections of internal commands or some results determined by a system or an algorithm. Adaptation in intelligent agents can be grouped into three categories based on the relationship between the internal adaptation and the external behaviors of the agent: 1) —where the internal systems used by the agent are adaptive, but the agent external actions do not reflect any adaptive behavior (e.g., an agent may optimize its search algorithm which improves its performance time, however, the agent still produces the same exact services to the user); 2) —where the internal systems of the agent are not adaptive, but the agent external actions reflect adaptive behavior (e.g., an irrigation robot utilizes a simple equation of the temperature and the humidity to irrigate a green house; the agent may irrigate the green house different number of times each day at different hours); 3) —where the internal systems of the agent are adaptive and the consequences of these adaptations are reflected on the agent external actions (e.g., a robot follows a plan and updates the plan based on its observations which in return changes the course of actions of the robot). Considering such classification, can be defined as systems or machines that utilize inferential or complex computational methodologies to modify or change control parameters, knowledge-bases, problem-solving methodologies, course of actions, or other objects in order to accomplish a set of tasks that are of interest to the user. Intelligent adaptive agents can effectively improve the use of many application systems for different domains including military or strategic planning, mechanical control, interactive multimedia, image and voice recognition, etc.

This paper introduces a framework for the development of intelligent adaptation in agents. The framework

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

presents also a general architecture of intelligent adaptive agents and a set of key features that should be taken into consideration during the implementation of intelligent adaptive agents. These features include the goal and cause of adaptation, the relationship between adaptation process and the architecture of an agent or a society of agents, and others. Two examples of intelligent adaptive agents in the domains of air traveling and object identification are presented to illustrate different issues of the framework. In both examples, the agent was considered as a program agent learns from problem-solving cases how to adapt its model of other agents of the same group. Adapting the agent's model of other agents usually changes the course of actions the agent may follow in different situations. They demonstrated their approach using a distribute AI problem, called Predator-Prey. The problem is concerned with four agents (predators) attempting to capture another agent (prey). Each predator adapts its moves based on the potential moves of other predators to avoid conflicts. They proposed also solutions to avoid deadlock situations due to agents over-learning.

controls the input data, parameters, execution plan, set of cost functions, and a set of learning systems. Also, each agent has a set of heuristics to control the adaptation process. These heuristics were designed to minimize the number of learning systems used by the agent, to change the cost of attributes or attribute values to reach better solutions, etc. One of the learning systems used by both agents is the AQDT-2 system [7]. The AQDT-2 system learns task-oriented decision structures from decision rules.

2. Related Work

Since adaptation is desired whenever errors or unexpected changes in the environment occurred, it is very important to detect these errors or changes, determine their cause (if possible), determine the correct course of modifications, and adapt the agent functionality to resolve such situations. Laird, Pearson, and Huffman [6] introduced a very nice approach to model adaptation in agents. The approach characterizes the adaptation process into three levels of knowledge and control. These levels are the reflex level for reactive response, a deliberate level for goal-driven behavior, and a reflective layer for plan deliberation and problem decomposition. Their approach demonstrated adaptation at both the reflex and the deliberate levels. At the reflex level, the domain theory is modified and extended to determine needed actions for similar situations. At the deliberate level, the agent uses the reflective knowledge to update its course of action.

If the mind controls the body, the body is the main

information tributary to the mind. Haigh and Veloso [3] developed an approach for adapting the domain models of a planner based on a robot's direct observations of the environment. The approach introduced an agent, Rogue, which uses the planning and learning system Prodigy[12] to support the robot Xavier [11] in performing physical tasks. After performing each task, the robot Xavier provides the agent Rogue with its observations about the environment. Rogue responds to the observations by dynamically updating the domain model. This update may affect the set of tasks that the robot needs to perform. The robot then starts performing tasks of the modified plan. Haynes and Sen [4] introduced adaptation as a key component of any society of intelligent agents. Each In virtual reality simulation, agents can independently transfer through a network of computers to accomplish a task. Rus, Gray, and Kotz [10] introduced adaptive agents as systems that can completely terminate their existence at a given location of a network, transform to a better location to accomplish the given task, and resume the execution of that task. Such agents have capabilities to: 1) sense the state of network (e.g., to check if the local host is connected, to find out if a site is reachable, or to estimate the load of the network); 2) monitor conditions of software resource (e.g., monitor activities of a site or another agent which expected to receive or obtain relevant information to the current task); 3) interact with other agents (e.g., an agent may need to know other agent locations in the network, gather information about the tasks they can perform, or request a task from another agent).

In a multi-agent society, predicting environmental changes is another approach to plan for intelligent adaptation. To predict and adapt to environmental changes in information-based multi-agent systems, Decker, Sycara, and Williamson [2] presented an approach where a matchmaker information agent gathers organizational information about all agents' functionality, each agent plans the control-flow of its actions or decisions using information about the relationships between all current tasks, all agents utilize a flexible scheduling mechanism, and each agent can control its active execution load.

3. Examples of Adaptive Agents 3.1. Adaptive Travel Agents

This section presents an adaptive travel agent that optimizes a knowledge base for different user requests. The agent architecture follows the proposed general architecture described in section 3.2. The agent utilizes the AQDT-2 learning systems and a program for modifying the input files to the AQDT-2 system. The initial knowledge was learned by the AQ15c system [1]. For each new customer, the agent acquires information about the customer’s preferences (i.e., given situation), then it updates its cost functions, parameter settings, and other criteria. Updating these criteria biases the AQDT-2 system to optimize the initial knowledge for the given situation. Information about the given situation and the settings of all criteria is stored in the agent data

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

structure. After learning the optimized structure, the agent tests the knowledge against a set of constraints and heuristics. The goals of the agent are to: 1) determine accurate knowledge, 2) minimize the number of nodes in the obtained structure, and 3) minimize the average number of levels in the structure. Figure 1 shows a simple architecture of the main components of the travel agent. Also, Figure 2 shows a general algorithmic also sell tickets for any flight starts from the first destination to any intermediate destinations. The agent discovered that the customer’s preferences can be summarized by 8 attributes, Table 1. All possible trips from Washington to Tokyo were split into two categories. The first category of trips labeled (many customers requested these routes), while the rest of the data was labeled description of the adaptation process.

Task-orientedFigure 1: Architecture of the Adaptive Travel Agent.

The data was generated using Mugglton’s program[8]. User’s preferences of a flight are represented using a set of attributes describing: 1) if the customer requires over night stay, 2) the average waiting time during the whole trip, 3) if it is an over night flight, 4) if its frequent flight program is compatible with the customer’s program, 5) the kind of entertainment the airline company provides, 6) if smoking is allowed, 7) the name of the airline company, and 8) the number of meals served during the trip. Table 1 describes these attributes and their possible values.

Input: A set of decision rules or examples and description of

one or more tasks.

Output: A situation-oriented decision structure/tree for each

decision-making situation.

: For each decision making situation, the agent repeats

steps 2 to 4.

criteria) and uses the cost functions to update the ranking of the attributes.

structure/tree. It selects the top ranked attribute, assigns it to a node, creates branches equal to the number of its values, and divides the decision rules associated with this node into subsets each corresponds to one branch. inexpensive attributes can be used for further classifications of the decision rules at a certain node, the agent generates a leaf node with all possible decisions at this node. The agent can also determine a confidence probability for each decision or solution.

Figure 2: Description of the adaptive algorithm.

The travel database is concerned with trips between Washington D.C. and Tokyo. Each trip consists of two or more flights. The agent deals with six airline companies. Non of the six companies offers a direct-flight trip between the two destinations. The agent can agent asks the customer a set of questions to determine the most appropriate flight. In this paper, the agent will attempt to discover interesting combinations that of interest to the customer in order to optimize the process of finding a preferred trip for the customer.

Table 1: The set of attributes used in the experiments

(“i” : stands for the flight number).

Attribute Values

1

2 3

4

5

xi1 over-night-stayyes no xi2 waiting-time x< 11<x<3 3<x<6 6<x>10x>10

xi3 over-night-flightyes no xi4 frequent-flight yes no xi5 entertainment all music movie games none xi6 smoking no allowed xi7 airline-companyTWACAL PanAM United KLMJAL xi8 No.-of-meals one two more none

The agent first learns a classification of preferred and non-preferred trips. The agent uses the descriptions of the preferred trips to assist the user in selecting the best trip. Figure 3 shows a decision tree, obtained by AQDT-2, that classifying preferred and non-preferred trips. From this decision tree, one can observe that preferred trips depend highly on the airline company, and the frequent-flight-mileage. The agent offers any new customer the preferred trips. If the customer requires other options, then the agent presents him/her the non-preferred trips.

Figure 3: A decision structure obtained by AQDT-2 in

its default setting.

Adaptation is required whenever the user has a specific request that can not be answered directly by the agent. For example, suppose that the customer was interested in the frequent flight mileage program. For this task, the agent assigns lower costs to all attributes representing the frequent flight mileage in all flights, and runs the AQDT-2 system. Figure 4-a shows a decision tree obtained by AQDT-2 for the given task. The agent’s best choice is to propose the customer a trip consisting of three flights, where either the third flight should be on

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

TWA, or the first flight is not an overnight flight (e.g., short flight or one starts early in the morning).

Another example of an adaptive task is when the user requires an overnight trip. In this case, the agent assigns lower costs for all overnight flights. The agent runs AQDT-2 with the new task. AQDT-2 learns the decision tree shown in Figure 4-b. Parts of this decision tree show classifications of all trips which include an overnight flight. All such trips consist of three flights. The same Figure shows also that there are four preferred ways for a trip with an overnight flight, two of which have two a set of decisions or actions. Imam and Gutta [5] proposed an approach to improve the recognition of visual objects using adaptive methodology.

overnight flights.

Figure 4: Examples of adaptive situations.

A more complicated scenario would be, For example, if the customer asks for United airlines in as many flights as possible. The agent defines lower costs for all reduces the cost of the value 3 of attribute xi7). The agent groups all values representing other airline companies into one value “~”. The agent runs the AQDT-2 system with this new task to obtain the decision tree in Figure 5. The agent determined two preferences. The first has three trips and the third trip is a United flight. The second has four flights and requires staying over night. Note that the third preferred node may mean that there are other trips where the first or the second flight are served by United airlines. To obtain more details about these trips, the agent is supposed to set the cost of both attributes x37, x47 slightly higher and runs the AQDT-2 system to obtain a decision tree for the new task.

3.2. Identification Agents

The second adaptive agent presented here is an object identification agent. Object identification agents can widely be used by federal investigators to identify finger prints or facial images, companies to recognize identification cards and employees codes, by medical labs to diagnose diseases, by robots to identify known objects or surrounding environment, etc. Object identification is a part of the agent functionality. Usually, the results from the recognition process are used to form

United flights.

To illustrate the architecture of the agent, assume that the agent has a library of classifiers to recognize a set of objects. Each classifier can recognize the objects based on different set of characteristics. One of the agent’s goals is to determining which classifier should be chosen to obtain accurate recognition of a given object. The agent is not allowed to acquire any information about the testing object, however, it can use any number of classifiers to recognize that object. From a set of examples of recognition, the agent learns an optimized plan for recognizing any given object. The adaptation is done during the process of generating an optimized plan. Figure 6 shows an algorithm for identification agent.

Input: A set of training examples (records of recognition)

described by a set of attributes A.

Output: A tree shows a set of optimized plans of classifiers

needed for object recognition. : Quantize all attribute values in the records of

recognition.

: Specify the learning task for the agent (in this case, the

decision structure should have minimum number of classifiers and minimum number of levels). (*) For each attribute in the set A (i.e., classifier),

repeat steps 3 and 4. : Set the cost for that attribute lower than all other

attributes in the set A, and use AQDT-2 to learn decision tree. : Save the attribute name, the number of nodes, and

number of levels. Assign similar cost to all attributes in set A.

: The attribute produced the minimum number of nodes

and minimum number of levels, say C, is permanently assigned the lowest possible cost among the attributes in set A. Remove C from A. For each branch stemming from the node C, repeat

steps 6 to 8.

: Assign a copy of the attribute set A to each branch.

: If the node connected to the branch is a leaf node, skip step 8.

: If the branch is connected to a non-leaf node, go to (*).

Figure 6: The adaptive algorithm used by the agent.

The agent uses a set of heuristics to control the adaptation process. For example, the agent should recognize all objects using the minimum number of

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

classifiers. The agent uses the AQDT-2 learning system to create a complete plan for recognizing new objects. Two actions can be taken at each step of the plan, either to the object or to plan describes a sequence of actions based on the maximum value given by the classifier to a decision class. Whenever the action is “recognize”, the agent assigns the decision class with the maximum value to the tested object. The agent adapts the cost functions and the different parameters to obtain the optimal plan. Figure 6 shows a brief description of the adaptive methodology of the agent. The algorithm stops after testing all intermediate nodes. This algorithm is not concerned with building the decision tree. However, it controls the process of learning decision trees.

Select aClassifierThe application presented here was applied on a domain of hand gestures. A total of 150 gestures representing 15 different gestures were obtained. Three different testing combinations, The AQDT-2 program was modified to allow all nodes to contain actions in addition to the tested attributes. The agent generates a table of actions with their possible places. For example, in this case there are two actions “Select” and “Recognize”. The “Select” action is assigned to any internal node. The “Recognize” action is assigned to leaf nodes only. The goal of the adaptive process is to maximize the recognition rate of objects using the minimum number of classifiers. Figure 7 shows a portion of the complete set of plans obtained by the agent.

<=0.35Recognize

>0.35 &<=0.45Select aClassifier>0.45 &<=0.55Select aClassifier>0.55 &<=0.65Select aClassifier #4

>0.65 &<=0.75Select aClassifierClassifier #3

>0.75 &<=0.85Select aClassifierClassifier #7

>0.85Recognize

Classifier #7Classifier #5

>0.25 &>0.85<=0.65

Recognize:

:

:

:>0.35 &>0.65 &>0.75 &

<=0.65<=0.75<=0.85RecognizeRecognizeRecognize

>0.35 &>0.45 &

<=0.45<=0.55RecognizeGest. #11Gest. #1Gest. #4Gest. #3Gest. #8Gest. #5Gest. #2Gest. #10

Figure 7: Portion of a complete plan for recognizing visual objects.

adaptive behavior which usually driven by changes in the 4. Summary

environment; 3) Complete Adaptation—where the The paper proposed a framework for developing

internal systems of the agent are adaptive and its external intelligent adaptive agents. In this framework, intelligent

actions reflect adaptive behavior. adaptive agents are defined as systems or machines that

utilize inferential or complex computational The paper presents a set of fundamental issues in the

development of any intelligent adaptive agent including methodologies to modify or change control parameters,

knowledge-bases, task plans, problem-solving modeling the cause and the goal of the adaptation

process, the relationship between the adaptation process methodologies, course of actions (for the same agent or

and the agent architecture, and other criteria distinguish for other agents), or other objects in order to successfully

adaptation in multi-agent society from adaptation in accomplish a set of tasks that are of interest to the user.

single agent. Also, the framework presents intelligent The framework distinguishes between two types of

adaptation as a process that indicates the agent’s ability intelligent adaptation, external (behavior) and internal

to accomplish: different tasks within the scope of the (systematic). Intelligent adaptive agents are classified

agent functionality, similar tasks within different into three categories based on the agent capabilities on

environments, similar tasks within similar environment performing external and internal adaptation. These

but using different problem-solving methodology, etc. categories are: 1) Internal Adaptation—where the

The paper presented two adaptive agents that control internal systems of the agent are adaptive, but its

adaptive (as well as non-adaptive) systems. The results of external actions do not reflect any adaptive behavior; 2)

utilizing these systems are used in accomplishing External Adaptation—where the internal systems of the

external actions. These actions reflect adaptive behavior.

agent are not adaptive, but its external actions reflect

The paper presents two applications of intelligent agents to support the concept of adaptation defined in previous work. The concept of adaptation differs from the concept of intelligence and they do not necessarily associated with each other. Agent adapta

The agent in both cases is a program makes use of a set of heuristics to control one or more learning systems. A data structure is associated with each agent to store intermediate information that may help during the adaptation process. The agent utilizes also a set of parameters, cost functions, and other criteria to perform the adaptive process. The first agent, a travel agent, adapts existing knowledge-base describing preferred flights to fit new and unknown situations. The agent repeatedly changes the cost functions to simulate different possibilities of the given situation. For each situation, the agent runs the AQDT-2 program and stores information about the results. The agent uses different criteria to evaluate these results and to determine the best solution. The output of such methodology can be mapped to different external actions (e.g., reserve a ticket on flight number 534 on TWA, print a hotel accommodation form for one night) and/or other internal actions (e.g., ask the hotel agency to reserve a one night for the current customer).

An identification agent adapts plans for recognizing visual object. It generates dynamic plans for utilizing a set of systems or classifiers for recognizing visual objects. The goal of the agent is to determine the best classifier for recognizing a given object without knowing any information about the given object. Once the recognition is made the agent transform these results into external action to either open a door or a safe. The agent uses also a set of cost functions and data structures to optimize the plans. Plans generated by the agent describe different phases of the process of recognizing objects. This methodology could be applied to many applications and the recognition results can be mapped into many different external actions.

The two agents demonstrate different aspects of the proposed framework. The adaptation process in both agents is mainly internal, however, its results can be used in many ways to reflect adaptive behavior (externally). Both agents follow the general architecture proposed by the framework for intelligent adaptive agents. The cause of adaptation in both agents is the evolution of new task. The goal of each agent is defined by the service it provides to the user. In the travel agent, the agent adapt knowledge-base, cost functions, parameters and other criteria. In the identification agent, adaptation occurs in the architecture of the agent. The structure of tools used by the agent to accomplish the given task is dynamic. A future work is to analyze the proposed framework and extended to cover different issues in multi-agent societies.

REFERENCES

[1] Bloedorn, E., Wnek, J., Michalski, R.S., and Kaufman, K., “AQ17: A Multistrategy Learning System: The Method and User’s Guide”, Report of Machine Learning and Inference Labratory, MLI-93-12, Center for AI, George Mason University, 1993.

[2] Decker, K., Sycara, K., and Williamson, M., "Intelligent Adaptive Information Agents", AAAI Technical Report No. WS-96-04, Imam, I.F. (Edr.), pp. , AAAI-Press, 1996.

[3] Haigh, K., and Veloso, M., "Using Perception Information for Robot Planning and Execution", AAAI Technical Report No. WS-96-04, Imam, I.F. (Edr.), pp. , AAAI-Press, 1996.

[4] Haynes, T., and Sen, S., "Adaptation Using Cases in Cooperative Groups", AAAI Technical Report No. WS-96-04, Imam, I.F. (Edr.), pp. , AAAI-Press, 1996.

[5] Imam, I.F., and Gutta, S.V., “A Hybrid Learning Approach for Better Recognition of Visual Objects”, Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), Portland, OR, AAAI press, 1996.

[6] Laird, J., Pearson, D., and Huffman, S., "Knowledge-directed Adaptation in Multi-level Agents", AAAI Technical Report No. WS-96-04, Imam, I.F. (Edr.), pp. , AAAI-Press, 1996.

[7] Michalski, R.S., and Imam, I.F., “Learning Problem-Optimized Decision Trees from Decision Rules: The AQDT-2 System”, Lecture Notes in Artificial Intelligence, No. 869, Ras, Z.W., and Zemankova, M., (Eds.), pp. 416-426, Springer Verlag, 1994.

[8] Michie, D., Muggleton, S., Page, D. and Srinivasan, A., “International East-West Challenge”, Oxford University, UK, 1994.

[9] Minsky, M., “A Conversation with Marvin Minsky about Agents”, Communications of the ACM, Vol. 37, No. 7, pp. 23-29, July, 1994.

[10] Rus, D., Gray, R., and Kotz, D., "Autonomous and Adaptive Agents that Gather Information", AAAI Technical Report No. WS-96-04, Imam, I.F. (Edr.), pp. , AAAI-Press, 1996.

[11] Simmons, R., Goodwin, R., Haigh, K.Z., Koenig, S., and O'Sullivan, J., "A Modular Architecture for Office Delivery Robots", Proceedings of the First International Conference on Autonomous Agents, 1997. (To Appear) [12] Veloso, M., M., Carbonell, J., Perez, M.A. Borrajo, D., Fink, E., and Blythe, J., "Integrating planning and learning: The Prodigy architecture", in the Journal of Experimental and Theoretical Artificial Intelligence, pp. 81-120, Vol. 7, No. 1, January, 1995.

本文来源：https://www.bwwdw.com/article/pi51.html