TAG | software agent

Dec/09

What is a Software Agent?

0 Comments | Posted by Chris Fournier in Software Agents

What is a software agent? Previously I had used the term without actually defining what it is, is not, or what makes up a software agent.

Breaking it down

To define the term ’software agent’, let’s first break it into it’s parts. The word ‘software‘ should be obvious, it’s a computer program that executes instructions on a machine. The word ‘agent‘ however has a multitude of meanings depending upon the area of research that it is being used in. Researchers who study ’software agents’ also have no claim over the word ‘agent’, as H. S. Nwana investigates:

“…agent researchers do not ‘own’ this term in the same way as fuzzy logicians/AI researchers, for example, own the term ‘fuzzy logic’ – it is one that is used widely in everyday parlance as in travel agents, estate agents, etc.” [Nwana]

‘Agent’ is an everyday word which has been picked up by researchers to describe all manner of software systems, and even among researchers, it’s definitions are many. Does an agent inhabit a virtual, or physical world? If it is in a physical world, why is it not then termed a ‘robot’? There are also many adjectives that can come before the word ‘agent’, which make pinning down even a specific contextual definition difficult:

“… search agents, report agents, presentation agents, navigation agents, role-playing agents, management agents, search and retrieval agents, domain-specific agents, development agents, analysis and design agents, testing agents, packaging agents and help agent.” [Nwana]

WordNet provides a number of definitions for the term ‘agent’, and one that is applicable to the context we desire to describe is that an agent is:

“a representative who acts on behalf of other persons or organizations” [WordNet]

Perhaps more precise, but somewhat confusing to those uninitiated into the realm of computational linguistics, an agent could also be defined as:

“the semantic role of the animate entity that instigates or causes the hapening[sic] denoted by the verb in the clause” [WordNet]

Along these lines, and adding to our context the domain of software, the words ‘representative’, and ‘animate entity’ are both fitting descriptions of a property that many researchers consider software agents to have: autonomy.

Nwana explains that when pressed for a definition for ‘agent’, it can be said to be “a component of software and/or hardware which is capable of acting exactingly in order to accomplish tasks on behalf of its user.” [Nwana]. This definition is fitting, but not specific, and does not capture the fact that the term ‘agent’ is really an “umbrella term, meta-term or class, which covers a range of other more specific agent types…” [Nwana].

The term ‘agent’ has too many uses, interpretations, and no general meaning, making it’s usage alone insufficient to describe the type of artificial intelligence implementation we wish to refer to. A specific meaning of the term, in a particular context, can be made when it is paired with the adjectives ‘software‘, and ‘intelligent‘, to make ‘intelligent software agent‘. This adds to the term the context of being a piece of software, and an implementation of artificial intelligence. One troubling property about this context though is that it relies upon the definition of the term ‘artificial intelligence’, which is itself contested! We then cannot rely solely upon this context to supply our definition of the term ‘intelligent software agent’, and to that end a number of researchers have sought to provide a thorough definition of what a software agent is.

For the duration of this article we will concern ourselves with ‘intelligent software agents‘, which are often referred to in short form as ‘software agents‘.

Definitions

Wooldridge & Jennings

The definition chosen for the Software Agent Design course I took at Carleton University in the fall of 2009 was that of N. R. Jennings & M. Wooldridge, as described in their paper ‘A Roadmap of Agent Research and Development’:

“An agent is a computer system, situated in some environment, that is capable of flexible autonomous action in order to meet its design objectives.” [Wooldridge & Jennings]

This definition has the desirable properties of including: the physical system a piece of software runs upon and interacts with, the concept of autonomy, and the concept of a designed objective. Prof. Esfandiari provides a succinct summary on his course website [Esfandiari] of the details of these properties as defined by [Wooldridge & Jennings]:

Situated: It receives sensory input from it’s environment, and can perform actions that can change it’s environment in some manner. Some important properties of the environment include whether it is:
- Accessible, or inaccessible;
- Deterministic, or non-deterministic;
- Static, or dynamic; and
- Discrete, or continuous.
Autonomous: It has no direct intervention from humans, and has control over its own actions, and internal state.
Flexible: When interacting with it’s environment, it is:
- Responsive to change (environmental or conceptual);
- Proactive (recognizes a potential future situation, and acts to prevent or support it); and
- Social: interactive with humans, and other agents (a research area entitled multi-agent systems).

Nwana

A competing definition was proposed by Nwana when describing the different types (typology) of agents that existed at the time. He starts by classifying agents by their mobility, either static or mobile, “i.e. by their ability to move around some network ” [Nwana]. Agents are then classified as either deliberative or reactive.

Deliberative agents are those that have some form of internal method of reasoning, and storing information, and they engage in planning. Reactive agents are those that have no method of reasoning, but may store a small amount of information (for example: a light switch can be either on, or off, which stores 1 bit of information). Though they are agents, they are not intelligent, and therefore reactive agents could be discarded from the definition of a software agent because of their lack of deliberation (or learning). Additionally, reactive agents are not a novelty, and exist everywhere in the form of simple devices that are under the control of a human (not autonomous).

Nwana identifies a minimal list of attributes which deliberative software agents should ideally possess: autonomy, learning and cooperation. This list of attributes shares explicitly with Wooldridge & Jenning the autonomy property, and implicitly the other two. Software agents could then be classified as being of differing types depending upon the combination of attributes they posses:

Software Agent
Figure 1 – Nwana’s agent typology [Nwana]

Comparison

To necessitate that a software agent must have cooperation as an attribute is in my opinion too broad, but it does classify a large number of software agent’s, and is analogous to Wooldridge & Jenning’s property of flexibility, particularly socialization. Take for example a peer to peer network, a piece of software (like a bit-torrent client) interacts with other peers (bit-torrent clients), to retrieve the whole of a particular file. Such a piece of software should probably not be considered a software agent, because the file it fetches, and the central location in begins it’s search, is specified directly by a human. It is not autonomous.

Nwana’s ‘learning’ property is analogous to Wooldridge & Jenning’s flexibility definition, specifically that of responsiveness to change. If an agent does not learn, or is not flexible, then it does not have any internal method of reasoning, or internal state, and could be considered a reactive agent, and not a software agent.

The definition put forth by Wooldridge & Jenning appears to encompass much of Nwana’s typology, and more (situatedness), and in my opinion produces a list of entities that could truly be described as intelligent, and independent. It seems fitting then to use Wooldridge & Jenning’s definition when qualifying something as an intelligent software agent.

More boldly, Wooldridge & Jenning’s definition could potentially be used to describe a living system such as a human, which is used in countless research domains as the golden standard for comparisons when testing for intelligence. If one was to think of the biological body of a human as a computer, their current knowledge, experience, and the objective of the organism as it’s software, and being situated in the environment that is this universe, such an organism would meet Wooldridge & Jenning’s definition of a software agent. This is interesting, because much of the work of artificial intelligence aims to produce something as sophisticated as a human.

Structure

A software agent itself could be conceptualized as a system containing two black boxes: the environment, and the software agent itself. The environment produces events, and receives actions, whereas the software agent receives events (as input), and produces actions (as output), as shown below in Figure 2.

Figure 2 – Software agent diagram (adapted from [Wooldridge])

This definition is practical in that it allows for the specific definition of the environment (eg: an email inbox), and the software agent (eg: a spam filter). A finite set of events (reception of email), and actions (deletion as spam, categorization as potential spam) could be defined, and the order of these is defined by the entity producing them.

How does a software agent determine what action to perform, given a sequence of events? That is up to the mechanisms implemented inside the software agent for reasoning, and memory. The abstract representation defined in [Wooldridge] can be seen outlined in the remainder of this section:

An agent’s environment could contain “a finite set $E$ of discrete, instantaneous states:” [Wooldridge]

$E=\{ e,e^{`},\ldots\}$

Agents then “have a repertoire of possible actions available to them, which transform the state of the environment.” [Wooldridge]

$Ac=\{\alpha ,\alpha^{`},\ldots\}$

A run, $r$ , could then be defined as a sequence of environment states, precipitated by various actions (one of which could represent that no action has taken place):

$r : e_0 \overset{\alpha _0}{\rightarrow} e_1 \overset{\alpha _1}{\rightarrow} e_2 \overset{\alpha _2}{\rightarrow} e_3 \overset{\alpha _3}{\rightarrow} \ldots \overset{\alpha _{u-1}}{\rightarrow}e_u$

Now, let:

$\mathcal{R}$ be all the possible finite sequences over $E$ and $Ac$
$\mathcal{R}^{Ac}$ be the subset of all $\mathcal{R}$ that end in an action; and
$\mathcal{R}^{E}$ be the subset of all $\mathcal{R}$ that end in an event.

We can then define a state transformer, our environment black box, as taking a series of actions, and producing a particular realized event:

$\tau : \mathcal{R}^{Ac} \rightarrow \varrho (E)$

Further, we can define a state transformer, our software agent, as taking a series of events, and producing a particular action:

$Ag : \mathcal{R}^{E} \rightarrow Ac$

But how do we choose which action to execute? We could define a utility function $u$ to evaluate the utility of a particular environment state as a real number:

$u : E \to \mathbb{R}$

The utilities of various environment states could then be compared, and an optimal, and reachable, environment identified as a goal. This doesn’t offer much in the way of analyzing, and learning, from sequences of events, so instead $u$ could be defined to evaluate the utility of entire runs:

$u : \mathcal{R} \to \mathbb{R}$

Now all you must do is implement a $u$ function, an intelligent $Ag$ function, and model your environment as a $\tau$ function, and then you have a fully functional software agent. In reality though, it’s not quite as easy as that.

Summary

A software agent is not a:

Reactive agent (eg: light switch);
Statistical classifier (they can learn, but until they are situated as part of a larger system, are generally supervised by a human, and not autonomous); or an
Application like Microsoft Word, or Excel.

A software agent could be a:

Spell checker (if it can learn new words from a human, and perform it’s own reasoning as to whether a word is spelt or used correctly or not, especially if it could converse with other spell checkers interacting with other humans to find a consensus);
Bayesian email spam filter (because it meets Wooldridge & Jenning’s criteria, clearly demonstrating flexibility through learning what is and is not spam).

A software agent is:

Situated in some environment, that is capable of flexible autonomous action in order to meet its design objectives.” [Wooldridge & Jennings];
Clippy (an annoying assistant accompanying earlier versions of Microsoft Office products that watches a human, determines that they may need help performing an action, interacts with the human to automate their task, and learns mostly through customer complaints that it should not pop up);
Always debatable as to whether such software fits the definition, primarily because of the flexibility property required, and whether the degree of learning implemented is enough to adequately react to it’s environment, and how autonomous the software truly is.

References

[Nwana] H. S. Nwana, and M. Heath, “Software Agents: An Overview,” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.660, 2006.

[Wooldridge & Jennings] N. R. Jennings, K. Sycara, and M. Wooldridge, 1998. “A Roadmap of Agent Research and Development,” Autonomous Agents and Multi-Agent Systems 1, 1, Jan. 1998, 7-38.

[WordNet] Princeton University, 2006. “WordNet Search – 3.0,” http://wordnetweb.princeton.edu/perl/webwn?s=agent; accessed Dec. 23, 2009.

[Wooldridge] M. Wooldridge, 2009. “An Introduction to MultiAgent Systems,” Second Edition, Wiley.

[Esfandiari] B. Esfandiari, 2008. “AgentDefinition,” http://netman.sce.carleton.ca:8080/cgi-bin/agentcourse.cgi?AgentDefinition; accessed Dec. 23, 2009.

A software agent using bayesian trust, and decision tree learning

0 Comments | Posted by Chris Fournier in Projects, Software Agents, trust

As a group term project for my Software Agents Design course, Catalin Patulea, Mike Lepard, Pierre Dinnissen and I developed a software agent using Java for the Agent Reputation and Trust (ART) Testbed, called the CCMPAgent. Unlike most academic software projects, our professor encouraged us to not only develop an agent, but also separate the code into distinct, reusable components with a certain degree of software quality. Our particular agent had two interesting components: a WEKA based learning framework; and the bayesian trust framework. The learning framework was required so that the agent could understand how to act inside the ART testbed (which is essentially a game setting, pitting all the software agents playing against each other), and the trust framework was required to by the agent to keep track of whether it should cooperate, or not, with the other agents it was competing against. To add to the quality, we wrote javadoc documentation, performed unit testing on key components, and wrote documentation that described the system.

The ART testbed

The ART testbed is designed to test a software agent’s ‘trust’ functionality. The agents all participate in a game, and interact with eachother, where the goal is to end up with the most virtual currency at the end. Specifically, it is an art trading game:

“Clients request appraisals for paintings from different eras; if an appraiser agent does not have the expertise to complete the appraisal, it can request, at a price, opinions from other appraiser agents. Appraiser agents may also purchase from each other reputation information about other appraisers. Appraiser agents must decide when, and from whom, to request opinions and reputation information to generate accurate appraisals for clients. Appraisers receive more clients, and thus more profit, for producing more accurate appraisals. The winning appraiser agent is selected as the appraiser with the highest bank account balance.” [ART]

Navigating ART is a difficult task, and if you too want to develop an agent then read the: game description, ART usage documentation, ART 2.1.1 javadoc, and start by looking at our SimpleCCMPAgent as an example.

What is trust?

Trust between software agents is a measurement of the degree to which a software agent trusts the other entities it interacts with. How do we determine whether we can interact with another, in a particular context, and trust that we will have a satisfactory encounter? Will another agent lie to us if we ask them a question, or will they cooperate? How do we take the information we know about another and determine whether we should trust them? Some information we could be provided with includes satisfaction of past encounters, recommendations from agents about other agents, and initial preconceptions.

Trust can be applied to P2P networks to determine whether we trust particular nodes to provide files, or other information. Does it have a fake file? Or does it have a real file, but is the node’s network connection unstable, making it untrustworthy?

If you want to add trust metrics to your software, there are many existing trust frameworks to choose from, including Peer Trust, Advogato, Eigen Trust, and Bayesian Trust. To handle trust in our agent, we chose to implement Bayesian Trust, detailed in the paper entitled “B-trust: Bayesian trust framework for pervasive computing” [Quercia et al.] by D. Quercia, S. Hailes, and L. Capra. We chose this paper because it’s data structures scale linearly with respect to the number of other agents tracked; and it embodies what the paper describes as three main properties of trust:

Subjectiveness: identical actions taken by different agents may lead to different levels of trust;
Context-dependence: trust in one context does not necessarily transfer to another; and
Dynamism: trust should increase after successful observations, and decay over time.

After implementing this paper, we enabled our agent to track the trustworthiness of the other agents it interacted with in the ART testbed (given recommendations from other agents, which may have been untrustworthy themselves, and direct interactions). For further information on trust, see the slides of the talks by Steve Marsh, and his other publications.

Bayestrustlib

A few changes were made in the math seen in the original B-trust paper, and are summed up in our term report [pdf] on the agent for our class [CCMPAgent]. The framework is written in Java (1.5), and is licensed under the BSD license. You can download the bayestrustlib [jar] itself, view the source, and the javadoc documentation needed to use it. The bayestrustlib project itself contains 58 unit tests to verify the underlying math.

Usage

Using the bayestrustlib is quite easy. Simply add bayestrustlib.jar to your project, and create a new instance of the BayesTrust class. You must specify the number of levels of trust your agent will understand, and all the potential contexts (interactions) you will have.

// 0 = untrustworthy, 1 = moderately trustworthy, 2 = trustworthy

int nLevels = 3;

List contexts = new LinkedList();

Context c1 = new Context("asking for a recommendation");

Context c2 = new Context("asking for an appraisal");

contexts.add(c1);

contexts.add(c2);

BayesTrust trust = new BayesTrust(nLevels, contexts);

When you meet a new entity (agent, or human) that you intend to interact with, you have to notify the library about it’s name.

Peer p1 = new Peer("agent 1");

Peer p2 = new Peer("agent 2");

trust.addPeer(p1);

trust.addPeer(p2);

If you have an encounter with an entity, you can record your satisfaction in the encounter with the entity as a continuous value between 0 and 1 (which should relate to your trust levels you have defined).

double satisfaction = 1.0/(nLevels - 1) ; // Moderately trustworthy

trust.storeEncounter(c1, p1, satisfaction);

If you ask an entity for a recommendation about another entity, you can record that value as a continuous value between 0 and 1.

double recommendation = …

trust.storeRecommendation(c1, p1, p2, recommendation);

After collecting data, you may wish to determine your level of trust in another agent for a particular context. This allows you to determine whether you should interact with a particular entity, and situation.

double c1p1trust = trust.getCondensedOverallTrust(c1, p1);

But how do we know that we have collected enough information to trust this trust value? Trust values are initialized to a trust value that has low confidence. After calls to storeEncounter(), and storeRecommendation(), we can assume that our confidence should increase. To measure the confidence in a trust value, we measure the variance of our probability mass function of our trust values (more details on this can be found in the Bayesian Trust Framework, Theory section of our term report [pdf]), which can be obtained by calling the following API:

double c1p1trust = trust.getOverallTrustConfidence(c1, p1);

That covers the basic functionality of bayestrustlib, and don’t worry, if you make a mistake on the input values, a number of custom exceptions will inform you of how you went wrong. For a complete example of an implementation, see the BayesTrustNetwork class of the CCMPAgent agent project.

References

[ART] Agent Reputation and Trust (ART) Testbed.Game Description. http://megatron.iiia.csic.es/art-testbed/competition_rules.htm; accessed Dec. 15, 2009, Feb. 28 2008.

[Quercia et al.] D. Quercia, S. Hailes, and L. Capra, “B-trust: Bayesian trust framework for pervasive computing,” in iTrust, pp. 298-312, 2006.

[CCMPAgent] C. Patulea, C. Fournier, M. Lepard, and P. Dinnissen, “SYSC 5103 Term Project: CCMP Agent for the ART 2.1.1 Test Framework.” http://cloud.github.com/downloads/cfournie/ccmpagent/report.pdf; accessed Dec. 15, 2009, Dec. 7 2009.

art, b-trust, bayesian trust, java, software agent, trust, weka

λx.Blog(x)(Cfournie) | A.I. in Ottawa, Canada

Recent Posts

Twitter Updates

TAG | software agent

What is a Software Agent?

Breaking it down

Definitions

Wooldridge & Jennings

Nwana

Comparison

Structure

Summary

References

Further reading

A software agent using bayesian trust, and decision tree learning

The ART testbed

What is trust?

Bayestrustlib

Usage

References

Categories

Archives