Abstract

This thesis investigates the application of Genetic Algorithms (GAs) for evolving autonomous decision-making strategies in dynamic grid-world environments. The study focuses on scenarios in which obstacles appear, disappear, or move during agent navigation, creating conditions where traditional pathfinding and reinforcement learning (RL) approaches often struggle or require extensive retraining. Two GA-based agent models: rule-based agents and finite state machine (FSM) agents were evolved using population-based search to develop adaptive and generalizable behaviors. Their performance was evaluated in the MiniGrid DynamicObstacles environment and compared against a Q-learning agent across multiple metrics, including path efficiency, adaptability under environmental volatility, convergence time, and generalization to unseen map configurations. Experimental results show that GA-evolved agents achieve strong adaptability and high generalization performance, outperforming the RL baseline in dynamic and previously unseen environments. The findings demonstrate the viability of evolutionary methods for generating robust autonomous behaviors in uncertain, real-time settings, with implications for robotics, simulation platforms, and adaptive navigation systems.

References

• Z. Liu, B. Chen, H. Zhou, G. Koushik, M. Hebert, and D. Zhao, “MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments,” Jul. 30, 2020, arXiv: arXiv:2007.15724. doi: 10.48550/arXiv.2007.15724.
• Y. Lin et al., “Evolutionary Reinforcement Learning: A Systematic Review and Future Directions,” Mathematics, vol. 13, no. 5, p. 833, Jan. 2025, doi: 10.3390/math13050833.
• K. M. C. Zielinski et al., “Flexible control of Discrete Event Systems using environment simulation and Reinforcement Learning,” Appl. Soft Comput., vol. 111, p. 107714, Nov. 2021, doi: 10.1016/j.asoc.2021.107714.
• J. Lehman and K. O. Stanley, “Efficiently evolving programs through the search for novelty,” in Proceedings of the 12th annual conference on Genetic and evolutionary computation, in GECCO ’10. New York, NY, USA: Association for Computing Machinery, Jul. 2010, pp. 837–844. doi: 10.1145/1830483.1830638.
• Y. Li, J. Zhao, Z. Chen, G. Xiong, and S. Liu, “A Robot Path Planning Method Based on Improved Genetic Algorithm and Improved Dynamic Window Approach,” Sustainability, vol. 15, no. 5, p. 4656, Jan. 2023, doi: 10.3390/su15054656.
• M. Flageat, F. Chalumeau, and A. Cully, “Empirical analysis of PGA-MAP-Elites for Neuroevolution in Uncertain Domains,” ACM Trans Evol Learn Optim, vol. 3, no. 1, p. 1:1-1:32, Mar. 2023, doi: 10.1145/3577203.
• A. Cully and Y. Demiris, “Quality and Diversity Optimization: A Unifying Modular Framework,” May 12, 2017, arXiv: arXiv:1708.09251. doi: 10.48550/arXiv.1708.09251.
• A. Faust, A. Francis, and D. Mehta, “Evolving Rewards to Automate Reinforcement Learning,” May 18, 2019, arXiv: arXiv:1905.07628. doi: 10.48550/arXiv.1905.07628.
• F. Rekabi Bana, T. Krajník, and F. Arvin, “Evolutionary optimization for risk-aware heterogeneous multi-agent path planning in uncertain environments,” Front. Robot. AI, vol. 11, Aug. 2024, doi: 10.3389/frobt.2024.1375393.
• M. Chevalier-Boisvert et al., “Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks,” Adv. Neural Inf. Process. Syst., vol. 36, pp. 73383–73394, Dec. 2023.