Reinforcement Learning for Optimize Coverage in Art Gallery Problem Using Q-Learning Based in Grid World

This paper presents a novel approach to solving the Art Gallery Problem (AGP) using a grid-based system and Reinforcement Learning (RL) in a two-dimensional space. The algorithm converts complex polygons into grids to simplify coverage calculations, allowing for scalable extensions. The method employs a Q-learning agent that interacts with the environment to optimize guard placement by balancing the number of guards and the coverage area. Experiments show that finer grid densities improve accuracy, while parameter adjustments (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula>) significantly impact performance. The algorithm effectively handles varying map complexities, demonstrating robust and efficient coverage solutions.