Evolução de Criaturas Virtuais
Um trabalho de Karl Sims
(1994)
Estrutura da apresentação
• Introdução
• Criaturas Virtuais
– Estruturas Genéticas
– Estruturas Morfológicas
– Estruturas Controle
•
•
•
•
•
Processo Evolutivo
Simulações e Resultados
Trabalho Futuro
Conclusões
Video
1/24
Objectivos
• Na área da animação digital, existe um
trade-off entre complexidade e controle.
• Seria interessante poder construir de
forma simples entidades complexas mas
com comportamentos realistas.
• Aplicação de técnicas de optimização
baseadas em algoritmos genéticos e a
teoria de evolutiva de Darwin.
(sobrevivência do mais apto)
2/24
Trabalho Realizado
• Uma linguagem para representação de
genomas de criaturas virtuais.
• Um ambiente virtual 3D configurável, para
testar as criaturas.
• Mecanismos para gerar e testar criaturas
virtuais.
• Um conjunto de simulações para observar
o percurso evolutivo destas criaturas em
várias tarefas.
3/24
Criaturas Virtuais: genoma
• Genoma é composto por um grafo orientado.
• Genoma codifica a morfologia da criatura mas
também as estruturas de controle desta.
• Possibilita a existência de ciclos que podem
gerar estruturas com feedback.
• Genoma contem parâmetros de controle para a
construção de criaturas como por exemplo:
dimensões de uma componente, pontos de
contacto entre estruturas...
4/24
Exemplo de uma representação de
um genoma
Neurónios Centralizados
Neurónios
Morfologia
5/24
Criaturas: Morfologia
• Criatura é composta por uma hierarquia de
partes rígidas 3D conectadas.
– Potencialmente utilizando recursividade
• Cada ligação entre partes rigidas possui
características próprias (também definidas no
genoma), nomeadamente um tipo, e grau de
liberdade sobre movimentos.
• Existe informação que controla a geração da
morfologia das criaturas como número máximo
de iterações em ciclos recursivos, dimensões,
número de ligações, etc...
6/24
Exemplos de morfologias
7/24
Criaturas: Estruturas de controle
Sensores (sensors)
• Associados a partes especificas do corpo,
recolhem informação “física” relativa a essa
porção do corpo.
• Joint angle sensors
• Contact sensors (existe uma em cada face de
cada porção do corpo)
• Photosensors
• Poderiam existir outros como: accelerometers,
sound detectors, smell detectors...
8/24
Criaturas: Estruturas de controle
(continuação)
Neuronios (neurons)
• Processam informação proveniente de sensores
• Enviam informação para actuadores
• Podem computar um conjunto de operações: sum, product,
divide, sum-threshold, greater-than, sign-of, min, max, abs, if,
interpolate, sin, cos, atan, log, expt, sigmoid, integrate,
differentiate, smooth, memory, oscillate-wave, oscilate-saw.
Actuadores (effectors)
• Recebe informação de um sensor ou neurónio
• Escala informação recebida com um certo peso e efectua
uma força sobre uma junção entre porções do corpo.
• Poderiam existir outras variantes...
9/24
Combinaçao entre morfologia e
controle
• Estrutura de controle é distribuída, associada a
cada parte rígida do corpo da criatura.
• Existe a possibilidade de comunicação entre
estruturas de controle posicionadas entre nós
com pontos de contacto.
• Pode existir uma estrutura de controle central,
independente de qualquer parte do corpo, que
possibilita o aparecimento de controle
coordenado de todo o corpo.
10/24
Exemplo de uma criatura virtual
11/24
Mecanismos de selecção
• População inicial gerada aleatoriamente
– Esta população inicial é testada para eliminação de
indivíduos não viáveis.
• População é testada e atribuído um nível de
fitness de acordo com o objectivo do teste.
• Uma percentagem de sobreviventes são usados
para gerar elementos da próxima geração
– Através de mecanismos de mutação e reprodução
• Os sobreviventes integram a geração seguinte.
• São efectuados um conjunto elevados de
iterações.
12/24
Mutações
• Parâmetros dos nós são sujeitos a potenciais
mutações (alterações do seu valor).
• Adiciona-se um nó (desconexo) ao grafo.
• Os parâmetros das ligações são potencialmente
alterados.
• Novas ligações são adicionadas aleatoriamente
e outras são removidas.
– Não ao nível dos grafos das estruturas de controle.
• Elementos desconexos do grafo são eliminados.
13/24
Reprodução
• Existem três técnicas disponíveis:
– Assexuada, através de mutações.
– Sexuada através de Crossovers.
– Sexuada através de Grafting.
14/24
Implementação das simulações
• Foi usada uma arquitectura distribuída baseada em
passagem de mensagens com 32 processadores.
• As populações era tipicamente de 300 indivíduos
• A taxa de sobrevivência era de 1/5
• As probabilidades para o tipo de reprodução eram:
– 40% assexuada
– 30% sexuada através de crossovers
– 30% sexuada através de grafting
• Simulações decorriam tipicamente entre 50 a 100
gerações.
15/24
Simulações Individuais
• Nadar
– Simulação sem gravidade, e com efeitos de resistência devido a
viscosidade.
– Fitness é calculada com base na velocidade de deslocamento,
premiando deslocamentos não cíclicos e contínuos (não baseados num
impulso inicial).
• Andar
– Basicamente movimentação em terra.
– Fitness é novamente baseada na velocidade, ignorando componente
vertical.
• Saltar
– Fitness baseada na altura máxima ou média da parte mais baixa da
criatura.
• Seguir
– Seguir uma fonte de luz, recorrendo a photosensors.
– Velocidade média da criatura a deslocar-se para a fonte de luz.
16/24
Resultados
Saltar
Nadar
17/24
Resultados (continuação)
Caminhos
para seguir luz
Andar
18/24
Simulações de competição
• Competição entre duas espécies (cruzamentos
dentro da mesma espécie apenas)
• Tipicamente modelo de competição era: All vs.
best entre espécies.
• Fitness depende da distancia final ao recurso
disputado (cubo com fonte de luz), sendo
premiada a maiores distancias do adversário ao
recurso.
– Valores entre 0.0 e 2.0.
19/24
Simulações de competição (cont.)
20/24
Resultados
21/24
Resultados (cont.)
22/24
Trabalho Futuro
• Avaliar optimizações de comportamentos simples, como
por exemplo maior distancia percorrida consumindo
menos energia.
• Adaptar a linguagem genética de forma a gerar apenas
criaturas que pudessem ser construídas sobre a forma
de robôs.
• Dar um aspecto mais realista às criaturas acrescentando
características como pelo, escamas, garras, etc.
• Aumento do numero de espécies em competição.
• Premiar comportamentos cooperativos em competições
em grupos.
• Simulações em grandes mundos virtuais, super
populados.
23/24
Conclusões
• Comportamentos e morfologias
interessantes podem emergir de um
processo de selecção natural como este
partindo de criaturas simples.
• Emergiram padrões de evolução
consistentes que possibilitaram a
aquisição de estratégias, assim como, por
vezes surgiram processos adaptativos.
24/24