UM ESTUDO DE ESTRATÉGIAS
PARA COLETA DE RECURSOS EM
AMBIENTES MULTI-AGENTES
Sergio Schechtman Sette
<[email protected]>
JOGOS RTS
As ações são realizadas em tempo real
 Cada unidade tem um tempo para realizar o
processamento
 Etapas principais comuns na maioria dos RTS:






Coleta de Recursos
Criação de Construções e Unidades
Pesquisa de Tecnologias
Exploração
Combate
IA EM JOGOS RTS

Historicamente, game designers têm criado a
ilusão de inteligência através de scripts. O
problema dos scripts é que para serem efetivos,
eles devem ser complexos, mas a complexidade
acaba criando fraquezas e previsibilidade.
Eventualmente um jogador humano será capaz
de reconhecer e se aproveitar destas fraquezas,
destruindo a ilusão.[1]
COLETA EM JOGOS RTS
Jogos RTS oferecem uma grande variedade de
problemas fundamentais de IA, ao contrario de
outros gêneros de jogos estudados pela
comunidade de IA até agora. [2]
 Problemas principais

Pathfinding
 Coordenação
multiagente
 Escolha do recurso

PROBLEMAS NA COLETA MULTIAGENTE

PathFinding
A*
 A* colaborativo


Escolha do melhor recurso

Distância

Manhatan e Euclideana
Disponibilidade
 Acessibilidade

A*
Simples, eficiente e completo
 Trata obstáculos e terrenos com diferentes custos
de travessia
 Eficiente em ambientes monoagentes

A* COLABORATIVO
A* + reservas
 Cada agente reserva o path encontrado pelo A*
 Na verificação de colisão, as reservas também são
consideradas

DISTÂNCIA
Manhattan e Euclideana
 Distância real vs Estimativa

DISPONIBILIDADE E ACESSIBILIDADE
Disponibilidade: Número de vagas vs número de
agentes coletando
 Acessibilidade: Considera a dificuldade que o
agente encontra para chegar ao recurso

ESTADO DA ARTE

Optimal Foraging Theory


E/(h+s)
jcmjWorker
A*
 Recurso mais próximo
 Tratamento de colisão simples

ESTRATÉGIA PROPOSTA

Pathfinding



A* Colaborativo
Tratamento de delay
Escolha do recurso

Distância
Inicial = Manhatan
 Atualizada a cada visita


Regiões
Clusters de minas adjacentes
 A atualização é propagada pelas regiões


Função de utilidade
Distância
 Distância ao agente
 Numero de agentes no mesmo recurso

ESTRATÉGIA PROPOSTA (CONT)

Agente Explorador (Scout)
Procura as minas menos visitadas
 Atualiza com peso


Máquina de estados
SIMULAÇÃO
Simulador escolhido: RTSCup
 Tick: 50ms
 Foram realizados testes em 5 mapas

RESULTADOS
Agente
Mapa1 Mapa2 Mapa3 Mapa4 Mapa5
CloserWorker
260
1330
720
5973
1487
ZigWorker
510
1340
870
6388
1800
ZigWorker com agente
explorador
X
X
896
6397
1820
ZigWorker sem utilizar
propagação de regiões
X
X
X
X
1610
ZIGWORKER
CLOSERWORKER
DEMONSTRAÇÃO
ZigWorker
 CloserWorker

REFERENCIAS
[1] ARNOLD, Rachael. Real Time Strategy
Games as Domain for AI Research
 [2] BURO, Michael, Real-Time Strategy
Games: A New AI Research Challenge
 [3] MOURA, José Carlos. Uma estratégia
eficiente de coleta multiagente para jogos
RTS
