Vida Artificial
Ano Lectivo 2005/2006
EvoCAD
Evolution-Assisted Design
Eduardo Ferreira (Nº 26524)
Alinhamento da Apresentação
• Introdução;
• Mecanismos Constituintes do EvoCAD;
• Estruturas 2D;
• Estruturas 3D;
• Aplicações Educacionais do EvoCAD.
Vida Artificial
Alinhamento – 2
Introdução
• O conceito inicial do EvoCAD surgiu em 1996 pelas mãos de dois
investigadores: Pablo Funes e Jordan Pollack;
• Estes deram início à investigação do desenho evolucionário com
peças de Lego;
• As simulações levadas a cabo são concebidas tendo em conta a
versatilidade dada pela construtividade inerente ao Lego:
– Um algoritmo evolucionário simples;
– Uma simulação parcial com peças de Lego estáticas;
– A combinação destes pontos permite a evolução de estruturas que são
retornadas pelo computador, estando prontas a construir;
• Um sistema de EvoCAD possui diversas características (parte 1):
– Apresenta as mesmas propriedades dos sistemas comerciais de CAD
mais comuns, ao nível da produção de desenhos.
Vida Artificial
Introdução – 3
Introdução
• Um sistema de EvoCAD possui diversas características (parte 2):
– O papel principal é dado ao utilizador, partindo deste o conceito para o
desenho de um objecto ou estrutura;
– Podem ser definidas restrições e/ou objectivos evolucionários que o
motor do EvoCAD utiliza para efectuar fazer evoluir um dado desenho;
– O resultado produzido por este motor evolucionário pode ser alterado,
testado e re-evoluído um qualquer número de vezes;
• De um ponto de vista conceptual, um sistema EvoCAD apresenta
dois focos de creatividade:
– O utilizador humano;
– O motor evolucionário do sistema;
• Para demonstrar estes conceitos, foi desenvolvido um pequeno
sistema de EvoCAD que permite a evolução de estruturas 2D
construídas com peças de Lego.
Vida Artificial
Introdução – 4
Introdução
• Este sistema permite:
– Manipular estruturas em Lego;
– Testar a resistência gravitacional destas estruturas através da utilização
de um simulador estrutural implementado para este propósito;
• O EvoCAD recorre a um algoritmo evolucionário que:
– Utiliza como dados iniciais os objectivos estabelecidos por um utilizador
e um processo de simulação previamente definido;
– Combina estes dois focos de informação para fazer evoluir soluções
candidatas para a resolução dos problemas estruturais colocados;
• Os resultados obtidos são apresentados na interface gráfica, o que
permite subsequentes re-estruturações até que seja atingida uma
solução satisfatória.
Vida Artificial
Introdução – 5
Mecanismos Constituintes do EvoCAD
• Os mecanismos do sistema EvoCAD são:
– Algoritmo de simulação;
– Algoritmo de evolução;
– Linguagem de descrição dos problemas do domínio das peças de Lego
(brick problem description language - BDL);
– Condicionantes a ter em conta;
– Função de fitness;
• O algoritmo de simulação baseia-se no conceito da capacidade
máxima de pressão nas juntas de peças:
– Uma estrutura de Lego na qual estejam colocadas cargas torna-se
numa rede de fluxo de pressão em que cada junta apresenta uma
capacidade máxima;
– Este tipo de algoritmo apenas aceita estruturas que não apresentem
uma excesso de pressão em qualquer uma das suas juntas, sendo o
fluxo global válido.
Vida Artificial
Mecanismos – 6
Mecanismos Constituintes do EvoCAD
• Para permitir a utilização dos operadores genéticos Mutation e
Crossover, uma estrutura de Lego é representada por uma função
de cariz formal:
– Tem uma ou mais peças “raíz” com zero ou mais descendentes ligados
em diversos pontos;
– As mutações podem modificar a dimensão ou a posição de uma peça;
– As recombinações permitem a troca de segmentos entre dois pais;
• O algoritmo de evolução necessita de uma estrutura inicial que
consista em uma ou duas peças, para que se possa dar início ao
processo evolutivo:
– É atribuída uma representação genética a este conjunto inicial de
peças, sento então criada a população inicial;
– Os operadores genéticos Mutation e Crossover são aplicados de forma
iterativa, fazendo crescer e evoluir uma população de estruturas.
Vida Artificial
Mecanismos – 7
Mecanismos Constituintes do EvoCAD
• O simulador é executado para cada uma das estruturas obtidas:
– Testa a estabilidade e a capacidade de carga, sendo estes dados
utilizados para o cálculo do valor de fitness a atribuir a cada estrutura;
– A evolução termina quando todos os objectivos forem satisfeitos ou
quando um número inicialmente definido de iterações for atingido;
• Foi definido um formalismo para a representação das peças de
Lego, cujo objectivo é servir de ligação entre o algoritmo evolutivo, o
simulador e a interface com o utilizador do sistema;
• Quando o utilizador clica no botão evolve, uma descrição BDL do
estado inicial fornecido é enviada para o servidor, que, por sua vez,
evolui uma solução para o problema;
• O resultado desta operação de evolução é enviado para o sistema
CAD utilizando o mesmo formalismo.
Vida Artificial
Mecanismos – 8
Mecanismos Constituintes do EvoCAD
• Neste ponto, o simulador recebe estruturas codificadas com o BDL
de dois pontos distintos:
– Do sistema CAD (quando um utilizador deseja testar a estabilidade da
sua estrutura);
– Do algoritmo evolucionário, que testa todas as estruturas mutadas ou
recombinadas;
• Os objectivos a atingir pelo algoritmo evolucionário são deduzidos
das condicionantes definidas pelo utilizador:
– Restrições:
• Regiões da área de evolução onde não é permitido que a estrutura se
implante;
– Pontos de destino:
• Pontos específicos aos quais a estrutura deverá chegar;
– Pontos de pressão:
• Pontos específicos onde a estrutura deverá suportar uma dada carga.
Vida Artificial
Mecanismos – 9
Mecanismos Constituintes do EvoCAD
• Uma estrutura será considerada completamente satisfatória se:
– Tocar em todos os pontos de destino definidos;
– Evitar todas as regiões restritas;
– Suportar as cargas especificadas em cada ponto de pressão definido;
• Relativamente à função de fitness, é necessário calcular um valor
de fitness genérico para qualquer estrutura codificada em BDL;
• A função de fitness é dada pela seguinte fórmula:
– d calcula a distância entre um ponto e a peça mais próxima de uma estrutura;
– supp utiliza o simulador para determinar a fracção de uma dada carga que a
estrutura suporta.
Vida Artificial
Mecanismos – 10
Mecanismos Constituintes do EvoCAD
Vida Artificial
Mecanismos – 11
Mecanismos Constituintes do EvoCAD
• Nesta figura é apresentado um exemplo de uma sessão de trabalho
com o EvoCAD:
– O utilizador define duas peças ground e diversas pistas evolucionárias:
• Restrições (x);
• Pontos de destino (ponto);
• Carga (seta);
– O processo de evolução retornou a estrutura apresentada, que satisfaz
todos os requisitos iniciais;
– O utilizador efectua algumas correcções de cariz cosmético;
– A estrutura é então construída com peças de Lego reais.
Vida Artificial
Mecanismos – 12
Estruturas 2D
• A Ponte de Lego (Lego Bridge) é uma estrutura, construída apenas
com blocos de Lego, que é obtida por um algoritmo evolucionário
que executa uma simulação computacional das propriedades físicas
do Lego;
• O algoritmo desenvolvido obteve uma solução para o problema de
construir uma estrutura semelhante a uma ponte:
– Fixar o início da estrutura numa mesa;
– Alongar a estrutura de forma a atingir uma mesa vizinha, percorrendo
uma distância de 1,5 metros;
• A animação seguinte mostra o processo de criação da estrutura de
Lego a partir de um único bloco de Lego, no qual acontecem as
seguintes situações:
– Utilização dos operadores genéticos Mutation e Crossover;
– Operações de adição e remoção de parte da estrutura de um indivíduo
ou bloco.
Vida Artificial
Estruturas 2D – 13
Estruturas 2D
http://helen.cs-i.brandeis.edu/pr/buildable/anim1/anim1.gif
Vida Artificial
Estruturas 2D – 14
Estruturas 2D
• A Ponte Longa (Long Bridge) é uma estrutura para a qual apenas foi
pedido ao simulador que a evoluísse, tornando-a o mais longa
possível (atingiu quase 2 metros de comprimento).
Vida Artificial
Estruturas 2D – 15
Estruturas 2D
Vida Artificial
Estruturas 2D – 16
Estruturas 2D
Vida Artificial
Estruturas 2D – 17
Estruturas 2D
Vida Artificial
Estruturas 2D – 18
Estruturas 2D
Vida Artificial
Estruturas 2D – 19
Estruturas 2D
• O Guindaste (Crane) é uma estrutura 2D cujo braço evoluiu de
forma a conseguir erguer objectos com um peso até 0,5 kg;
• Foi criada uma base rotativa para o guindaste, ampliando o seu
leque de movimentos;
• Representou-se o guindaste com um conjunto de restrições;
• As restrições foram então fornecidas a um algoritmo genético cuja
missão era encontrar um braço considerado satisfatório.
Vida Artificial
Estruturas 2D – 20
Estruturas 2D
http://helen.cs-i.brandeis.edu/pr/buildable/crane/cranesm.mpeg
Vida Artificial
Estruturas 2D – 21
Estruturas 2D
• A Árvore (Tree) é uma estrutura 2D que tenta expandir-se em altura
e largura, com o objectivo de se tornar “leve” ao afastar-se da raíz;
• A acto de se tornar “leve” é apenas uma tentativa de maximização
dos valores da sua função de fitness;
• Serve como demonstração de uma simulação melhorada e de um
algoritmo evolucionário mais eficiente;
• Embora os “braços” da estrutura sejam muito pesados, por si só, o
processo evolucionário conseguiu determinar uma estrutura que é
perfeitamente equilibrada no centro.
Vida Artificial
Estruturas 2D – 22
Estruturas 2D
http://helen.cs-i.brandeis.edu/pr/buildable/tree/treesm.mov
Vida Artificial
Estruturas 2D – 23
Estruturas 2D
Vida Artificial
Estruturas 2D – 24
Estruturas 2D
Vida Artificial
Estruturas 2D – 25
Estruturas 3D
• Uma Lego Table (mesa de Lego), que foi a primeira experiência na
evolução de estruturas 3D de Lego;
• Todos os modelos construídos anteriormente diziam respeito à
evolução de estruturas 2D de Lego;
• A mesa satisfaz diversas especificações estabelecidas nas funções
de fitness:
– Altura: tem uma altura de 10 blocos;
– Superfície: o seu topo cobre um quadrado de 9x9;
– Suporte: suporta uma carga de 50 gramas em qualquer ponto da sua
superfície;
– Leveza: usa o menor número de blocos possível.
Vida Artificial
Estruturas 3D – 26
Estruturas 3D
Vida Artificial
Estruturas 3D – 27
Aplicações Educacionais do EvoCAD
• Estudantes podem construir estruturas, imprimí-las e construí-las
com Lego real;
• Testar problemas de engenharia (exemplos):
– Construir uma estrutura que aguente com uma certa quantia de peso;
– Construir uma ponte resistente utilizando:
• duas peças ground bastante afastadas;
• recorrendo a pontos de restrição para dificultar a construção em locais
considerados óbvios;
• O motor de inteligência artificial pode ser utilizado em qualquer
momento para auxiliar um estudante:
– Criar uma estrutura que se mantenha estável;
– Proceder à sua análise e determinar as propriedades que a tornam
estável.
Vida Artificial
Aplicações – 28
Referências
•
http://demo.cs.brandeis.edu/pr/buildable/evocad/
•
FUNES, Pablo, LAPAT, Louis and POLLACK, Jordan B. (2000)
– EvoCAD: Evolution-Assisted Design
– Artificial Intelligence in Design 00 Poster Abstracts
– Key Centre of Design Computing and Cognition, University of Sydney, p. 21-24.
•
FUNES, Pablo et al (2000)
– Evolutionary Techniques in Physical Robotics
– Computer Science Department, Brandeis University, Waltham, Massachussets.
•
FUNES, Pablo and POLLACK, Jordan B. (1998)
– Computer Evolution of Buildable Objects for Evolutionary Design by Computers
– Computer Science Department, Brandeis University, Waltham, Massachussets.
Vida Artificial
Referências – 29