TL;DR
This paper introduces Factorio, a popular video game, as a novel platform for researching operational research and AI optimization problems, specifically focusing on the "logistic belt problem." They developed an interface to connect external AI solvers to Factorio and benchmarked several metaheuristics, finding that a specialized Genetic Programming approach achieved the best results.
What Problem Does This Paper Address?
Efficient resource optimization is crucial in many real-world domains, from logistics to manufacturing. However, developing and testing solutions for these complex problems can be expensive and time-consuming. The authors propose using the video game Factorio as a rich, accessible, and engaging simulator for these operational research challenges. Factorio's core gameplay loop involves building complex automated factories, which inherently presents numerous optimization problems, such as resource routing, scheduling, and production line design. This paper specifically tackles the "logistic belt problem" within Factorio, which involves efficiently transporting items using conveyor belts, a direct analogy to real-world conveyor systems. The challenge lies in finding optimal belt configurations to maximize throughput, minimize resources, and avoid obstacles, all within the game's constraints.
Methods
The authors developed a Factorio Optimizer Interface (FOI) to bridge the gap between external optimization algorithms and the Factorio game engine. FOI uses the RCON protocol and Factorio's modding capabilities to translate problem descriptions and solutions into in-game actions, and to receive feedback on solution performance.
They then benchmarked three metaheuristic approaches for solving the logistic belt problem:
- Parallel Simulated Annealing (PSA): A classic search heuristic adapted for parallel execution to handle the large search space.
- qGenetic Programming (qGP): An evolutionary algorithm that evolves computer programs (in this case, sequences of belt placement and connection commands) to solve the problem. This approach uses specialized operators like "Connect" and "Place" tailored for the Factorio environment.
- Evolutionary Reinforcement Learning (ERL): A machine learning approach that combines Genetic Programming with Reinforcement Learning to develop agents capable of solving multiple belt problems and generalizing their learned behaviors.
Datasets
The paper introduces a set of newly defined benchmark problems within Factorio:
- Logistic Belt Problems: These are defined by grid sizes (3x3, 6x6, 12x12) and the presence or absence of obstacles.
- The problems are encoded as integer matrices, with specific integer values representing different game entities (belts, walls, inserters, etc.).
Key Insights and Ideas
- Factorio as a Research Platform: The paper strongly advocates for using video games like Factorio as valuable simulators for operational research and AI problems, offering a more accessible and engaging alternative to traditional simulations.
- Specialized Operators in GP: The success of qGP highlights the benefit of designing problem-specific operators (like "Connect" and "Place") that directly map to the game's mechanics, leading to more efficient exploration of the solution space.
- Generalization in ERL: The ERL approach demonstrated the potential for developing agents that can solve a variety of belt problems, showcasing a degree of generalization beyond single problem instances.
- Impact of Obstacles: The presence of obstacles significantly impacts the performance of different algorithms, particularly for PSA, while qGP shows more robust performance but still faces challenges.
Key Results
- qGP Outperforms: qGenetic Programming (qGP) consistently achieved the highest average best fitness across most problem configurations, indicating its effectiveness in finding high-quality solutions for the logistic belt problem.
- PSA Limitations: Parallel Simulated Annealing (PSA) performed well on smaller (3x3) problems but struggled with larger grids (6x6, 12x12), likely due to the vast search space.
- ERL for Generalization: Evolutionary Reinforcement Learning (ERL) showed promise in solving multiple unique belt problems, especially in the absence of obstacles, demonstrating its ability to learn generalized behaviors.
- Obstacle Impact: Obstacles posed a significant challenge, particularly for PSA, and even affected qGP's performance on larger grids.
Limitations and Future Work
- Computational Cost: The paper acknowledges the high computational cost of evaluations, especially for ERL, which limited its testing to smaller problem sizes.
- Iteration Equivalence: The authors note that comparing iterations across different algorithms is not straightforward due to varying computational demands.
- Future Work: The authors suggest expanding the logistic belt problem by incorporating more complex logistic elements (splitters, varying belt speeds), refining fitness functions to include cost, size, and throughput, and exploring co-evolutionary techniques for related problems like electricity pole placement. They also propose investigating path-finding hybridization and exploring the benefits of qGP's multi-output operators for more complex models.
Summary updated