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.
2006
978-1-4244-0570-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/1434517
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo