Optimal strategies for resource-task network problems

Resource-task network problems arise in both the industrial world and (in an idealized form) in many computer games (such as Minecraft or Factorio). In these problems, the goal is to transform a set of initial resources over time into more useful objects or resources, through the scheduling of tasks, which may involve resource extraction or manufacturing (often referred to as “crafting” in the game context. In some contexts these problems become more complex because some of the crafted entities are also tools or machines that can be used for crafting, resulting in a much deeper and more highly connected network of decisions and outcomes. The problem takes the form of an objective, such as to obtain a certain set of end products in the shortest possible time. Finding an optimal strategy is known to be a highly challenging task, and in most cases an optimal strategy is not known. This project will focus on optimization strategies for deep resource-task network problems, using networks from the game Factorio as test cases. A first approach to the problem is to discretize time and apply linear programming techniques, but this involves a number of efficiency tradeoffs. The student will work out this discretization and test and explore the effects of different choices. The goal will be to devise a strategy that outperforms those known and used by speedrunners, or to show that no such strategy exists. Additionally, if time permits, other approaches such as machine learning will be explored and tested.

- Computer code to solve deep resource task network problems

- A paper detailing the methods and results, to be submitted for publication