Integrando Planejamento e
Execução de Ações no
Domínio de Jogos do Tipo RTS
Aluno: Augusto Afonso Borges Branquinho
Orientador: Carlos Roberto Lopes
Evento: II Workshop de Dissertações
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
1. Introdução
• Jogos do tipo RTS (Real-time Strategy)
– Disputa em tempo real (Real-time)
• Intercala planos e execuções de ações
• Domínio com informações incompletas
• Tempo limitado
• Busca local
– Jogos de Guerra
– Ambiente inexplorado
• Exemplos: Age of Empires e Warcraft
Universidade Federal de Uberlândia (UFU)
1. Introdução
• Tipos de “Ações”
–
–
–
–
–
Coleta de recursos
Construção de edifícios
Treinamento de unidades
Desenvolvimento Tecnológico
Combate contra o inimigo
• Planejamento de Recursos
– Recursos Materiais: gold, wood, oil, energy, magma
– Outros Recursos: footman, townhall, barracks
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
• Planejamento
– Estado Inicial
– Ações
• Pré-condições
• Duração
• Efeitos
– Metas
Peasant
Townhall
collect-gold
Gold
• Progressivo/Regressivo
• Makespan (Tempo do Plano)
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
• Ações do Warcraft 2 (Exemplo)
action collect-gold :duration 300
:require 1 townhall :borrow 1 peasant :produce 100 gold
action collect-wood :duration 1200
:require 1 townhall :borrow 1 peasant :produce 100 wood
action build-supply :duration 600
:borrow 1 peasant :consume 500 gold 250 wood :produce 4 supply
action build-townhall :duration 1530
:borrow 1 peasant :consume 1200 gold 800 wood :produce 1 townhall
action build-peasant :duration 225
:borrow 1 townhall :consume 400 gold 1 supply :produce 1 peasant
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
100 collect-gold
1 Peasant
1 Townhall
Makespan = 30100
action collect-gold :duration 300
:require 1 townhall :borrow 1 peasant
a gold
melhor solução?
:produceÉ100
Universidade Federal de Uberlândia (UFU)
10000 Gold
1 Peasant
1 Townhall
2. Caracterização do Problema
1 build-peasant
1 Peasant
1 Townhall
50 collect-gold
50 collect-gold
2 Peasant
1 Townhall
10000 Gold
1 Peasant
1 Townhall
Executar build-peasant compensa os gastos?
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
1 peasant
1 townhall
5 collect-gold
4 collect-gold
3 collect-wood
build-supply
build-peasant
1 peasant
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
1 peasant
1 townhall
3 collect-wood
9 collect-gold
Makespan = 7140
build-supply
build-peasant
1 peasant
Universidade Federal de Uberlândia (UFU)
2. Caracterização do Problema
1 build-peasant
1 Peasant
1 Townhall
50 build-gold
50 build-gold
2 Peasant
1 Townhall
Makespan = 7140 + 15050 = 22190
Universidade Federal de Uberlândia (UFU)
10000 Gold
1 Peasant
1 Townhall
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
3. Planejamento e LRTA*
Estado Inicial
1 Peasant makespan
1Townhall
Estado
+1 P
2 Peasant
1Townhall makespan
3 Supply
+1 P
Estado
3 Peasant
1Townhall makespan
2 Supply
+1 T
+1 T
Estado
makespan 1 Peasant
2Townhall
Estado
2 Peasant
makespan 2 Townhall
3 Supply
+1 P
Estado
3 Peasant
makespan
2 Townhall
2 Supply
+1 T
Estado
2 Peasant
makespan
3 Townhall
3 Supply
3. Planejamento e LRTA*
• Resultado da Busca com Adição de Recursos
Meta: 10000 gold
Meta: 5 footman
makespan peasant adicional makespan
peasant adicional
30100
0
28761
0
22189
1
22570
1
18577
2
19268
2
17072
3
18667
3
16771
4
18068
4
21569
5
23178
5
3. Planejamento e LRTA*
• Learning Real-time A* (LRTA*)
– Algoritmo de Busca
– Heurística
– Aprendizagem
• Eliminar o makespan da árvore de busca
• Criação de uma Heurística
• Aplicação do LRTA*
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
4. Trabalho Relacionados
• Chan (2007)
– Algoritmo de planejamento Means-ends Analysis
(MEA)
– Algoritmo de Escalonamento
• Shue (2008)
– Escalonamento baseado no LRTA*
– SLA* e SLA*T
• Algoritmos de busca em tempo real
– TB-LRTA*, Weighted-LRTA*, FALCONS, LCM,
LRTA*(k, d)
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
5. Conclusão
• Possibilidade de Melhorias com o LRTA*
• Trabalhos Futuros
–
–
–
–
Planejamento
Busca
Aprendizado
Escalonamento
• Ações com durações variáveis
• Aplicação em Jogos do Tipo RTS
Universidade Federal de Uberlândia (UFU)
Sumário
•
•
•
•
•
•
1. Introdução
2. Caracterização do Problema
3. Planejamento e LRTA*
4. Trabalhos Relacionados
5. Conclusão
Referências
Universidade Federal de Uberlândia (UFU)
Referências
• BLUM, A. and FURST,M.,1997. Fast Planning Through Planning
Graph Analysis. Artificial Intelligence, Volume 90, 281-300.
• BULITKO, V. and LEE, G., 2006. Learning in Real Time Search: A
Unifying Framework. Journal of Artificial Intelligence Research
(JAIR), Volume 25, 119-157.
• BURO, M., 2003. ORTS: A hack-free RTS game environment. In
Proceedings of the International Joint Conference on AI 2003.
• CHAN, H. and FERN, A. and RAY, S. and WILSON, N. and
VENTURA, C., 2007. Online Planning for Resource Production in
Real-Time Strategy Games. Appears in the Proceedings of the 17th
International Conference on Automated Planning & Scheduling,
Providence, RI, USA.
Universidade Federal de Uberlândia (UFU)
Referências
• CHAN, H. and FERN, A. and RAY, S. and WILSON, N. and
VENTURA, C., 2007. Extending Online Planning for Resource
Production in Real-Time Strategy Games with Search. Workshop on
Planning in Games, ICAPS 2007, Providence, RI, USA.
• FILHO, V. and JÚNIOR, J. and WEBER, R. and RAMALHO, G.
TEDESCO, P., 2006. JaRTS: Java RTS Simulator. Simpósio
Brasileiro de Jogos para Computador e Entretenimento Digital SBGames, Recife, PE.
• FURCY, D. and KOENIG, S., 2000. Speeding up the Convergence of
Real-Time Search. In Proceedings of the National Conference on
Artificial Intelligence, 891-897.
• HERNÁNDEZ C. and MESEGUER, P., 2007. Improving LRTA*(k).
In Proceedings IJCAI-07, 2312-217.
Universidade Federal de Uberlândia (UFU)
Referências
• HOFFMANN, J and NEBEL, B., 2001. The FF Planning System:
Fast Plan Generation Through Heuristic Search. In: Journal of
Artificial Intelligence Research, Volume 14, 253-302.
• KAUTZ, H., and
SELMAN, B., 1992. Planning as Satisfiability.
In Proceedings of the 10th European Conference on Artificial
Intelligence (ECAI 92), 359-363.
• KOENIG, S., 2004. A Comparison of Fast Search Methods for RealTime Situated Agents. In: Proceedings of the International Joint
Conference on Autonomous Agents and Multiagent Systems
(AAMAS), 864-871.
• KORF, R., 1990. Real-time heuristic search. Artificial Intelligence,
Volume 42, 189-211.
Universidade Federal de Uberlândia (UFU)
Referências
• PEMBERTON, J. and KORF, R. E., 1992. Making Locally Optimal
Decisions on Graph with Cycles. Technical Report 920004, Computer
Science Department, University of California at Los Angeles, Los
Angeles (California).
• POSEN, M. and URBAN, S. and AVILA, H. and AHA, D.
MOLINEAUX, M., 2005. Stratagus: An Open-Source Game Engine
for Research in Real-Time Strategy Games. In: Proceedings of
IJCAI 2005.
• RUSSEL, S. J. and NORVIG, P., 2002. Artificial Intelligence: A
Modern Approach, 2nd Edition, Prentice Hall.
• SHIMBO, M. and ISHIDA, T., 2003. Controlling the learning process
of real-time heuristic search. Artificial Intelligence, Volume 146, 143.
Universidade Federal de Uberlândia (UFU)
Integrando Planejamento e Execução de Ações no Domínio
de Jogos do Tipo RTS
Dúvidas? 
[email protected]
[email protected]
Universidade Federal de Uberlândia (UFU)