A Multi-Agent System to Model the Labor Market Simulating a New Job Contract

A Multi-Agent Approachto Vehicle Monitoring in MotorwayEnrico Appiani,Maurizio Martelli,and Viviana MascardiElsag s.p.a.,Via Puccini2,16154Genova,ItalyEnrico.Appiani@elsag.itDISI–Universit`a di GenovaVia Dodecaneso35,16146,Genova,ItalyFax+390103536699martelli,mascardi@disi.unige.itAbstract.This paper describes CaseLP,a prototyping environment for Multi-Agent Systems(MAS),and its adoption for the development of a distributed in-dustrial application.CaseLP employs architecture definition,communication,logic and procedural languages to model a MAS from the top-level architecturedown to procedural behavior of each agent’s instance.The executable specifi-cation which is obtained can be employed as a rapid prototype which helps intaking quick decisions on the best possible implementation solutions.Such capa-bilities have been applied to a distributed application of Elsag company,in orderto assess the best policies for data communication and database allocation beforethe concrete implementation.The application consists in remote traffic controland surveillance over service areas on an Italian motorway,employing automaticdetection and car plate reading at monitored gates.CaseLP allowed to predictdata communication performance statistics under different policies of databaseallocation.1IntroductionFor Police and Financial Police,the control of wide sections of motorway represents a powerful means to individuate vehicles of suspects,trace their movements and take the proper actions consequently.Such control takes place by a distributed network of car detection and licence plate reading systems,placed at motorway service areas,sending their transit information to control centers and detecting possible matches with suspect number-plates.Besides law enforcement,this kind of car monitoring can be useful for vehicle transit control,such as in motorway gates,parking areas and urban zones with restricted access.The scenario for vehicle monitoring is extremely complex since it involves a large number of heterogeneous entities.They can be human entities(the policeman who in-serts a new number-plate to be monitored or who receives an alarm concerning a suspect vehicle),physical entities(remote cameras for getting number-plates images,commu-nication infrastructure)and software ones(the client interface,the application server and the remote sensor control with image processing for licence plate reading).Due to the heterogeneity and complexity of this scenario the assessment of the real framework2 E.Appiani,M.Martelli,V.Mascardifor vehicle monitoring requires a careful design and the full understanding of all the involved parameters,as well as their relations and mutual influence.The distinguishing features of the entities involved in the application,namely their heterogeneity,their physical distribution,the ability to autonomously accomplish their specific tasks but also to interact with other entities to achieve a common goal,highlight the suitability of a Multi-Agent System(MAS)approach for modeling the scenario.An agent is commonly described as an entity situated in some environment,perceiving it and capable offlexible autonomous actions in order to meet its design objectives. Flexibility is specified as responsiveness(ability to react in timely fashion to changes happening in the environment),pro-activeness(ability to pursue a long-term goal)and sociality(ability to interact with other agents or human beings belonging to the system) [4].This definition matches quite well the features characterizing the entities in the vehicle monitoring application.Once understood that the MAS metaphor can be properly adopted for modeling this scenario,it is also necessary to identify the best method to follow in order to develop the real monitoring environment,starting from the initial specifications and requirements. The development of a working prototype is a good choice since it allows to easily test and modify some design choices and to get immediate feedbacks on their impact on the global scenario.According to these considerations,the Computer Science Department of Genova University(DISI)and Elsag s.p.a.,an international company working in several ser-vice automationfields,have developed a working prototype of the vehicle monitoring application modeled as a MAS.This prototype has been used to improve the applica-tion specifications,to properly dimension the communication channels,andfinally to provide a formal specification to be followed during the implementation stage.The im-plementation has been completed successfully and the vehicle monitoring apparatus has been installed in the motorway section between Salerno and Reggio-Calabria(Italy);it is currently used by the Italian Police,Financial Police and by the“Autostrade”(motor-way)organization for traffic monitoring.The aim of this paper is to describe how CaseLP,a prototyping environment for MAS developed by the Logic Programming Group of DISI,has been used to model and prototype the vehicle monitoring application.The organization of the paper is the following:Section2describes CaseLP,Section3describes the vehicle monitoring application and Section4shows how a prototype of the application has been modeled and realized in CaseLP.Section5compares our approach with simulation and CASE, presents future improvements and concludes the paper with other possible industrial applications which may benefit from it.2CaseLP:a Prototyping Environment for Multi-Agent Systems The development of an application following the MAS metaphor is a very delicate enter-prise:the MAS approach is usually adopted when the application needs to be modeled in terms of more complex entities than processes or objects,which interact follow-ing some communication protocol and which act with a certain degree of autonomy. Following a clear development methodology greatly helps the application developer in his/her job.A MAS Approach to Vehicle Monitoring in Motorway 3At the Computer Science Department of Genova University two of the authors have developed CaseLP ,a prototyping environment for MAS which also provides a devel-opment method and a set of tools and languages to support the development stages.The acronym CaseLP stands for Complex Application Specification Environment based on Logic Programming :CaseLP was originally conceived as a logic-based environment where the specification of the agents could be provided in two different logical lan-guages and executed/animated.As the research on CaseLP went on,other non-logical specification languages have been added to CaseLP in order to make it closer to the habits of users from the indus-try,who are not usually very accustomed with LP.Now CaseLP integrates various specification languages and provides the means to semi-automatically translate them into executable programs (one for each agent)written in an extended Prolog with com-munication capabilities and a safe management of state updates.The execution of the agents is controlled by an engine which maintains a trace of the events the user wants to monitor and provides on-line and off-line statistics on the simulation execution.The CaseLP framework is graphically depicted in Fig.1:the integration of external com-ponents is also shown.The high level specification of agents can be written in any of the specification languages described in Section 2.2.In a very near future also UML will be available as a specification language integrated within CaseLP :we are currently working at describing agents using a suitable subset of UML and translating the UML agents into executable Prolog agents.For this purpose a textual representation of UML is used.from high levelto executable spec.Compilation processo o oospecification of agentsLegacy software specification of agentsExecutableHigh levelCommunication links integrationLegacy software CaseLP engine Fig.1.CaseLP framework.The prototype development,which deals with the specification,implementation and execution of agents,is carried out following a well defined and experimented4 E.Appiani,M.Martelli,V.Mascardimethodology.Section2.1describes the methodology,while section2.2describes the tools CaseLP provides to support any step of the methodology.The CaseLP ap-proach to MAS development is to clearly separate the task of defining the agent ar-chitecture,namely the agent’s internal components and the controlflow among them, from the task of defining the application-dependent knowledge of agents.For exam-ple,agents may have a reactive architecture,characterized by an event-queue and a set of event-condition-action rules,or they may be conceptualized in terms of human-like belief-desire-intentions,and so on.The data structures and controlflow neces-sary to make these architectures work are very different.The agent architectures are domain-independent and,once defined,can be reused for multiple applications.Since all the agents involved in the vehicle monitoring application share a reactive architec-ture,where reaction is triggered by the reception of a message,we just marginally face all the issues related with the definition of different architectures and the consequent choice of“the right agent architecture to do the right thing”.For sake of clarity,the method we propose in this paper is a simplification of the complete CaseLP method described in[8]and it is limited to the steps we followed for the development of the vehicle monitoring application.As far as the tools and languages are concerned,we just give a brief overview of all of them and,in Section4,we exemplify the adoption of some of them for the vehicle monitoring application.2.1Prototyping methodThe CaseLP method is summarized in the following steps:1.Static description of the application architecture.In this step the applicationdeveloper defines:–the classes of agents that the application needs.A class is characterized by the kind of the agents belonging to it,e.g.if they are yellow page facilita-tors,or if they are interfaces towards external software,and so on;the architecture of agents;the services required and provided by the agents in that class;–the instances of each class that will form the MAS;–the interconnections between agents,that is,how a service provided by an agent is linked to a service required by another agent.2.Description of communication between agents.Each provided or requested ser-vice needs a specific conversation between the agents providing and requiring the service.This step allows to specify the sequence of exchanged messages,as well as their content.3.Description of the procedural knowledge of each agent class.Agent instancesbelonging to the same agent class,described in thefirst step of the method,share the same procedural knowledge depending on the agent’s class and on the communi-cation protocol the agent adheres to,as described in the second step of the method.The way the agent’s procedural knowledge and state are formalized depends on the agent’s architecture.A MAS Approach to Vehicle Monitoring in Motorway54.Verification and testing of the agent’s specifications.If the language adopted forthe specification of the agents is executable or animable,it is possible to verify some properties of the MAS behavior before implementing the prototype.5.Prototype implementation.The specification of the agents given in the previoussteps are(semi)-automatically translated into an executable piece of code.In order to implement the agents,all the details concerning their architecture must be com-pletely specified.However,the burden of this task will not fall on the application developer.The CaseLP approach is to provide the application developer with a pre-defined library of architectures from which he/she can choose the most appro-priate ones.The architectures in the library have been specified,verified and tested before being employed.6.Execution and testing.In thefinal step of the method the prototype is tested in dif-ferent conditions,in order to evaluate its behavior in as many situations as possible.This kind of testing does not ensure that the prototype is correct,since it is usu-ally not possible to exhaustively test it in all the possible initial conditions which can take place.Nevertheless,a good choice of test cases gives a reasonably high confidence in the prototype correctness and allows the prototype developer to get important feedbacks on the system behavior.Ifflaws are detected,a revision of the previous steps of the method is possible.This refinement cycle through the method steps can go on until a“correct”prototype is obtained.2.2Prototyping tools and languagesMAS-adl:a simple architectural description language.In thefirst step of the method MAS-adl,a simple,customized,architectural description language[5]for MAS,is adopted.MAS-adl describes three main constructs:AgentClassDef defines the classes of agents used in the MAS under construction;AgentInstancesDef defines the in-stances of classes previously defined i.e.,the agents that constitute the MAS;LinksDef defines the directed links between instances of agents,from a service provided by an agent to a service required by another agent.The use of MAS-adl for the vehicle mon-itoring application is described in Section4,while its full syntax is described in[7]. Tools for conversation model.The second step of the method describes the conversation model of the MAS.The agent communication language is a subset of KQML[9].The conversation model is defined by choosing,for each service,the sequence of messages (conversation),as well as their performative and the content of each message.A relation defines which conversations eventually start during other conversations.Letbe a conversation composed by messages and let be another conversation.denotes that must start after message in has been handled by the receiving agent.denotes that eventually starts after message has been handled by the receiving agent.In the latter case,the decision about starting is up to the receiving agent.ACLPL.In the third step of the given method the agents’procedural knowledge is defined.CaseLP provides three languages for describing this knowledge;the simplest one,suitable for specifying the simplest kind of agents,namely the reactive and proac-tive ones,is ACLPL which allows to define both reactive and proactive rules.A reactive6 E.Appiani,M.Martelli,V.Mascardirule has the formon message Msg check Condition do ActionsListThis rule isfired by a message taken from the agent’s mail-box,and if the condition is satisfied,corresponding actions are executed.Condition expresses what must be true in the current agent’s state in order to execute a sequence of actions.If it is satisfied the actions are executed;they usually deal with state update or communication.A proactive rule is similar to a reactive one,but it only depends on the state condition.The agents in the vehicle monitoring application have been specified with this language,as described in Section4.The syntax of ACLPL can be found in[8].HEMASL and.There are many applications where the agents involved need to be conceptualized in terms of mentalistic or emotional attitudes,thus requiring a more complex architecture than the reactive or proactive ones.In such situations where ACLPL is inadequate,the description of the agents can be formalized using either HEMASL or.Thus being extremely different,the two languages share a common feature:they can be used to specify both the architecture of agents,and their procedu-ral knowledge and initial state.As we have already highlighted,the specification of the internal structures and controlflow of CaseLP agents is kept separate from the specifi-cation of their domain-dependent knowledge.HEMASL have been purposely designed for describing agents at both the architecture and domain-dependent knowledge levels, while,which was not conceived as a language for specifying agents,has proven to be very suitable also for this purpose.[6]provides a complete description of HEMASL design,while[2]and[1]describe the adoption of as an architecture specification language and as a procedural knowledge specification language respectively. HEMASL.HEMASL allows to specify MAS in which agents are characterized by–a state which contains the data that may change during the execution of the agent;–a program,namely that part of procedural information that does not change during the execution of the agent;and–an engine which controls the executionflow of the agent by providing a meta-interpreter for the program and for the data(state)on which the program operates. In order to describe the agent at both the architectural and domain-dependent levels, HEMASL supports a hierarchy of four concepts going from the description of the agent’s abstract and concrete architecture,to its complete definition in terms of domain-dependent knowledge(agent’s class)and initial state.This approach combines features borrowed from the object-oriented paradigm(abstract architectures do not need to be fully implemented,like abstract classes;more agent classes can share the same con-crete architecture which is extended by the class domain knowledge;agent instances play the same role as objects in OO languages)together with a simple procedural lan-guage for describing the engine of the agents.The agent program is expressed is some architecture-dependent language for which the engine is a meta-interpreter.We have al-ready developed engines for existing agent architectures,and we are currently working on extending this library.We think that HEMASL features make it suitable for adoption by industrial users who are more accustomed with the imperative and object-oriented paradigms than with the logic one.A MAS Approach to Vehicle Monitoring in Motorway7.The linear logic language[3]is an executable language for modeling con-current and resource sensitive systems based on the general purpose specification log-ical language Forum[10].has a multiset-based logic combining features of ex-tensions of logic programming languages like Prolog,e.g.goals with implication and universal quantification,with the notion of formulas as resources at the basis of linear logic.A-program is a collection of guarded multi-conclusion clauses.Clauses of this kind consume the resources(formulas)they need in order to be applied in a reso-lution step.For this reason they can profitably model the dynamics of agent execution, where the old state is“consumed”when the agent moves in a new state.Moreover, thanks to its support of concurrency,easily models the autonomous concurrent entities which form the MAS.The adoption of is particularly suitable to safety critical applications,where model checking is needed to ensure the specification cor-rectness w.r.t.some critical property.The relevant features of the application can be modelled in which,thanks to its interpreter,can be used to prove properties of the specification.PROLog for AGents.The target language for implementation is ProlAG(PROLog for AGents),an extended platform-independent Prolog language.ProlAG is defined as stan-dard Prolog extended with communication capabilities and with safe state updates.The predicates for state update are safe in the sense that they can be backtracked.The predi-cates for communication allow agents to send messages asynchronously,and to perform both blocking and non-blocking message reception.Semi-automatic compilers from ACLPL and into ProlAG have been developed,as described in[8].CaseLP Simulator and Visualizer.The obtained ProlAG prototype is tested using the CaseLP Simulator.The simulator provides the means to set the simulation parameters, such as the time grain and the simulation length,as well as some parameters of the communication network.In particular,it is possible to set the latency and reliability of the communication channels between any couples of communicating agents.It is also possible to associate a weight to any message which can represent any measure significant for the application.As an example,it can represent the number of bytes necessary to code the message itself,or a rate of the message importance,and so on.The simulation provides the complete trace of the events(communication or state change events)that the developer decided to monitor.It also provides statistical in-formation on message exchange:the maximum and average number of messages of a certain type per time unit or time interval,the maximum and average weight of mes-sages per time unit or time interval and their standard deviation.A graphic version of the simulation execution and statistics is provided by the CaseLP Visualizer.3The Case-Study:Vehicles Monitoring in MotorwayElsag has been designing and integrating remote surveillance systems,including auto-matic detection and reading of licence plates,since1990.They have been applied in different scenarios,such as:motorway gates and service areas;parking areas;urban sectors with traffic limitations;entrance/exits of harbours and commercial areas.8 E.Appiani,M.Martelli,V.MascardiEach application has its own user interface,distributed configuration and database schema;however,they are all based on the“intelligent sensor”called LPR(Licence Plate Recognizer),a software component hosted in standard PCs equipped with framegrabbers linked to cameras.The relevant process,called“”(Out-door OCR),is applied to each camera’s videoflow,with no need for specific vehicle passing sensors.In fact,motion detection limits the number of relevant video frames;on each frame, image segmentation localizes the regions of interest;on each region,character segmen-tation detects the licence plate characters,if present;the specialized OCR recognizes them;finally,context processing provides feedback to region segmentation and camera set-up(such as adaptation to changing illumination).The specific application,which has been modeled by a MAS,implements the moni-toring of vehicles entering and exiting the service areas of a motorway section,between Salerno and Reggio Calabria in Italy,whose specific characteristics are heavy traffic in most days(being a main connection in south Italy)and toll-free transit,sometimes allowing vehicles to enter and exit the motorway at the service areas themselves.These peculiarities fostered,more than for other motorway sections,the need fortraffic monitoring with automatic alarm detection,this consisting in detection of sig-nalled vehicles,such as stolen or improperly used ones.In the rest of description,tran-sit defines a recognized car plate number with related time/place stamp and reference image(back side of the detected vehicle),black list is a list of signalled licence plate numbers and alarm is a transit whose licence plate matches an item in a black list.The configuration is distributed on a protected TCP/IP W AN,using both cables andsatellite links with limited bandwidth,and includes the following physical and software entities:–Executive Center(EC):client site of motorway management or Police,with oneor more client stations,allows to browse transits,get alarms,visualize vehicle im-ages,modify the black lists,and require database operations according to users’privileges;–Application Server:usually centralized on a server machine or server LAN,coor-dinates any communication with the Executive Centers and the Surveillance Areas (see below),dispatches alarms according to ECs’requests(black lists can be dif-ferent,so each EC must get just the alarms of interest)and manages the central transit/alarm database;–Surveillance Area(SA):hosts the peripheral intelligent sensors on one or morePCs in a LAN,located at a service station,gets video frames from the local cameras, generates transits and alarms by storing a local black list,sends transits and alarms to the Application Server.The communication topology is therefore star-like around the Application Server, with more ECs and SAs linked to it,as represented in Fig.2.Direct links between EC and sensors in SAs are just used for direct video monitoring,but this function usually employs different cameras and does not take part in the intelligent alarm system.Communication takes place by TCP/IP messages with dedicated session protocol. Current evolution is towards higher level,standard middleware such as CORBA be-tween Server and SA,CORBA or HTTP(Web-based clients)between EC and Server. The main messages between an EC and the Application Server are:A MAS Approach to Vehicle Monitoring in Motorway9Fig.2.Motorway Monitoring Application Architecture–requests to inquiry/browse/modify the transit database,with related answers;–requests to inquiry/browse/modify the black lists(signalled)database,with related answers.The black lists can be specific of each EC,and each signalled licence plate number can be limited to a subset of SAs;–incoming alarms requesting attention by operators;while the main messages between the Application Server and the SAs are:–requests to update each SA’s local black lists.In fact,this allows for fast alarm detection directly by SAs,while the Server takes care of dispatching alarms to the right ECs;–incoming transit lists;–incoming alarms.Data allocation(for instance,whether to centralize the database of transits or keep it distributed on SAs)and communication strategies had to be modeled in advance,in order to take the best solutions before achieving physical implementation on the real W AN.Besides,modeling each entity’s behavior was needed to pre-test the entire mes-sage exchange system against coherence,deadlock absence and performance.To this objectives,application prototyping by means of CaseLP proved to be very effective, as described in the next section.A careful work was made to make the specification as modular and extensible as possible,keeping into account the possibility to have more application servers managing and exchanging information coming from different mo-torway tracks.10 E.Appiani,M.Martelli,V.Mascardi4Realization of the Prototype in CaseLPIn this section we exemplify how some of the tools described in Section2.2have been used in the various steps of the method.As already said,not all the languages provided by the CaseLP environment have been used for this application.The aim of CaseLP is to let the developer choose the most suitable and useful languages according to the application features.Static description of the application architecture.As introduced in Section3,three classes of agents have been identified for this application:the executive center(EC),the surveillance area(SA)and the common server(EC SERVER),called Application Server in the previous section.One of the reasons for developing a working prototype was to understand whether it was better to maintain a distributed database of monitored transits(different databases should be maintained by the surveillance areas,each one containing information on the transits occurred in that specific area)or a centralized one(maintained by the EC SERVER,and containing all the transits occurred in all the surveillance areas).The static descriptions in the centralized and distributed settings are almost the same,there are only small differences concerning the monitored transits of number-plates.In case of a centralized solution,the surveillance areas asynchronously send an update of transits to the EC SERVER.The frequency of this update is parametric, and different experiments have been done in order to choose the best one.In this case, when an EC needs informations on transits,it just interacts with the EC SERVER which provides the answer.If the databases are distributed,the surveillance areas do not send any information on transits to the EC SERVER;when an EC asks the EC SERVER for obtain-ing information on transits,this query is forwarded to the SAs involved in the query, and the answers are combined into a unique answer sent to the EC.In the rest of the section,we deal with the MAS specification for the centralized solution of the transit database.The specification in the distributed case is quite similar. agentclass EC_SA_SERVER{kind:logical;architecture:reactive;requires:update_plate_trans;update_wanted_plate;alarm_wanted_plate;provides:alarm_wanted_plate;wanted_plate;update_wanted_plate;plate_trans;}agentclass EC{kind:logical;architecture:reactive;requires:plate_trans;wanted_plate;alarm_wanted_plate;provides:update_wanted_plate;}agentclass SA{kind:logical;architecture:reactive;。

A Multi-Agent System Frame Model for Dynamic IntegrationYingqiang Wang, Qingshan Li, Chenguang Zhao, Hua XingSoftware Engineering Institute, XiDian Univ., Xi’an, 710071apriliner@, qshli@AbstractSince low flexibility and non-dynamic problems exit in the process of software system integration, a Multi-Agent System frame model which introduces the agent techniques into system integration domain is proposed for problem solving. Based on the MAS frame model, independent software units are wrapped to agents, and their integration logic is described by the script language. Through explaining the file, the collaboration of multi-agent is under control. Dialogue Expansion Contract Net Protocol is used for the cooperation when agent cannot solve problems by itself. In order to achieve the aim of flexible and dynamic integration, new wrapped agents can be added into MAS dynamically and the edited script can be explained by the parser. Finally, the Agent-based System Integration Tools is built upon this frame model, and an application of this model about the Border and Coast Defense System is presented, which verifies the rationality, feasibility and efficiency.Keywords: Software integration, integration control agent, multi-agent system frame model, dialogue expansion contract net protocol, script controlling strategy1. IntroductionAt present, most distribution software systems consist of many modules. These modules often have the properties of the entity autonomy, geographical dispersion, and interaction among members that demand flexibility in a changing environment. In addition, the integrated systems have the requirement of dynamic integration. All these factors increase the difficulty of the integration and lessen the integration effect.The traditional way to solve these problems is developing them in the format of components. However, due to the weakness of autonomy, intelligence, dynamic expansion towards different domains, the traditional component models and assembly mechanism have no capability to integrate the modules in an intelligent and dynamic way. Although the application integration based on WebService solves the problem of the interconnecting among different platforms and various services, it neither works well in the single computer applications nor the isomorphism LAN procedure.With the properties of bounded autonomy, rationality, sociability, reactivity, cooperation, and responsibility, agent is quite suitable for the software integration. The studies of multi-agent develop quickly in recent years. The multi-agent techniques have been applied to the network, robot system, traffic control system as well as computer simulation fields. A lot of knowledge and experience are accumulated owing to the researches and applications.Many researchers and organizations do research in different aspect upon the foundations of FIPA (the Foundation for Intelligent Physical Agents) [1]. Min-Jung Yoo proposed a concept of agent-oriented software integration [2]. A MAPWeb model was discussed by David Camacho [3], which solved the traffic and accommodation problems by integrating the services on the web. Rinkesh J. Patelg and other researchers developed RADE (Role-based Agent Development Environment), which allowed users adding or removing agent during the working process [4]. However, research by David did not consider the requirement of the C/S architecture system. Rinkesh did not extend the result to the field of negotiation and interaction between agents. Min-Jung Yoo’s research was based on WebService.A widely used coordination mechanism in MAS is the well-known Contract Net Protocol (CNP) [5] proposed by Reid G. Smith and Randall Davis in 1980, which is one of the classical negotiation protocols in distributed artificial intelligence area. However, in the actual application, it is hard for the manager to selects an agent as the successful bidder, because of the incomprehension of the task execution experience, other’s status and task difficulty.The 9th International Conference for Young Computer ScientistsIn this model, the traditional CNP is expanded to Dialogue Expansion Contract Net Protocol (DECNP), and the script controlling strategy is applied to system integration too. It has been tested with the Border and Coast Defense Simulation System. Compared with traditional method, it solves the information isolation and un-interactive problems effectively in the military command and control system.2. The MAS frame model for dynamicintegration2.1. The conceptual model of agentAmong the mature agent models, one architectureviews the system as a rational agent having certainmental attitudes of Belief, Desire and Intention (BDI),representing, respectively, the information,motivational, and deliberative states of agent [5]. It notonly contains the thought attribute of the multi-agent,but also describes the mutual relationships of agents.Considering the software integration requirement, themodel shown in Figure 1 is expanded from the BDI.Figure 1. The conceptual model of agentIn this model, agent apperceives the environmental variation (including acquaintances and collaborations of agents) through the sensor . The Event Handler and the Inference Engine are the core modules. The former one analyzes and processes the received messages, and decomposes task to subtasks; the latter infers and makes decisions according to the agent knowledge, invoking the COM component which is packed from integrated system unit. These COM modules form Agent Capability Base , acting for the units. With the support of the Event Handler and the Inference Engine , the agent takes action on the external environment through the Effector . The Autonomous Thread provides autonomy management for the agent.Agent in this paper has following characters:Agent : Agent provides the function proxy for the original software unit.Unity : Agent communicates with the exterior through the unified interface by shielding the specific differences between the software units.Sensation : Agent can apperceive external environment changes, which consist of the MAS members’ structure, acquaintance agent information, and consultation content.Independency : Agent registers to the service agent automatically and completes the task independently. Cooperation : Many agents cooperate to complete the task in MAS. When an agent is unable to completeit by itself, it will cooperate with other agents throughDECNP which is realized with the help of the MessageBlackboard described in 2.2.Agent has 4 states: Dead , Idle , Running andWaiting . The transition between Dead and Idle iscaused by the action of registration or deregistration. Ifthere needs some cooperation with other agents, theagent shifts to Waiting from Running .Agent life cycle plays an important role in the agentapplication. This paper manages agent life cycle by theAMS (Agent Management Service). 2.2. The MAS frame modelBefore applying MAS to system integration domain, there has some analysis work to do. In this domain analysis, we refine a service process model of the domain as well as the integration workflow. The integration logic doesn’t bind to concrete unit but the agent set which has a corresponding ability.The domain analyses abstract the service of the integrated from the system workflow. Hence the flow model, which is irrelevant with the service, can be used generally. Additionally, each service flow node can match the appropriate service by distribution cooperation with intelligent property.A single agent can not run without multi-agent frame platform. The MAS frame model which supports dynamic integration in this paper is showed in the Figure 2. MAS consists of agents which distribute in different areas. With the assistance of this frame structure, a number of executable programs can be integrated with dynamic link libraries from different systems. Besides the original interface provided to the users, the frame model also provides two other interfaces. One is integration development interface used for unit wrapping and the domain analysis. The other is the user’s management interface used to watch and manage each agent and information in MAS. Users can wrap software units, domain analyses and edit the integration script by these interfaces. They can also usethem to monitor and manage agent states and systemdynamic information.Figure 2. MAS model for dynamic integration The MAS frame model is formally defined as follows:MAS =<AgentBase , SvrAgent , CtrAgent , Blackboard , MTS >.·MTS (Message Transport Service) implements the MTS of FIPA standards, it routes messages to each module in the frame.·AgentBase =<Agent 1, Agent 2, …Agent m ,…>. As a physical organization for agent storage, AgentBase permits agent to join and leave the organization. It apperceives the joint intention of agents, and absorbs them to be members. Agent is also assisted by AgentBase to obey the rules of agent in the MAS, such as registration flow. Agent i works as its member.·Agent =<S , R >. S indicates agent own function. In this paper, it is implemented by the COM module. R is the collaboration relationships between agents.·SvrAgent =<CRC , AMS >. SvrAgent is a special kind of agents which supports each agent working and interacting in the frame model, including CRC (Capability Register Center, a yellow page service which holds the ability and address of each agent) and AMS (Agent Management Service, managing agent lifecycle).·CtrAgent is also a special kind of agent which gains user’s integration logic, it controls the flexibility of all agents.·Blackboard holds the cooperation information of agents, referring to bids mainly in the system.·Task =<T 1, T 2,…T n , Seq >. T i indicates some sub-tasks which are decomposed from the MAS Task. Seq is the cooperation order and the cooperation flow among T i .·T i =<Cap 1, Cap 2,…Cap k >. Cap i is the sub-ability which accomplishes the sub-task of agent.After system domain analysis, the integration logic and unit are not coupled tightly. This kind of relationship enables MAS to assign the service flownode to the agent dynamically for fulfilling the task through their cooperation.2.3. Workflow of MAS frame modelFigure 3 illustrates the typical application flow when the MAS platform is running. Step ○1○2○3establish the status of agent in MAS. CtrAgent distributes task T to Agent j according the script content in step ○4. The task T is decomposed and finished byAgent j in step ○5and ○6. Agent j cooperates with Agent i in ○7○8○9○10.Figure 3. The sequence diagram of MASSupported by MAS, Each agent presents the independence and intelligence and cooperates with other agents till the whole MAS system platform realizes the purpose of software integration. In order to work effectively in MAS, agent must register to MAS before CtrAgent distributing the task T correctly. If Agent j completes the task T i distributed, it will submit to CtrAgent . Otherwise, it cooperates with Agent i for T j . This paper proposes a collaboration process between agents based on the Blackboard model. As a data share space, the Blackboard enables every agent gaining other agents’ real-time information by the process of bidding.3. Frame model analysisAs an intelligent entity, each agent can solve problems by itself for own purpose. However, agent needs the cooperation with others in MAS. It becomes a problem when the number of agents increases upon a scale. The system based on this model has not only centralization control, but also distribution collaboration.3.1. Dialogue Expansion Contract Net ProtocolIn DECNP, the Blackboard is used as a shared work space for problem solving. Any agent in the system can put its tasks on the Blackboard, as while as obtain useful information to solve own tasks. Besides, with the monitoring mechanism, each agent in the system can share part solutions among each level on the Blackboard model. In a word, the Blackboard model is very suitable for solving the problems which are not determined beforehand.The cooperation process of the Dialogue Expansion Contract Net Protocol is described as follows. (Cooperation is used for representing the cooperation strategy. In this phrase, agents will decide whether to tender and how to cooperate with the tenderee according to its capability and external circumstance. Different strategies of cooperation model are available in real applications.)(1)Agent i encapsulates the unfinished task T to atender, and sends it to the Blackboard.(2)When the tender arrives at the Blackboard, it willbe sent to those agents who are requesting tendersand have authority to obtain the tender.(3)Receiving the tender, agents will decide whetherto bid or not in terms of their Cooperationstrategy. If the agent has the intent to bid, it willsend a message to Agent i for tender, otherwise it eliminates the tender.(4)If Agent i doesn’t receive any message from agentsat the bidding deadline, it will send the tender again or re-plan the task.(5)Agent i negotiates with the agents who take part inthe bidding until it chooses the bidding off Agent jfor the task. Then the contract is assigned betweenAgent i and Agent j. If Agent j starts to execute the task, it will respond with commission. If Agent jwants to cooperate with Agent i to complete the task together, the responding will be cooperation.If Agent j requests Agent i to replan, it will send a message with the identifiers of replaning. The performatives such as done, which denotes that theresponder has finished the task, and refuse, whichdenotes that the responder refuses to execute the task, are also used in this protocol.The DECNP offers a kind of universal interacting language for agents to communicate with. By this language, different agents do not need to communicate several times for solving s single problem. Therefore it is possible for the MAS frame model to represent several kinds of communication information without depressing the flexibility of each agent, and the information sharing is enhanced among agents, also the interaction efficiency is improved. 3.2. The strategy of parsing scriptThe strategy of parsing script is applied to the multi-agent interaction for the flexible and dynamic integration. We implement this script language and the Visual Editing Tool. This mechanism of controlling multi-agent by the strategy is as follows.(1)The Visual Editing Tool transfers the integrationlogic workflow to script file Scr. CtrAgent parsesthis file to gain TaskTree and CapTree with the size of M and N;(2)CtrAgent requests CRC for the proper AID i bytraversing CapTree, and the result is kept in AIDSet;(3)CtrAgent requests task T i for AID i by traversingTaskTree;(4)After gaining T i information, Agent i solves it in theway described in 3.1. At the end, the result is returned to CtrAgent;(5)In terms of the structure of CapTree, CtrAgentrequests next task for proper Agent j with the response of T i.(6)Repeat this process to finish the whole script.The time and space complexity of this process are both at the lever of M or N. CtrAgent executes the tasks in sequence, i.e., it explains the task one by one till all tasks are finished. In the restricting period, the cooperation is aborted if the explanation of the script is failed. The collaboration procedure will be finished at a stated time with a result success or unsuccess, so CtrAgent will not be waiting eternally.3.3. Cooperation of multi-agentsCooperation and collaboration between agents are always the key point in the research of MAS. The interactive relationships in this paper consist of followings.1) There are agent name, physical address, BDI, initial parameters and the acquaintance information in the agent definition. The acquaintance is a kind of agent that has direct relationship or common interests with others. After registering to SvrAgent, the agent will execute task independently. If it can not do it completely, it may ask acquaintance agent for help. Therefore, this method improves the efficiency evidently.2) Bidding will get to work if the agent finds no acquaintance in its acquaintance base. Subtask will upload to the Blackboard as a bid, which can be completed by other agents. When bidding time is exhaust, this agent will filter the best bid off agent to cooperate with. After this, that cooperated agentbecomes an acquaintance of the former. This process is accomplished by agents independently.3) With the purpose of controlling agent cooperation, the script is used to describe the integration logic of the software in this paper. The script contains Task , T i , Cap i and Seq (described in 2.2). When the script is explained, CtrAgent will look up in SvrAgent for proper agents. These agents will be invoked for T i by the sequence of Seq . This is the general way for the agent interaction.3.4. The dynamic character of MAS frame modelThe dynamic character of MAS includes:1) Agent can be added into or removed from AgentBase when MAS is running. Agent does not have a fixed social relationship in MAS. Any agent which does not work can be removed away. If there are new agents having higher efficiency with less cost, they can also be added in present multi-agent organization. This MAS frame model supports this modification by takingmeasures.Figure 4. Dynamic integration of MAS2) Parsing script is the general way to control units. When integrating the original system for the first time, the service workflow model is refined to separate the independent module into agents. Then, the service node is assigned to proper agent sets by the definition of integration logic. CtrAgent accomplishes the object of integration according to task decomposing status. If there is a new requirement, CtrAgent should redefine the workflow model for the new purpose. This procedure is revealed in Figure 4.4. A Case-study: Integration of the Border and Coast Defense Simulation SystemBased on the agent and MAS frame model, we developed the Agent-based System Integration Tools (ASIT). An application of MAS model in the Border and Coast Defense Simulation System is presented to confirm the rationality and feasibility of this framemodel. BCDSS is composed of 8 subsystems. Each subsystem is wrapped by 1 to 3 agents which have their own capabilities to finish tasks.4.1. Dynamic integrationDue to the process of analysis described in section 2.2, the main workflow of BCDSS is as follows: the data collected by Radar Source Subsystem are transmitted to Message-Handler Subsystem through Gathering Subsystem. Message-Handler Subsystem invokes the Radar Handler module before keeping on transmitting data to Show Subsystem. After modeling, 12 agents and 4 service agents are wrapped by Agent Wrapping Tool in ASIT. After adding them in MAS, CtrAgent parses the script, distributes the subtask and gains the purpose of integration.Figure 5. Script workflow definitionThe following work was made to verify how this MAS model supported the dynamic integration. In the running system, Infrared Source would add into the system. Under this condition, Infrared Source module was wrapped to InfraredSourceAgent, and the workflow was redefined to form a new workflow script, as shown in Figure 5.With the purpose of dynamic integration, InfraredSourceAgent enrolled in MAS, and the new script was parsed after the old script stopped. As a result, the infrared data revealed in the window, which validated that this MAS frame model could support the software dynamic integration.4.2. The efficiency analysis of static integrationThe efficiency of tasks finished by agents in BCDSS is calculated by the ratio of quality to time. In this case, we just calculate the efficiency of tasks finished successfully, i.e., the quality is 1 and the efficiency is the reciprocal of time. In this test, the number of task is ranged from 5 to 30. Compared to non-integration by this MAS model(N-MAS), theNew ModuleWorkflowefficiency of tasks in the frame model of MAS isdenoted in Figure 6.Figure 6. The efficiency of static integration This result presents that, when fulfilling the same task, N-MAS needs more time than MAS. Besides, N-MAS requires more increment time than MAS when the number of tasks increases.4.3. The efficiency analysis of dynamic integrationA dynamic integration is also tested in this paper. We choose a consecutive section during which the N-MAS system and the MAS system running steadily for 30mins. The infrared source module adds to both the system at 15min. the number of completed tasks per minute is shown in Figure 7.The figure illustrates that the original system must be stopped to do some modification or re-configuration for the new adding module, hence the number of tasks is about 0 around 15m. By contraries, the MAS model system keeps the same task efficiency, which proves that this MAS model can support the dynamicintegration effectively.Figure 7. The efficiency of dynamic integration5. ConclusionsThis paper introduces agent techniques into software system integration because of the advantage of agent. Wrapping the software units to agents, the software integrated by this MAS frame model is intelligent. The interaction among units is described byscript, which is abstracted from system workflow. Therefore, the aim of dynamic integration can be achieved by explaining the new script. The Multi-Agent System Frame Model for Dynamic Integration is tested finally to verify its rationality and validity.AcknowledgmentsThis work was supported by the Defence Pre-Research Project of the ‘Eleventh Five-Year-Plan’ of China under contract number 513060401.References ：[1] Document OC00019 - Agent Management, FIPA 97 Version 2.0 Part 1. [2] Yoo, Min-Jung. Enterprise application integration and agent-oriented software integration Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics , 2004, p 2119-2124[3] Camacho David, Aler Ricardo, Borrajo Daniel, Molina Jose M. A Multi-Agent architecture for intelligent gathering systems. AI Communications , v 18, n 1, 2005, p 15-32[4] Rinkesh J. Patel. Developing Role-Based Open Multi-Agent. International Journal of Computational Intelligence Theory and Practice . Vol. 2, No. 1, June 2007, p39-56.[5] A.S. Rao, M.P. Georgeff, “BDI agents: From theory to practice”, In: M P Georgeffed. Proc of the 1 st Int’ l Conf on Multi-agent Systems . San Francisco: ACM Press, 1995, pp.312-319.[6] Rao A S. AgentSpeak(L): BDI Agents Speak Out in a Logical Computable Language. 7th European Workshop on Modelling Autonomous Agents in a Multi-Agent World , MAAMAW’96, Berlin: Springer, 1996, pp. 42-55[7] FACTS - FIPA Agent Communication Technologies and Services, ACTS Project AC317. /profsoc/facts/[8] FIPA-NET. /fipanet[9] H. Xu and S. M. Shatz, “A Framework for Model-Based Design of Agent-Oriented Software,” IEEE Transactions on Software Engineering (IEEE TSE), January 2003, Vol. 29, No. 1, pp. 15-30.[10] Kang Xiao-Qiang SHIC hun-Y, Multi-Agent Interaction Based on BDI. Chinese Journal of Computers . 1999, 22(11): pp. 1166-1171.。

Stability∗of Multi-Agent Systems†Maria Chli,Philippe De Wilde‡,Jan Goossenaerts,Vladimir Abramov,Nick Szirbik§,Luis Correia,Pedro Mariano,Rita Ribeiro¶Abstract–This work attempts to shed light to the fundamental concepts behind the stability of Multi-Agent Systems.We view the system as a discrete time Markov chain with a potentially unknown transitional probability distribution.The system will be considered to be stable when its state has converged to an equilibrium distribu-tion.Faced with the non-trivial task of establishing the convergence to such a distribution,we propose a hypoth-esis testing approach according to which we test whether the convergence of a particular system metric has oc-curred.We describe some artificial multi-agent ecosys-tems that were developed and we present results based on these systems which confirm that this approach qual-itatively agrees with our intuition.Keywords:Distributed systems,stability,games,de-cision making,equilibrium distribution.1IntroductionMulti-agent systems is a growingfield mainly because of the recent development of the Internet as a means of circulating information,goods and services.Many researchers have contributed valuable work in the area in the recent years.However what is still missing is a clear notion of the stability of multi-agent systems. The agents of a multi-agent system are computer pro-grams in a distributed environment that execute tasks on behalf of their human owners.These tasks often in-volve decision-making.Stability,understood intuitively as the property of a system that exhibits bounded be-haviour is perhaps the most desired feature in the sys-tems we design.It is important for us to be able to ∗Funded by IST-1999-10304†0-7803-7952-7/03/$17.00c 2003IEEE.‡Chli and De Wilde are with the Electrical and Electronic Engineering Department,Imperial College,London,UK.Email: {m.chli,p.dewilde}@§Goossenaerts,Abramov and Szirbik are with the Information and Technology Department,Tech-nical University of Eindhoven,Netherlands.Email: {j.b.m.goossenaerts,v.a.abramov,n.b.szirbik}@tm.tue.nl ¶Correia,Mariano and Ribeiro are with the Depart-ment of Informatics,New University of Lisbon,Portugal. Email:{luis.correia,pedro.mariano,rita.ribeiro}@di.fct.unl.pt predict the response of a multi-agent system to various environmental conditions prior to its actual deployment. This is why we believe that a clear mathematical defi-nition of the concept will allow us to develop tools and methods for its analysis.2BackgroundComputer scientists often talk[5,9]about stable or unstable systems without having a verifiable definition of stability.On the other hand,control engineers have a very well established definition[6],which however,is not suitable for multi-agent systems.This is mainly because the agents have to make decisions which is dif-ferent than changing the values of variables,performing arithmetical operations or differentiation and integra-tion.Similarly the widely accepted notion of stability, which comes from thefield of dynamical systems[8,4], is not appropriate for multi-agent systems either.This is because this definition is restricted for closed systems. Agents,as they act on behalf of humans,are not isolated from the real world.They constantly have to deal with new concepts and changing input.Similarly the defini-tion of stability in the context of population dynamics is not adequate[10].In thisfield the research concentrates on grouping agents into types and studying how popu-lations of different types evolve by looking at the size of the population.However,the agents may not always fall into classes,as they are independent individuals. We propose that considering agents as utility max-imising players who take decisions in a game,instead of computer programs,would be a more appropriate ap-proach that concentrates on the actions of the agents rather than implementation issues.In addition we want to account for systems that are as close to reality as pos-sible.In order to do this we have to cater for systems with a varying number of agents.This is the reason we work with ecosystems of agents.In an ecosystem,new agents can appear and existing agents can vanish.In this work we propose a definition of stability for multi-agent systems based on the stationary distribu-tion of a stochastic system.We provide simple example systems to illustrate this.3Markov Chains PrimerThis section presents a brief and by no means exhaus-tive introduction to the theory of Markov Chains which underlies the approach taken in this work to defining stability.More comprehensive introductions to Markov Chain theory and stochastic processes in general are available in[7]and[1].Definition:We say that(X n)n≥0is a Markov chain with initial distributionλ=(λi:i∈I)and transition matrix P=(p ij:i,j∈I)if:1.P r(X0=i0)=λi2.P r(X n+1=i n+1|X0=i0...X n=i n)=p ini n+1The crucial point is that a Markov process is mem-oryless,which means that the current state of the sys-tem is the only state that is required to describe its subsequent behaviour.We say that a Markov pro-cess X1,X2,···,X m has a stationary distribution if the probability distribution of X m becomes independent of time(m).We view a multi-agent system as a countable set of states I with implicitly defined transitions between them.At time n the state of the system is the random variable X n.3.1Definition of stabilityA system considered under the terms described above is said to be stable when the distribution of the state of the system converges into an equilibrium distribution. In other words when P r(X n=j)→πj as n→∞∀j∈I.Our definition can also be stated by:A stochas-tic process x1,x2,x3,x4,...is stable if,the probability distribution of x m becomes independent of the time in-dex m for large m.3.2Dealing with a varying number ofagentsWe want the definition of stability we propose to ap-ply to systems with a varying number of agents(ecosys-tems).The system state will be represented by an infi-nite vector X that has one or more elements for each agent and a number of elements to describe general properties of the system state that are not particular to any single agent.We model an agent being‘dead’by setting the vector elements for that agent to some predefined value(e.g.-1).4Example gamesA couple of example-‘toy’games we dealt with are given below.We will explain how our definition of sta-bility applies to them and then investigate how we deal with more complicated ones.4.1The3-player+/-gameThe three players of this game,can each be in one of two states‘+’or‘-’.If two players are in the same state the third goes into that state.If all three players are in the same state,there is probability0.9that they all remain in that state and probability0.1that they all change state.This game has eight states:(1)—, (2)–+,(3)-+-,(4)+–,(5)+-+,(6)-++,(7)++-,(8) +++.From the rules of the game we devise the state transi-tion probabilities.For example the probability of going to state8(+++)from state1(—)is0.1,the proba-bility of remaining in state8is0.9,the probability of going from state8to state7(++-)is1,or the one of going to state4(+–)from state6(-++)is0and so on. Thus we construct an8x8state transition matrix.It is shown in Table1.State Id1234567810.90000000.121000000031000000040000000050000000160000000170000000180.10000000.9 Table1:The transition matrix for a3-player+/-game We often refer to the transition matrix as P.Once we have this we can check whether an equilibrium distribu-tion exists or not by solving the following simultaneous equations forπ:πP=ππi=1If one or more solutions exist then the system is stable. In the case where only one solution exists,this solution will be the equilibrium distribution into which the sys-tem will converge.In the case where there exists more than one solution,this means that the system can con-verge into one of many stable solutions/distributions of states.It is uncertain in which one the system will fall, but as soon as it does it then remains into that one forever and this why we consider it stable.In this example we saw how we can devise state tran-sition probabilities from the rules of a game,which we formulated from a multi-agent system scenario.These transition probabilities allowed us to predict whether the system will eventually reach an equilibrium distri-bution or not,in other words whether the system is stable or not.4.2The simple random walkAn example of an unstable system is the simple ran-dom walk,where we start in state 0and at each time-step,if we are in state K ,we go either to state K +1or to state K −1with equal probabilities.It can be shown that the distribution of the state X m ,where m is the time,is centred on zero but its variance is proportional to √m which means that the p.d.f.is not independent of m .4.3A coin gameIn another slightly more complicated game,N players toss a coin in pairs.The loser gives to the winner a unit of its wealth.Players are destroyed if their wealth is below 1and can generate another player if their wealth is more than 4.The sum of all players’wealth should be 6.If we try out this game with three players we realise that its state space consists of 19states.Solving the sys-tem of simultaneous equations shown above we conclude that it has an equilibrium distribution.It is remarkable however;the fact that such a simple game,with so few players has so many states.The number of states rises tremendously as we increase the number of players and adjust the wealth in the system accordingly.For exam-ple,if we try the same game with four players instead of three we will be presented with a state space of around 70states.At least theoretically one could evaluate the transi-tion probabilities of the multi-agent system and through a simple eigenvalue analysis find its equilibrium distri-bution,if it exists.In practice due to the state space explosion problem in real multi-agent systems,this ap-proach is not viable.We therefore propose statistical analysis as a means of testing for the probabilistic be-haviour of more complex multi-agent systems.Multi-agent systems are often used to analyse prob-lems such as trading in a stock exchange or transporta-tion problems.This type of situations can easily be for-mulated as games and their stability can be analysed in the way we propose.In the next section we show how we formulated a trading scenario and a loads transportation scenario as games and comprehensively analysed their stability.We also present the results we obtained from extensive simulations and statistical analysis.5ExperimentsWe worked on various different models we developed in Java,in order to test and experiment with our defi-nition of stability.As these models are somewhat more complicated than the simple games we saw in the previous section we do not go about finding out the state space of each one of them.Their state spaces are probably quite large.What we do instead is to check that several indicativemetrics do reach a stationary distribution after the sys-tem has been left to run for a while.5.1Trading Simulation Model5.1.1ScenarioInitial setting There is an array of N different re-sources in this model.There are M traders each with its capital,its discounting percentage and its available re-sources.All traders are endowed with the same amount of wealth;the amount of each resource given to each trader is randomly calculated.A discounting percent-age is used when the trader recalculates its prices.Fi-nally,the scenario involves tasks that are generated by agents.A task requires some resources and produces some others.At each clock tick every trader with its turn issues a task and advertises it amongst the other traders.Each task carries a random combination of required and pro-duced resources.Every trader gives an offer for the task (provided that they possess the required resources).The cheapest offer is selected.If the issuer cannot pay for any offer then the task is not executed.Otherwise,it selects an offer and the task is executed.The required resources are subtracted from the task executor’s set of resources,the produced resources are added to the is-suer’s set of resources and the issuer pays to the executor an amount of money equal to the price for executing the task.Finally each trader recalculates its prices accord-ing to its discounting percentage and whether its offer was accepted or not.Generation and Destruction of agents When a trader is sufficiently rich,i.e.its wealth exceeds a cer-tain threshold;it generates a new trader to which it gives half its wealth.Also,the parent trader endows the child trader with half of its resources.The new trader inherits its generator’s discounting factor.When a trader’s wealth goes below zero then it is destroyed.5.1.2Stability ConditionsIn order to consider the system stable,its state must reach a stationary distribution when it has been left to run for a while.Strong indications of stability would be that metrics such as the proportion of traders that execute tasks,the number of traders,the prices of he resources,the wealth per trader would all reach station-ary distributions when the system has been left to run for a while.5.1.3ExperimentsIn order to explore the entire parameter space we per-formed an extensive and exhaustive set of experiments,for as many combinations of initial parameter values and perturbation sizes as possible.The parameter values we varied for this model were the discounting factor’s,prices’and resources’order of magnitude and the initial,generation and destruction wealth for the traders.An unstable system We performed an experiment with 50traders,10different types of resources.The simulation was left running for 104time ticks.Each trader is endowed with 106monetary units and a ran-dom amount of each of the 10resources.The amount from each resource it gets is of the order of 103(calcu-lated randomly).The resources’prices are initially of the order of 100monetary units (calculated randomly).The discounting factor’s initial order of magnitude is 10−3.A trader can generate a new trader if its wealth exceeds 1.5×106and it dies if its wealth goes below 0.In Fig.1we show how the ratio Tasks per Trader varies throughout time.However,the graph is not enough to demonstrate stability of the system;this is why we used statistical analysis.20004000600080001000000.10.20.30.40.50.60.70.80.91Time TickT a s k s /T r a d e rFigure 1:TRADE UNSTABLE:Tasks per Trader Our aim was to show that after the system has been left to run for some time,the metrics mentioned above reach a stationary distribution.We utilised statistical hypothesis testing which indicates whether two samples come from the same distribution to establish if this was the case.More specifically we used t-test for the equality of the means and F-test for the equality of the variances.For in-depth information on these tests one can refer to any statistics textbook such as [3,2].The tests showed that when the model is run with these initial conditions results in an unstable system.A stable system If we re-run the above experiment with the same initial parameters,only changing the dis-counting factor’s initial order of magnitude from 10−3to 10−13and the prices’initial order of magnitude from 103to 104the system’s behaviour is significantly differ-ent.We can see from Fig.2that the system looks much more stable than it did before.We performed the hy-pothesis tests for each metric as described above.We saw that for all of them there was significant evidence in the 5%significance level the metrics reached a station-ary distribution.Therefore the system is stable when run with those specific initial conditions.Perturbations It would be interesting to find out how the system responds when we disturb its normal running by introducing a perturbation.0.10.20.30.40.50.60.70.80.91Time TickT a s k s /T r a d e rFigure 2:TRADE STABLE:Tasks per Trader We started an experiment with the same initial condi-tions as the first one we described (which was unstable).However,this time we injected a shock into the system.At time tick 4000,the prices of all the resources of each trader are increased arbitrarily by 500%.We then al-lowed the simulation to run until time tick 106and ob-served the results.Fig.3shows how the ratio of tasks per trader varies for this experiment.2000400060008000100000.10.20.30.40.50.60.70.80.91Time TickT a s k s /T r a d e rFigure 3:TRADE PERT 1:Tasks per Trader (before and after the shock)The tasks per trader ratio seems to follow a much more stable trend after recovering from the shock at time tick 4000.When we perform statistical testing we notice that at the 5%significance level there is signifi-cant evidence that the values for the metric tasks exe-cuted per trader after the shock come from a common distribution.In general,the system after the shock is stable and the effect of the shock is noticeable.In another experiment the system was started with the same initial parameters as the stable system shown above.0.10.20.30.40.50.60.70.80.91Time TickT a s k s /T r a d e rFigure 4:TRADE PERT 2:Tasks per Trader (before and after the shock)At time tick 4000the following shock was injected into the system.The wealth of each trader was increased by 60%.Fig.4shows that the effect of the perturbation was quite significant.We showed,once more using hy-pothesis testing at the5%significance level,that there is evidence that after the recovery from the perturbation the values of this metric belong to a common distribu-tion,i.e.the metric is stable after it recovers from the shock.In general the system after the substantial effect of the perturbation has more or less elapsed goes into a stable phase.5.2Loads’Transportation Model5.2.1ScenarioInitial setting We define a number N of cities and a map of interconnections between these cities.Some cities are directly connected to each other while some others are not.The distance between two cities that are directly connected takes one day to travel.For example, if the cities A and B are connected via city C(i.e.:A →C→B),it takes two days to travel from A to B. The simulation operates with a granularity of one day.A number of M lorries travel around the map each of them being at a city at any particular day.0up to M lorries can be at city at a time.Loads are generated at a certain rate at each city and have a specific city as a destination e.g.a load can be generated at city A and be destined for city B.Each lorry can carry up to K loads,from which it earns rewards.Rewards are added to the lorry’s wealth.Load Allocation and Distribution The loads lo-cated at a city are allocated to the lorries present at that city randomly.A lorry has an algorithm which de-cides the route it will follow based on information such as the city it currently is in and the destinations of the loads it carries.Every D number of days the lorries are required to reduce their wealth by a certain amount. This is a form of taxation.Generation and Destruction of Agents When a lorry’s wealth exceeds a certain threshold,it generates a new lorry at the city it currently is and endows it with half its wealth.When a lorry’s wealth is below a certain threshold then it is destroyed.5.2.2Stability ConditionsAccording to our definition of stability the system will be considered stable if its metrics show evidence that they reach a distribution after some time the system has been running and remain in this distribution for-ever.The proportion of lorries that carry loads,the proportion of loads that have been carried,the loads carried per lorry,the wealth per lorry,the number of lorries are the metrics we observe to decide on whether the system is stable or not.5.2.3ExperimentsAn unstable system We performed an experiment with100lorries and a network of500cities connected to each other with a connectivity percentage of40% between the cities of the network.The simulation was left running for20000time ticks.Each lorry is endowed with10monetary units.The maximum capacity of a lorry is3loads.A lorry can generate a new agent if its wealth exceeds50and it is destroyed if its wealth goes below0.Tax equal to2monetary units is deducted every5time ticks.A new load is generated in each city every3time ticks.The maximum number of loads that can be waiting in a city at any time is5.x 1040.080.10.120.140.160.180.2CarriedLoads/AllLoadsTime TickFigure5:LOAD UNSTABLE:Carried Loads RatioThe graph in Fig.5shows how the carried loads ratio varies with time.Hypothesis testing at the5%signifi-cance level showed that there is significant evidence that the system is unstable when run under those initial con-ditions.A stable system In an attempt to make the system more stable we run it again,performing another exper-iment.We keep the initial conditions mostly the same as they were for the previous experiment.However, this time we change the intercity connectivity percent-age from40%to90%.Fig.6shows the behaviour of the carried loads ratio for this experiment.x 1040.020.040.060.080.10.120.140.16Time TickCarriedLoads/AllLoadsFigure6:LOAD STABLE:Carried Loads RatioThe graph depicts a fairly stable system.This is also the evidence we get when we perform statistical testing on the metrics ratio of working lorries,carried loads, loads per lorry,wealth per lorry.Perturbations In an attempt to challenge the be-haviour of the system when something unexpected hap-pens we introduce perturbations.It is interesting to see what their effect is,if any,and whether it is justifiable. During this experiment we inject a shock into the sys-tem.The initial conditions are the same as those for the previous experiment where the system was stable.Thistime,at time tick 4000,we increase the minimum wealth a lorry has to have in order to be able to generate a new lorry from 50to 5×107monetary units,keeping all other parameters the same.0.511.52x 1040.020.040.060.080.10.120.14Time TickC a r r i e d L o a d s /A l l L o a d sFigure 7:LOAD PERT 1:Carried Loads Ratio (before and after the shock)This perturbation will naturally cause the frequency of new lorry generation to decrease.Due to the de-crease in the number of lorries,there are more jobs for the remaining lorries to carry out;therefore the work-ing lorries ratio increases dramatically,as is the wealth per lorry and the loads per lorry ratio.However,the re-maining lorries do not seem to be enough to cope with the number of loads that are generated in the system therefore the carried loads ratio drops after the shock occurs.We know from the previous experiment that the sys-tem is stable under those specific initial conditions.It is evident from the graph in Fig.7that the system is driven to instability after the shock is injected.This is a case where a perturbation causes a stable system to become unstable.In another experiment we performed we saw that it is possible the opposite can happen,i.e.an unstable system can become stable after it has un-dergone a perturbation.This simulation was started with the same initial pa-rameters as the experiment for the unstable system we showed above.We injected a shock at time tick 4000,which was to decrease the maximum number of loads in each city by 80%.0.51 1.52x 10400.050.10.150.20.250.30.35Time TickC a r r i e d L o a d s /A l l L o a d sFigure 8:LOAD PERT 2:Carried Loads Ratio (before and after the shock)As there are now less loads in the network of cities,there are less jobs for the lorries,hence the popula-tion decreases.Consequently,the remaining lorries have greater workload.The working lorries ratio increases.The system seems to work much more efficiently after the injection of the shock,as the carried loads ratio isboosted from 15%to 30%.In addition to all these,hypothesis testing confirms that after the system has recovered from the shock the metrics we examine fall in stationary distributions.Therefore,we can deduce that there is significant evidence that after a small transient phase the system is stable.6ConclusionThis has been a study of the concept of stability of ecosystems.We began by evaluating definitions of sta-bility that already existed in well-established fields of mathematics.We then explained the reasons these defi-nitions are not suitable for application in the context of multi-agent systems and ecosystems.Subsequently,we proposed a definition of stability which is the only one which takes into account the game nature of multi-agent systems,is relevant to systems with a varying number of agents and is supported by the mathematical framework of stochastic systems.The study included the design and development of experimental multi-agent platforms which we analysed,with the intention of illustrating the validity of our def-inition.Moreover,we introduced statistical hypothesis testing as a means of applying our definition analyti-cally to quantify the stability of complex multi-agent systems.References[1] D.R.Cox and ler.The Theory of StochasticProcesses .Chapman and Hall,1972.[2]J.Crawshaw and J.Chambers.A Concise Course inAdvanced Level Statistics .Stanley Thornes Pub Ltd,2001.[3]R.A Fisher.Statistical methods for research workers,14th ed.Oliver and Boyd,1970.[4]N.Glance,Hogg T.,and puta-tional ecosystems in a changing environment.Intl.J.of Modern Physics ,C(2):735–753,1991.[5]Balakrishnan Hari and Srinivasan Seshan.Analyzingstability in wide-area network performance.ACM SIG-METRICS Conference on Measurement and Modeling of Computer Systems ,1997.[6]Hassan K.Khalil.Nonlinear Systems .Prentice Hall;2edition,1995.[7]J.R.Norris.Markov Chains .Cambridge UniversityPress,1997.[8]Lawrence Perko.Differential Equations and DynamicalSystems .Springer Verlag,2001.[9]J.D.Thomas and K.Sycara.Heterogeneity,stability,and efficiency in distributed systems.Proceedings of the 1998International Conference on Multi Agent Systems ,1998.[10]J.W.Weibull.Evolutionary Game Theory .MIT Press,1995.。

MIS简答题MIS简答题Chapter1SHORT-ANSWER QUESTIONS (p. 33)1.What is the relationship between management information systems (MIS)and information technology (IT)?ANSWER: MIS is a broad business function and the study of the use of IT.IT is a set of tools and a resource within MIS.2.What four steps should an organization follow in determining whichtechnologies to use?ANSWER: The four steps are: (1) assess the state of competition andindustry pressures, (2) determine business strategies, (3) identify important business processes, and (4) align technology tools with the businessprocesses.3.What is the relationship between data, information, business intelligence (BI),and knowledge?ANSWER: Each build on the previous. Data are raw facts, whileinformation is data that has meaning. Business intelligence is collectiveinformation that gives you the ability to make strategic business decisions.Finally, knowledge is a broad term that can encompass BI context, how toaffect BI, patents and trademarks, and organizational know-how.4.How does the granularity of information change as it moves from lower toupper organizational levels?ANSWER: At the lowest levels, information granularity is very finebecause people need tremendous detail to perform their jobs. Asinformation moves up through the organization, it becomes more coarsebecause people don’t need as much detail but rather aggregations ofinformation.5.What is the difference between a technology-literate knowledge worker andan information-literate knowledge worker?ANSWER: A technology-literate knowledge worker knows how and when to apply technology; that is, he/she understands the value and role oftechnology. An information-literate knowledge worker knows all aboutinformation; that is, he/she understands the value and role of information. 6.How do ethics differ from laws?ANSWER: Laws either clearly require or prohibit an action. Ethics are more subjective, more a matter of personal or cultural interpretation.7.What role does the Five Forces Model play?ANSWER: Porter’s Five Forces Model helps business people understand the relative attractiveness of an industry and the industry’s competitivepressures in terms of buyer power, supplier power, threat of substituteproducts or services, threat of new entrants, and rivalry among existingcompetitors.8.Why are competitive advantages never permanent?ANSWER: Once an organization creates a competitive advantage, allcompetitors move to offer similar or even better competitive advantages,thus nullifying the competitive advantage of the first organization.9.What are the three generic strategies according to Michael Porter?ANSWER: The three generic strategies according to Michael Porter are: overall cost leadership, differentiation, and focus.10.How are Porter’s three generic strategies, an above-the-line versus abelow-the-line approach, and the RGT framework similar?ANSWER: They are similar as follows: (1) run = overall cost leadership = bottom line, (2) grow = focus and differentiation = top line, and (3)transform = (new) differentiation = top line (when the focus is innovation). 11.What is the role of value-chain analysis?ANSWER: Value-chain analysis is a systematic approach to assessing and improving the value of business processes within your organization tofurther increase it competitive strengths. So, value-chain analysis helps you identify important business processes and how technology might helpsupport them.Chapter2SHORT-ANSWER QUESTIONS (p. 59)1.Why is the traditional buy-hold-sell inventory model an expensive andpotentially risky one?ANSWER: The traditional inventory model requires that (1) you create inventory without a known demand, (2) you keep a lot of inventorythroughout the supply chain, and (3) you sell off obsolete inventory at a very low price.2.What is the role of a supply chain management (SCM) system?ANSWER: The role of a supply chain management (SCM) system is tosupport supply chain management activities by automating the tracking of inventory and information among business processes and across companies.3.How does SCM fit into Porter’s three generic strategies?ANSWER: SCM is most commonly associated with the overall costleadership generic strategy.4.What are the typical functions in a CRM system?ANSWER: The typical functions in a CRM system include sales forceautomation, customer service and support, and marketing campaignmanagement and analysis.5.How does CRM fit into the RGT framework?ANSWER: CRM is most commonly associated with growing theorganization in the RGT framework.6.What is the difference between front office and back office systems?ANSWER: A front office system is the primary interface to a customer anda sales channel, while a back office system is used to fulfill and supportcustomer orders.7.For what five things does e-collaboration provide support?ANSWER: E-collaboration supports (1) work activities within integrated collaboration environments, (2) knowledge management with knowledgemanagement systems, (3) social networking with social networking systems,(4) learning with e-learning tools, and (5) informal collaboration to supportopen-source information.8.What is the difference between a social networking site and a socialnetworking system?ANSWER: A social networking site (e.g., Myspace) is a site on which you post information about yourself, create a network of friends, share content, and so on. A social networking system is an IT system that links you topeople you know and, from there, to people your contacts know.9.What is open-source information?ANSWER: Open-source information is content that is publicly available (ina broad sense), free of charge, and most often updateable by anyone.10.What are the three most common ways in which the IT function can beplaced within an organization?ANSWER: The three most common ways in which the IT functions can be placed are: top-down silo, matrix, and fully integrated.appears in another file. So, primary keys must be unique in a given relation while foreign keys do not have to be. They are the same in that both are used to enforce integrity constraints.1.What are the five software components of a database management system?ANSWER: The five important software components of a DBMS are (1) DBMS engine, (2) data definition subsystem, (3) data manipulation subsystem, (4) application generation subsystem, and (5) data administration subsystem.2.How are QBE tools and SQL similar? How are they different?ANSWER: QBE tools and SQL are similar in that they both give you the ability to create queries to find information in a database. They are different in that QBE tools provide a GUI interface while SQL requires that you create your query in statement form.3.What is a data warehouse? How does it differ from a database?ANSWER: The four types of information according to what information describes are internal, external, objective, and subjective.4.What are the four major types of data-mining tools?ANSWER: The four major types of data mining tools are intelligent agents, query-and-reporting tools, multidimensional analysis tools, and statistical tools.5.What is a data mart? How is it similar to a data warehouse?ANSWER: A data mart is a subset of a data warehouse in which only a focused portion of the data warehoused information is kept.Chapter4SHORT-ANSWER QUESTIONS (p. 123)6.What are the four types of decision discussed in this chapter? Give anexample of each.ANSWER: Nonrecurring, or ad hoc, decision is one that you make infrequently (perhaps only once) and you may even have different criteria for determining the best solution each time. A merger with another company is an example. Recurring decisions are decisions that you have to make repeatedly and often periodically, whether weekly, monthly, quarterly, or yearly. An example would be which route to take to go to work.Nonstructured decision is a decision for which there may be several “right”answers and there is no precise way to get a right answer. An example would be whether to change a company’s strategy. Structured decision is a decision where processing a certain kind of information in a specified way so that youwill always get the right answer. An example would be deciding how much to pay employees. p. 957.What are the four steps in making a decision?ANSWER: The four steps are intelligence, design, choice, and implementation. p. 968.What is a DSS? Describe its components.?ANSWER: A decision support system (DSS)is a highly flexible and interactive IT system that is designed to support decision making when the problem is not structured. The components of a decision support system are the model management component, the data management component, and the user interface management component. p. 989.What is a geographic information system used for?ANSWER: A geographic information system is used for any type of information that can be represented spatially. p. 10310.How is information represented in a geographic information system?ANSWER: A geographic information system represents information in overlapping layers. p. 103.11.What is artificial intelligence? Name the artificial intelligence systems usedwidely in business?ANSWER: Artificial intelligence (AI)is the science of making machines imitate human thinking and behavior. The types of artificial intelligence widely used in business are expert systems, neural networks, genetic algorithms, and intelligent agents. p. 10412.What are four advantages of an expert system?ANSWER: Four advantages would be their ability to handle large amounts of data; to reduce errors; to aggregate information from various sources; and to improve customer service. p. 10613.What sort of problems is an expert system used for?ANSWER: An expert system is used or diagnostic (what’s wrong?) and prescriptive (what to do?) types of problems. p. 10514.What sort of problem does a neural network solve?ANSWER: A neural network solves problems involving the recognition and differentiation of pattersn. p. 10815.What three concepts of evolution are used by the genetic algorithm?ANSWER: The three concepts are selection, mutation, and crossover.Selection is the feature of a genetic algorithm that give preference to better outcomes. Mutation is a feature of a genetic algorithm; it’s the process of trying combinations and evaluating the success (or failure) of the outcome.Crossover is the feature of a genetic algorithm where portions of good outcomes are combined in the hope of creating an even better outcome. p.11216.What are intelligent agents? What tasks can they perform?ANSWER: Intelligent agents are software that assists you, or act on your behalf, in performing repetitive computer-related tasks. They can find good deals on the Internet, monitor computer networks for failures, fill out forms, play computer games, and so on. p. 11312. What is a multi-agent system?ANSWER: A multi-agent system is a group of intelligent agents that each has the ability to work independently and to interact with others. p. 11613. What do monitoring-and-surveillance agents do?ANSWER: Monitoring-and-surveillance agents(or predictive agents) are intelligent agents that observe and report on equipment. p. 114 Chapter5SHORT-ANSWER QUESTIONS (p. 155)1.What is electronic commerce?ANSWER: Electronic commerce is commerce, but it is commerceaccelerated and enhanced by IT, in particular the Internet.2.How can use you a B2B e-marketplace to reduce your dependency on aparticular supplier?ANSWER: You can use a B2B e-marketplace to find other suppliers and also participate in reverse auctions to find the best supplier with the bestprice.3.How do convenience and specialty items differ in the B2C e-commercebusiness model?ANSWER: Convenience items are lower-priced but something needed on a frequent basis. Specialty items are higher-priced, ordered on a lessfrequent basis, and often require customization.4.Why do commoditylike and digital items sell well in the B2C e-commercebusiness model?ANSWER: Commoditylike items work well because they are the same no matter where you buy them. Digital products work well because there is no real associated shipping or storage costs.5.What is mass customization?ANSWER: Mass customization is the ability of an organization to give its customers the opportunity to tailor its product o r service to the customer’s specifications.6.How does a reverse auction work?ANSWER: In a reverse auction, you place a request for products and/or services and suppliers continually submit lower bids until there is only one supplier left.7.How are vertical and horizontal e-marketplaces different?ANSWER: Vertical e-marketplaces connect buyers and sellers in a given industry while horizontal e-marketplaces connect buyers and sellers across many industries.8.What can a marketing mix include for a B2C e-commerce business?ANSWER: A marketing mix for a B2C business can include registering with search engines, online ads, viral marketing, and affiliate programs.9.What are the major types of B2C e-commerce payment systems?ANSWER: The major types of B2C e-commerce payment systems include credit cards, smart cards, financial cybermediaries, electronic checks, and Electronic Bill Presentment and Payment.10.What is the difference between a client-side digital wallet and a server-sidedigital wallet?ANSWER: You keep a client-side digital wallet on your personal computer while a server-side digital wallet is stored on a Web server.11.How are Secure Sockets Layers (SSLs) and Secure Electronic Transactions(SETs) different? How are they the same?ANSWER: SSLs and SETs are different in that SETs also provide amechanism for ensuring the legitimacy of the user of the payment device.They are both the same in that they create a secure connection between the client and the server computers.Chapter6SHORT-ANSWER QUESTIONS (p. 189)1.What are the three primary groups of people who undertake the systemsdevelopment process?ANSWER: The three primary groups of people who undertake the systems development process are in-house IT specialists (insourcing), end users (selfsourcing), and another organization (outsourcing).2.What is the systems development life cycle?ANSWER: The SDLC is a structured step-by-step approach for developing information systems.3.What are scope creep and feature creep?ANSWER: Scope creep occurs when the scope of the project increases beyond its original intentions. Feature creep occurs when developers (and end users) add extra features that were not part of the initial requirements.4.How do the four implementation methods differ?ANSWER: Parallel implementation uses both the old and new systems until the new system is verified. Plunge implementation immediately ceases using the old system and begins using the new system. Pilot implementation converts only a group of users until the new system is verified. Phased implementation converts only a portion of the system until it can be verified.5.What is component-based development?ANSWER: Component-based development is a general approach to systems development that focuses on building small self-contained b locks of code (components) that can be reused across a variety of applications within an organization.6.How are component-based development and a service-oriented architecturerelated?ANSWER: Component-based development is a technical implementation of a service-oriented architecture (SoA). An SoA is a holistic perspective of how an organization views and treats resources such as information and technology.7.Why do organizations prototype?ANSWER: Organizations prototype for a variety of reasons: (1) to gather requirements, (2) to help determine requirements, (3) to prove that a system is technically feasible, and (4) to sell the idea of a proposed system.8.What are the advantages of selfsourcing?ANSWER: The advantages of selfsourcing are many including: improving requirements determination, increasing end user participation and sense ofownership, increasing speed of systems development, and reducing the invisible backlog.9.What is the difference between a selling prototype and a proof-of-conceptprototype?ANSWER: A selling prototype is used to convince people of the worth of a proposed system while a proof-of-concept prototype is used to prove the technical feasibility of a proposed system.10.What is the role of a service level agreement (SLA) in outsourcing?ANSWER: A service level agreement in outsourcing defines the work to be done, the time frame, the metrics that will be used to measure the success of the systems development effort, and the costs.11.What are the three geopolitical forms of outsourcing?ANSWER: The three geopolitical forms of outsourcing include onshore outsourcing, nearshore outsourcing, and offshore outsourcing.Chapter7SHORT-ANSWER QUESTIONS (p. 220)1.How can a service-oriented architecture (SoA) be used to guide theorganization of the future?ANSWER: A service-oriented architecture (SoA) can guide theorganization of the future by enabling it to respond more adeptly tocustomers, end users, software development, information needs, andhardware requirements.2.How have ERP systems evolved over the last 30 years?ANSWER: ERP starts in the 1970s as basic material requirements planning systems. They then moved into an MRP II stage in which decision support and executive support capabilities were added. In the early 1990s,financials and accounting functions were integrated. Today finally, they are called ERP II, a complete integration of resource planning driven bycustomer relationship management and supply chain management activities.3.Why is interoperability important?ANSWER: Interoperability provides the capability for two or morecomputing components to share information and other resources, even ifthey are made by different manufacturers.4.What are the main differences between a decentralized infrastructure and acentralized infrastructure?ANSWER: A decentralized infrastructure involves little or no sharing of IT and IT-related resources, while a centralized infrastructure involves thecomplete sharing of IT and IT-related resources (albeit from onecentrally-control location).5.How does a client/server infrastructure work?ANSWER: A client/server network works by having one or more computers that are servers provide services to other computers, called clients.6.What are the four types of a tiered infrastructures?ANSWER: The four types of tiered infrastructures are 1-tier (presentation), 2-tier (application), 3-tier (data), and n-tier (business logic).7.How do efficiency and effectiveness metrics differ?ANSWER: Efficiency focuses on doing something right, such as reducing time or number of errors, while effectiveness focuses on doing the rightthings, such as making the right decisions.8.What are some commonly used infrastructure-centric metrics?ANSWER: Commonly used infrastructure-centric metrics includethroughput, transaction speed, system availability, accuracy, response time, and scalability.9.What are some commonly used Web-centric metrics?ANSWER: Commonly used Web-centric metrics include unique visitors, total hits, page exposures, conversion rate, click-through, cost-per-thousand, abandoned registrations, and abandoned shopping carts.10.Why are service level agreements important when contracting the services ofan application service provider (ASP)?ANSWER: A service level agreement (SLA) would provide the quantifiable measures by which the ASP must provide services.11.What is a business continuity plan?ANSWER: A business continuity plan is a step-by-step guideline defining how the organization will recover from a disaster or extended disruption of its business processes.12.Why do organizations implement a disaster recovery plan before testing it?ANSWER: Organizations implement a disaster recovery plan before testing it because organization cannot test their disaster recovery plans until the plan is implemented.。

高三英语人工智能基础单选题30题1. The concept of artificial intelligence (AI) refers to machines being able to perform tasks that usually require ____ intelligence.A. humanB. animalC. plantD. alien答案解析：A。

本题考查对人工智能概念的理解以及词汇辨析。

人工智能是指机器能够执行通常需要人类智力才能完成的任务。

选项A“human”（ 人类的）符合人工智能的定义，因为人工智能旨在模拟人类的智能。

选项B“animal”（ 动物的），动物的智能与人工智能所模拟的对象不符。

选项C“plant”（ 植物的），植物没有智力概念，与人工智能毫无关联。

选项D“alien”（ 外星的），目前人工智能主要是基于人类智能的模拟，与外星智能无关。

2. The development of artificial intelligence began in the ____.A. 1940sB. 1840sC. 1740sD. 1640s答案解析：A。

这题考查人工智能发展历程中的时间知识。

人工智能的发展始于20世纪40年代。

20世纪40年代计算机技术开始发展，为人工智能的发展奠定了基础。

选项B“1840s”、选项C“1740s”和选项D“1640s”，这些时期计算机技术还未发展起来，不具备产生人工智能概念和发展的条件。

3. One of the early milestones in AI development was the ____.A. creation of the first computer virusB. invention of the transistorC. Turing Test proposed by Alan TuringD. discovery of electricity答案解析：C。

Spark—A Generic Simulator for Physical Multi-agent Simulations Oliver Obst,Markus Rollmann7/2004FachberichteINFORMA TIKSpark—A Generic Simulator for Physical Multi-agent SimulationsOliver Obst Markus RollmannJune14,2004In this paper we describe a new multi-agent simulation system,calledSpark,for physical agents in three-dimensional environments.Our goal increating Spark was to provide a great amount offlexibility for creating newtypes of agents and simulations.To achieve this,we implemented aflexibleapplication framework and exhausted the idea of replaceable components inthe resulting system.In comparison to specialized simulators,users can ef-fortless create new simulations by using a scene description language.Spark isa powerful andflexible tool to state different multi-agent research questions.It is used as official simulator for thefirst three-dimensional RoboCup Sim-ulation League competition.We present the concepts we used to achieve theflexibility in our system and show how we seamlessly integrated the differentsubsystems into one user-friendly framework.1IntroductionSimulated environments are a commonly used method for researching artificial intel-ligence methods in physical multi-agent systems.Simulations are especially useful for two different types of problems:(1)to experiment with different sensors,actuators or morphologies of agents and(2)to study team behavior with a set of given agents.Ad-ditionally,the connection between both types of problems is an interesting research problem.To address each of these problem types without simulators,the actual hardware would have been to be built and set up in several experiments.Doing so with a number of real robots is often an expensive and also a difficult task because of the amount of param-eters generally involved.For many approaches,like for instance in machine learning, experiments have to be repeated a great number of times.In this paper we describe a multi-agent simulation system,called Spark,for physical agents in three-dimensional environments.Spark is a generic tool for creating simulations that can be used to address all of the above mentioned problem types.It was our goal to provide a great amount offlexibility,so that for somebody creating new simulations it is possible to choose how much attention should be paid to each of these problems.We show how we achieved thisflexibility by exhausting the idea of replaceable components in the underlying framework.For simulation designers,thisflexibility comes together with a user-friendly way to create simulations by using a scene description language and pluggable components.For users of the system creating agents for a given simulation it is interesting that they do not need to know internals of the system because agents are decoupled from the simulator. To achieve reliable and reproducible results,we built Spark integrating prior work in both physical and multi-agent simulation.2Related WorkA large number of simulators has been developed in both multi-agent and robotics research.From the multi-agent perspective,the primary interest is usually to study team behavior on an more or less abstract level of detail.In this domain,RoboCup Simulation League[Noda et al.,1998]is a prominent benchmark.The primary domain of RoboCup are robotic soccer games in which teams of robots or software agents have to cooperate and make decisions in real time.One of the landmark goals for RoboCup is that by mid-21st century,a team of fully autonomous humanoid robot soccer players shall win against the champion of the most recent World Cup.The official simulator [Noda,1995]for the annual RoboCup competitions has been developed since around 1992.In Soccer Simulation League competitions,two teams of11autonomous agents, represented as circles,compete in a two dimensional,discrete-time simulation.From thefirst official RoboCup competition1up to now the simulator has continuously been enhanced.However,one of the fundamental restrictions of the simulator–its limitation to a two dimensional world–remained.In order to accomplish the vision of the RoboCup Initiative,it is absolutely necessary to move the simulation into a three-dimensional world (cited from[Kitano and Asada,1998]).On the RoboCup2003Symposium,we proposed a new approach to a three-dimensional physically realistic soccer simulator[K¨o gler and Obst,2004].This system was a proto-type of the simulator we describe in this paper and not specially designed to simulate only soccer competitions,but a universal system for simulation of physical agents.However, the specific features for reproducible and distributed simulations,simple construction of articulated bodies and the scene description language we describe here were missing.Despite this,in a road map discussion for Soccer Simulation League on RoboCup 2003,a huge majority of participants voted for adding the three-dimensional simulationto the competitions;this year a simulation built on top of Spark is used officially forthefirst three-dimensional RoboCup Simulation League competition.In contrast to thetwo-dimensional simulation,our implemented three-dimensional simulation possesses a higher complexity with respect to the possible team behavior while it maintains a good degree of abstraction with respect to the possible agent actions and sensations.An entire different tool to study the behavior of a large number of agents in two-or three-dimensional continuous virtual worlds is XRaptor[Mark et al.,1998;Bruns et al.,2001]. For XRaptor,an agent is either a point,a circular area or a spherical volume.A detailed physical simulation is not supported by XRaptor,though in principle possible.The agent processes are not entirely decoupled from the simulation loop,unlike in Spark.Conse-quently,XRaptor is primarily useful for reactive agent types.For roboticists,the primary purpose of a simulation system is often to set up repro-ducible experiments and provide prototyping environments for mobile robots.Some ofthe existing simulators are tailored to specific robots platforms,most however address a number of robot types.The simulators below fall more or less into this category.Webots[Cyb,2004]is a commercially available mobile robotics simulation softwarethat is intended as a rapid prototyping environment for modeling,programming and simulating mobile robots.It includes robot libraries that allow the direct transfer of control programs to existing mobile robots platforms.Like Spark,it uses the ODE libraryfor accurate physics simulation.It comes with tools for visualization and for editing properties of objects in the world.The focus of Webots is the accurate modeling of existing robot platforms.This affects the level of abstraction of the provided sensorsand effectors.These are low level in order to match their real life counterparts.In this type of simulation a major part of the robot’s job is the classification of sensor datafor self-localization and obstacle avoidance.In comparison the focus of Spark is more towards general principles of multi-agent research as for example coordination or learningin multi-agent systems.¨Ubersim[Browning and Tryzelaar,2003]is a simulator specifically designed as a robot development tool for the RoboCup small-size soccer league.It uses afixed level of ab-straction to model the perception and action interfaces for the simulated robots.It provides a set of predefined robot models and can be parameterized only at compile time.Like Spark,¨Ubersim is an Open Source project and uses the ODE physics library.M-ROSE[Buck et al.,2002]is a2D simulator used for the rapid development of robot controllers.It features a three step approach for learning a desired controller behavior. First the individual motion profile of a robot is learned using a neural net.The learnedprofile is then the basis for a simulator specialized for this robot type,in which the controller learning tasks are performed.The trained controller is then transfered to thereal robot to validate its performance.This simulator is specialized for the developmentof controllers for robots with realistic sensor inputs.The approach is quite different toours in that it lacks features like for instance a full physical collision detection.The ultimate simulation system addresses all of these questions,and in fact this at least the direction Spark is aiming for.Admittedly,it does so from the multi-agent side of the spectrum,because with RoboCup Soccer Simulation League as one implemented application this is where its origin lies.With our underlying physics system and the way sensors and effectors are realized,simulations built with Spark are not constrained to high-level abstractions of multi-agent systems.The remainder of this paper is organized as follows:The following section describes the application framework we created as base for the whole simulation system.In Sect.4,we explain the functionality and integration of the core simulator engine.Section5shows how we integrated the underlying physics engine and provided a user-friendly way to access it by introducing the idea of connecting different simulation primitives via path expressions through a scene graph.Section6gives some details of the way network support has been added to the simulator,while Sect.7introduces a scene description language for setting up different kinds of simulations.Finally,Sect.8concludes the paper.3The Zeitgeist Application FrameworkOne of thefirst implementation steps was to create aflexible application framework, called Zeitgeist.Zeitgeist was invented2as application framework for the simulator,but has also been used successfully to create other applications such as software agents and monitors for the simulation.Theflexibility of Zeitgeist was one of the the key reasons why it was possible to refactor and build upon the prototype implementation instead of starting from scratch again.A variant of the reflective factory design pattern can be identified as key element for theflexibility of Zeitgeist.The reflective factory pattern was extended with methods supporting an object hierarchy of both created objects and factories in the same tree.We describe this pattern in the subsequent paragraphs.To our knowledge,a description of this element as design pattern cannot be found elsewhere, even though it is very likely that this pattern also occurs in other applications.We believe that it is also useful for other applications which have to provide a system of exchangeable and scriptable components.3.1Reflective Factory PatternThe reflective factory pattern[Hargrove,2000]is also known as the Class Object pattern. It allows the factory based instantiation of objects at runtime,given the class name as a string.Products of the factory,i.e.instantiated classes,maintain references to the factory that created them.The property that each instantiated object has the knowledge which factory cre-ated it distinguishes the reflective factory pattern from the abstract factory pattern [Gamma et al.,1995].It enables every object to access meta data stored in the associ-ated class object at runtime.Zeitgeist exploits this to store class names and information about supported interfaces in the class objects,allowing for queries about the class type and supported interfaces at runtime.By using this information we made all objects in the simulator accessible to a scripting language.The availability of this kind of meta data is native to object oriented programming languages,such as Objective C[Cox,1986], Smalltalk[Goldberg and Kay,1976]or Ruby[Matsumoto,2001],but not to C++.We have chosen C++as primary implementation language and adding this information“by hand”anyway,because it provided the most freedom in integrating external libraries. For instance the agent middleware system we are using(SPADES,see also below)offers only a C++interface.3.2Reflective Factory with Object HierarchyIn combination with the reflective factory pattern,Zeitgeist organizes factories and ob-jects created by factories in a tree like structure,comparable to a virtualfile system. To this end,each object stores its node name along with references to its parent and its child nodes.Based on these means we have aflexible mechanism to locate and reference objects at runtime:Given a path expression,similar to that used in a UNIX likefile system,Zeitgeist is able to retrieve the corresponding object instance.The object hierarchy is useful for implementation of a concept called pathname space mapping.Pathname space mapping appeared already in the QNX operating system and has been used to realize the QNX resource manager concept[QNX,2003].Resources are addressed by a path through the hierarchy given as string.The managed resources here are Spark services,called servers in our terminology.Servers are simply objects installed somewhere in the object hierarchy;they expose their functionality at locations which are known to applications.Applications can get services at runtime by querying the known location.Zeitgeist itself relies on the combination of the reflective factory in conjunction with the object hierarchy for the following reason:The factories themselves are installed at determined locations in the hierarchy.This can be used to create objects of classes that are unknown at compile time of the simulation system.This feature is useful because additional functionality can be added to the system with no recompilation of the whole system,but just by adding plugins.From these custom classes realized as plugins,it is possible to get instances via configuration scripts and install the instances as servers again.Zeitgeist makes further use of the pathname space mapping concept when the implementation of services is delegated to helper classes.In the object hierarchy,these helper classes are installed immediately below the server node.This leaves the server ob-ject as a lean mediator to several exchangeable sub-services with one common interface.An example application is thefile server in Spark,a service that provides access to various mountedfile systems.File systems are realized by objects implementing the file system interface used to access differentfile stores,like the standardfile hierarchy of the operating system or like afile archive contained in a zipfile.Thefile server implementation provides a single interface to transparently access differentfile system objects.During simulator run time,it is possible to create thefile server and requiredfile systems by using thefile server factory andfile system factories.The createdfile server is linked into the object hierarchy at a known location and the createdfile systems are installed directly below thefile server.From there,it is possible to use different variants offile systems with a common interface.Other useful applications of this facility are for instance protocols used between agents and the simulator or between the simulator and monitor programs.The greatflexibility of the Spark system stems from the fact that all services have been implemented in this fashion.Adding this kind offlexibility does not add much overhead to the system:the lookup of the objects in our framework usually happens during initialization time and is cached by ordinary pointers.4Core SimulatorFor an entire simulation,the simulator,agents,and monitors to watch simulations are all different processes that have to work together.The core of our simulator is the part of the system that contains the run loop and does the event management.It cares for the timing,and controls the communication between the simulator and external processes. The core part of the system is realized in the same spirit as other services described in the previous section.Thus even the run loop of the simulator is replaceable.We realized two different kinds of run loops,which users of the Spark simulation system can choose for their simulations:a straightforward implementation that realizes agent actions in the order in which they arrive at the simulator,and an implementation that cares for maximum reproducibility of distributed simulations.With the straightforward implementation,simulations and agents can be realized easily.The other implementation was implemented using SPADES[Riley and Riley,2003],a middleware system for agent-based distributed simulations.This system provides an abstraction that allows world model and agent designers to ignore machine load on different machines,networking issues and reasoning about distributed event realization.4.1SPADES-based SimulationsSPADES operates on simulation events that are sequentially realized.Agents simply receive sensations and send actions.For a simulation designer,two kinds of latencies are of interest:firstly,the latency inherent in the communication between agents and simulator,and secondly the modeled latency(dead time)of real sensors and effectors.SPADES is able to address both kinds of latencies.It hides away the network latency using simulation time stamps,so that this kind of latency is non-existent from the agents point of view.It further allows for explicitly modeling the dead times of sensors and effectors,addressing the second kind of latency.The system models agents as computational entities that receive sensation events from the simulation and return actions to be executed after some computation.Apart from the requirement that an agent can read and write to UNIX pipes,its internal architecture is not constrained in any way.In particular it is not required that agents are written in a special programming language or linked against a specific library.Agents are not executed as part of the simulator loop.This means that actions of agents do not have to be synchronized with the simulator.Therefore no single joint operation of agent and simulator is required at any particular time.4.2System StructureSPADES is one of the possible instantiations of the simulator run loop.From the SPADES point of view,a simulation is structured into several groups of components: These are a simulation engine,a world model,one or more communication servers,agents participating in the simulation and possibly some connected monitors.The simulation engine contains the main run loop of the SPADES system.It im-plements the event system and coordinates all network communication with connected monitors and communication servers.A communication server must be run on each machine on which agents run.It connects via TCP to the simulation engine and manages the communication with agents on the host machine through a Unix pipe as well as tracking their CPU usage to calculate their thinking latency.SPADES provides an integrated communication server that is part of the simulation engine process,useful for single machine setups to avoid the TCP overhead.The world model holds the state of the simulated world and advances it up to the time of the next event as requested by the simulation engine.It is further responsible to realize events,that means to change the state of the world in response to an occurring event.The most common source of an event is an act event in order to carry out an agent action.Finally,the world model generates sensations that are sent to participating agents.These events carry perception data about the current state of the world.4.3Event ProcessingIn the interaction with the world model,SPADES advances the world model several time quanta until the next pending event.In the interaction with the agents,SPADES is a discrete event simulator,following its model of agents.In this model agents react onlyin response to sensations from the world model.Actions an agent takes in response to a sensation are processed as new events which the world model carries out at a later time. Events are therefore the basis for a straight forward interaction between an agent and the simulation:An agent waits until it receives a sensation event from the communication server it is connected to.Based on this sensation it then generates a set of actions that it sends back to the communication server.The thinking cycle isfinished as soon as the communication server receives a done thinking message from the agent.After a sensation is sent to an agent,the corresponding communication server tracks the machine time used until it receives a done thinking message.The total amount of machine time used in the think cycle is then translated into simulation time.By correlating the consumed machine time with the corresponding simulation time SPADES assures that the simulation is reproducible and unaffected by network delays or load variations among machines hosting the agents.These factors only affect the overall simulation speed and not the generated sequence of events.SPADES offers multiple timer models that offer different compromises between precision and overhead.These are for example a jiffies based and a perfctr3based timer.To keep track of the simulation time an agent used during a thinking cycle,it can request think time messages from SPADES.This is a type of inform message that does not start a new thinking cycle.SPADES exploits concurrency by overlapping of events.It guarantees however that the order of event realization will not violate causality.That means no causally related events are realized out of order,for example like a sensation and a subsequent act event of an agent.In many cases however,the sense,think and act components can be overlapping in time.4.4Spades IntegrationIn order to build a simulation,SPADES expects an implementation of a world model and custom event realizations for sense and act events.Both,the simulation engine and the custom world model become part of the same process.In this way the Spark simulator implements the SPADES world model interface.We attached great importance to the separation between SPADES specific code and other Spark components.This allows for using simulation engines other than SPADES.Cur-rently the user can choose between SPADES,providing reproducibility with high accu-racy and a custom simulation server focusing on raw speed.Here,we drop the repro-ducibility SPADES provides with the remaining concepts being similar.We implemented this engine because we think that it will be useful in application domains where a large number of agent configurations and control parameters have to be evaluated,as for example in genetic evolution or machine learning.5Physical Simulation9 5Physical SimulationAnother equally important part is the physical simulation of the system.Instead of implementing an own physics subsystem,we integrated ODE[Smith,2004],the Open Dynamics Engine.ODE is a free,high quality library for simulating articulated rigid body dynamics.5.1Basic ConceptsRigid bodies are the basic entity of the physical simulation.They have several constant properties like mass,their center of mass and mass distribution.Other properties change over time.These are their position and orientation in space and further linear and angular velocity.Without any external influences a rigid body keeps its properties unchanged,resulting in a monotonous movement over time.ODE provides forces and torques as the two basic concepts used to act on rigid bodies.These two concepts model all interesting properties one expects from a physical simulation.A good example for properties that are modeled using forces are shape and extent of a simulated object.These are not direct properties of rigid bodies and are irrelevant to their simulation unless two objects collide.In this case they should influence each other, which can be accurately described in terms of forces and torques that are applied on the two colliding bodies.ODE models shapes of a simulated objects with a so called collider.It represents a geometric object whose only purpose is to detect intersections with other colliders.A collider does usually not model the exact shape of the associated visible object but a computationally less expensive shape.ODE supports boxes,spheres,capped cylinders and planes as collision primitives.Technically it is also possible to detect collisions with triangle precision.This allows collision detection of objects with arbitrary shapes and extents.Though not yet supported by Spark,we are currently about to implement this.5.2Articulated Bodies and JointsWhen a collision is detected it must be resolved.The correct forces that prevent the objects to interpenetrate must be applied to the bodies.This is done with the help of contact joints that are generated in response to a detected collision.Joints are used to actively enforce a relationship between two connected bodies.In the case of the contact joint mentioned above,the joint prevents two bodies from inter-penetrating each other.Other joint types model constraints that come more closely to the notion of a real life joint connecting two objects.Supported joint types of ODE are ball and socket joint,hinge joint,two-hinge joint, slider joint and universal joint.These joints constrain the relative movement of thetwo connected bodies along one or more axes.Additionally joints can act as motors by enforcing the movement along the non-restricted axes.A set of bodies that are connected with joints form an articulated structure,used to simulate vehicles or legged creatures.5.3Enhanced Usability of ODE ConceptsODE is a library with a plain C interface.Spark provides easy object oriented access to all ODE concepts,implemented on top of the Zeitgeist framework.All ODE concepts, rigid bodies,colliders and joints,are encapsulated by C++objects.Instances of these objects are installed into the scene graph.Specific groupings of objects express their responsibility for each other.This enables the objects to automatically care for the proper interaction.This concept is more natural for an object-oriented framework and hides the handle-based ODE interface.To relate arbitrary objects in the scene graph,for example to install joints between bodies,we use path expressions in the scene graph.This dramatically simplifies the construction of articulated bodies in comparison to the original handle-based ODE ap-proach.As these expressions are relative to the joint node,they further support the reuse of construction scripts and scene description languages that build upon them,as we show in one of the next sections.Spark also uses an object-oriented approach to handle the collisions occurring in a simulation.These are handled by collision handler classes grouped to colliders of sim-ulated objects in a similar fashion as we implemented the native ODE concepts.This allows simulation dependent reactions when two objects collide.Examples are playing a sound if a body touches the ground or triggering special simulation events.The latter approach is used in the RoboCup soccer simulation to detect if a goal is scored:this is the case if the ball collides with the goal box collider of the opposite team.The default reaction to a collision however is to resolve it.As described above,contact joints are used to prevent the bodies from interpenetrating each other.A contact joint takes several parameters that describe the contact surface:The resulting friction,if and how the two bodies slide along the contact surface and the“bouncyness”are some example parameters.Spark associates a surface description with each collider holding these parameters.When two objects collide,a resulting contact surface description is automatically calculated and applied by a contact joint handler.6Network SupportSpark supports both the separation of the simulation core from the connected monitoring applications and from agents participating remotely in the simulation.The network implementation focuses on modularity and reusability and a strict separation of protocol layers.。

高二英语科研项目实施单选题40题(带答案)1.In the scientific research project, we need to collect data _____.A.accuratelyB.exactlyC.preciselyD.correctly答案：A。

“accurately”强调准确地，在科研项目中收集数据需要准确无误。

“exactly”表示确切地、完全地；“precisely”精确地，和“accurately”意思较为接近但在科研收集数据的场景下，“accurately”更常用；“correctly”正确地，通常用于方法等正确，不太符合收集数据的语境。

2.When presenting the research results, we should express our ideas _____.A.clearlyB.obviouslyC.apparentlyD.visibly答案：A。

“clearly”清晰地，在展示研究结果时要表达清晰。

“obviously”明显地；“apparently”显然地；“visibly”看得见地，后三个选项不太符合表达想法的语境。

3.The scientific research project requires ______ teamwork.A.cohesiveB.unitedC.cooperativeD.joined答案：C。

“cooperative”合作的，科研项目需要合作的团队合作。

“cohesive”有结合力的；“united”联合的；“joined”连接的，这三个选项不太符合团队合作的语境。

4.We must analyze the data ______ to draw accurate conclusions.A.thoroughlypletelyC.entirelyD.wholely答案：A。

“thoroughly”彻底地，分析数据需要彻底才能得出准确结论。

C AR P LATOONS S IMULATED AS A M ULTIAGENT S YSTEMS.Hall´e,B.Chaib-draa and umonierD´e partement d’informatique et de g´e nie logiciel-Universit´e LavalSainte-Foy,QC,Canada,G1K7P4e-mail:{halle,chaib}@iad.ift.ulaval.caMarch7,2003AbstractCollaborative driving is an important sub-component of Intelligent Transportation Systems ITS and it strives to create vehicles that are able to cooperate in order to navigate through urban traffic by using communications.In this paper,we address this issue by putting emphasis on the simulation of a platoon of cars considered as more or less autonomous software agents.To do that,we propose a hierarchi-cal architecture based on three layers(guidance layer,management layer and traffic control layer)which can be used for simulating a centralized platoon(where a head vehicle-agent coordinates other vehicle-agents by applying its coordination rule)or a decentralized platoon(where the platoon is considered as a team of vehicle-agents trying to maintain the platoon).Such hierarchical architecture is sustained by a simulator that we describe in details.Finally we present ourfirst results concerning thefirst step of our project and which only focuses on thefirst level(autonomous longitudinal control)where only the relative distance and speed of the cars are actively controlled. KeywordsAutomated Highway System,Intelligent Transport System,Collabo-rative Driving,Multiagent Driving Simulation1IntroductionTraffic volume is increasing everywhere in the world.To address that,we generally build more and more roads in order to meet the increasing traffic volume.In fact,simply adding new roads is no longer the best solution because of the limited land areas.An alternative is to develop techniques that increase existing roads capacity and existing transportation systems capacity[GL00].This policy focuses on building fewer lane-miles,while investing in Intelligent Transportation Systems (ITS)infrastructure.It is shown that ITS may provide potential capacity improvements as high as20percent[Sto01].ITS can be seen as a complex set of technologies that are derived from information and computer technologies,as well as applied to transport infrastructure and vehicles[LL02].We can cite as ITS components:advanced/transportation management, advanced transportation information system,and commercial vehicle operations.Among these components,there are sub-components such as automobile collision avoidance and electronic guidance system.These sub-components are gener-ally sustained by some individual technologies as:electronic sensors,wire and wireless communications,computer software and hardware,GPS,GIS,etc.The main objectives of ITS include:reduce environmental impacts,enhance safety,reduce congestion,etc.Collaborative driving is an important sub-component of ITS and it strives to create vehicles that are able to cooperate in or-der to navigate through urban traffic by using communications. Simulation of driving agents as part of an ITS will enable us to develop and test this technology,while making appropriate amelioration to it.As canadian specific highways,climat and laws will be simulated,our simulation results will help us to prove the benefits of ITS for canadian roads.In this paper,we address this issue by putting emphasis on the simulation of a platoon of cars considered as more or less autonomous agents. 2Platoons of Collaborative vehiclesCollaborative driving is a research domain that aims to cre-ate automated vehicles which collaborate in order to navigate through traffic.In this sort of driving,one generally form a platoon,that is a group of vehicles whose actions on the road are coordinated by the means of communications.Thefirst vehicle of a platoon is called the platoon leader and its role is to manage the platoon and guide it on the road.Our work comes within this framework and is a part of the Auto21project [Aut03],a member of the Canadian Networks of Centres of Excellence,studying the automobile of the21st century within three levels of system functionality,examined in parallel.In the first level(autonomous longitudinal control),only the relative distance and velocity of the cars will be actively controlled in a type of generalized and distributed“cruise control system”, although drivers will still steer their vehicles.In the second level of complexity(semi-autonomous longitudinal-lateral control),the relative lateral and longitu-dinal motion of each vehicle,relative to the one preceding it, will be autonomously controlled,all the way up to thefirst “lead car”,in a form of generalized car-train with a specially equipped lead car and trained driver.Many such lead cars would co-exist in a given urban center,each with its own generic destination,much like a conventional train or bus,but with the added freedom of“getting off the train with your car”.In the level-3version(fully autonomous longitudinal-lateral control),the addition of cooperative steering,using the road and the telematic infrastructure as a guide for absolute motion control,will provide autonomous road-following capabilities. All three levels of functionality will be addressed during the conceptual design phase.This hierarchical decomposition 1will define the various achievement levels that will guide theevolution of the project.This will guarantee that a functional system will result from the long-term project.This paper presents our preliminary ideas on how we want to address the cooperative driving in the context of this project. For that,we have taken the road which consists to view the col-laborative driving as a group of agents more or less autonomous which try to drive without collision while communicating with each other.To achieve such a system,we propose a hierarchical architecture that we now describe in details.3Hierarchical Architecture for Collab-orative Driving3.1ITS ComponentsOur architecture was inspired by Tsugawa’s architecture [TST00]and other ideas coming mainly from the PATH’s project[Pro03].The resulting architecture has three major layers:guidance layer,management layer and traffic control layer,as indicated infigure1.DRIVING AGENT ARCHITECTURE Figure1:Hierarchical Architecture for Collaborative Driving.The guidance layer has as functions to sense the conditions and states ahead and around the vehicle and to activate the longitudinal or the lateral actuators.For the sensing systems, inputs come from sensors for speed,acceleration,raw rate, machine vision,etc.This layer also outputs sensing data and vehicles state variables to the vehicle guidance layer and then receives steering and vehicles velocity commands from the same guidance layer.These considerations have lead us to divide this layer in intelligent sensing and vehicle control sub-layers as depicted infigure1.The management layer determines the movement of each vehicle under the cooperative driving constraints with the data from(a)the guidance layer,(b)neighboring vehicles through the inter-vehicle communication,(c)the leader vehicle through the specific inter-vehicle communication leader-to-vehicles,(d)the traffic control layer through the road-vehicle communication.To determine the movement of each vehicle under the cooperative constraints,this layer needs to reason on the place of the vehicle in the platoon when this platoon remains the same(intra-platoon coordination),and its place in a new platoon when this platoon changes(inter-platoons coordination).Thefirst type of coordination is handled by the networking sub-layer and the second by the linking sub-layer. Generally,the task of the linking sub-layer is to communicate with the traffic control layer to receive suggestions on actions to perform.Resulting from this suggestion the agent’s linking module will try to coordinate inter-platoon actions like: join,split and lane-change.This layer is also responsible of maintaining a safe inter-platoon distance which will also define a desired velocity and inter-vehicle spacing for platoon members.This will be maintained using the networking module,which is responsible of the intra-platoon coordination and thus,the platoon formation.Finally,the management layer should also maintain a platoon formation plan,a task which is devoted to the planning sub-layer.The traffic control layer is a roads-side system composed of infrastructure equipments like sign boards,traffic signals and the road-vehicle communications as well as a logical part including:social laws,social rules,weather-manners and other ethics(more specific to Canada),etc.The implementation of those layers will be done using the two major architectures we are studying for the platoon grouped driving agent system,which are a centralized and a decentral-ized architecture.3.2How It can be used for Platoons3.2.1Centralized PlatoonsFirst,centralized architectures for a driving agent system will be presented.A centralized architecture can be defined either for the multi-agent interactions within a platoon or for the interactions between each platoons.Centralized architectures imply that a head agent will coordinate other agents by applying its coordination rules.As shown infigure 1,the intra-platoon coordination is done using the networking module,while the linking module is used for inter-platooncoordination,in an architecture inspired by[TST00].In this way,each coordination level can be implemented with a different model without disturbing the other.At the platoon level:The focus is on the intra-platoon coordination,which is centralized through the platoon’s leader, representing the head vehicle.Thus,the leader is the one who plans for the whole platoon and then prescribes inter-vehicle spacing for every member of its platoon.In this centralized model,split and merge task within a platoon are handled by the leader’s networking sub-layers which commands inter-vehicles spacing to create or close a gap between vehicles.In this way, the merge and split tasks are“transparent”to the follower agents that do not have direct contacts with each others but only with the leader.The leader agent will also try to define behaviors for each platoon member in collaboration with the networking sub-layer.Such relations between behaviors and the networking layer is useful to coordinate split and merge tasks or plans that would be more specific to a vehicle,in a peer to peer interaction.At last,the task of a follower consists in maintaining a prescribed constant spacing from the preceding vehicle.At the Highway System level:The centralization of inter-platoon coordination is done using a road-side traffic control layer as shown on top offigure2,which was inspired by a road-side system used in the PATH project[Ban21].This con-troller is in charge of a specific part of the highway where it will regulate its traffic.Thus,it receives real-time information about vehicles density and velocity profile on the road and determines the entryflow rate for a specific neighborhood and guides pla-toons’velocity and maximum platoons’size.In thefigure2 representation,platoon1(P1)and2(P2)send informations about their formation to the traffic controller using their link layer,in an asynchronous call.After it’s deliberation,the traf-fic control layer will send back a guide for the platoon velocity or a task command,which is explained next.Thus,the traffic control also determines the required actions by vehicles(when applicable)at every lane in the form of lane change,merging or splitting task directions.When the traffic control layer comes to a consensus,i.e.,an agreement on a specific task to be ex-ecuted,it has to coordinate on that task.In the case offigure 2,the traffic layer will command a higher velocity to the front (L1,F1,F2)of platoon1and a lower velocity to the back(F3, F4),creating a merging space.This is followed by a command to platoon2to steer right until it is aligned with follower2. 3.2.2Decentralized PlatoonsAs an alternative to the previous approach,we consider a decentralized approach where the definition of modules’roles presented in the introduction of section3.2.1remains the same but their implementation is different for a decentralized coordination.Thus,the definition of a leader is pretty much absent and the existence of a traffic control layer is not required. At the platoon level:In a decentralized platoon perspective, team-work theories might be used to maintain the platoon while giving each agent the same autonomy.The theory on multi-agents teamwork,explained in[PT02b],can be applied to ourFigure2:Centralized Decision Making Using a Traffic Control Layer.platoon,where it is considered as a team and vehicle drivers as ing this approach,the leader is seen as the team captain and the followers are assigned roles within the platoon. Each vehicle keeps its autonomy as there are local and team goals,but the platoon benefits from everyone’s knowledge and capabilities.Tambe’s COM-MTDP model[PT02a]presents a coordination architecture to support cooperative plans within platoon members allowing thus to maintain aflexible, persistent platoon formation.Theory on cooperative planning is defined in[GK96]where the definition of a Full Shared Plan(FSP)can be used to plan a platoon formation that will respect a given inter-vehicle spacing and velocity.But its most useful application is to coordinate merge and split tasks that require different vehicles’expertise,defined by their position in the platoon.Inspired by a distributed model,well known in networking,the teamwork for agents has the same benefits on a computing level,in addition to a powerful knowledge sharing. At the Highway System level:To create a decentralized ar-chitecture for our inter-platoon coordinations,we plan to con-sider mobile agents.Those agents create a merging interface through each vehicle’s linking layer and optimize the commu-nications by minimizing the round trips usually necessary to come to mutual intentions between platoons.Therefore,a mo-bile agent acting on the behalf of a platoon would coordinate itself with others using less bandwidth,since its coordination is done locally.In our application,a mobile agent carries infor-mation on the leader and its platoon formation relative to the current type of coordination.The mobile agent coordination model we are considering is a blackboard model for indirect co-ordinations[GC97].Applying this model to collaborative driv-ing,the previous organisation in neighborhoods will be kept. Each neighborhood has its own blackboard which resides on the biggest,previously elected,platoon.Platoons’representatives will locally coordinate themselves on this platoon blackboard in an asynchronous way.This is presented infigure3where a mobile agent representing platoon2(M.A.2)is sent to the blackboard situated on platoon1.There,it coordinates itself with platoon1representative(M.A.1)using information from other agents that passed by,stored on the blackboard.From their coordination,M.A.1will command it’s platoon velocity changes to create a merging space.Then,M.A.2comes back to platoon2and commands to steer right when merging space is available.Thus,mobile agents benefit our communications as they can coordinate themselves with available agents and leaveinformation for upcoming ones on the blackboard without hav-ing to wait for others.Figure 3:Decentralized Decision Making Using MobileAgents.4SimulationIn the previous section,the architecture for a vehicle driv-ing agent was defined and going from theory to practice,it’s implementation in a simulated environment will be defined in this section.First the simulator’s engine,around which vehicle shapes and dynamics are simulated will be explained.Then the agent framework used to implement our driving agent architec-ture will be defined in section 4.2with the tools and developing guidelines it offers.4.1Automated Highway System SimulatorWe now present the Automated Highway System (AHS)simulator developed as part of our multiagent approach.Similar to traffic simulators like Carnegie Mellon’s SHIV A [SHT97],our simulator,called HESTIA (a screen shot of it is presented in figure 4),aims a lower level of vehicle simulation,as its main purpose is to create an environment for Intelligent Transport Systems (ITS)developing and testing.To do so,it simulates a highway environment,with vehicles represented as 3D shapes,which are using simulated dynamics and sensors to retrieve information from the environment,as shown in figure 5.Here,the driver agent presented in section 3uses sensors,controller and a communication module to interact with the simulated environment.Shapes,data and dynamics modules are also used to complete a vehicle package that interacts with other vehicles in the 3D environment.Before we explain the simulator’s components in details in the following sub-sections,let us describe its simulator’s modelling language.Agents’environment :The agents’environment was built from JA V A 3D TM technology,which brings a 3D environment which is easy to use and in that our agents can easily evolve.First,the 3D environment offers a very pleasant user interfacethat is completely manageable.3D objects can then be dynamically altered,assigned different behaviors and picked on their contour in ing different object behaviorswe can easily represent different type of road conditions and their resulting friction,as well as an object’s behavior on such events as a collision.Sensors :Using the previous environment,JA V A 3D TM en-ables us to implement sensors by using their picking tool on 3D objects.This tool can provide informations about a vehicle’s Figure 4:Vehicles platoon formation in HESTIA 3D Simulator.Figure 5:HESTIA Vehicle Simulation Environment.surrounding objects’distances detected in the 3D environment.Since vehicles have a pickable behavior,other vehicles’sensors detect them and can then access available information about the sensed vehicle.Those sensors return a very precise information about the sensed object’s shape which can then be altered considering the sensor’s specifications.Notice that the simulator also plays the role of an internal-sensor by providing information based on the vehicle’s specifications and dynamic information,as the engine status for example.These informations are taken from figure 5’s Vehicle Data box.Dynamics :The dynamics engine simulates the vehicle’s dy-namics using data on the vehicle’s engine,shape and tires,from the Vehicle Data box and the road conditions from the 3D en-vironment box.These informations are transformed,using the current steering and throttle level,in angular forces applied on the vehicle.Putting all those forces together gives us the current acceleration,speed,heading and position.The latter heading and position are sent to the 3D engine to change the vehicle’s appearance.4.2Simulator’s Multi-Agent Framework Over the previously defined simulator is the agent frame-work,which was also developed in JA V A TM .This framework is based on a set of tools required by agents to evolve in an automated highway environment.We already defined the tools to sense on the environment,as part of the 3D engine,and toact on the environment,as part of the dynamics engine,wihch are the two principal properties that define an agent,as pre-sented in[RN95].Thus,starting from a simulator that responds to an agent’s basic needs,the framework was completed using JACK Intelligent Agents TM,a JA V A based programming lan-guage that extends agent-oriented concepts.To complete this strong framework,our own communications module was de-veloped,so we could control and simulate different communi-cation devices as used in platoons(radio or others).The global view of this framework is presented infigure6where the agent architecture from section3is implemented in accordance with the following agent framework,using an interface with the en-vironment formed by sensors and controller.Figure6:Global view on the simulator’s multi-agent frame-work.4.2.1Agent Modelling LanguageThe agent modelling language used as part of this AHS sim-ulation framework is mainly based on JACK,a programming language related to the BDI agent model[RG95].Useful tools from IBM’s ABLE have been added to this framework forming thus a powerful building toolkit.This toolkit has been completed with an inter-agent communication module which is related to our AHS simulator.JACK Intelligent Agents TM extends six major agent-oriented concepts:agents,capabilities,events,plans,knowledge bases, and resource and concurrency management.It even includes a model for agent teams programming.All of these concepts are implemented usingfive main classes that are extended for specific usage:plan,event,beliefset,capability,and task manager.Thefirst three will be described,making reference to their usage in our simulator.A plan is used to define a sequence of actions that an agent can do when an event occurs.In our case,plans will be used in the Planning sub-layer offigure1,mostly for tasks like merging,splitting and lane changes.Different plans will then be declared for different event types,and plans handling the same events will be differentiated using relevance and context criterions defined in JACK language’s documentation.More-over,plans are closely related to event types and definitions,since they occur when an event arise.JACK offers a number of event models for different needs,represented as:internal stimuli,external stimuli,and motivations.These events will then be used in multi-agents communication,mostly for intra-platoon coordination.In addition events will arise from the lower levels of our agent architecture infigure1,as the sensors will inform planners about sensed vehicles or situations.Then, to determine an agent’s environmental context,Jack provides a data structure called a Beliefset,which enables our agents to collect information on traffic,platoon formation,and platoon members and to infer on it.In addition to the BDI extension,JACK provides an extension to support Team Oriented programming,called SimpleTeam.Team Oriented programming is a sort of agent oriented programming where agent collaboration is specified from the abstract viewpoint of the group as a whole[Cob02]. This extension supports shared plans and enables us to easily implement the theory on platoons represented as teams, presented in section3.2.2.ABLE,the complementary toolkit to our agent framework, was created for agent building purpose and it offers a variety of agent’s artificial intelligence tools in the way of Java Beans.For the moment,neural network tools from Able librairy have been used as part of our agent guidance layer to create a learning brake and accelerator controller presented in section5.2.4.2.2Inter-Agents communicationsThe inter-agents communications are related to the environ-ment simulator and to the multi-agent framework.Thus,to sim-ulate communications within an AHS environment,we should take into account:the environment properties,the agents’vehi-cle properties and the communication system.This is done by the communication module in collaboration with the communi-cation manager which is in charge of dispatching the messages (as shown infigure7).The communication module,part of the simulated vehicle shown infigure5,is used by agents to communicate between them.These communications are done in order to coordinate themselves or to share results or infor-mation.The messages are then sent by the agent’s communica-tion module to the communication manager which dispatches them using the specification of the currently simulated commu-nication system.Depending on the these specifications and the message type launched by the agent,the manager determines the agent(s)that is(are)in the right to receive the message,and send it within an appropriate simulated time.For example,a radio communication simulator will determine agents in the ra-dius of the current broadcast,using the3D engine,and will send the message to those agents in a radio communication interval. 5First ExperimentsWe are currently in thefirst phase of this project devoted to collaborative driving and this phase focuses only on thefirst level(autonomous longitudinal control)where only the rela-tive distance and velocity of the cars are actively controlled. The longitudinal control consists infinding the acceleration or braking of a vehicle,called the following vehicle,in orderDrivingFigure7:Agent Communications Simulation.that it follows another vehicle,called the preceding vehicle, with security and without delay.To achieve thisfirst phase, the guidance layer of our arhcitecture,presented infigure1, was implemented using Tsugawa’s longitudinal control func-tion[TKT+01].More precisely,we have experimented two versions:Thefirst one is the direct implementation of the func-tion,whereas the second is the evaluation of the function by a neural network.Both methods use the simulated laser sen-sor as external sensor to evaluate the inter-vehicle distance and the difference of velocity between both vehicles.Moreover,an internal sensor is used to get the current velocity.5.1Using a Longitudinal Control FunctionA longitudinal control function calculates the commanded velocity of the following vehicle according to the current ve-locity of the preceding one,the relative velocity and the inter-vehicle distance.It includes also a minimal inter-vehicle dis-tance.The commanded velocity is given by the following:v c=v p+k1(−δv)+k2(L r−L m)withv c:the commanded velocity of the following vehicle.v p:the current velocity of the preceding vehicle.k1=m1|L r−L m|r,and k2=m2k1δv:the relative velocity between the following vehicle and the preceding vehicle.If d v is positive,the both vehicles are getting closer.L r:the minimal inter-vehicle distance.L m:the measured inter-vehicle distance.m1,m2:control gains.The tests show that their sign must be the opposites to give correct results.One of the best solution is m1=1and m2=−1.Some more precise tests must be performed to have a better solution.Thefigure8shows the result of such a function:the com-manded velocity is calculated according to the relative velocity and the inter-vehicle distance.In this example,we assume that the preceding vehicle velocity is equal to zero.It shows that as the distance with the precedent vehicle gets higher,the acceleration of the current vehicle gets higher.Moreover,the closest the following vehicle gets with the precedent one,the more important is its braking.We can see in thefigure8,that the commanded velocity is zero when the distance is equal to the minimal inter-vehicle distance(one meter in this example). This means the following vehicle velocity must be the same as the preceding vehicle to keep the minimal distance.f(x,y)-10-5510Relative velocity0246810Inter-vehicle distance -40-2020406080100120140160180New SpeedFigure8:The new velocity evaluation function.However,since the agent can only act on the vehicle’s ac-celeration and braking,the new acceleration must be calculated by the velocity derivative.Obviously,as we can see infigure8, this function calculates a theoretical commanded velocity nec-essary to keep the minimal inter-vehicle distance.That is why, in some case,the velocity seems to be too high but this function is evaluated several times per second and the next calculated velocity will be smaller.5.2Evaluation of the Longitudinal ControlFunction by a Neural NetworkThe second implementation is based on a neural network which evaluates the previous function.The learning and testing data have been generated with the following parameters: from0to25m/s with a step of0.5m/s for the velocity of the following vehicle,from−10to10m/s with a step of0.5m/s for the difference of velocity and from0to10meters with a step of0.5m for the inter-vehicle distance.Although the neural network is just a function evaluation, it reacts appropriately to the situations.However,since it is an evaluation,it will not work as well as the function in the extreme cases.Despite this weakness,one strength of the neural network is the capacity to learn from real situation.The longitudinal control has been implemented with an eval-uation function based on a robotic control and a neural network trained with simulation data.These approaches gave very sat-isfactory results for following vehicles,part of the centralized platoon approach.The next step will focus on the coordination, moving through a decentralization of the platoon.6ConclusionThis paper presented a complet simulation environment based on agents driving vehicles in platoon formation.This kind of simulator offers many advantages,both on a developing side and a marketing side.First,simulations enable us to test。

A MULTI-AGENT SYSTEM FOR A DISTANCE SUPPORT IN EDUCATIONAL ROBOTICSSébastien GEORGEChristophe DESPRESLaboratoire d’Informatique de l’Université du Maine Avenue René Laennec, 72085 Le Mans Cedex 9, FranceE-mail: george@lium.univ-lemans.frAbstractThis paper deals with a distance learning environment in the field of educational robotics. On the one hand, the learners interact with this environment through pedagogical activities (browsing electronic book, designing and building micro-robots, describing and driving micro-robots). On the other hand, the teacher has to prepare these activities and to help the learners when they encounter difficulties during their learning sessions. We highlight the usefulness of a multi-agent architecture for remote assistance through the Internet. We present an example of distance assistance in which the teacher can drive remotely the micro-robot of a learner to detect the origin of a malfunction.1. IntroductionIn this paper, we present a distance learning environment in educational robotics that takes into account the role of the teacher to organise learning activities and to assist learners. This environment is designed to allow the teacher to have a feedback of learners’ activities. Thus, the teacher can obtain information about the learners’ work and s/he can be informed automatically by the system when learners encounter difficulties. Furthermore, s/he can directly operate to help the learners to achieve their activities. These interventions can be made with communication tools (electronic mail, videoconferencing, etc.) but in some cases s/he has to manipulate the learners’ interface from a distance.The distance learning environment described in this paper is based on Roboteach that is an Interactive Learning Environment (ILE) designed by P. Leroux in the field of educational robotics. It enables the learners to discover technology concepts through pedagogical activities [3].In the next section we present succinctly this ILE. Then, we describe the distance learning situation and the environment based on the ILE Roboteach. The section 4 shows a multi-agent system for the distance assistance. In the section 5, we present an example of distance assistance.2. Context of workRoboteach is a learning environment developed to support activities based on a pedagogical method named ATRIUM [3]. This method uses pedagogical micro-robots driven by computer. The micro-robotics activities aim at helping learners to discover technology by handling, building, designing and driving micro-robots. The role of the teacher consists in setting up and managing these activities that are organised for groups of 2 or 3 learners. ATRIUM's approach is mainly centred on problem solving tasks conducted by learners. Three main kinds of activities have been defined to achieve this goal:-driving of a pre-assembled micro-robot. Learners use programmed commands given by the teacher or create their own programs to solve problems such as driving a floor-turtle ina labyrinth;-building of a micro-robot such as an arm (see Figure 1) from a descriptive handbook.Once the micro-robot is built, learners must drive and program its movements;Figure 1:An exemple of a micro-robot-carrying out of projects. Learners must design, build and drive a micro-robot from a technical directive notebook. A project is defined by its pedagogical goals, its technical goals, its content and its constraints (e.g. costs, time, reliability, maintenance, evolutivity, security, etc.) [5].In order to support these activities, Roboteach contains three environments:-course environment: electronic course books that embed all notions introduced in the technological context;-description environment: when the micro-robot is not known by the system, learners have to describe it to Roboteach (translation axis, rotation axis, sensors, etc.) which generates automatically elementary driving programs;-programming environment: in this environment the learner creates complex programs from the elementary driving programs so as to drive the micro-robot.Roboteach has been experimented for more than 400 hours and is currently used in secondary school but also in lifelong learning in small and medium enterprises. At the moment, the teacher and the learners groups are in the same room. Now we present the use of such a learning environment in a distance context.3. Distance Learning in Educational RoboticsIn the new learning situation, the learners groups and the teacher are geographically distributed but they are connected through a communication network. Each learners group owns a micro-robot and a computer with the learning software and has to carry out its activities (Figure 2).The teacher has to plan these various activities and to assist the learners during their learning sessions. In face-to-face learning, the teacher’s over-solicitation has often been observed,particularly when learners begin the micro-robotics activities [3]. We think that thisphenomenon will still be true in the distance learning situation. To avoid this over-solicitation, we have created a system that provides a software support to the learners and assistance to the teacher.3.1. Support to the learnersThe system supports the learners either when they ask for it or when it detects that they have difficulties. The system can detect different difficulties like:- critical cases (stop emergency button);- difficulty to carry out a task (e.g. the description of the micro-robot);- learners lost among the tasks;- difficulty to use the learning environment;- etc.According to the kind of difficulty encountered by the learners, there are several ways tosupport learners. We call them the support styles. For instance, the system can present a part of the course to the learner (the aim is not to give the solution but to incite learners to find the solution of their problem through this part of the course) or can give an advice to the learners (the advice can describe one by one all the steps which ensure the end of the deadlock of the Figure 2:TeacherLearners Learners - Planification of learners'activities- Assistance to the learners- Browse of electronic books- Design of micro-robots- Building of micro-robots- Description of micro-robots- Driving of micro-robotssituation, or be more suggestive). The support style is set by the teacher before the learning session and for each kind of activity according to his/her pedagogical objectives. Yet, the system abilities are restricted as well for the difficulties detection as for the support to learners. So when the system is no longer competent to support learners, it can ask for the teacher's help.3.2. Assistance to the teacherIn a distance learning situation, the teacher is physically far apart from learners; therefore s/he can not observe them during learning sessions. So, the teacher needs information about the learners group and its activities. This information has to be relevant in comparison with the support to provide, so that the teacher is not inundated with needless information. The information, concerning the learners and their difficulties, is provided by the as a control panel. So, assistance is given to the teacher through an intelligent aid for supervising and organising the learners group [4].With this assistance, the teacher can decide on the way s/he will intervene. First of all, s/he can communicate with learners using telecommunication tools like videoconference or telephony. Furthermore, s/he has the possibility to remotely modify the learners group's interface. Thus s/he can give them an advice, open an electronic course book or modify their programs while commenting on it. The teacher has also the possibility to act on the distant physical device (the micro-robot). S/he can know the current state of the robot (sensors) and remotely act above in order to diagnose an error of design, movement or assembling.In order to assure this support to the learners and to assist the teacher we have developed a multi-agent system with agents specialised in the detection of learners’ difficulties, assistance to the learners, and monitoring of session. The next section describes such a multi-agent architecture.4. Multi-Agent System for Distance AssistanceTo implement the distance learning environment, we have achieved a multi-agent platform in Java© with communicating agents distributed across a network like Internet. The figure 3 shows the architecture of our system based on this platform. Using multi-agent architecture presents some advantages. The system and its functionality can easily be distributed in the space between teacher’s workstation and learners’ workstations. The modular side of multi-agent system ensures easy modification of an isolated agent's behaviour. Furthermore, a multi-agent system offers an open architecture allowing the integration of new agents if required.Figure 3: Multi-agent architectureThe agents of the multi-agent system are organised as follow. First of all, the agents of the "Detection of Difficulties" group observe the interactions between the learners group and the ILE in order to detect the difficulties encountered by the learners. Each of these agents detects one kind of difficulty. For this, they use different detection methods. An example of adetection method is given in [1]. This particular method detects learners which are lost among the tasks required to achieve an activity.When an agent of the "Detection of Difficulties" group detects a difficulty, the system tries to support the learners group. This is done by the agents of the "Assistant" group. Each one of these agents is specialised to support learners groups during a given activity according to the support style set by the teacher before the learning session. When an assistant agent is no longer competent to support learners, it informs the teacher of the learners' difficulty through the "Monitoring of Session" agent.The "Monitoring of Session" agent provides information about the learners group by monitoring the interactions and the activities that have been carried out by learners. Then the teacher can decide to intervene by remotely manipulating:-the interface of the learners group: s/he can intervene on the interactive learning environment in order to open an electronic course book, modify their programs, etc.-the micro-robot of the learners group: the "Driving of Robot" agent give him/her the sensors states and allows him/her to act on the micro-robot.5. An example of distance assistanceWe present now an example illustrating how the teacher can remotely support the learners group by driving their micro-robot. We consider a situation in which a learners group describes an axis of a micro-robot (e.g. a vertical translation). When they have done it, they can test elementary movements on this axis (e.g. going up, going down, etc.). If their description does not match the real wiring of the robot, the learners will observe a malfunction and will have the possibility to click on the emergency stop button (see Figure 4). This difficulty is one of the easiest to be detected by the system. So, in this situation, the system can support the learners group itself through one of the support styles.Figure 4: Learners' screenNevertheless the teacher can have asked to be informed for this kind of problem. In this case, the system alerts him/her and shows him/her the particular circumstances in which the problem occurred. Then, s/he can communicate with the learners by videoconference and s/he can use specific tools to diagnose the problem. The Figure 5 shows the teacher's screen. On the top left of this screen, s/he can see the sensors states of the remote robot. Just below, some buttons activate the motors of the remote robot. As the teacher remotely drives the robot, s/he can observe on the video the change in the states of the sensors and the movements of the robot. So s/he can analyse the situation and understand the source of the learners' problem. Then, either s/he explains how to resolve their problem (giving a more or less suggestive advice) or s/he just guides them by displaying an appropriate electronic course book on the learners' screen.Figure 5: Teacher's screen6. ConclusionWe took advantage of our experience with the ILE Roboteach to conceive a distance learning environment in the field of educational robotics. The architecture of our environment is based on a multi-agent system that we have developed in Java©. We showed that this architecture is particularly suited to assist the teacher in supporting the learners. Thus the teacher can supervise the learners' work by monitoring their activities and by intervening if necessary. In our context the intervention can consist in manipulating micro-robot. Tests have proved that our multi-agent architecture enables the remote driving of micro-robots.Furthermore, this remote driving can be used not only to provide assistance but also to create new learners’ activities. Now, we focus on the setting up of activities requiring cooperation between learners [2]. These activities will consist in designing and driving distributed micro-robots.7. References[1] C. DESPRES, P. LEROUX, Raisonner sur la trace : Analyse de sessions avec l'application ROBOTEACH,in: Actes des 5° journées EIAO de Cachan, Cachan 1997.[2] S. GEORGE, P. LEROUX, Computer-Supported Project Pedagogy in a Distributed Collaborative LearningEnvironment, in: Proceedings of The 9th International Conference on Artificial Intelligence in Education, Le Mans 1999.[3] P. LEROUX, M. VIVET, Micro-robots Based Learning Environments for Continued Education in SMEs, in:The International Journal of Continuing Engineering and Life-Long Learning,Special Issue 1999.[4] M. MÜHLENBROCK, F. TEWISSEN, H. U. HOPPE. A framework System for Intelligent Support in OpenDistributed Learning Environments, in:Proceedings of The 8th International Conference on ArtificialIntelligence in Education, B. du Boulay and R. Mizoguchi (Eds.), IOS Press, Kobe 1997.[5] M. VIVET, Educational Uses of Control Technology. Control technology in elementary education. Berlin,Springer Verlag, NATO ASI Series, series F, 116, 1992.。