Um cientista explica o Microsoft Kinect, Parte II

A recepção ao meu primeiro artigo explicando a tecnologia por trás do Kinect, o novo acessório da Microsoft sendo lançado essa semana, foi surpreendente, em vários aspectos. O primeiro foi a enorme quantidade de visitantes, comentários e elogios, o que obviamente me deixou muito feliz…

O segundo aspecto, entretanto, foi mais interessante e inesperado: o diretor de incubação da Microsoft Alex Kipman, responsável pelo desenvolvimento do Kinect (e brasileiro!), leu o artigo! E, para minha surpresa, explicou que eu estava enganado com relação à tecnologia usada para obter os resultados surpreendentes que descrevi no artigo anterior, e me apontou no caminho certo.

A minha primeira reação foi a de ficar com vergonha: afinal de contas dei uma explicação que fazia muito sentido mas que não estava totalmente correta, e para uma audiência enorme. Vergonha ou não, só existe uma alternativa correta nesse caso, que é assumir o engano e corrigir a informação, o que é o que faço hoje. Alguns amigos me consolaram dizendo que qualquer cientista erra, e esse é o único jeito de continuar aprendendo, e concordo com eles! Além do mais, é inegável que ser corrigido pelo próprio Alex Kipman é no mínimo algo bem empolgante!

O que continua valendo?

Expliquei no artigo anterior que a antiga Power Glove, o Wii e o Move retornam informações limitadas, e semelhantes. Todos retornam informação a respeito de um ou dois pontos no espaço; o que muda são os graus de liberdade (DOF, de degrees of freedom) retornados para o ponto. O ideal é que você tenha seis graus de liberdade, ou seja, que o sistema saiba não só a posição espacial do controle (as coordenadas x,y,z do controle) mas também os três ângulos (roll, pitch e yaw) que determinam para onde ele está inclinado. O Move e o Wiimotion Plus retornam isso, o que é bem bacana; a Power Glove, nos 1980s, já retornava x,y,z, yaw e roll, ou seja, 5DOF.

Seis graus de liberdade no Wiimote

Seis graus de liberdade no Wiimote

O problema desses sistemas é que eles se restringem à posição (mesmo que com 6DOF) apenas do controle propriamente dito. O Kinect, por sua vez, entrega informação 3D da cena inteira (ou seja, entrega um mapa de profundidade, como apontou o nic nos comentários do primeiro artigo). A partir desse mapa ele detecta a posição do corpo inteiro da pessoa que está em frente à câmera. Essa é a grande inovação, e a explicação continua valendo! O que muda é como esse mapa é construído, e quem desenvolveu o sensor.

Um conto de duas empresas israelenses

No artigo anterior eu disse que a tecnologia usada no Kinect veio da empresa israelense 3DV, que produzia a ZCam, uma câmera TOF (time-of-flight) que entrega um mapa de profundidade como o que era necessário. A 3DV foi comprada pela Microsoft há algum tempo. Pouco depois foi anunciado o Project Natal, que virou o Kinect, e mais tarde comunicaram que a tecnologia dele era de uma empresa israelense que fazia câmeras 3D

Meu engano foi assumir que a empresa israelense era a 3DV! Na verdade a Microsoft comprou a 3DV, mas com interesse no seu portfólio de patentes. conforme explicado no venturebeat.com. Como eu assumi que a tecnologia usada era a da 3DV, eu expliquei como funcionava a câmera dela, a ZCam, que é uma câmera TOF…

Mas o sensor do Kinect foi desenvolvido pela Microsoft, internamente, numa parceria com uma outra empresa israelense que produzia câmeras que retornam mapas de profundidade, a PrimeSense (foi aqui o Alex Kipman me corrigiu). Essa informação muda completamente a minha hipótese, porque a PrimeSense usa um outro método para detectar a profundidade na cena, baseado em luz estruturada (structured light)! E o Kinect não é idêntico aos produtos da própria PrimeSense, pois o sensor em si foi projetado especificamente para as necessidades da Microsoft.

O sensor de profundidade da PrimeSense

Explicada a confusão, posso explicar como funciona o sensor da PrimeSense. Como disse, o sensor do Kinect não é exatamente o mesmo sensor da PrimeSense, então pode ser que algum detalhe seja diferente do que vai ser descrito aqui, mas o princípio é simples de entender a partir de um pequeno exemplo.

Vamos começar por um projetor comum, como os que são usados em cinema e home theaters, ou mesmo um retroprojetor dos antigos, que usam transparências. Esse projetor é usado para projetar um quadriculado uniforme. Se você coloca o projetor perto da parede, o quadriculado aparece pequeno, com cada quadradinho ocupando pouco espaço. Similarmente, se você projeta numa parede bem distante, os quadrados aparecem enormes.

Se você entra na frente do projetor, o quadriculado é projetado em seu corpo. A parte do quadriculado que acerta você aparece de um tamanho, e a parte que acerta a parede lá no fundo aparece de outro… Ou seja, se você mede, na imagem da câmera, o tamanho de cada quadradinho do quadriculado você sabe, baseado no tamanho dele, a que distância ele está! O quadriculado é luz estruturada, ou seja, luz com uma estrutura bem definida que permite que você descubra informações sobre a cena baseado na forma como essa luz é refletida.

Note que você pode detectar a profundidade não só com o tamanho do quadradinho (esse é só um exemplo didático), mas também observando, por exemplo, como linhas que deveriam ser retas são distorcidas ao serem projetas em superfícies curvas.

Luz estruturada projetada em superfície irregular

Luz estruturada projetada em superfície irregular

Um ponto difícil é que você precisa de uma óptica bem precisa: quanto mais resolução tem o quadriculado, mais exata a sua medida. Para enxergar o quadriculado você precisa de uma câmera de alta resolução, e para medir em tempo real o tamanho de todos os quadradinhos você precisa de hardware e software dedicados, numa arquitetura paralela.

No Kinect o quadriculado é projetado com luz infravermelha, invisível, logo você não percebe. Qualquer câmera digital comum detecta infravermelho: se você filmar com seu celular um controle remoto comum de TV funcionando você consegue enxergar o LED infravermelho dele piscando toda vez que você aperta uma tecla. Isso é uma vantagem enorme, porque isso implica que com uma câmera de infravermelho comum você consegue enxergar o quadriculado! Não é preciso o hardware dedicado caro da 3DV, que descrevi no artigo anterior, em que cada “pixel” tem o equivalente a um cronômetro para medir o tempo de vôo. Provavelmente o custo foi a principal razão por terem escolhido a PrimeSense ao invés da 3DV, aliás.

Mas isso não significa que o Kinect seja simplesmente uma câmera infravermelho comum, porque o processamento em tempo real necessário para extrair o mapa de profundidade a partir da imagem do quadriculado é bem sofisticado. Ele usa um sensor (CCD) comum, mas tem bastante coisa por trás.

Ilustração do design de referência da PrimeSense

Ilustração do design de referência da PrimeSense

Alguns aspectos ainda não estão claros para mim: o padrão exato usado, por exemplo (não precisa ser necessariamente um quadriculado; linhas paralelas podem ser usadas, ou mesmo padrões bem sofisticados que codificam mais informação), a resolução desse padrão (e consequentemente a resolução do mapa de profundidade) e outros detalhes do algoritmo usado. Mas isso não afeta o entendimento de como o processo funciona.

Galantucci, L. M. , Percoco, G. and Dal Maso, U. 'Coded targets and hybrid grids for photogrammetric 3D digitisation of human faces', Virtual and Physical Prototyping, 3:3, 167 - 176

Galantucci, L. M. , Percoco, G. and Dal Maso, U. 'Coded targets and hybrid grids for photogrammetric 3D digitisation of human faces', Virtual and Physical Prototyping, 3:3, 167 - 176

Quem estiver interessado em maiores detalhes pode ler as patentes da Prime Sense, como por exemplo:

Conclusão

O fato do sensor do Kinetic usar luz estruturada desenvolvida em conjunto com a PrimeSense, ou uma câmera TOF da 3DV não muda o meu entusiasmo. O interessante, como já expliquei, é ter um mapa de profundidade em tempo real, de baixíssimo custo. O aprendizado de máquina usado para extrair informações de postura corporal a partir do mapa continua o mesmo, e as muitas aplicações que uma tecnologia assim tem também.

A comparação de preço que fiz com a SwissRanger SR4000 da Mesa Imaging agora não é mais tão justa, já que câmeras TOF são mesmo bem mais caras que câmeras baseadas em luz estruturada. Mas comparar, por exemplo, a resolução do mapa de profundidade e a velocidade com que ele é produzido continua válido.

Uma vez mais, gostaria de agradecer a todos os leitores pela atenção, e de me desculpar com eles pelo engano. Um agradecimento especial, é claro, vai para o leitor mais ilustre, o Alex Kipman, e pela atenção e gentileza dele ao me corrigir. Espero que a leitura tenha sido divertida!

Mundos Virtuais, Processamento de Sinais, Reconhecimento de Faces, Robótica, Visão Computacional 9 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5,00 out of 5)

Mobilidade de agentes

Inaugurando a minha participação no blog do Vetta Labs, vou falar um pouco sobre mobilidade de agentes inteligentes.

Meu interesse por essa área se confunde com o surgimento dos primeiros jogos isométricos com pathfinding. Inicialmente, eu podia perder horas tentando tapear um NPC para ver se ele era inteligente de verdade. Claro que, com o tempo, a inteligência artificial nos jogos ficou mais elaborada, e eu passei a correr para me manter vivo mesmo. :P

Algoritmos de pathfinding consistem, basicamente, em um ou múltiplos agentes com destino definido distribuídos em um ambiente (mapa) determinado. Sendo assim, o agente deve se deslocar pelo ambiente respeitando suas restrições de movimento e obstáculos dinâmicos ou estáticos até atingir seu objetivo. Geralmente o algoritmo faz um cálculo de custo de deslocamento para definir a melhor direção ou trajetória a seguir. Além disso, o ambiente pode ter inúmeras características, o que viabiliza ou não a utilização de algoritmos de pathfinding específicos.

Path Planning

Muitos dizem que nada melhor do que um A* para começar. De fato, trata-se de um dos algoritmos mais utilizados no planejamento de caminhos em jogos e robótica. Diversos frameworks, controladores e game engines possuem esse algoritmo embutido; porém, são bastante enriquecedoras a sua implementação e a de algumas variações (RTA*, IDA*, GAA*, etc).

Em 2008, participei da elaboração de um artigo para o SBGames, fazendo experimentos com algoritmos de busca online e offline para MMOs. O objeto do meu estudo foi o path planning do jogo Ultima Online, o qual considero o melhor MMORPG de todos os tempos.

Como fruto desse experimento, pude entender de forma mais clara o porquê dos problemas de gameplay no pathfinding dos NPCs do jogo: era uma questão de otimização de recursos computacionais. Sendo assim, foi muito interessante estudar como os algoritmos clássicos de inteligência artificial são adaptados para melhorar o desempenho dos servidores, algo bastante exigido nesse gênero de jogo.



Path Follow

Outra estratégia bastante utilizada na mobilidade de agentes é a definição de trajetórias baseadas em checkpoints seqüenciais, gerando um caminho virtual. O agente, por sua vez, possui um atuador que corrige a sua direção e minimiza o desvio em relação ao segmento de reta corrente para manter-se na trajetória. É uma solução comum para agentes de jogos de corrida e para controle de UAVs na robótica, pois permitem uma margem de erro em relação à trajetória ótima.



Vector Fields

Como o próprio nome diz, trata-se de um conjunto de vetores que sugerem uma direção e/ou velocidade a partir de determinada coordenada ou região. Tais vetores podem ser dispostos na forma de um grid uniforme ou dispostos nos centros de polígonos em uma malha geométrica.

Esses algoritmos são muito utilizados para mobilidade de agentes em robótica e simuladores de física de modo geral.


Nos jogos digitais, também podem ser utilizados para simular fenômenos naturais, como a atuação do vento na vegetação, por exemplo.



Voronoi Diagrams

Os diagramas de Voronoi foram desenvolvidos com o objetivo de decompor espaços a partir de um conjunto de pontos de referência. As bordas da decomposição são formadas por linhas eqüidistantes a pontos vizinhos.

Esse algoritmo possui inúmeras aplicações computacionais. Na mobilidade de agentes, é utilizado na simulação de espaços superlotados, pois as bordas dos espaços decompostos indicam os caminhos mais seguros a passar entre diversos obstáculos.


Observando as células dos diagramas de Voronoi, percebemos uma grande semelhança com estruturas orgânicas, o que, de fato, faz sentido. Diversas estruturas naturais podem ser reproduzidas computacionalmente a partir de modelos matemáticos. As asas de uma libélula também podem ser reconstruídas a partir de diagramas de Voronoi, assim como a fragmentação de corpos rígidos em simulações de física.


Boids

Com o objetivo inicial de simular o comportamento da revoada de pássaros, esse algoritmo é muito utilizado em sistemas multiagentes. O curioso nesse tipo de algoritmo é que as ações individuais desempenhadas pelos agentes resultam em um comportamento de grupo coeso. Sendo assim, podemos simular, também, cardumes, manadas, enxames, etc…

Cada agente nesse sistema pode efetuar três ações básicas: distanciamento, alinhamento e aproximação em relação ao centro de massa. Isso permite que o grupo se desloque em massa, na mesma direção, sem que haja colisões entre os agentes.



Considerações finais

Nesse post apresentei uma visão bastante resumida da mobilidade de agentes e como eles podem ser utilizados em áreas distintas. Opções não faltam para solucionar problemas diversos em planejamento de caminhos, porém, antes de escolher um algoritmo, é preciso colocar na balança alguns fatores como: consumo de recursos computacionais, tempo de resposta, margem de erro, gameplay, entre outros.

Espero que tenham gostado e até o próximo post. :)

Robótica 2 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 4,00 out of 5)

Fluídica: Computação a Água

No meu artigo anterior falei sobre a idéia de computadores completamente mecânicos, falando um pouco da Máquina de Turing (um modelo matemático de um computador abstrato) e das Máquinas Diferencial e Analítica de Charles Babbage (inclusive sobre implementações em LEGO). Depois que publiquei me lembrei que poderia ter citado também o Mecanismo de Anticítera – então agora remeto vocês para o artigo sobre ele escrito pelo amigão Kentaro Mori.

Depois dos computadores mecânicos, no final eu prometia falar de computadores fluídicos – computadores sem partes móveis em que o fluxo de elétrons é substituído por fluidos como ar, água ou óleo, com tubos, canos e mangueiras ao invés de fios. Ao assunto, então!

Fluídica na Ficção Científica

Provavelmente o primeiro contato com de muita gente com a idéia foi assistindo ao clássico Rollerball – Os Gladiadores do Futuro (1975). No filme existe Zero, um supercomputador fluídico baseado em lógica fuzzy que armazena toda a informação de todos os livros do mundo:

rollerball

Livros, livros ? Mudaram completamente. Todos foram transcritos. Toda a informação está aqui. Temos o Zero, é claro. Ele é o cérebro central, o cérebro do mundo. Mecânica de fluidos, fluídica. Ele é líquido, vê ? Suas águas tocam todo o conhecimento do mundo. [...] Ele flui por todos os nossos sistemas de armazenamento. Ele considera tudo. Tornou-se tão ambíguo hoje em dia que parece não ter certeza de nada.

Hoje em dia, mesmo sem o Zero é fácil encontrar o trecho de Rollerball em que Zero aparece (vídeo em inglês, sem legendas em português) e também o script original do filme.

Rollerball é 1975, e na época a Fluídica estava bombando – uma quantidade enorme de verbas foi investida em sua pesquisa, nos Estados Unidos (falaremos disso mais tarde) – e provavelmente por isso ela foi a tecnologia escolhida para aumentar a suspensão de descrença do filme.

Água x Elétrons

Quando estudava eletrônica (e até hoje, quando preciso explicar pra alguém) eu costumava imaginar que os elétrons se comportavam como água. Carga elétrica (em Coulombs) virava quantidade de água (em litros). A corrente (em Ampère, Coulomb por segundo) virava o fluxo de água (litros por segundo). A tensão da corrente (em Volts) é equivalente à pressão da água, e a resistência de um fio, à espessura do cano que transporta o líquido.

Uma bateria armazena energia potencial química, que causa uma diferença de potencial elétrico nos terminais (que faz com que a corrente elétrica circule). No nosso exemplo didático, temos uma caixa d’água, e a diferença de pressão entre a caixa d’água e um cano no térreo é o potencial que coloca a água nos canos em movimento (usando a energia potencial gravitacional). Quando você abre a torneira (o interruptor) a diferença de pressão (potencial) faz com que a água (elétrons) fluam da caixa d’água (pólo positivo) pelo cano (fio) até o ralo (pólo negativo / “terra”).

Pensar desse jeito torna o básico que se aprende de eletrônica e eletricidade no ensino médio algo bem concreto – a maioria das pessoas já brincou mais com mangueiras de jardim e torneiras do que com fios e baterias. Fica fácil entender porque uma tensão (pressão d’água) muito alta danifica um aparelho (ao ligar um aparelho 110V numa tomada 220V) mas uma bateria com capacidade de fornecer muita corrente não danifica aparelhos de baixo consumo (você simplesmente tem mais água na caixa d’água).

De qualquer forma, eu imaginava que esse raciocínio era só um recurso didático, e não poderia ser aplicado em nada mais sofisticado. Por exemplo, eu sempre imaginava torneiras – dispositivos mecânicos, móveis, que controlam o fluxo, da mesma forma que interruptores fazem com a corrente elétrica. Mas o mais interessante da eletrônica (pelo menos pra mim, na época) era usar a eletricidade para controlar eletricidade: usando um transistor (o amplificador mais simples que existe) uma corrente elétrica de baixa intensidade controla uma corrente elétrica muito mais forte (e.g. a corrente baixíssima induzida por um microfone controla a corrente muito mais alta consumida pelas caixas de som enormes no seu show de rock preferido).

Descobri que meu problema era fazer um transistor de água. Anos mais tarde eu iria aprender como fazer um, lendo sobre uma feira de ciências de 1962!

Os Circuitos de Água de Murray O. Meetze, Jr.

Em 1962, o estudante de segundo grau Murray O. Meetze, Jr, ganhou a Feira Nacional de Ciências de 1962, nos Estados Unidos. O projeto dele era o equivalente a uma válvula triodo a água, sem partes móveis. A válvula triodo foi aposentada há décadas; hoje em dia ninguém a usa (exceto uns poucos audiófilos, entusiastas de rádios e TVs antigos, ou interessados em aplicações muito específicas). Ela foi substituída pelo seu equivalente de estado sólido (feito apenas com metais semicondutores, sem necessidade de tubo de vidro a vácuo), o transistor.

Certa vez, completamente por acaso, eu me deparei com uma longa reportagem numa Scientific American da época, descrevendo o tabalho de Meetze. Eu fiquei maravilhado; as soluções dele eram incrivelmente simples, e com elas daria pra aumentar meu “laboratório fluídico imaginário” de uma forma que não achava que seria possível. Além do transistor, Meetze mostrava como fazer um flip-flop (ou multivibrador bi-estável) fluídico, o equivalente a um bit de memória RAM, e também um amplificador (com funcionamento igual ao de um amplificador eletrônico de som).

meetze-flipflop

Depois de vários anos procurando, enquanto me preparava para escrever esse artigo eu encontrei novamente a deliciosa matéria da Scientific American. A qualidade do scan está bem baixa, mas a leitura é recomendadíssima. Uma curiosidade: a página sobre Fluídica da Wikipedia em inglês cita Murray O. Meetze como criador da válvula triodo fluídica, mas não dá referências! Vou tentar editar o post para incluir isso, mas é preciso uma correção: o próprio Meetze diz à Scientific American que a tecnologia havia sido desenvolvida pelo Diamond Ordnance Fuze Laboratories, do exército americano, mas quase tudo era confidencial na época.

Com transistores fluídicos eram possível criar portas lógicas fluídicas. Com portas lógicas e flip-flops, a única coisa que impedia a construção de um computador completamente fluídico era o tamanho ! Aliás, recentemente um estudante do MIT pôs a mão na massa e resolveu fazer algo parecido, usando – é claro – peças de LEGO! O projeto, bem simples, foi feito com fins exclusivamente didáticos – bem alinhado com o que me despertou o interesse por fluídica (e também com o trabalho de Meetze).

mlfabpauloandadder1

Ao revisar esse artigo, o Kentaro me falou de um outro tipo de computador baseado em água, o MONIAC. Ele também foi construído originalmente com fins didáticos, mas era capaz de fazer simulações bem complexas da economia do Reino Unido. O MONIAC é um computador analógico que usa quantidade de água para representar os dados, como os integradores a água da União Soviética dos anos 1930, que eram capazes de resolver equações diferenciais parciais não-homogêneas – se você sabe o que é isso vai entender a importância da coisa! Mas o MONIAC era baseado em hidráulica, não em fluídica. A diferença é que sistemas hidráulicos têm várias partes móveis, mecânicas – êmbolos, pistões, “torneiras”, etc.  – uma abordagem bem diferente da fluídica, onde só o que se move é o próprio fluido.

A Fluídica nos Anos 1960-1980

Assim como eu, muita gente ficou animadíssima com as possibilidades que a Fluídica trazia. Nos anos 1960 e 1970 computadores eletrônicos eram frágeis, caros e lentos, e a robustez e simplicidade dos circuitos fluídicos era muito atrativa. Esse entusiasmo é fica claro ao ler artigos da época, publicados em revistas como Popular Mechanics e Popular Science. O divertido é que o conteúdo integral dessas revistas está disponível on-line, gratuitamente; o Google, mesmo sem tecnologia fluídica, faz o papel do Zero de Rollerball, hoje em dia! :-) Além disso, os artigos são extremamente acessíveis, explicando de forma bem clara o funcionamento dessa Fluídica de primeira geração.

Na época falavam-se, por exemplo, de circuitos fluídicos para controlarem o câmbio automático e a injeção de combustível em automóveis (ao invés da moderna injeção eletrônica que temos hoje), e substitutos fluídicos dos giroscópios dos sistemas de navegação pré-GPS.

Fluídica: Como Ensinaram uma Corrente de Ar a Pensar. Popular Science, junho de 1967

Controle Potência com Fluido. Popular Mechanics, julho de 1967

coanda

Mais tarde, outras aplicações envolviam aviônicos e circuitos de controle de mísseis e aviões militares; a idéia é que no caso de um ataque nuclear, o pulso eletromagnético gerado pelas bombas danificaria qualquer aparelho eletrônico, tornando impossível o vôo de caças aerodinamicamente instáveis. Caças aerodinamicamente instáveis precisam de auxílio de computador o tempo todo durante o vôo; um dos primeiros exemplos famosos foi o Grumman F-14 Tomcat, cujo ângulo das asas e outras superfícies de vôo é controlado por um dos primeiros microprocessadores eletrônicos integrados (desenvolvido secretamente antes do histórico Intel 4004).

Em 1985 a mesma Grumman investia pesadamente em sistemas fluídicos de controle de vôo, e nem tudo ficou só na especulação ou em projetos militares de pesquisa; chegaram a ser produzidos modelos do Honda Accord com esses sistemas de navegação, por exemplo.

Fluídica: Computação sem Eletrônica. Popular Science, fevereiro de 1985

Mas apesar do oba-oba a Fluídica nunca obteve o sucesso previsto, muito provavelmente por causa do avanço rápido da eletrônica. Válvulas eram caras e frágeis, mas com o advento do transistor e, mais tarde, do circuito integrado tornou-se possível o uso de eletrônica em cenários muito mais críticos e extremos, e o chão de fábrica foi um dos primeiros alvos. A velocidade dos circuitos eletrônicos – milhares ou milhões de vezes superior a dos fluídicos – foi outro fator decisivo para a tecnologia ser esquecida ou relegada a nichos muito específicos.

1990s: Microfluídica

A Fluídica clássica não cumpriu todas as promessas, mas nos anos 1990 surgiram vários produtos baseados na sua prima de menor escala, a Microfluídica. A diferença está na escala: circuitos cujos dutos são da ordem de micrômetros (e não milímetros ou centímetros) apresentam comportamentos muito diferentes, porque nessa escala efeitos antes desprezíveis como tensão superficial e fluxo laminar tornam-se importantíssimos. Essa escala menor permite, por exemplo, que construam circuitos fluídicos “digitais”, em que se manipulam não um fluxo contínuo de fluido mas minúsculas gotas individuais.

Uma das tecnologias mais populares que foram muito influenciadas pela microfluídica foram as células de combustível. Células de combustível produzem eletricidade diretamente a partir de oxidante e combustível (oxigênio e hidrogênio, na maioria das vezes), sem a necessidade da tradicional combinação de motor a explosão e gerador elétrico (como nos carros). A microfluídica é usada para controlar o fluxo de oxidante e combustível, tornando essas células muito mais eficientes.

Mas, de longe, a aplicação de microfluidica que mais me interessa são os microarrays de DNA. Microarrays são chips, produzidos por processos microfluídicos, que contém milhares de fragmentos de material genético, organizados em forma de matriz. Quando se deposita material genético nesse chip, ele identifica exatamente quais trechos de material genético – quais genes – estão ativos naquela amostra. Isso permite a criação em larga escala de perfis de expressão genética, ou seja, perfis que mostrem quais genes do DNA estão “funcionando” num determinado momento. Simplesmente saber a seqüência de genes de um organismo (o objetivo do projeto Genoma) não é tudo; é muito mais importante descobrir como esses genes interagem entre si e a dinâmica deles ao longo da vida. Doenças, atividade física e intelectual, e vários outros fatores ativam e desativam a expressão genética em questão de horas, e os microarrays permitem que se tire uma “foto” dos genes em atividade.

Aqui no Vetta Labs trabalhamos há vários anos desenvolvendo software para análise de perfis de expressão genética produzidos por experimentos com microarrays. A maior parte desse esforço é feito em conjunto com a empresa americana Biomind, e desse esforço surgiu também um projeto opensource de ferramentas de bioinformática, o OpenBiomind, cujo principal mantenedor é o amigão Lúcio “Dr. Omni” Coelho.

O Futuro: Nanofluídica

Quando reduzimos ainda mais a escala saímos da microfluídica e entramos em algo ainda mais complexo, a nanofluídica. Agora os “canos” dos circuitos fluídicos são tão pequenos que sua espessura pode ser medida em moléculas dos fluidos que passam por eles (são usados, por exemplo, nanotubos de carbono). Nessa escala a noções como viscosidade e as propriedades elétricas das moléculas envolvidas são completamente diferentes do que se observa em circuitos fluídicos e microfluídicos, produzindo efeitos extremamente interessantes, como a dupla camada elétrica produzida usando nanocapilares.

As pesquisas em nanofluídica despertam muito interesse hoje; os planos são o desenvolvimento, por exemplo, de “laboratórios em um chip”, um circuito nanofluídico e microfluídico capaz de realizar uma série de experimentos bioquímicos de forma autônoma, usando amostras reduzidíssimas de material. Esses laboratórios poderiam ser utilizados em diagnóstico de doenças, monitoramento e análise de ambientes, aplicações de segurança como detecção de armas químicas e explosivos.

A Fluídica não é mera curiosidade histórica ou recurso didático. Como a maioria das tecnologias, as previsões feitas a respeito de como ela seria utilizada se mostraram bem distantes da realidade; ao mesmo tempo, as aplicações reais desenvolvidas acabam se mostrando ainda mais fantásticas e interessantes que os sonhos dos primeiros pesquisadores.

Biotecnologia, Robótica, Teoria da Computação 2 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5,00 out of 5)

Computadores Mecânicos feitos com LEGO

Costumo dizer que a palavra preferida de cientistas da computação é abstração: de sistemas complexos de software até o nível mais baixo no hardware, quase tudo que fazemos tem a ver com abstrair os detalhes do nível abaixo para realizar de forma simples tarefas no nível superior. Ao acessar à Internet com seu browser, por exemplo, você não precisa fazer a menor idéia de como a informação é transmitida por cabo, linha de telefone ou rede sem fio.  Abstraímos esses detalhes dizendo que estamos apenas conectados à Internet.

E, se fosse pra escolher a abstração preferida dos cientistas da computação, eu diria que é a Máquina de Turing (proposta pelo genial Alan Turing em 1936). Todo computador – do seu celular ou videogame até o maior supercomputador do mundo – pode ser visto como uma Máquina de Turing. Ela é um modelo matemático simplificado do que é um computador. Qualquer programa de computador pode ser reescrito para ser executado por uma máquina de Turing.  Provar que é impossível resolver um problema usando uma Máquina de Turing é provar que nenhum computador é capaz de resolver esse problema.

A Máquina de Turing é uma abstração, um conceito – não existe de forma concreta. Quando você constrói um computador, você está implementando parcialmente uma máquina de Turing (a Máquina de Turing ideal tem memória infinita). Ela segue regrinhas simples: os programas e os dados são escritos numa fita (imagine uma fita de papel ou uma fita magnética) e a máquina lê as instruções e os dados da fita, toma decisões simples, e escreve os resultados na fita. Seu computador lê do disco rígido ou da rede, e mostra informações na tela, mas no fim das contas funciona como se lesse ou escrevesse da fita (ou seja, a fita é uma abstração dos dispositivos de entrada, saída e armazenamento).

Recentemente fez sucesso (pelos tradicionais 15 minutos) um vídeo de uma Máquina de Turing feita de LEGO, mostrado abaixo.

Eu disse que todo computador é uma Máquina de Turing; isso significa que alguém construiu um computador de verdade, completamente mecânico, apenas com pecinhas de plástico ? Estamos acostumados a computadores eletrônicos; será possível um computador mecânico, movido a manivela ?

Infelizmente, não. A tal da Máquina de Turing de LEGO é só uma brincadeira, uma ilustração, é uma máquina de Turing de mentirinha. Quem controla todo o movimento da máquina é na verdade um pequeno microcomputador eletrônico, um módulo do LEGO Mindstorms. Ora, o microcontrolador dos Mindstorms é uma implementação eletrônica da Máquina de Turing, então nossa esperança de um computador não-eletrônico feito de LEGO foi por água abaixo!

Mas não desanimem ainda. Várias décadas antes do Alan Turing, Charles Babbage, um inventor do século XIX, propôs dois mecanismos interessantíssimos, a Máquina Diferencial (ou Máquina de Diferenças) e a Máquina Analítica. As duas eram completamente mecânicas, parecidas com um relógio extremamente complexo, e projetadas para serem movidas por um motor a vapor (ou qualquer outra coisa capaz de girar uma manivela).

A Máquina Diferencial era capaz de realizar cálculos matemáticos bastante complexos. Ela chegou a ser construída na época, mas Babbage nunca conseguiu terminá-la. Muitos anos depois, especialistas completaram uma Máquina Diferencial seguindo as plantas originais, e mostraram que ela realmente funcionava. Esse modelo completo pode ser visto no Museu de Ciências de Londres (que aliás é um passeio espetacular pra quem estiver visitando a Inglaterra – eu passei um dia inteiro lá).

Já a Máquina Analítica nunca saiu do papel – pelo menos não da forma imaginada por Babbage. A Máquina Analítica seria um computador programável completo, totalmente mecânico, nos moldes da Máquina Diferencial. Era, portanto, uma Máquina de Turing mecânica – algo espetacular e tão complexo que mesmo hoje em dia não é viável implementá-la, apesar de todos os conceitos importantes terem sido corretamente planejados por Babbage. A primeira implementação real de uma Máquina Turing – ou seja, o primeiro computador – só veio muitos anos depois, com o advento dos componentes eletrônicos e eletromecânicos.

E o LEGO ? Bom, a máquina de Turing em LEGO é de brincadeirinha, e uma Máquina Analítica mecânica nunca foi construída. Mas teve gente que construiu uma Máquina Diferencial de LEGO, um feito genuinamente incrível! Não é um computador de verdade, mas é o mais próximo que já se chegou disso com mecanismos de plástico:

Máquina Diferencial em LEGO

Máquina Diferencial em LEGO

Acharam bizarro ? Aguardem então meu próximo artigo, em que quero falar de computadores a água. E não estou falando de usar água para fornecer energia a computadores mecânicos ou eletrônicos, mas sim de usar água ao invés de elétrons, e canos ao invés de fios, num dispositivo sem partes móveis. Depois da Mecânica e da Eletrônica, chegou a vez Fluídica!

Robótica, Teoria da Computação 5 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)

Sobre futebol e robôs

Imagination will often carry us to worlds that never were. But without it we go nowhere.” Carl Sagan

Este é o primeiro de uma série de posts descrevendo uma paixão antiga minha, fruto de um trabalho de pesquisa iniciado há mais de 12 anos: o futebol de robôs. Apesar (ou justamente por isso) de ser um perna-de-pau de primeira na vida real, me envolvi nesta que é, para a maior parte dos mortais, uma modalidade esportiva (?) no mínimo curiosa.

O futebol de robôs surgiu na primeira metade dos anos 90 como uma forma divertida de desenvolver as habilidades de robôs autônomos atuando em equipe para atingir uma determinada meta. Para os que acham que é uma mera brincadeira, há diversos exemplos sérios e concretos de como a tecnologia desenvolvida pode ser útil para a humanidade:

  • tarefas repetitivas mas não facilmente automatizáveis, como limpar a sua casa:

Rosie the robot

  • lavar as louças:

Ops, como eu ia dizendo, diversos exemplos sérios e concretos:

  • tarefas em ambientes inóspitos ou perigosos, como dar manutenção em gasodutos, implantar bases submarinas para extração de petróleo ou reparar linhas de transmissão de alta-tensão;

  • situações extremas onde é necessário tomadas muito rápidas de decisão, como a automação do controle de veículos na iminência de um acidente;

  • e qualquer outra situação onde o ser humano não possa ou não deva agir, por risco ou por incapacidade, e que haja necessidade de tomada de decisão rápida com base em variáveis do ambiente e em eventual comunicação com outros agentes (planejamento em equipe).

A menção ao futebol de robôs geralmente traz ao imaginário leigo imagens de robôs humanóides driblando, fazendo embaixadinhas e comemorando os gols. Apesar disto ser o objetivo final destes projetos, algo assim só deverá ser alcançado, na mais otimista das hipóteses, daqui a 20 anos. Hoje até já temos robôs humanóides, mas uma partida típica nesta categoria ainda se parece mais com um jogo de idosos portadores de esclerose múltipla, ou outra disfunção motora:

Portanto, para evitar frustrações, vamos assumir que me refiro especificamente à categoria das “caixinhas com rodas”: pequenos robôs capazes de “empurrar” a bola até o gol, desviando dos adversários quando possível:

Sim, eu sei que tem muito menos glamour do que os tais humanóides esclerosados acima, mas como sempre dizia meu grande orientador na graduação, Prof. Mário Campos, KISS (Keep It Simple, Stupid).

Nesta categoria, de pequenas caixinhas com rodas, os dois campeonatos mais conhecidos são a copa RoboCup e a copa Mirosot. Foi nessa última que nós participamos nos idos de 1998 e 1999, inclusive conquistando um honroso título de campeão sul-americano em 1999 (ok, os outros times não eram lá muito fortes também, mas ninguém precisa ficar sabendo disso).

Então vamos começar a falar do que interessa: a tecnologia. O projeto de um time de futebol de robôs envolve diversos estágios multi-disciplinares:

  • projeto mecânico;

  • projeto elétrico e eletrônico;

  • componentes de software para suporte (sensoriamento e transmissão de comandos);

  • componentes de software para estratégia e controle.

Tentarei dar uma breve visão dos últimos dois itens, especialmente nos componentes de visão (sensoriamento), controle e estratégia. São estes três os itens que mais me interessam, e que, suponho, sejam de maior interesse dos leitores deste blog. Portanto, este artigo será seguido de três outros, cada um descrevendo uma dessas três áreas.

Espero também que os leitores mais técnicos me perdoem pelo estilo literário menos científico. Mantendo a linha editorial do blog, pretendo escrever da forma mais simples possível para o leigo. Sempre que possível, deixarei referências para quem quiser se aprofundar no assunto.

Renato Mangini é arquiteto de software sênior. Foi sócio fundador da Vetta Technologies e da Vetta Labs e hoje ele trabalha em sua startup de tecnologia (nome e produto ainda não divulgados). Sua formação acadêmica inclui um bacharelado em Ciência da Computação e um mestrado inacabado, ambos pela UFMG, e cursa agora um MBA no Ibmec.

Inteligência Artificial, Robótica 3 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)

Otimização inspirada em formigas

O campo de inteligência artificial é cheio de técnicas inspiradas na natureza. Os dois exemplos mais famosos são redes neuronais, que emulam grupos de neurônios e suas conexões, e algoritmos genéticos, que tentam resolver um problema codificando a solução nos genomas de uma população artificial, sujeita à sobrevivência e recombinação dos mais fortes. Talvez falemos mais dessas técnicas por aqui, se houver interesse.

Hoje eu vou falar de uma outra técnica, ou família de técnicas: Ant Colony Optimization (ACO), ou otimização de colônias de formigas. ACO foi inventada por Marco Dorigo em 1992, e se baseia na capacidade de grupos de formigas de apresentar comportamento coletivo muito mais inteligente que o que uma formiga sozinha seria capaz de fazer. Por exemplo, formigas podem achar o melhor caminho entre o formigueiro e uma fonte de comida. Se algum obstáculo mudar o terreno, elas se adaptam rapidamente e encontram um novo caminho, como você pode ver na figura abaixo.

Adaptando o caminho

Isso acontece porque as formigas se “comunicam” de forma indireta, através do ambiente, usando feromônios. As formigas deixam uma trilha de feromônio pelo caminho que seguem. Quanto menor o caminho, mais forte o feromônio. Outras formigas tendem a seguir o feromônio mais forte. Caminhos alternativos, e piores, são abandonados porque o feromônio mais fraco depositado ali evapora com o tempo. Esse é o princípio básico de Ant Colony Optimization. O Dorigo usou essa capacidade para resolver o clássico problema do Caixeiro Viajante, com excelentes resultados.

Isso foi em 92. Hoje, o trabalho do Dorigo e de outros pesquisadores deu origem a todo um subcampo de pesquisa em computação, chamado de Inteligência de Enxame, que se baseia na premissa de usar agentes muito simples, mas que colaboram entre si, para atingir objetivos complexos e de forma robusta, ou seja, tolerante a falhas e mudanças no ambiente. Um exemplo interessante, também baseado em formigas, é clustering. As formigas sabem naturalmente agrupar objetos por grupos e fazem isso para limpar o formigueiro, separando comida de lixo.

Antes do agrupamentoDepois do agrupamento

A combinação de robustez e inteligência coletiva é muito interessante pro pessoal que trabalha com robótica. Agentes simples são baratos, se você tem um grupo de robôs que pode se adaptar à perda de um deles, por falha mecânica, falta de energia ou qualquer outro motivo, diminuem as chances de seu enorme investimento em robôs ir por água abaixo por um detalhe bobo.

O casamento de inteligência de enxame com robótica atende pelo nome de Swarm Robotics. Os robozinhos, sempre trabalhando em equipe, realmente têm um comportamento coletivo interessante. Por exemplo, eles aprendem que podem se conectar, formando um objeto maior, para passar por um obstáculo intransponível para um único robô:

Saltando um obstáculo

Eles também conseguem transportar grandes objetos, navegar um terreno em formação e otras cositas más. Aqui tem um bando de videos bacanas.

Inteligência Artificial, Robótica 1 Comentário

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5,00 out of 5)