Um dos projetos que eu sempre sonhava em implementar eram os bots de tarefas modulares com memória. O objetivo final do projeto era criar um mundo com criaturas capazes de agir de forma independente e coletiva.
Eu costumava programar geradores mundiais, então queria preencher o mundo com bots simples que usam IA para determinar seu comportamento e interações. Assim, graças à influência dos atores no mundo, foi possível aumentar seus detalhes.
Eu já implementei o sistema básico de pipeline de tarefas Javascript (porque simplificou minha vida), mas queria algo mais confiável e escalável, por isso escrevi esse projeto em C ++. A competição pela implementação do jardim processual na geração subreddit / r / procedural me levou a isso (daí o tópico correspondente).
No meu sistema, a simulação consiste em três componentes: o mundo, a população e um conjunto de ações que os conectam. Portanto, eu precisava criar três modelos, os quais discutirei neste artigo.
Para aumentar a dificuldade, eu queria que os atores mantivessem informações sobre experiências anteriores com o mundo e usassem o conhecimento sobre essas interações em ações futuras.
Ao criar um modelo do mundo, escolhi um caminho simples e usei o ruído Perlin para colocá-lo na superfície da água. Todos os outros objetos no mundo foram localizados absolutamente aleatoriamente.
Para o modelo de população (e sua "memória"), simplesmente criei uma classe com várias características e coordenadas. Era para ser uma simulação de baixa resolução. A memória é uma fila, os bots são procurados, salvam informações sobre seu ambiente, gravam na fila e gerenciam essa fila como uma interpretação de sua memória.
Para conectar esses dois sistemas de ações, eu queria criar uma estrutura de tarefas primitivas dentro de um sistema hierárquico de filas de tarefas, para que entidades individuais pudessem implementar um comportamento complexo no mundo.
Mapa de exemplo. A água tomou a forma de um rio completamente sem intenção. Todos os outros elementos estão localizados aleatoriamente, incluindo o formigueiro, que nesta semente é deslocado muito longe para a beira (mas o rio parece bonito).Decidi que um monte de formigas nas folhas coletoras de grama se tornaria um bom modelo de teste que garante a confiabilidade da implementação de funções básicas (e o sistema da fila de tarefas como um todo) e evita vazamentos de memória (havia muitas).
Quero descrever com mais detalhes a estrutura dos sistemas de tarefas e da memória e também mostrar como a complexidade foi criada a partir (principalmente) de funções básicas primitivas. Também quero mostrar alguns "vazamentos de memória de formigas" engraçados que você pode encontrar quando as formigas começarem a correr loucamente em círculos em busca de grama ou ficarem paradas e tornarem o programa mais lento.
Estrutura geral
Eu escrevi essa simulação em C ++ e usei o SDL2 para renderização (eu já escrevi uma pequena classe de apresentação para o SLD2 antes). Também usei a implementação A * (ligeiramente modificada) que encontrei no github porque
minha implementação era irremediavelmente lenta e não conseguia entender o porquê.
Um mapa é apenas uma grade 100 × 100 com duas camadas - uma camada de solo (usada para procurar caminhos) e uma camada de preenchimento (para concluir caminhos de interação e pesquisa). A classe mundial também lida com várias funções cosméticas, como o crescimento de grama e vegetação. Estou falando sobre isso agora, porque essas são as únicas partes que não serão descritas no artigo.
A população
Bots estavam em uma classe com propriedades que descreviam uma única criatura. Alguns deles eram cosméticos, outros influenciaram a execução de ações (por exemplo, a capacidade de voar, o alcance da visão, o que come e o que a criatura pode usar).
Os mais importantes aqui foram os valores auxiliares que determinam o comportamento. Ou seja: um vetor contendo seu caminho atual A *, para que não precise ser contado em cada ciclo do relógio (isso economiza tempo de computação e permite simular mais bots) e uma fila de memória que define as criaturas que interpretam seu ambiente.
Fila de memória
Uma fila de memória é uma fila simples que contém um conjunto de objetos de memória limitados em tamanho por uma propriedade bot. Cada vez que novas memórias eram adicionadas, elas eram empurradas para a frente e tudo o que passava além das fronteiras atrás era cortado. Graças a isso, algumas lembranças podem ser mais "frescas" do que outras.
Se o bot queria recuperar informações da memória, ele criou um objeto de memória (pedido) e o comparou com o que estava na memória. Em seguida, a função de rechamada retornou um vetor de memórias que correspondiam a algum ou a todos os critérios especificados na consulta.
class Memory{ public:
As memórias consistem em um objeto simples que contém várias propriedades. Essas propriedades de memória são consideradas "associadas" uma à outra. Cada memória também recebe um valor de "recallScore", que é iterado cada vez que as memórias são lembradas pela função de recall. Cada vez que o bot se lembra das memórias, ele executa uma classificação de uma passagem, começando por trás, mudando a ordem das memórias se o recallScore de uma memória antiga for maior que o de uma nova. Graças a isso, algumas memórias podem ser mais "importantes" (com grandes tamanhos de memória) e armazenadas por mais tempo na fila. Com o tempo, eles serão substituídos por novos.
Filas de memória
Também adicionei vários operadores sobrecarregados a essa classe para que comparações diretas entre a fila de memória e a consulta possam ser executadas, comparando as propriedades "any" ou "all", para que somente as propriedades especificadas sejam substituídas quando a memória for substituída. Graças a isso, podemos ter a memória do objeto associada a algum lugar, mas se olharmos novamente para esse local e o objeto não estiver lá, podemos atualizar a memória substituindo-a pela memória que contém um novo bloco de preenchimento, usando a consulta correspondente a esse local .
void Bot::updateMemory(Memory &query, bool all, Memory &memory){
No processo de criação do código para esse sistema, aprendi muito.
Sistema de tarefas
A natureza do loop ou da renderização do jogo é que as mesmas funções são repetidas em todas as medidas; no entanto, eu queria implementar um comportamento não cíclico nos meus bots.
Nesta seção, explicarei duas visões sobre a estrutura do sistema de tarefas projetado para combater esse efeito.
Estrutura de baixo para cima
Decidi passar de baixo para cima e criar um conjunto de "ações primitivas" que os bots devem executar. Cada uma dessas ações dura apenas uma batida. Com uma boa biblioteca de funções primitivas, podemos combiná-las em ações complexas que consistem em várias primitivas.
Exemplos de tais ações primitivas:
Observe que essas ações contêm referências ao mundo e à população, permitindo que você as altere.
- A espera faz com que a criatura não faça nada nesse loop.
- O Look analisa o ambiente e enfileira novas memórias.
- O swap pega um objeto na mão da criatura e o substitui por um deitado no chão.
- Consumir destrói o item na mão da criatura.
- Etapa leva o caminho calculado atual para o destino e executa uma etapa (com várias verificações de erro).
- ... e assim por diante.
Todas as funções de tarefas são membros da minha classe de tarefas; após testes rigorosos, eles comprovaram sua confiabilidade e capacidade de combinar tarefas mais complexas.
Nessas funções secundárias, construímos funções simplesmente encadeando outras tarefas:
- A tarefa de caminhada é apenas algumas etapas (com tratamento de erros)
- A tarefa take é a tarefa look and swap (é necessária devido ao processamento da memória ant, que explicarei mais adiante)
- A tarefa inativa é selecionar um local aleatório e mudar para lá (usando caminhada), aguardar vários ciclos (usando espera) e repetir esse ciclo por um determinado número de vezes
- ... e assim por diante
Outras tarefas são mais complicadas. A tarefa de pesquisa executa uma consulta de memória para procurar por memórias de locais que contêm o objeto "comida" (comestível para esse tipo de bot). Ela baixa essas memórias e percorre todas elas, “procurando” comida (no caso das formigas, isso é grama). Se não houver lembranças alimentares, a tarefa faz a criatura vagar aleatoriamente pelo mundo e olhar em volta. Observando e estudando (fazendo um "olhar" com viewRadius = 1; isto é, olhando apenas para o ladrilho embaixo), a criatura pode atualizar sua memória com informações sobre seus arredores, procurando comida de maneira inteligente e intencional.
Uma tarefa forrageira mais generalizada consiste em encontrar comida, pegar comida, inspecionar (para atualizar a memória e encontrar comida na vizinhança), voltar para casa e armazenar comida.
Você pode notar que as formigas saem do formigueiro e procuram comida de propósito. Devido à inicialização, o caminho inicial das formigas é direcionado para um ponto aleatório, porque sua memória em t = 0 está vazia. Eles recebem a ordem de pegar comida na tarefa de forragem e também olham em volta, certificando-se de que não há mais comida. De tempos em tempos, começam a perambular, porque ficam sem lugares onde viram comida (falta de visão ameaçadora).E, finalmente, o bot tem uma "visão" que determina o tipo de IA atribuído a ele. Cada visualização é associada a uma tarefa de controle que define todo o seu comportamento: consiste em uma cascata de tarefas cada vez menores, facilmente determinadas por um conjunto de filas de memória e tarefas primitivas. Estas são tarefas como Ant e Bee.
Estrutura de cima para baixo
Se você olhar de cima para baixo, o sistema consiste em uma classe de mestre de tarefas que coordena as tarefas de controle e sua execução para cada bot individual no mapa.
O Taskmaster possui um vetor de tarefas de controle, cada uma delas associada a um bot. Cada tarefa de controle, por sua vez, possui uma fila de subtarefas carregadas durante a primeira inicialização do objeto de tarefa com a função de tarefa associada.
class Task{ public:
Cada objeto de tarefa na fila armazena uma matriz de argumentos, que são transmitidos ao manipulador de funções associado. Esses argumentos determinam o comportamento dessas tarefas primitivas criadas da maneira mais geral possível. Os argumentos são passados por referência, para que o objeto de tarefa na fila possa armazenar seus argumentos e permitir que suas subfunções sejam alteradas, para que você possa implementar coisas como iterações para aguardar um certo número de ticks ou solicitações para coletar um certo número de itens, etc. As subfunções alteram o valor do iterador (argumento [n]) da função pai por referência e tornam sua condição de sucesso dependente de seu valor.
Em cada medida, o mestre de tarefas percorre a lista de tarefas de controle e as executa chamando seu método de execução. O método perform, por sua vez, examina o elemento superior da fila dentro da tarefa e o executa com os argumentos da tarefa. Assim, você pode cascatear a fila de tarefas, sempre executando a tarefa mais alta. Em seguida, o valor de retorno da tarefa determina a conclusão da tarefa.
Quando uma tarefa primitiva retorna true, ela atingiu seu ponto estável, ou pelo menos não deve ser repetida (por exemplo, step retorna true quando a criatura atinge o ponto final). Ou seja, sua condição de retorno é satisfeita e é removida da fila para que a próxima tarefa possa ser concluída na próxima medida.
Uma tarefa que contém uma fila de tarefas retorna true após a fila estar vazia. Graças a isso, é possível criar tarefas complexas com a estrutura de filas e sub-filas nas quais as mesmas funções são chamadas constantemente, mas cada chamada itera o estado do jogo e o estado da tarefa em uma etapa.
Finalmente, as tarefas de controle usam uma estrutura simples - elas são chamadas em cada ciclo, carregam a tarefa apenas se estiverem vazias e, de outra forma, executam tarefas carregadas em sua fila.
Com a ajuda do meu loop de fila (consulte o código), posso executar repetidamente uma função e cada vez que executar o elemento superior em sua fila, retirando elementos dela se chamar o método perform retornar true.
Resultados
Tudo isso está envolvido no libconfig, portanto os parâmetros de simulação são muito fáceis de mudar. Você pode codificar muitas tarefas de controle sem problemas (criei formigas e abelhas), e definir e carregar novas espécies usando libconfig é surpreendentemente simples.
Eles foram elegantemente carregados na simulação. Graças a uma nova pesquisa aprimorada de caminhos, posso simular um grande número de bots ativos individuais coletando alimentos em um plano bidimensional.
Simulação de 40 formigas coletando grama ao mesmo tempo. Os caminhos que eles criam na areia se devem ao aumento do peso atribuído à terra "intocada". Isso leva à criação de "estradas de formigas" características. Eles também podem ser interpretados como feromônios, mas seria mais parecido com a verdade se as formigas realmente trocassem memórias.A modularidade desse sistema garante a rápida criação de novas espécies cujo comportamento é determinado por uma simples tarefa de controle. No código acima, você pode ver que eu criei worms e abelhas de IA simplesmente mudando de cor, restrições de pesquisa de caminho (elas não podem voar), alcance de visibilidade e tamanho da memória. Ao mesmo tempo, mudei seu comportamento geral, porque todos esses parâmetros são usados por funções de tarefas primitivas.
Depurando memórias Ant
A estrutura de tarefas e memória complexas levou a dificuldades imprevistas e à necessidade de lidar com exceções.
Aqui estão três erros de memória particularmente complexos que me fizeram refazer os subsistemas:
Formigas correndo em círculo
Um dos primeiros insetos que tive que enfrentar: formigas corriam loucamente pelo padrão fechado na praça em busca de grama no chão nu. Esse problema surgiu porque naquela época eu ainda não havia implementado uma atualização de memória. As formigas tinham lembranças da localização da comida e, assim que pegaram a grama e olharam em volta novamente, novas lembranças se formaram.
O problema era que a nova memória estava no mesmo ponto, mas a antiga foi preservada. Isso significava que, no processo de busca de alimentos, as formigas se lembravam e mantinham a localização dos alimentos que não eram mais válidos, mas essas memórias antigas eram preservadas e substituíam novas (elas se lembravam dessa deliciosa erva).
Corrigi-o da seguinte forma: os dados do objeto são simplesmente substituídos em memórias antigas, se virmos o mesmo lugar e o objeto mudar (por exemplo, a criatura vê que não há mais grama ali, mas não se lembra que costumava haver grama). Talvez, no futuro, apenas adicione a propriedade "inválida" às minhas memórias, para que os robôs possam lembrar informações antigas que possam ser importantes, mas as informações que não são mais válidas "apareceram" ("vi um urso aqui, mas agora não está lá").
Formigas pegam objetos sob outras formigas
De tempos em tempos (especialmente com um grande número de formigas e uma alta densidade de grama), duas formigas podem pegar um pedaço de grama de uma só vez e tentar pegá-lo. Isso significava que a primeira formiga entrou no ladrilho, olhou em volta e pegou o item em 3 etapas. Por sua vez, a segunda formiga fez o mesmo, apenas logo antes de levantar o objeto, outra formiga o pegou debaixo do nariz. Ele calmamente continuou suas tarefas, examinando o mesmo ambiente que a outra formiga na medida anterior, e processou sua linha de memória da mesma maneira (porque nesse estágio suas memórias são idênticas). Isso levou a segunda formiga a copiar a primeira, nunca pegando objetos e seguindo a primeira, o que realmente fez todo o trabalho. Percebi isso porque, na simulação das cinco formigas, apenas três eram visíveis. Demorou muito tempo para encontrar a causa.
Resolvi esse problema, tornando a tarefa de troca primitiva e criando a tarefa take, que primeiro olha para o chão para ver se há um objeto lá. Se for, "troca" e, se não, "espera" por dois movimentos, para que a outra formiga saia definitivamente. Em um caso, essa ação é para duas medidas, no outro - para uma medida.
Locais inacessíveis
Outro bug desagradável que me forçou a refazer o processamento da memória foi que alguns lugares que a formiga podia ver eram inatingíveis para ele. Eles surgiram por causa da minha preguiçosa colocação de "grama cruzada" em terra, que às vezes pairava sobre a água. Isso me fez generalizar a tarefa da etapa.
Ao transmitir um pedido de busca de alimentos, as formigas geralmente tinham lembranças de lugares que realmente não podiam alcançar (viam grama acima da água e
insanamente desejavam recolhê-la). Se não estava marcado em sua memória (por exemplo, a variável booleana “alcançável”), eles continuaram lembrando e gravando na fila até que essa ação fosse a única. Isso causou uma inibição severa, porque eles
executavam constantemente operações de localização de caminhos em cada medida, tentando chegar lá e falhavam .
A solução foi atualizar a memória na tarefa da etapa se ela não conseguir encontrar o caminho para o local, marcando-a na memória como inatingível. Além disso, a tarefa de pesquisa consulta apenas locais com comida em busca de memórias alcançáveis.
Sistema em geral
Em geral, quero dizer - sim, me arrependo de ter passado uma semana da minha vida em uma maratona de programação porque fui inspirado a criar bots que fazem o que lhes digo (e também o que eles querem fazer!). Eu tive que fazer alguns truques e aprendi muito.
O sistema que criei não é 100% confiável e ainda percebo alguns artefatos. Por exemplo, como a direção para analisar a aparência, a ação é usada de cima para baixo e esquerda-direita, ou seja, a última memória está no canto inferior direito. Ao recuperar informações para procurar itens, isso significa que as criaturas tenderão a se mover para sudeste. Isso é especialmente notável em grandes simulações, quando a grama cresce rapidamente e se inclina levemente em direção ao sudeste, independentemente da semente.
Aprimoramentos
Penso que são necessárias melhorias significativas para simular memórias mais complexas de criaturas mais complexas.
Isso inclui aumentar a confiabilidade das funções de processamento de memória, além de adicionar novas primitivas, como "pensar" e derivados de tarefas de alto nível, como "decidir" ou "sonhar". "Pensar" pode ser uma ação primitiva de uma solicitação de memória. Um "sonho", por sua vez, pode consistir em várias chamadas de "pensar": escolher uma memória aleatória, obter uma propriedade aleatória e repeti-la repetidamente para reforçar temas comuns ou associações importantes.
Para o futuro, planejo três adições específicas:
- Adicione manipulação de interrupção e priorização de tarefas
- Adicionar comunicação entre entidades
- Adicione uma estrutura de grupo para que as entidades possam se identificar formalmente
A interrupção do processamento e a priorização de tarefas podem ser necessárias para a interação entre entidades, porque o bot não pode continuar cegamente suas atividades quando se comunica com ele (deve de alguma forma "ouvir") ou é atacado ("foge" ou "luta" )
A comunicação entre entidades provavelmente consiste em uma ou duas tarefas primitivas para trocar memórias ou fazer solicitações às memórias de outros bots (por exemplo, "diga" ou "pergunte"). Dessa forma, informações como a localização de alimentos ou outros recursos podem ser transmitidas.
Espero implementar essas tarefas e elaborar um gráfico da taxa de acumulação de recursos por um grande grupo com e sem comunicação. A população já está acompanhando a quantidade de alimentos coletados em cada medida. Seria interessante mostrar que compartilhar memórias pode afetar a eficiência.
O futuro
A função mais importante para simular comunidades será adicionar estruturas de grupo e dotar esses grupos de propriedades em nível macro, por exemplo, seus “objetivos e responsabilidades” comuns. Isso nos dá um tipo de "semente" a partir da qual podemos obter tarefas de alto nível delegadas na hierarquia das estruturas de grupos para "tarefas inferiores de alto nível" que afetam diretamente o mundo. Também permite criar uma forma de estrutura política.
Esse sistema é bastante auto-suficiente e a visualização é simplesmente sobreposta a ele. Será muito simples substituir insetos por humanóides, coletando recursos e armazenando-os em algum lugar, para que cresçam em tamanho.
A natureza do crescimento de sua casa pode, por exemplo, ser muito dependente ou completamente independente das ações dos bots. Diferentes espécies podem ter tribos diferentes, com características e tendências diferentes.Além disso, eu posso combinar esse sistema com geradores de mapas criados anteriormente (expandindo a classe mundial) para tornar o mundo mais real.Em conclusão
No futuro próximo, pretendo substituir as criaturas por pessoas e implementar algumas das últimas funções. Talvez eu publique o código fonte completo quando melhorar a qualidade do sistema (em alguns lugares, o código é bastante caótico).Aguarde o próximo artigo. Enquanto isso, aqui está um vídeo com abelhas procurando pólen em flores; eles são codificados usando a mesma estrutura.Eu escolhi essa semente porque o ponto de partida está localizado em uma pequena ilha. No entanto, as abelhas não são programadas para retornar à colméia, mas simplesmente coletam constantemente o pólen. Você pode perceber que a visão deles é maior e, às vezes, eles intencionalmente se movem para a flor que acabaram de ver.... e aqui está a função do membro Bee Task: bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){