Transcript PPT

peer-to-peer and
agent-based computing
Agents & Multi-Agent
Systems: Introduction
Agents and Multi-agent Systems (MAS)
• Software agents are programs with unique features
such as:
– Autonomy (no/little human input or interference)
– Proactiveness (act in an anticipatory fashion, i.e., before
things happen)
– “Social skills” (agents communicate)
• A MAS has many autonomous entities (the agents)
interacting with one other to achieve
– Conflicting goals (competition) or
– Joint goals (cooperation)
Inevitable conclusions:
• not every program is a software agent
• not every IT/e-business solution requires a MAS
peer-to-peer and agent-based computing
2
Agents, MASs & AI
• Classical Artificial Intelligence (AI) concentrates on
modelling single agents:
– A single, stand-alone expert system
– A single, stand-alone natural language processing
system
– A single, stand-alone robot that learns
– ...
• Work on agents & MASs investigate scenarios in
which various agents communicate:
– Individual agents do not have to be clever…
– The “intelligence” may only arise in the agents’
collective behaviour, as in, for instance, an ant colony
peer-to-peer and agent-based computing
3
The goal of this part of the course is…
Introduce aspects of agents and MAS:
1. Case studies and technologies (platforms,
languages)
2. Communication languages and protocols
3. Auctions and voting mechanisms
4. Negotiation
5. Game theory
peer-to-peer and agent-based computing
4
Agent-Oriented Programming
• Computer science has a number of goals:
– Develop human-oriented, ubiquitous systems,
– Interconnect disparate elements,
– Create systems to make autonomous and intelligent
decisions about delegated tasks.
• Programming has progressed through:
– sub-routines, procedures and functions,
– abstract data types, and objects
– to agents
peer-to-peer and agent-based computing
5
Agents in e-Commerce
Software agents can be delegated tasks such as:
• Information retrieval
• Finding the cheapest/best supplier
• Maintaining a company’s stock of components
• Buying and selling in an energy market
• Management & coordination of business processes
peer-to-peer and agent-based computing
6
Agents in e-Science
Software agents can be delegated tasks such as:
• Finding an appropriate computational resource
• Distributing results of scientific experiments
• Negotiating the provision of a high-demand tool
• Management & coordination of scientific processes
peer-to-peer and agent-based computing
7
How to build agents & MASs…
• How do we build software agents to carry out the
tasks delegated to them?
– How do we build agents that can interact with others in
order to do what they were told to…
– We may not have control as to how the other agents
“out there” will behave!
• How do we engineer a MAS consisting of many
independent components that interact?
– How do we address features from individual agents as
well as global properties of the group of agents?
– Do we write each agent individually? There may be
100’s of them!
• Let’s make this discussion more concrete:
– Scenario: “agentifying” Microsoft’s Outlook…
peer-to-peer and agent-based computing
8
How to build agents & MASs… (Cont’d)
• Microsoft’s Outlook offers means for people to share their
diaries:
– A person can organise a meeting and invite other people to
attend it
• An invitation can either be accepted or refused
– If refused the person who is trying to organise the meeting will
need to try again, and tell everyone who has accepted that the
meeting will be changed, etc.
– This is a tedious process which can take a long time!
• Would it not be better if the people who could not attend
suggested a time that would suit them?
– This task could, however, be delegated to a program!
• How would you program this?
peer-to-peer and agent-based computing
9
How to build agents & MASs… (Cont’d)
• We would want the following to happen:
Can we meet at 2PM tomorrow?
Sorry, I can’t. What about 3PM? Failing
that, would Monday be any good?
Dead easy:
• A program provides communication between running copies of Outlook
• Which language?
• This program exchanges messages
• Which kinds of messages are permitted and in which order?
• Can we ensure the “dialogue” always terminates?
• Which setup? Peer-to-peer? Client-server?
• Will we allow “foreign” agents to join in?
peer-to-peer and agent-based computing
10
How to build agents & MASs… (Cont’d)
• However, the solution should scale up:
peer-to-peer and agent-based computing
11
The Agent Concept
•
•
•
•
•
What is an agent?
Agent characteristics
Agents and other things
Environment characteristics
The “intentional stance”
peer-to-peer and agent-based computing
12
What is an Agent?
• Main point:
– Agents act independently, controlling their internal state
• Agents are capable of autonomous action in some
environment within which they “live”
– Agent’s actions may affect/change the environment
– Environment, on its turn, is the input to the agent
peer-to-peer and agent-based computing
13
The Environment
Environments are:
• The physical or virtual space within which the agent
works
• Examples:
– A program controlling a door mechanism
– A program roaming the Web for cheap flights to Dublin
peer-to-peer and agent-based computing
14
Agents: reactivity
• If the environment is fixed and
– Only the agent can cause the environment to change
– The effects of the actions are stable
then the system may execute blindly.
– E.g., a thermostat and a heater
• However, realistic environments are not like that:
– Other factors influence the environment
– The effects of actions may be unstable
– E.g., agents in a network of computers
• Interesting environments are dynamic
peer-to-peer and agent-based computing
15
Agents: reactivity (Cont’d)
• Software for dynamic environments is hard to build!
– It must expect the unexpected & possibility of failure
• Reactive system:
– Maintains an on-going interaction with its environment
– Responds to significant changes in time for the response to be
useful (no point in responding 3 hours later…)
• Given a stimulus, agents respond with a designated
response:
– Programming by events outwith the agent’s control
– If the environment is very diverse then we cannot foresee all
possible events…
– Therein lies the challenge and beauty of agent design
peer-to-peer and agent-based computing
16
Agents: goal-directed behaviour
• Agents monitor and react to environment…
• On top of that, we want our agents to achieve the
goals we delegated to them:
– E.g., a shop-bot should text us with a deal on tickets
• This feature of agents is called proactiveness:
– When left on its own, an agent that has programmed
goals, will strive to achieve them
– It is part of its design to actively pursue its goals
peer-to-peer and agent-based computing
17
Agents: social ability
• A lonely agent is a contradiction:
– Many agents can achieve something bigger than each of them
can do in isolation…
• The world is a large multi-agent environment:
– People, Java programs, Web services, etc.
– The actions and goals of other agents must be taken into account
when we are designing our agents
– Some goals can only be achieved with the cooperation of other
agents; other goals may lead to competition!
• Agents should be endowed with social abilities:
– The ability to interact with other agents meaningfully
– Direct or indirect communication (message-passing)
– Terms of a cooperation can be negotiated and agreed
peer-to-peer and agent-based computing
18
Agents: other features
Agents may also possess
– Mobility: the ability to move around machines
– Veracity: they will not knowingly provide false
information
– Benevolence: they will, if possible, do what is asked
– Rationality: an agent will act towards achieving its goals,
and not act to make these goals unachievable
– Learning/adaptation skills: agents improve their
performance from experience
peer-to-peer and agent-based computing
19
Reading List
• An Introduction to Multi-Agent Systems, M.
Wooldridge, John Wiley & Sons, 2008
• Is it an agent or just a program? S. Franklin and A.
Graesser, available on-line at
http://www.msci.memphis.edu/~franklin/AgentProg.html
• Artificial Intelligence: A Modern Approach (2nd Ed.),
S. Russell and P. Norvig, Prentice-Hall, 2003.
• Multi-Agent Systems: A Modern Approach to
Distributed Artificial Intelligence, G. Weiss (editor),
MIT Press, 1999.
• Multi-Agent Systems: An Introduction to
Distributed Artificial Intelligence, J. Ferber, AddisonWesley, 1999.
peer-to-peer and agent-based computing
20