Online Planning for Resource Production in Real-Time Strategy Games

All Papers

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 producing 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 effects 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 initial 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 Wargus 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.