A new metaheuristic approach for the art gallery problem

In the problem Localization and trilateration with minimum number of landmarks, we faced 3-guard and classic Art Gallery Problem. The goal of the art gallery problem is to find the minimum number of guards within a simple polygon to observe and protect the entire of it. It has many applications in Robotics, Telecommunication and so on and there are some approaches to handle the art gallery problem which 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 near optimal. The experimental results on the randomly polygons generated by Bottino shows that the new method is more accurate with less or equal guards. Furthermore, we discuss the resampling and particle numbers to minimize the running time.