×

Constrained light deployment for reducing energy consumption in buildings. (English) Zbl 1483.68471

Chan, T-H. Hubert (ed.) et al., Combinatorial optimization and applications. 10th international conference, COCOA 2016, Hong Kong, China, December 16–18, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10043, 350-364 (2016).
Summary: Lighting systems account for a major part of the energy consumed by large commercial buildings. This paper aims at reducing this energy consumption by defining the Contrained Light Deployment problem. This new problem is related to the classical Art Gallery problem (AGP) in computational geometry. In contrast to AGP, which asks for the minimum number of guards to monitor a polygonal area, our problem, CLDP, poses a new challenging requirement: not only must each point \(p\) have an unobstructed line-of-sight to a light source, but also, the combined illuminance at \(p\) from all light sources must exceed some given threshold value. We provide evidence that our new problem is NP-hard, based on known results for AGP. Then we propose fast heuristics for floor plans shaped like orthogonal polygons, with and without holes. Our problem formulation allows lights to be placed internally, not only at vertices. Our algorithm, which combines ideas from computational geometry, clustering and binary search, computes a set of light placements that satisfies the illumination requirement. The algorithm seeks a light set of minimum size by an iterative binary search procedure that progressively tightens upper and lower bounds.
For the entire collection see [Zbl 1377.68004].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bajuelos Domínguez, A.L., Hernández Peñalver, G., Canales Cano, S., Martins, A.M.: Minimum vertex guard problem for orthogonal polygons: a genetic approach. In: Proceedings of MAMECTIS 2008. World Scientific and Engineering Academy and Society, WSEAS (2008)
[2] Bajuelos Domínguez, A.L., Martins, A.M., Canales Cano, S., Hernández Peñalver, G.: Metaheuristic approaches for the minimum vertex guard problem. In: Third International Conference on Advanced Engineering Computing and Applications in Sciences, ADVCOMP 2009, pp. 77–82. IEEE (2009)
[3] Baumgartner, T., Fekete, S.P., Kröller, A., Schmidt, C.: Exact solutions and bounds for general art gallery problems. Science 407, 14–1 (2011) · Zbl 1284.05297
[4] Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res. 18(4), 425–448 (2011) · Zbl 1269.90151
[5] csep10.phys.utk.edu. Intensity: the inverse square law (2015). http://csep.10.phys.utk.edu/astr162/lect/light/intensity.html
[6] EIA. How much electricity is used for lighting in the united states? (2016). https://www.eia.gov/tools/faqs/faq.cfm?id=99&t=3
[7] Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158(6), 718–722 (2010) · Zbl 1189.52008
[8] Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recogn. Lett. 31(8), 651–666 (2010)
[9] Jang, D.-S., Kwon, S.-I.: Fast approximation algorithms for art gallery problems in simple polygons. arXiv preprint arXiv:1101.1346 (2011)
[10] King, J.: Fast vertex guarding for polygons with and without holes. Comput. Geom. 46(3), 219–231 (2013) · Zbl 1262.65032
[11] King, J., Kirkpatrick, D.: Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46(2), 252–269 (2011) · Zbl 1226.68122
[12] Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: AAAI, vol. 7, pp. 1650–1654 (2007)
[13] Muhamad, W.N.W., Zain, M.Y.M., Wahab, N., Aziz, N.H.A., Kadir, R.A.: Energy efficient lighting system design for building. In: 2010 International Conference on Intelligent Systems, Modelling and Simulation (ISMS), pp. 282–286. IEEE (2010)
[14] Nagy, Z., Yong, F.Y., Frei, M., Schlueter, A.: Occupant centered lighting control for comfort and energy efficient building operation. Energy Build. 94, 100–108 (2015)
[15] O’rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, Oxford (1987)
[16] Schaeper, A., Palazuelos, C., Denteneer, D., Garcia-Morchon, O.: Intelligent lighting control using sensor networks. In: 2013 10th IEEE International Conference on Networking, Sensing and Control (ICNSC), pp. 170–175. IEEE (2013)
[17] Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261–267 (1995) · Zbl 0827.68115
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.