D.1.3 NIAD&R: Plan for 2003

D.1.3 NIAD&R: Plan for 2003

Scientific Objectives

In the following sub-sections a more detailed description of the work we intend to pursue is presented.

D.1.3.1 Negotiation Models for Autonomous Agents

Coordinator: Eugénio Oliveira

Research direction: Research in the context of this issue aims at developing appropriate models for both Business to Business and Business to Consumer Negotiation processes as well as to provide platforms, tools and frameworks enabling Agents' interaction in the context of Virtual Enterprise formation process

Models and Protocols for Autonomous Agents' Negotiation

Research goals: To develop, implement and test models for autonomous, individually rational, agents representing either individuals or enterprises for the sake of reaching agreements through flexible negotiation.

• To develop, implement and test models for autonomous, individually rational, agents representing either individuals or enterprises for the sake of reaching agreements through flexible negotiation.
• To enhance and test a specific tool we have been developing for B2B interaction.
• To implement a specific E-Brokering System for the Insurance Domain. For the past, a prototype (MACIV) for Distributed Resources Management for the Civil Construction domain has already been concluded and demonstrated.
• Implementing second generation bots for agent-mediated electronic commerce.

• We have now established, together with our colleagues in the AgentLink Network of Excellence (Agent-Mediated Electronic Commerce Special Interest Group) the concept of Electronic Institution. In order to implement the concept, i.e. a framework enabling secure and responsible (enterprise delegate) agents'interaction we have now a first implemention of ForEV (Virtual Enterprises Formation framework). Besides all the facilities for registration and matching between mutually interested agents, ForEV provides sophisticated negotiation protocols with learning capabilities - Q-Negotiation Algotithm [Roc02].

 

 

Q-Negotiation is a multi-attribute negotiation protocol for agents in the context of the Virtual Enterprise Formation stage, that encompasses the following characteristics:

• It uses an evaluation function relying on the several different agents individual preferences;
• It provides qualitative feedback, enabling the agents keeping their own preferences private;
• It continuously adapt to the dynamics of the market by using a slightly modified reinforcement learning algorithm to find out the new current proposal to submit to the market.

 

 

The proposed B2B Negotiation Model also includes procedures to solve distributed constraints among the items under negotiation trying to make all the process to converge to the mutually accepted solutions space.[Roc02]

• We have specified and proposed [Nog02b], [Nog02c], [Nog02d], a new model for automatic agent-based E-brokering in the important domain of insurance products. This model encompasses different kinds of negotiation protocols between both the Broker agent and the Insurance companies agents and the Broker agent and the Customer agents. The main idea is to intelligently mediate by supplying Customers with meaningful information gathered from the available Insurance products as well as to take advantage of inferred customer preferences to negotiate different offer and rank them for the customer. The Broker Agent is then able to incrementally build up differnt and separate Customers groups and associate to them meaningful stereotypes. Specific learning algorithms like Cobweb are used.
• In order to develop "second-generation bots" used in agent-mediated electronic commerce encounters, "seller agents" have to be capable to implement marketing strategies through offer differenciation, enabling a model of "dynamic posted offering" as opposed to a single negotiation-based approach.In particular we are now exploring the possibility of adapting a technique widely used in marketing research - conjoint analysis - in order to endow these agents of market analysis skills, extracting market information for insightful offer generation applying differentiation strategies [Car02].
• A systematic study on Ontologies has been done in the framework of a new PhD work. The ultimate aim is the creation of special Agents capable of providing ontology-related services to heterogeneous agents willing to interact. We have designed (A. Malucelli) a specific scenario where agents representing car parts supplyers need an Ontology to interact. This Ontology has been specified through Rational Rose and edited through OntoEdit. Agents exchange messages in OXML format.

• Our main concern is now to specify what a suitable and effective "contract" can be as a result of all the negotiation process that leads to a set of procedures all the agents have agreed upon. This establishec "contract" has to be at the disposal of the Electronic Institution in order to permit this entity to verify all the important steps that should be checked and, if this is the case, to enforce previously agreed corrective actions or punishements. The Contract, general Rules and Norms, either from generic legislation or specific to that particular Electronic Institution, all are important means to guarantee that next stages of the Virtual Enterprise Life Cycle are correctly supervised.
• Based on the model developed for the E-Brokering negotiation, we are currently implementing an agent-based system we intend to present, together with a credible scenario, for automatic mediation of Insurance products offers and needs. Further developments will imply enhancement of agent negotiation strategies and automatic product offers on the Insurance companies side.We reserve our decision to go in this direction depending on the impact the prototype will have on potential interested software houses.
• We consider the application of techniques such as bundling, demand aggregation, price and market segmentation to enhance "second-generation bots" that are supposed to negotiate. Related to this approach is the buyer-side of the process, where agents need to build models of shoppers in order to select the best possible offer according to their preferences. We want our agents to incrementally build up dynamic preferences models. An adaptation of conjoint analysis - choice based conjoint - might be applied by presenting to potential buyers real products alternatives in order to induce a preference model.
• In order to develop further the ontology-services agents, we envisage to integrate it with ForEV framework. Ontology can then be explored in the sense of helping different agents, representing different companies, to understand each others when negotiating their joint participation in a Virtual Enterprise through their commitment in supplying complementary parts of the final overall business process.

D.1.3.2 Agents' Adaptation, Learning and Emotions

Coordinator: Eugénio Oliveira

Research direction: We here identify two separate research lines we believe will increase their relative importance in our group in 2003 and that can be seen as an attempt to explore agents advanced features:

(i) Multi-agent learning. The goal of this study is to find an answer to the following question: "(How) can several different, heterogeneous, Learning Agents improve their performance by exchanging information during their own learning process?".

(ii) Emotional-based agents' architectures. Here we would like to answer another important question: "Will it be possible to escape from usual utility-based decision functions in which decision-making for autonomous agents is concerned?"

Multi-Agent Learning () Research goal: (How) can several different Learning Agents improve their performance by exchanging information during their own learning process?" that is the question.

RECENT WORK (2002):

• In order to answer that question, we have been studying the effects of exchanging information during the learning process in heterogeneous groups of agents in controled, and somewhat simplified,scenarios, with the objective of detecting possible improvements of agents' individual and global performances.
• To achieve the above mentioned goal, and having in mind that first question, a method for information exchange during the learning process based on the exchange of advice amongst learners has been under development. The learning environment launches several learners solving different instances of the same problem. The instances of the problem may be either totally independent, or similar parts of the same global problem. [Nun02b], [Nun02c].

 

 

As an example in one of our learning environments, agents control traffic lights in different crossings. Experiments with disconnected crossings have proved that advice-exchange, even in its simplest form, is effective. Current work is focused on solving the problems that appear when agents share the same environment and their actions affect others. In order to analyze the problems that emerge when several agents are acting concurrently in the same environment, a set of experiments in the Pursuit Problem was made, whose results allowed us to uncover and solve several of the problems that caused disturbances in the learning process. These disturbances are due to negative interactions between agents'actions or between the learning algorithms and advice-exchange.

Giving advice consists on sending the best response an agent (taking the role of advisor) can give to the problem being solved considering the state of the problem as seen by another agent (the advisee). The advisee uses this information as input to a supervision mechanism. The way the advisee uses information depends on the expected quality of the advice given by the advisor and a measure of trust kept by the agent based on the result of previous advice given by the same advisor. Several other mechanisms, such as providing unsolicited advice and combining advice, are under study.

• This work has deserved an article in the Technical Research News after an interview to one of the authors [Kimberly, September 18/25, 2002].

• For a first evaluation of this method, a traffic control problem is being simulated. The simulation is similar to the one used by the Gerhard-Mercator-Universität Department of Physics of the University of Duisburg (Germany) to study traffic phenomena. This simulation is being built using Java2 and C++, running on Linux.
• The first results have been published and extensively discussed in the "Adaptive Agents and Multi-Agent Systems" AAMAS-2 workshop collocated with AISB'02 conference [Nun02c], and the interest generated by this approach lead to the acceptance of several other works accepted for publications [Nun02a], [Nun02d], [Oli02a].
• The tests are now concentrating in the interaction between agents that use Reinforcement Learning and Evolutionary Algorithms, although the approach is, in many respects, generalizable to other learning algorithms.
• Future work will focus on refining the advisor selection process, extending this approach to other learning algorithms and testing its effectiveness in problems of traffic-simulation and traffic-control. Other problems, such as load-balancing and band-width management are under study as possible applications.

Research goals: The second question to be answered is now: Will it be possible to escape from usual utility-based decision functions in which decision-making for autonomous agents is concerned?

We are pursuing research efforts towards the understanding how emotion-like concepts can endow agents' architectures with more sophisticated, although still reliable, decision-making capabilities. new agents' architectures are being proposed and experiments are being done in simple simulation scenarios.

Although the study of emotion in the realm of Artificial Intelligence is not totally new and has been addressed by Simon, Minsky, Sloman and Croucher among others. Recently much more attention has been devoted to this subject by several researchers like R. Picard. This renewed effort is being motivated by trends in neuroscience (see Damásio's recent work), that are helping to clarify and to establish new connections between high level cognitive processes, such as memory and reasoning, and emotional processes. These recent studies point out the fundamental role of emotion in intelligent behaviour and decision-making. From our perspective, as engineers and computer scientists, we are mostly interested in studying the functional aspects of emotional processes. Particularly, we aim at understanding how emotional mechanisms can improve cognitive abilities, such as planning, learning and decision-making, for hardware and software Agents. RECENT WORK (2002):

• We have developed a model of the emotional valence-based mechanisms for agents. These "mechanisms" receive input from internal sources, "I", as well as external sources, "E", and produce a valence-based measure, "V", according to what we call Emotional Valence Function EVF. Emotional Valence Functions return the valence of the situation regarding a given goal, G: V = EVF(I,E,G)

 

 

The valence measure and the sources of evaluation are then associated in order to form a Valence Vector: < V, I, E, G >. The Valence Vector is stored in working memory and made available for all Agent processes for further consideration, such as, for example, decision, planning and learning modules.

We assume that for each goal, Agents will have one Emotional Valence Function that try to relate their performance both with the environment and their own internal state. We also assume that there may be Emotional Valence Functions exclusively concerned with either environment evaluation or internal state evaluation. The Valence Vector may be stored afterwards in long-term memory by a process that selects which vectors to store according to their respective relevance. Valence Vectors that have significant valence may be stored for later processing while the others may be simply discarded.

• We were looking for an evolutionary scenario for Emotional Agent Architectures. Our first platform was based on RealTimeBattle (RTB). This platform provided a simulated real-time environment where softbots fought for survival in dynamic scenarios. However we have decided to switch to a more complete and rich scenario, giving up this simplified one.

• We are now proposing an agent architecture that includes several emotional-like mechanisms, namely: emotional evaluation functions, emotion-biased processing, emotional tagging and mood congruent memory. These emotional-like mechanisms are intended to provide agents with increased performance and adaptability in real-time environments.

 

 

Previously, we have divided emotional phenomena in 3 different categories: specific emotions, moods and emotional dispositions. We are now concerned with the dynamics of emotional mechanisms.

The duration of the elicitation process and the activity period of the emotional phenomenon thereby elicited can be better understood according to two functional requisites of the response they motivate: urgency and temporal consistency.This lead us to the definition of Emotion Accumulators. Emotional Accumulators (EA) couple with Emotional Evaluation Functions (EEF) to build another element of our architecture, the Basic Emotional Structure similar to well known emotions ("Fear", "Anxiety", "Self-confidence",...). We want to alter parameters that influence the agents' planning capabilities to achieve specific goals.

• Emotional Tagging and Mood-Congruent Memory are ideas also under development. Besides the possibility of considering emotional states as relevant direct information to cognitive processes there are yet other important relations between emotion and information. There is a very strong link between emotion and memory, a link that has several functionalities associated.

 

 

The first of those functionalities is emotional tagging. Instead of being simply stored in memory, information is first marked with an emotional tag, relating that information with the current emotional state of the agent. The tagging procedure is itself important because it allows selecting which information should be stored in long-term memory and which should be stored in short-term memory or simply discarded [Oli02b].

Mood-Congruent Memory is being explored once it may help the agent in discovering interesting opportunities or possible threats in the current situation, based on its own past experiences.

It may also simplify processes of decision by reusing knowledge acquired in similar past situations.

We also intend to formalize most of the concepts we have introduced or, at least to relate them in a systematic way.

• The experiments made using RealTimeBattle allowed us to develop a sharper understanding about emotional-like structures, namely Emotional Evaluation Functions coupled with Emotional Accumulators [Oli02b]. They also made possible to validate some of our initial ideas about the functionalities of emotional-like structures, in particular in biasing the dominant behavior of the agent (action tendency). However, we soon realized that to effectively test other emotion-cognition interactions (e.g.: Mood-Congruent Memory and Processing Strategy management) we needed a more complex simulated environment that would impose higher demands on the Agents.

 

 

The main requirements for this needed simulation environment are: (1) high level of complexity for the participating Agent; (2) real-time, highly dynamic, demands; (3) multiple concerns at stake;(4) Overall goals asking for a Multi-Agent System approach; (5) closeness to a real-world problem.

Based on all these requirements we decided to develop a forest fire environment simulator, the Pyrosim [Oli02c]. This simulator supports multi-agent efforts and imposes several low-level and high-level demands on each agent. In a complex environment such as Pyrosim, which demands real-time response from the agent, we believe emotional-like mechanisms will play an essential role. Thus, it seems useful to include in agent design the following Emotion Structures:"Fear", "Anxiety", "Frustration", "Self-confidence".

These concepts, together with Mood-Congruent Memory, are examples of agents' features we are willing to test through the new simulator. We belief Pyrosim will become an important test-bed for Emotional-like agents Architecture and that it will help us in enhancing and introducing new emotional-like mechanisms.

D.1.3.3 Multi-Agent Coordination

Coordinator: Eugénio Oliveira

Research goal: Coordinating teams of autonomous (or semi-autonomous) agents that perform in rich, dynamic, both competitive and adversarial environments is a major aim of this work line. For this objective, we are exploring four main research directions that can be seen as complementary:

• (i) Developing new coordination protocols that enable teams of agent's to perform complex tasks in open multi-agent environments
• (ii) Organising and making available knowledge, languages and protocols for enabling agents' teamwork;
• (iii) Defining policies for coaching teams of autonomous agents;
• (iv) Design and implement an agent-based common framework suitable for controlling teams of cooperative robots (either physical or simulated) playing in RoboSoccer-like competitions or performing other team complex tasks in dynamic domains.
• These approaches have been anchored on one main application domain: (i) The RoboCup international initiative (simulation, small-size, middle-size and Sony legged leagues, together with RoboCup coach competition). However, the research conducted along this line, may be partially applied to several very useful social areas, like search and rescue domains, fire combat, battlefield scenarios, mine clearance, land exploration, control of hospital robots, public transport coordination, satellite control, cleanup of radioactive and toxic contamination and other problems that imply team coordination.

RECENT AND FUTURE WORK:

• Previous concluded work in this research direction, includes DiPLoMAT prototype (Distributed Project Location Multi-Agent based Testbed). DiPLoMAT applies most of the theoretical work on conflict resolution done before, to the Project Location assessment domain. Evaluation Agencies have to identify the project land requirements (area, natural resources, transports, price, etc.), and finding an adequate location for that specific project. The achieved result is an Intelligent Decision Support System to assist the project team in finding adequate projects' locations which comply with the applicable legislation and satisfies the project requirements.

• Other previous work concluded in 2002 consisted in the application of constraint satisfaction techniques, together with specific problem description languages and multi-agent systems architectures to problems close related to school management. We developed a simple prototype for distributed school timetabling: UNIPS - University Planning and Scheduling illustrating the application of our theoretical work. The prototype is able to compute solutions for several timetabling sub-problems described in our standard language (UniLang) for representing timetabling problems. UniLang intends to be a standard suitable as input language for any timetabling system information. It enables the representation of data, constraints, quality measures and solutions of different timetabling (and related) problems, like school timetabling, university timetabling, examination scheduling, room assignment, service assignment and student scheduling.

RECENT WORK (2002):

• Simulated Soccer Team: Our Simulated soccer team - FC Portugal (developed in collaboration with IEETA/Univ.Aveiro), ranked 5th in RoboCup 2002 competition held in Fukuoka, Japan.
• Coach Agent: Our Coach agent - FCPortugal Coach [Rei02b] [Rei02c] - won the 2002 coach competition in the RoboCup competition that took place in Fukuoka, Japan.
• Other RoboCup teams: We have developed some simple methodologies for coordinating teams of physical robots [Mor02] and applied them in the context of 5dpo RoboSoccer small-size and middle-size league teams (developed by ISR-Porto).
• Coordination of Teams of Homogeneous/Heterogeneous Agents in Adversarial Environments. We proposed several coordination methodologies for dynamic spatial domains, namely: Strategic coordination, Situation Based Strategic Positioning (SBSP), Dynamic Positioning and Role Exchange (DPRE) [Lau02] [Rei02d].
• Coordination using High-Level Communication. We have proposed Intelligent Communication policies based on appropriate (multi-level) World State knowledge(ADVCOM) together with a way of balancing strategic and active communication.
• Coordination without Communication. We have proposed some opponent modeling and teammate modeling techniques enabling coordination without communication. We also have developed a more adequate perception mechanism called Strategic Looking Mechanism (SLM) for coordination without communication [Rei02d].
• Partial Hierarchical Coordination. We have developed techniques enabling a team of autonomous agents to integrate coach advice in their reasoning processes, together with their local reasoning process [Rei02c].
• A Visual Debugger for analysing intelligent agent-based players was improved and released as well as COACH UNILANG, a standard Language for Coaching a (Robo) Soccer Team [Rei02b].
• A Graphical 3D Visualizer for simulated soccer games was developed and released [Lou02].

• Definition of new coordination protocols for our simulated soccer team (in the context of FC Portugal - New Coordination Methodologies Project).
• Enhancing the definition of a COACH UNILANG as a general language to enable a special agent ("coach") to supervise a team of co-operative robots.
• Research on opponent modeling and automated coaching and enhancement of our automated coach. We intend to develop a new graphical tool called Team Designer enabling easy definition of a complete soccer strategy by a human designer. This tool will be fused with our automated coach, with a game analyzer and with a graphical visualizer into a complete coaching environment.
• Increasing the co-operation with ISR-Porto (in the context of 5DPO and Portus projects) applying, to real robots, several methodologies developed for the simulated robots.
• Developing a Sony legged RoboSoccer team in the context of Portus and LEMAS projects (together with ISR-Porto).

D.1.3.4 Other Agent-based systems applications

Coordinator: Eugénio Oliveira

Research direction: To apply agent architectures, negotiation protocols and adaptation to specific application domains.

Communications network management

Research goal: To apply learning algorithms to improve resource allocation in multi-class packet switched networks. The system will be applicable to multi class settings where decision-making problems are exceptionally complex.

RECENT WORK (2002):

• We have tried several different methods for Time Series Analysis to deal with all the past information on traffic control in multi-class packet switched networks. The objective is to conceive a learning-based system that adapts to changing traffic conditions and predict traffic conditions based on past traffic patterns. Both Deterministic Linear and Non-Linear methods as well as Stochastic methods (ARMA, ARIMA, TES Models) have been used. TES Models have been reported as the most advantageous.

• We are now applying an Inductive Logic Programming algorithm [Alv02b] to time series data. The models generated by the ILP algorithm are expectd to give acurate predictions of the observed data over the "lead-time" period and they also should contribute to the human understanding of the network behavior. Many experiments have been done. The main conclusion points out the fact that using compositional modeling enables a wider coverage of the time series by the induced theory both for the training as well as test examples.

 

 

A complete multi-agent system managing the allocation of all available resources in multi-class packet switch networks and using the induced prediction capabilities will be specified and, hopefully, implemented.

RECENT WORK (2002):

• In the specification of the multi-agent system encompassing the needed functionalities for the Electrical Energy e-market, we have untill now emphasising security procedures, accountability of the communications, good performance and software portability. Also, integration with legacy systems has been privileged.
• The Agents' architecture has been proposed and all the interaction protocols specified. Giving the choices of using XML and FIPA-ACL, it was settled that message transfer should be made using HTTP POST requests (both from each agent to the facilitators and from this one to specific advisor agent). Also Client requests are made using CET requests. All interactions use MIME type text/XML.
• The slow process of standardization and wide acceptance of open protocols for secure data packet transfer induced by IETF (Internet Engineering Task Force) together with slow specification of message digital signature implementations creates problems in which concerns security policies selection.IPsec, SSL and TLS specifications have been under observation, comparing respective pros and cons.

• We are now implementing a prototype for the Electrical Energy e-Market agent-based system. We have selected the TLS/SSl protocol and, as for the message digital signatures is concerned, the open standards are being used. They rely on classical MAC and cryptography algorithms used in SSL. A first scenario will be specified to check secure and reliable agent interaction.

 

 

A secure Multi-Agent System framework making available negotiation algorithms tuned for this specific domain is to be achieved. We foresee the implementation of a prototype to showcase all the technological options.

Research & Development goals: To specify and implement a generic multi-agent system platform suitable for supporting automatic Travel Services Agency. This research has been motivated by the "Personal Travel Assistant" application from British Telecom and the Trading Agent Competition.

RECENT WORK (2002):

• We have designed a platform combining the distributed nature of a multi-agent system with the security and encryption facilities provided by web servers, separating data from knowledge and encouraging the use of distributed data structures in a concurrent, scalable, transaction-safe and remote-event generator common area. We also endow our agents with learning capabilities directed to two different aspects: Reinforcement Learning for bidding policies and a kind of Concept Learning technique for user profiling. The main features of the proposed architecture are agent communication through a common area, remote user access through servlets with authentication and encryption, data/knowledge separation as well as agent reputation assessment using customer satisfaction values. The functionality of all the proposed multi-agent system features is now being illustrated through an agent-based Travel Services application.
• The system allows flight and hotel booking from local or remote customers. There are three main types of agents: customer, company and hotel agents who represent the respective entities. There is also a facilitator, a press agent and a softbot. The facilitator is responsible for storing travel packages bundled by company and hotel agents. The press agent is an agent who will publish customer complaints as well as good impressions. It serves as a mean to establish company and hotel agent reputation. It has to be capable of extracting information from real world web pages updating company and hotel agent information systems.

• Agent reputation is a major asset in e-commerce applications. In this kind of applications there are customer agents trying to buy a certain good or service and supplier agents trying to sell it. Customer agents should use information about supplier agents' reputation in order to choose which supplier agent to buy from. Our proposal is that this reputation associated to supplier agents should be defined in terms of a subset of the cumulative function of customer agent satisfaction in every commercial transaction with that supplier agent. The agent satisfaction is defined as the difference between expected and real price of a certain good or service provided by a certain supplier agent in a commercial transaction.
• Also a complete scenario where gains from the agents learning features, concerning both user profiling and negotiation adaptation, can be highlited is to be specified.

D.1.3 NIAD&R: Plan for 2003