Mobilidade de agentes

2:34 pm Robótica

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. :)

2 Respostas
  1. Carlos Augusto :

    Date: julho 14, 2010 @ 6:39 pm

    Muito interessante os diversos tipos de algoritmos sobre movimentação de agentes. De fato, algo muito curioso, em especial os diagramas de Voronoi que criam figuras tão orgânicas… Espero continuar a ver sua evolução nestes estudos… Keep it up!

  2. Moisés :

    Date: julho 15, 2010 @ 10:07 pm

    E eu achava que era tão simples…