Transcript Multi-Agent Systems - AI-MAS - Universitatea Politehnica

Sisteme multi-agent
Universitatea “Politehnica” din
Bucuresti
anul universitar 2005-2006
Adina Magda Florea
[email protected]
http://turing.cs.pub.ro/blia_06
Curs 1





Motivatie pentru agenti
Definitii agenti
Sisteme multi-agent
Inteligenta agentilor
Sub-domenii de cercetare
De ce agenti?






Sisteme complexe, pe scara larga,
distribuite
Sisteme deschise si heterogene –
construirea independenta a componentelor
Distributia resurselor
Distributia expertizei
Personalizare
Interoperabilitatea sistemelor/ integrare
legacy systems
3
Agent?
Termenul agent este frecvent utilizat in:
• Sociologie, biologie, psihologie cognitiva, psihologie
sociala si
• Stiinta calculatoarelor  IA
 Ce sunt agentii?
 Ce sunt agentii in stiinta calculatoarelor?
 Aduc ceva nou?
 Cum difera agentii software de alte programe?
4
Definitii ale agentilor in stiinta
calculatoarelor

Nu exista o definitie unanim acceptata
De ce este greu de definit?
IA, agenti inteligenti, sisteme multi-agent
Aparent agentii sunt dotati cu inteligenta

Sunt toti agentii inteligenti?

Agent = definit mai mult prin caracteristici,
unele pot fi considerate ca manifestari ale
unui comportament inteligent



5
Definitii agenti

“Most often, when people use the term ‘agent’
they refer to an entity that functions
continuously and autonomously in an
environment in which other processes take
place and other agents exist.” (Shoham,
1993)

“An agent is an entity that senses its
environment and acts upon it” (Russell,
1997)

“Intelligent agents continuously perform three
functions: perception of dynamic conditions in the
environment; action to affect conditions in the
environment; and reasoning to interpret
perceptions, solve problems, draw inferences, and
determine actions. (Hayes-Roth 1995)”

“Intelligent agents are software entities that carry
out some set of operations on behalf of a user or
another program, with some degree of
independence or autonomy, and in so doing,
employ some knowledge or representation of the
user’s goals or desires.” (the IBM Agent)
7

“Agent = a hardware or (more usually) a software-based
computer system that enjoys the following properties:

autonomy - agents operate without the direct intervention
of humans or others, and have some kind of control over
their actions and internal state;
Flexible autonomous action

reactivity: agents perceive their environment and respond
in a timely fashion to changes that occur in it;

pro-activeness: agents do not simply act in response to
their environment, they are able to exhibit goal-directed
behaviour by taking initiative.”

social ability - agents interact with other agents (and
possibly humans) via some kind of agent-communication
language;
(Wooldridge and Jennings, 1995)
8
Caracteristici identificate
2 directii de definitie
 Definirea unui agent izolat
 Definirea agentilor in colectivitate 
dimensiune sociala  SMA
2 tipuri de definitii
 Nu neaparat agenti inteligenti
 Include o comportare tipica IA  agenti
inteligenti
9
Caracteristici agenti











Actioneaza pentru un utilizator sau un program
Autonomie
Percepe mediul si actioneaza asupra lui reactiv
Actiuni pro-active
goal-directed behavior vs reactive behaviour?
Caracter social
Functionare continua (persistent software)
mobilitate ?
inteligenta?
Scopuri, rationalitate
Rationament, luarea deciziilor
cognitiv
Invatare/adaptare
Interactiune cu alti agenti – dimensiune sociala
Alte moduri de a realiza inteligenta?
10
Mediul agentului
Proprietatile mediului
- Accesibil vs inaccesibil
Agent
- Determinist vs
nondeterminist
Sensor
intrare
Actiune
iesire
- Episodic vs non-episodic
- Static vs dinamic
Mediu
- Deschis vs inchis
- Contine sau nu alti agenti
11
Exemple de agenti?
Agenti inteligenti?




Thermostat
Calendar electronic
Lista emails
Sistem de control al traficului aerian
12
Exemple de agenti
Buttler agent




Imagine your very own mobile butler, able to
travel with you and organise every aspect of
your life from the meetings you have to the
restaurants you eat in.
The program works through mobile phones
and is able to determine users' preferences
and use the web to plan business and social
events
And like a real-life butler the relationship
between phone agent and user improves as
they get to know each other better.
The learning algorithms will allow the butler to
arrange meetings without the need to consult
constantly with the user to establish their
requirements.
13
NASA agents


NASA uses autonomous agents to handle tasks that appear
simple but are actually quite complex. For example, one mission
goal handled by autonomous agents is simply to not waste fuel.
But accomplishing that means balancing multiple demands, such
as staying on course and keeping experiments running, as well
as dealing with the unexpected.
NASA’s Earth Observing-1 satellite, which began operation in
2000, was recently turned into an autonomous agent testbed.
Image Credit: NASA
14
Robocup agents


The goal of the annual RoboCup competitions,
which have been in existence since 1997, is to
produce a team of soccer-playing robots that
can beat the human world champion soccer
team by the year 2050.
http://www.robocup.org/
15
Swarms




Intelligent Small World Autonomous Robots for Micromanipulation
A leap forward in robotics research by combining experts in microrobotics, in
distributed and adaptive systems as well as in self-organising biological
swarm systems.
Facilitate the mass-production of microrobots, which can then be employed as
a "real" swarm consisting of up to 1,000 robot clients. These clients will all be
equipped with limited, pre-rational on-board intelligence.
The swarm will consist of a huge number of heterogeneous robots, differing in
the type of sensors, manipulators and computational power. Such a robot
swarm is expected to perform a variety of applications, including micro
assembly, biological, medical or cleaning tasks.
16
Intelligent IT Solutions
Goal-Directed™ Agent technology.
AdaptivEnterprise™ Solution Suite
allow businesses to migrate
from traditionally static,
hierarchical organizations to
dynamic, intelligent distributed
organizations capable of
addressing constantly changing
business demands.
Supports a large number of
variables, high variety and
frequent occurrence of
unpredictable external events.
17
True UAV Autonomy



In a world first, truly autonomous, Intelligent
Agent-controlled flight was achieved by a
Codarra ‘Avatar’ unmanned aerial vehicle
(UAV).
The flight tests were conducted in restricted
airspace at the Australian Army’s Graytown
Range about 60 miles north of Melbourne.
The Avatar was guided by an on-board
JACK™ intelligent software agent that
directed the aircraft’s autopilot during the
course of the mission.
18
Sisteme multi-agent
Mai multi agenti intr-un mediu comun
Mediu
Zona de influenta
Interactiuni
19
SMA – mai multi agenti in acelasi mediu

Interactiuni intre agenti
- nivel inalt

Interactiuni pentru- coordonare
- comunicare
- organizare

Coordonare
 motivati colectiv
 motivati individual
-
scopuri proprii / indiferenta
scopuri proprii / competitie pentru resurse
scopuri proprii si contradictorii / competitie pentru resurse
scopuri proprii / coalitii
20

Comunicare
 protocol
 limbaj
- negociere
- ontologii

Structuri organizationale
 centralizate vs decentralizate
 ierarhie/ piata
abordare "agent cognitiv"
21
How do agents acquire intelligence?
Cognitive agents


The model of human intelligence and human perspective of
the world  characterise an intelligent agent using
symbolic representations and mentalistic notions:
knowledge - John knows humans are mortal
beliefs - John took his umbrella because he believed it was going to
rain





desires, goals - John wants to possess a PhD
intentions - John intends to work hard in order to have a PhD
choices - John decided to apply for a PhD
commitments - John will not stop working until getting his PhD
obligations - John has to work to make a living
(Shoham, 1993)
22
Premises

Such a mentalistic or intentional view of agents - a kind of
"folk psychology" - is not just another invention of computer
scientists but is a useful paradigm for describing complex
distributed systems.

The complexity of such a system or the fact that we can not
know or predict the internal structure of all components
seems to imply that we must rely on animistic, intentional
explanation of system functioning and behavior.
Is this the only way agents can acquire intelligence?
23


Comparison with AI - alternate approach of realizing intelligence - the
sub-symbolic level of neural networks
An alternate model of intelligence in agent systems.
Reactive agents

Simple processing units that perceive and react to changes
in their environment.

Do not have a symbolic representation of the world and do
not use complex symbolic reasoning.

The advocates of reactive agent systems claims that
intelligence is not a property of the active entity but it is
distributed in the system, and steams as the result of the
interaction between the many entities of the distributed
structure and the environment.
24
The wise men problem
A king wishing to know which of his three wise men is the wisest,
paints a white spot on each of their foreheads, tells them at least one
spot is white, and asks each to determine the color of his spot. After
a while the smartest announces that his spot is white
The problem of Prisoner's Dilemma
Outcomes for actor A (in hypothetical "points") depending on the combination of
A's action and B's action, in the "prisoner's dilemma" game situation. A similar
scheme applies to the outcomes for B.
Player A / Player B
Defect
Cooperate
Defect
2,2
5,0
Cooperate
0,5
3,3
25
The problem of pray and predators





Cognitive approach

Detection of prey animals
Setting up the hunting team; allocation of roles
Reorganisation of teams
Necessity for dialogue/communication and for coordination
Predator agents have goals, they appoint a leader that organize the
distribution of work and coordinate actions
Reactive approach
The preys emit a signal whose intensity decreases in proportion to
distance - plays the role of attractor for the predators
Hunters emit a signal which acts as a repellent for other hunters, so
as not to find themselves at the same place
Each hunter is each attracted by the pray and (weakly) repelled by the
other hunters
26

Is intelligence the only optimal action towards a a goal? Only rational
behaviour?
Emotional agents

A computable science of emotions

Virtual actors
– Listen trough speech recognition software to people
– Respond, in real time, with morphing faces, music, text, and speech

Emotions:
– Appraisal of a situation as an event: joy, distress;
– Presumed value of a situation as an effect affecting another: happy-for,
gloating, resentment, jealousy, envy, sorry-for;
– Appraisal of a situation as a prospective event: hope, fear;
– Appraisal of a situation as confirming or disconfirming an expectation:
satisfaction, relief, fears-confirmed, disappointment

Manifest temperament control of emotions
27
MAS links with other disciplines
Economic
theories
Decision theory
OOP
AOP
Distributed
systems
Markets
Autonomy
Rationality
Communication
MAS
Mobility
Learning
Proactivity
Cooperation
Organizations
Character
Sociology
Reactivity
Artificial intelligence
and DAI
Psychology
28
Areas of R&D in MAS
 Agent architectures
 Knowledge representation: of world, of itself, of the
other agents
 Communication: languages, protocols
 Planning: task sharing, result sharing, distributed
planning
 Coordination, distributed search
 Decision making: negotiation, markets, coalition
formation
 Learning
 Organizational theories
29
Areas of R&D in MAS
 Implementation:
– Agent programming: paradigms, languages
– Agent platforms
– Middleware, mobility, security
 Applications
– Industrial applications: real-time monitoring and management
of manufacturing and production process, telecommunication
networks, transportation systems, electricity distribution
systems, etc.
– Business process management, decision support
– eCommerce, eMarkets
– Information retrieving and filtering
– Human-computer interaction
– CAI, Web-based learning
- CSCW
– PDAs
- Entertainment
30