Auto-Organização
Manoel Teixeira
[email protected]
Sumário
• Motivação
• Visão Geral
• Padrões Básicos
• Padrões Derivados
• Referências
05/11/2015
Manoel Teixeira © LES/PUC-Rio
2
Motivação
• Operar em ambientes dinâmicos e heterogêneos e encarar o
desafio de mudanças freqüentes nos requisitos. Como em
sistemas ubíquos, biológicos e na computação autonômica.
• Deve ser flexível, robusto e capaz de se adaptar às
circunstâncias.
• A característica de um sistema ter uma resposta coletiva e
complexa decorrente das interações entre simples
componentes.
05/11/2015
Manoel Teixeira © LES/PUC-Rio
3
Motivação – SMA?
• As entidades autônomas são agentes
• SMA é um grupo de agentes cooperando entre si
• Comportamento macroscópicos usando apenas interações
locais entre agentes
05/11/2015
Manoel Teixeira © LES/PUC-Rio
4
Visão Geral – Auto-organização
• Definido como o processo ou o mecanismo que permite um
sistema mudar sua organização sem um comando externo
explicito
• Sistemas auto-organizáveis fortes
• Sistemas auto-organizáveis fracos
• Interações ocorrem localmente
05/11/2015
Manoel Teixeira © LES/PUC-Rio
5
Visão Geral – Auto-organização
• Propriedades:
– Inexistência de um controle externo – Obrigatória
– Controle descentralizado – Não obrigatória
– Operação dinâmica – Obrigatória
• Medidas/Métricas
– Capacidade de alcançar uma organização capaz de atender ao
objetivo do sistema como um todo a partir da inicialização do
sistema
– Capacidade de alcançar uma re-organização depois de uma
perturbação
– Nível de descentralização do controle
– Capacidade de contornar perturbações
05/11/2015
Manoel Teixeira © LES/PUC-Rio
6
Visão Geral – Auto-organização
• Emergência
• “O todo é maior que a soma das partes”. Holland, 1998.
Padrões Básicos
• São eles: (Gardelli, 2007)
– Replication Pattern
– Collective Sort Pattern
– Evaporation Pattern
– Aggregation Pattern
– Diffusion Pattern
05/11/2015
Manoel Teixeira © LES/PUC-Rio
8
Padrões Básicos – Replication
• Problemas:
– Como podemos reduzir o tempo de acesso às informações?
– Em caso de ataque ou falhas, como evitamos a perda de
informações?
• Trata os dados a serem replicados, GF
• Ação de coordenação: copia os dados localmente
• Regra de propagação: propaga para locais vazios na
vizinhança (abordagem flooding)
• Exemplos: Cache, RAID, Grid
05/11/2015
Manoel Teixeira © LES/PUC-Rio
9
Padrões Básicos – Collective Sort
• Problema:
– Ambientes multiagentes que não impõe restrições nos
repositórios de informações podem sofrer de overhead na
descoberta das mesmas
• Trata os dados a serem ‘ordenados’
• Ação de coordenação: mantém os dados se necessário
• Regra de propagação: propaga para os vizinhos
05/11/2015
Manoel Teixeira © LES/PUC-Rio
10
Padrões Básicos – Evaporation
• Problema:
– Ambientes multiagentes podem rapidamente ficarem
sobrecarregados de informações inseridas pelos agentes
• É agregado aos dados um peso/tempo
• Ação de coordenação: a falta ou o decremento dos dados
implicam em novas ações
• Regra de propagação: os dados propagados decrementam
os seus pesos localmente e nos vizinhos iterativamente até
alcançar o valor 0
05/11/2015
Manoel Teixeira © LES/PUC-Rio
11
Padrões Básicos – Aggregation
• Problema:
– Sistemas multiagentes de larga escala sofrem por conta do
grande número de dados gerados pelos agentes, que precisa
ser sintetizado
• Trata os dados a serem agregados, GF
• Ação de coordenação: reforço da ação pela presença da
informação
• Regra de propagação: reforça a informação
• Com o padrão Evaporation, forma-se um feedback loop
05/11/2015
Manoel Teixeira © LES/PUC-Rio
12
Padrões Básicos – Diffusion
• Problema:
– Em sistemas multiagentes onde agentes só podem acessar
dados locais, estes agentes sofrem da falta de informações
sobre os nós vizinhos
• É agregado aos dados um peso
• Ação de coordenação: fazem algo em virtude da nova
informação
• Regra de propagação: dados propagados (pelo ambiente)
decrementam seu peso localmente e incrementam nos
vizinhos
05/11/2015
Manoel Teixeira © LES/PUC-Rio
13
Padrões Derivados
• São eles: (De Wolf, 2007)
– Stigmergy / Gradient Field / Field-based coordination
• Evaporation + Aggregation + Diffusion (Gardelli, 2007)
– Pheromone Paths
• Evaporation + Diffusion
– Market-based coordination
• Aggregation
05/11/2015
Manoel Teixeira © LES/PUC-Rio
14
Padrões Derivados
Problem(s)
Solution
Pattern
Spatial Source to
Destination Routing,
Task Recruitment,
Relation Identification,
Integration of various
information Sources
Agents explicitly search for goals, tasks, or related items and drop
pheromones to form paths for other agents to follow to the goal or task.
Reinforcement of an existing path by other agents can be seen as a
reinforcement of the relation between source and destination.
Evaporation, Aggregation, and Propagation keep the pheromones up-todate and support integration of various information sources.
Digital
Pheromone
Paths
Spatial Movement,
Pattern Formation,
Structure Formation,
Routing, Integration of
Contextual Information
Spatial, contextual, and coordination-related information is automatically
spread/propagated by the environment as multiple computational fields.
Agents simply follow the “waveform” of these fields to achieve the
coordination task, no explicit exploration is needed. The spatial
information comes to the agents instead of agents explicitly searching.
Gradient Fields
Resource Allocation in
general (resource=task,
power, bandwidth,
space, time, etc.) ,
Integration of resource
Usage/Need Information
A virtual market where resource users sell and buy resource usage with
virtual currency. The price evolves according to the market dynamics and
indicates a high (high price) or low (low price) demand. This information is
used by agents to decide on using the resource or not. Economic market
theory states that the prices converge to a stable equilibrium.
Market-based
Coordination
Team-formation, Trust
and reputation
Agents put and modify tags on other agents and a team is formed by only
collaborating with agents with the same tag or some other condition. If
tags indicate how well agents behaved in collaborations with others then
trust and reputation information can be available.
Tags
Synchronisation,
Resource Allocation
A capability or a resource is represented by a token. Synchronisation
happens because only the holder can use the resource or executes a
certain capability. Tokens can be passed among agents to allocate the
resource or capability to others.
Tokens
…
…
…
Referências
•
Gatti, M. A. de C.; Lucena, C. J. P. de; Garcia, A.; A pattern Language for Self-Organizing
Systems. SASO 2009 (Submetido).
•
Gatti, M. A. C. ; Lucena, C.J.P. de . A Multi-Environment Multi-Agent Simulation Framework for SelfOrganizing Systems. In: The 10th Workshop on Multi-Agent-Based Simulation (MABS'09) at
AAMAS'09, 2009, Budapest. The Eighth International Conference on Autonomous Agents and
Multiagent Systems, 2009.
•
Jan Sudeikat and Lars Braubach and Alexander Pokahr and Wolfgang Renz and Winfried Lamersdorf.
Systematically Engineering Self–Organizing Systems: The SodekoVS Approach. In
Proceedings des Workshops über Selbstorganisierende, adaptive, kontextsensitive verteilte Systeme
(KIVS 2009 – March).
•
Luca Gardelli, Mirko Viroli and Andrea Omicini. Desing Patterns for Self-Organizing Multiagent
Systems. In 5th International Central and Eastern European Conference on Multi-Agent Systems.
25-27 September 2007, Leipzig, Germany.
•
T. De Wolf, and T. Holvoet, Design Patterns for Decentralised Coordination in Self-organising
Emergent Systems, Editors: Sven Brueckner, Salima Hassas, Màrk Jelasity and Daniel Yamins,
Engineering Self-Organising Systems: Fourth International Workshop, ESOA 2006, Future
University-Hakodate, Japan, 2006, Revised Selected Papers, Lecture Notes in Computer Science,
Volume 4335, 2007, pp. 28–49, Springer Verlag
•
Jan Sudeikat and Wolfgang Renz: "Toward Requirements Engineering for Self-Organizing
Multi-Agent Systems" in: Proceedings of the First International Conference on Self-Adaptive and
Self-Organizing Systems, 2007.
05/11/2015
Manoel Teixeira © LES/PUC-Rio
16
Referências
•
G. Di Marzo Serugendo, M.-P. Gleizes, A. Karageorgos. "Self-organisation and emergence in
MAS: an overview", Informatica 30(1): 45-54, Slovene Society Informatika, Ljubljana, Slovenia,
2006.
•
G. Di Marzo Serugendo, M.-P. Gleizes, A. Karageorgos. "Self-Organisation in MAS", Knowledge
Engineering Review 20(2):165-189, Cambridge University Press, 2005.
•
G. Di Marzo Serugendo. "Autonomous Systems with Emergent Behaviour". Chapter in
“Handbook of Research on Nature Inspired Computing for Economy and Management”. Jean-Philippe
Rennard (Ed), Idea Group, Inc., Hershey-PA, USA, pp. 429-443, September 2006.
•
T. De Wolf, Analysing and engineering self-organising emergent applications, Ph.D. Thesis,
Department of Computer Science, K.U.Leuven, Leuven, Belgium, May, 2007.
•
T. De Wolf, and T. Holvoet, Emergence Versus Self-Organisation: Different Concepts but
Promising When Combined, Engineering Self Organising Systems: Methodologies and
Applications (Brueckner, S. and Di Marzo Serugendo, G. and Karageorgos, A. and Nagpal, R., eds.),
Lecture Notes in Computer Science, 2005, Volume 3464, May 2005.
A Pattern-Based Framework to Build SelfOrganization Multi-Agents Systems
Fim
Manoel Teixeira de Abreu Netto
[email protected]