Online planning for resource production in real-time strategy games
Hei Chan, Alan Fern, Soumya Shubhra Ray, Nick Wilson, Chris Ventura · 2007
Planning in domains with temporal and numerical properties is an important research problem. One application of this is the resource production problem in real-time strategy (RTS) games, where players attempt to achieve the goal of produc-ing a certain amount of resources as fast as possible. In this paper, we develop an online planner for resource production in the RTS game of Wargus, where the preconditions and ef-fects of the actions obey many properties that are common across RTS games. Our planner is based on a computationally efficient action-selection mechanism, which at each decision epoch creates a possibly sub-optimal concurrent plan from the current state to the goal and then begins executing the ini-tial set of actions. The plan is formed via a combination of means-ends analysis, scheduling, and a bounded search over sub-goals that are not required for goal achievement but may improve makespan. Experiments in the RTS game of War-gus show that the online planner is highly competitive with a human expert and often performs significantly better than state-of-the-art planning algorithms for this domain.