A new metaheuristic approach for the art gallery problem
This addresses a computationally hard problem in robotics and telecommunications with incremental improvements in accuracy and efficiency.
The paper tackled the art gallery problem by developing a particle filter-based metaheuristic to find the minimum number of guards for polygon coverage, achieving more accurate results with fewer or equal guards in experiments on random polygons.
In the problem "Localization and trilateration with the minimum number of landmarks", we faced the 3-Guard and classic Art Gallery Problems. The goal of the art gallery problem is to find the minimum number of guards within a simple polygon to observe and protect its entirety. It has many applications in robotics, telecommunications, etc. There are some approaches to handle the art gallery problem that is theoretically NP-hard. This paper offers an efficient method based on the Particle Filter algorithm which solves the most fundamental state of the problem in a nearly optimal manner. The experimental results on the random polygons generated by Bottino et al. \cite{bottino2011nearly} show that the new method is more accurate with fewer or equal guards. Furthermore, we discuss resampling and particle numbers to minimize the run time.