Nesse artigo os autores apresentam os resultados da evolução de controladores baseados em redes neurais para carros de corrida radio controlados. Os experimentos foram realizados em um simulador criado por eles. Várias pistas com diferentes níveis de dificuldade foram usadas durante o processo.

A evolução dos controladores é baseada em algoritmos genéticos. Em alguns testes, permite-se que a posição e alcance dos sensores de distância instalados no carro também evoluam. Os controladores são redes neurais com três camadas. As entradas vêm dos sensores e as saídas são comandos para o carro.

O carro percebe o ambiente através de dois tipos de sensores: de waypoint e de obstáculo. O sensor de waypoint dá a diferença entre a orientação atual do carro e o angulo para o próximo waypoint. A distância não é medida pelo sensor mas é considerada pela função de avaliação. Já os sensores de obstáculo medem a distância que o carro encontra-se do obstáculo, que no caso do experimento são as paredes.

Os melhores resultados são obtidos quando um controlador genérico é especializado para uma nova pista ao invés de evoluir um novo controlador do zero.

Download

Nesse artigo, redes neurais são evoluídas com o intuito de alertar motoristas sobre situações perigosas. Os testes são realizados em um simulador de corrida de carros chamado RARS que foi criado para avaliação de métodos de Inteligência Artificial para controle de tempo real. Para tal, foi necessário que uma rede neural que dirija o carro fosse evoluída. Esse é o ponto do artigo que tem mais relevância no contexto de navegação de NPCs.

O método usado para evolução das redes neurais foi a o NEAT (NeuroEvolution of Augmenting Topologies). Esse método é capaz de evoluir a topologia da rede de acordo com a complexidade do problema.

O treinamento dessas redes neurais que alertarão o motorista sobre situação de risco exigem um motorista que cometa alguns erros. Esse motorista foi obtido gerando um pequeno ruído nos pesos de uma rede neural que controla o carro de maneira correta.

A parte mais interessante desse artigo é como essas redes neurais são evoluídas. A função de avaliação leva em conta os danos causados ao veículo que por sua vez considera o fato do carro passar por fora da pista (que não é completamente delimitada por muros). O controlador percebia o ambiente através de sensores de distância.

Tal experimento obteve um motorista cujo desempenho foi satisfatório, superando alguns dos melhores NPCs motoristas para pista de testes.

Download

Links relacionados:

• Reynolds Engineering e Design:
  • Steering Behaviors For Autonomous Characters
  • Navigational Overview
• Togelius:
  • How better AI can make racing games more fun: discute como um NPC piloto que modela os comportamentos de um jogador humano (através de redes neurais) pode ser usado para construir pistas de corrida mais divertidas.
  • Evolutionary car racing videos: apresenta alguns vídeos com os resultados dos experimentos que envolveram a evolução de um conjunto de redes neurais para controlar carros em uma corrida.
  • Another evolutionary car racing video: mais um resultado do experimento anterior. Nessa pista, em particular, existem caminhos alternativos.
• Using Particle Swarm Optimization for Offline Training in a Racing Game

Download

O artigo apresenta duas otimizações simples capazes de diminuir o número de operações realizadas na estrutura que representa a open list (normalmente usa-se uma fila de prioridades implementada através um heap binário) do A*. Conseqüentemente, diminui-se o tempo de execução do algoritmo em questão.

A primeira otimização ocorre se o algoritmo retira da open list um nó com o f-value igual a f e, durante sua expansão, um de seus filhos possui um f-value também igual a f. Nesse caso, pode-se expandir diretamente esse filho sem a necessidade de inseri-lo na open list e remove-lo em seguida. Isso é possível apenas porque os f-values são monotonicamente não decrescentes (assumindo que a heurística usada é monotônica e que os custos das arestas do grafo pesquisado são positivos). No artigo, denota-se tal técnica por A* Variant 1.

Na segunda otimização, o algoritmo gera todos os filhos de um determinado nó. Seja n o nó que possui o menor f-value f presente nesse conjunto. O nó n será expandido diretamente se f não é maior que o f-value do menor nó presente na open list. Novamente, isso só é possível devido a monotonicidade não decrescente dos f-values (garantida pelas mesmas suposições adotadas na primeira otimização). No artigo, denota-se tal técnica por A* Variant 2.

Essas otimizações foram avaliadas experimentalmente no algoritmo A* e no algoritmo GAA*. Também variou-se a estrutura de dados utilizada para implementar a open list adotando um heap binário e buckets. Na implementação utilizando buckets (de acordo com o código fornecido pelos autores) cada bucket é um arranjo e dentro desse bucket todos elementos possuem o mesmo f-value. Dessa forma, as operações de inserir e remover são mais rápidas na estrutura implementada através de buckets do que no heap binário.

Avaliando os resultados dos experimentos chega-se a três conclusões:

• Se a open list é implementada através de buckets as operações são rápidas e o overhead da implementação das otimizações supera o economia de tempo proporcionada. Já se a open list é implementada através de um heap binário, as operações são mais lentas e ocorre exatamente o contrário: o beneficio das otimizações supera seu custo.
• A variação 1 gerou melhores resultados do que a variação 2 devido ao custo associado a essa última.
• A variação 1 no GAA* gerou resultados melhores do que no A* devido a forma como o h-value é atualizado nesse algoritmo.

Download

Download

O artigo propõe estruturas de dados (filas de prioridades) capaz de implementar o algoritmo de Dijkstra (menor caminho entre dois nós de um grafo) eficientemente. As três estruturas propostas são: one level radix heap, two level radix heap e two level radix heap combinado com o Fibonacci heap.

A principal propriedade do algoritmo de Dijkstra usada nessas estruturas (chamadas genericamente de filas de prioridade monotônicas) é que a chave dos elementos na fila são maiores ou iguais que a chave do último elemento extraído. Ou seja, para todo vértice (que não seja o vértice inicial) no estado labeled o seu custo é maior ou igual ao custo associado ao nó expandido mais recentemente. Além disso, assume-se que o custo associado aos nós (que serão suas chaves no momento de inseri-los na fila de prioridades) são inteiros.

O algoritmo A* também apresenta essa propriedade se o custo das arestas do grafo não é negativo e a heurística é monotônica (consistente). Considera-se, ao invés do custo, o valor f associado a cada nó como chave.

O one level radix heap é composto por buckets. Em cada bucket coloca-se os nós cujas chaves estão dentro do intervalo associado ao bucket. Os intervalos crescem exponencialmente de forma que o primeiro e segundo bucket têm intervalo de tamanho 1, o terceiro tem intervalo de tamanho 2, o quarto de tamanho 4 e assim por diante. O último bucket tem um intervalo que cobre o custo do maior caminho possível no grafo. Esses intervalos são alterados ao longo tempo de modo que o intervalo do primeiro bucket sempre contemplará o menor valor de chave possível (considerando a restrição monotônica).

O two level radix heap é semelhante ao one level radix heap só que os bucket são divididos em segmentos. Todos buckets, com exceção do último, possuem o mesmo número de segmentos escolhido pelo implementador.

Essas estruturas possuem dois problemas principais: determinar o menor bucket não vazio no momento de extrair o menor elemento e determinar a qual bucket um dado elemento pertence. Na versão que usa segmentos também existe o problema de encontrar o menor segmento não vazio dentro de um bucket. A terceira estrutura de dados apresentada tem objetivo de sanar esse problema.

O artigo não apresenta resultado experimental comparando as estruturas propostas. Nos testes realizados com o A* usando one level radix heap e two level radix heap o desempenho foi pior do que usando um heap binário. No entanto, no A* usando grids é muito comum que vários nós apresentem o mesmo valor de f fazendo com que sejam colocados no mesmo bucket. Assim, a principal vantagem da estrutura de dados não é aproveitada.

Download

Links relacionados:

• Shortest Path Algorithms in C++: Fornece o código fonte (em C++) de algumas variações de heap: fibonacci heap, 2-3 heap, trinomial heap, extended trinomial heap e radix heap.
  • Radix Heaps: Apresenta um descrição do radix heap mais clara do que a explicação apresentada nesse artigo.
• Radix Heap Animation: Mostra uma execução do algoritmo de Dijkstra implementado com um radix heap.
• Radix Heaps: descrição alternativa dessa estrutura de dados.

Download

Links relacionados:

• Andrew Goldberg's Network Optimization Library: Fornece o código fonte (em C++) de vários algoritmos da otimização para grafos dentre eles o algoritmo de Dijkstra implementado com hot priority queue e multi-level buckets.

Download

Download

Download

O artigo apresenta o GAA* - algoritmo de busca heurística incremental para o cálculo do menor caminho entre dois nós de um grafo. Desenvolvido com base no algoritmo Adaptative A*, permite que ocorra, entre as buscas sucessivas, o aumento e/ou a diminuição do peso das arestas, a mudança do start e a mudança do goal. Diferentemente do seu predecessor, é capaz de tratar a diminuição do peso das arestas (razão pela qual recebe o nome de Generalized Adaptive A*).

Como mencionado, o GAA* adota o paradigma conhecido como busca incremental. Nesse paradigma, reutiliza-se a informação das buscas anteriores para encontrar a solução de uma série de problemas de busca de menor caminho semelhantes mais rápido do que recomputar cada um deles do início. O reaproveitamento das informações das buscas anteriores dá-se através da atualização dos h-values dos nós. Nessa atualização, agrega-se mais informações a heurística. Dessa forma, os h-values atualizados dominam, pelo menos fracamente, os h-values providos inicialmente. Após as atualizações, eles são sempre mantidos consistentes em relação ao goal o que garante a otimalidade da solução calculada pelo A* (empregado no GAA* como uma espécie de subrotina). A versão do algoritmo apresentada é chamada de lazy por postergar a atualização da heurística sempre que possível.

Para avaliação experimental, o algoritmo é comparado com outros três (A*, busca em largura e D* Lite) em duas situações de ambientes dinâmicos (com o goal imóvel e com o goal movendo-se). Todos algoritmos, com exceção do D* Lite, possuem duas versões: uma que expande os nós do goal para o start e a outra que expande de maneira tradicional (do start para o goal). As versões que expandem da maneira não usual mostraram-se mais rápidas. O GAA* mostrou-se mais rápido do que os demais quando o goal podia deslocar-se.

Apesar de avaliar o algoritmo comparando-o com vários outros, os testes foram limitados, pois os ambientes dos testes foram restritos. Todos testes foram feitos em um labirinto gerado com uma busca em profundidade, ou seja, o ambiente possui arestas de custo unitário e, inicialmente, muitas células bloqueadas. Experimentos realizados sugerem que o desempenho é bastante comprometido em grafos cujas arestas apresentam pesos não uniformes, mapas com células bloqueadas distribuídas livremente e um número de células bloqueadas menor. Além disso, apesar de não ficar claro no artigo, assume-se que sempre exista uma solução ao longo da série de buscas. Ou seja, se durante a série de buscas alguma delas não possui solução, os h-values não poderão ser atualizados.

Download

Links relacionados:

• Applet do GAA*

A principal contribuição desse artigo é a apresentação de uma nova classe de algoritmos de busca incremental através do algoritmo FSA*. Nessa classe, restaura-se o conteúdo da open list e da closed list (o estado da busca) para o conteúdo no momento onde a busca atual poderia divergir da busca anterior (na busca incremental assume-se a existência de várias buscas sucessivas semelhantes - chamadas de episódios).

O contexto de aplicação do algoritmo apresentado está restrito a grids finitos, completamento conhecidos, cujas células são quadradas (cada célula tem no máximo 4 sucessores) que estão bloqueadas ou livres. Ao longo das execuções, células bloqueadas podem ser desbloqueadas e vice versa. Nessa versão, o start e o goal não são alterados e, caso não exista solução, não é possível prosseguir aproveitando os cálculos anteriores (ou seja, será preciso iniciar uma nova busca).

De maneira simplória, o algoritmo é composto pelos seguintes passos:

1. Executar o A* e terminar se não existir uma solução.
2. Aguardar mudanças no grid.
3. Restaurar o conteúdo da closed list. Intuitivamente, basta podar a árvore de busca do episódio anterior e armazenar os nós fechados pertencentes à árvore. O ponto de poda, por exemplo, seria uma célula antes livre e agora bloqueada.
4. Restaurar o conteúdo da open list. Intuitivamente, serão os nós sucessores das folhas da árvore do passo anterior.
5. Restaurar os g-values e o campo parent dos nós da open list.
6. Ordenar os nós da open list (heapify).

A restrição para aplicação do FSA*, somente em grids, justifica-se primeiramente pela facilidade de encontrar os nós na etapa 4 e de restaurar o seu conteúdo (g-values e o campo parent) na etapa 5. Essa restrição também foi usada durante a prova de teoremas relacionados com o funcionamento do algoritmo.

Na avaliação experimental o FSA* foi comparado com o A*, LPA* e iA* (uma versão incremental do A* muito semelhante ao FSA* que não foi publicada). Apesar das particularidades da situação de teste, o FSA* mostrou-se mais rápido em alguns casos.

Download

Download

Atomic