Download Agents and Multi-Agent Systems Carles Sierra

AAMAS Tutorial. Course. Carles Sierra.
Lecture 12: Evolutionary
computing and agents
1
IIIA-CSIC
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Lecture plan
Autonomous robots and evolution
Evolution and negotiation
Evolution in agent societies
2
AAMAS Tutorial. Course. Carles Sierra.
AUTONOMOUS ROBOTS AND
EVOLUTION
3
IIIA-CSIC
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Evolutive design. The Golem Project
• Population = candidate robots.
• Made of basic blocks: bars,
actuators and neurons.
• Initialy: empty robots.
• Key: eleccion of blocks and
operators.
• With greater simplicity in the
blocks, lower inductive bias.
• Co-evolution of structure and
control.
• The evolution of control leads
to complex neuronal structures.
4
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Typical evolutionary process
Initialy: 200 robots.
Fitness: locomotion.
300-600 generations.
Co-evolution of
morphology and
control.
• Many generations
before getting any
movement. (A minimal
neural net must be in
place.)
•
•
•
•
5
Para ver esta pel’cula, debe
disponer de QuickTimeª y de
un descompresor .
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Evolutive patterns
• Convergence
– fitness
proportional
selection
• Divergence
• Especiation
• Massive
extintion
6
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Evolution example (I)
7
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Evolution example (II)
8
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Fitness evolution
• ‘jumpy’ progress
• Progress decreces when fitness increases.
9
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
The Golem Project
Para ver esta pel’cula, debe
disponer de QuickTimeª y de
un descompresor Cinepak.
10
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Evolution of a Lego crane
• 1/2 kg weight
• The rotating based was an input modeled as a set
of constraints.
• The program generates a contruction map.
Para ver esta pel’cula, debe
disponer de QuickTimeª y de
un descompresor .
11
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Evolution of a bridge
Para ver esta pel’cula, debe
disponer de QuickTimeª y de
un descompresor GIF.
12
13
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
NEGOTIATION AND EVOLUTION
14
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Negotiation scenario
15
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Objectives
• To study negotiation techniques in multiagent systems.
• To analize the negotiation dynamics in agent
populations through an evolutionary approximation.
Recall the negotiation model introduced before ...
16
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Negotiating genes
Issues’ genes
17
Strategic genes
Tactic genes
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Fitness function
• We consider the average of the following
function over the results of negotiation rounds
with other agents in the population.
• Where
18
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Method
19
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Experiments
• Parameters
– Crossover probability: 1/2
– Crossover points: 6
– Mutation probability: 0.02
– Populations: |S| = |B| = 100
– Number of experiments: 100
• Scenarios
– Homogeneous strategies: Agents use a
single tactic
– Flexible strategies: Agents combine
20
tactics
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Results (I)
Successive generations of agents adapt to the negotiation
environment. For instance, when concessive agents negotiate
with boulware agents, the value of the beta parameter decreases:
21
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Results (II)
• Homogeneous strategies
– The amount of time is relevant.
– Tactics based on resources are very succesful
for short times, with longer times concessive
tactics improve.
– When time is larger the imitative tactics also
improve.
• Flexible strategies
– No clearly dominant strategies.
– Flexible strategies are more robust.
22
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Agent architectures
23
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
CBR negotiating agent
24
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Fuzzy agents
25
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Populations
26
AAMAS Tutorial. Course. Carles Sierra.
EVOLUTION IN AGENT
SOCIETIES
27
IIIA-CSIC
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
SADDE Methodology
SIMILE
(simulator and
graphic editor)
EBM
(SIMILE)
EIM
(ISLANDER-)
ISLANDER
(verifier and
ghaphic editor)
EIM
(ISLANDER)
MABLE
(simulator)
AM
(MABLE)
AGEN T
GENERATOR
AM
(PROLOG)
PROMELA
TRANSLATOR
AM
(Promela)
MAS
Synthesizer
Multiagent
system
(PROLOG)
Promela
(Model checker)
Model
Checking
Results
JADE+PROLOG
(Laboratory)
MILORD
(editor and
simulator)
Experiment
results
Design
rules
(MILORD)
Development
complete
28
To be implemented
Under development
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
(from MAS Synthesizer)
Multiagent
System
(PROLOG)
JADE+PROLOG
(Laboratory)
MILORD
(editor and
Simulator)
Experiment
results
We don’t know how to start!
We need a mechanism that guides our initial
movements in the right (or potentially right)
direction.
29
Design
Rules
(MILORD)
?
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
(from MAS Synthesizer)
Multiagent
System
(PROLOG)
JADE+PROLOG
(Laboratory)
Genetic
Algorithm
Experiment
results
Conclusions
from
GA analysis
30
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
(from MAS Synthesizer)
Multiagent
System
(PROLOG)
Experiment
results
JADE+PROLOG
(Laboratory)
Conclusions
from
GA analysis
31
MILORD
(editor and
Simulator)
Design
Rules
(MILORD)
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Genetic algorithm cycle
The individuals
are generated
•Each individual is a complete multi-agent
system.
producers
Population
32
manufact.
consumers
IIIA-CSIC
AAMAS Tutorial. Course. Carles Sierra.
Genetic algorithm cycle
The individuals
are generated
•One gen in a chromosoma represents one
agent in the multi-agent system.
...
...
...
gen
Chromosoma
producers
33
manufact.
consumers
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
Supply chain EBM
34
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
EBM Cash prediction
35
AAMAS Tutorial. Course. Carles Sierra.
IIIA-CSIC
EBM Cash prediction
36