Locating sensors in 2D can be modeled as an Art Gallery problem, which asks to locate the minimum number of omnidirectional sensors, or "guards" to "cover" a polygonal floor map. The problem is NP-hard, and no finite algorithm, even exponential, is known for its exact solution. The approximate algorithms in the literature are polynomial in the worst case, but their performance with respect to the optimal solution is either bad or, in most cases, unknown. Recently, a new incremental sensors location algorithm that attempts to balance execution times and closeness to optimum has been presented. The algorithm converges toward the optimal solution, and uses a lower bound for the number of sensors, specific of the polygon considered, for evaluating the quality of the solution. We have implemented and extensively tested the algorithm. Closeness to optimal and computation times have been measured for a large number of randomly generated polygons with or without holes, rectilinear polygons and real building floor maps. The experimental results show that the algorithm supplies solutions very close to, and often coincident with, the lower bound and therefore nearly optimal or optimal. Running times allow dealing with polygons with many tens, or even a few hundreds of edges, which appears adequate to most practical cases.
Experimental Results Show Near-Optimality Of A Sensor Location Algorithm / Bottino, ANDREA GIUSEPPE; Laurentini, Aldo. - STAMPA. - (2006), pp. 340-345. (Intervento presentato al convegno IEEE International Conference on Robotics and Biomimetics (ROBIO 2006) tenutosi a Kunming, China nel December 17-20, 2006) [10.1109/ROBIO.2006.340199].
Experimental Results Show Near-Optimality Of A Sensor Location Algorithm
BOTTINO, ANDREA GIUSEPPE;LAURENTINI, ALDO
2006
Abstract
Locating sensors in 2D can be modeled as an Art Gallery problem, which asks to locate the minimum number of omnidirectional sensors, or "guards" to "cover" a polygonal floor map. The problem is NP-hard, and no finite algorithm, even exponential, is known for its exact solution. The approximate algorithms in the literature are polynomial in the worst case, but their performance with respect to the optimal solution is either bad or, in most cases, unknown. Recently, a new incremental sensors location algorithm that attempts to balance execution times and closeness to optimum has been presented. The algorithm converges toward the optimal solution, and uses a lower bound for the number of sensors, specific of the polygon considered, for evaluating the quality of the solution. We have implemented and extensively tested the algorithm. Closeness to optimal and computation times have been measured for a large number of randomly generated polygons with or without holes, rectilinear polygons and real building floor maps. The experimental results show that the algorithm supplies solutions very close to, and often coincident with, the lower bound and therefore nearly optimal or optimal. Running times allow dealing with polygons with many tens, or even a few hundreds of edges, which appears adequate to most practical cases.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/1434517
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo