Formalization and solution of the maximum area coverage problem using library Shapely for territory monitoring

Abstract

To ensure the life of society, it becomes necessary to create systems for monitoring processes or objects using a network of sensors that can control part of the space (territory). Monitoring is understood as a systematic observation of the parameters of an object to obtain information on their compliance with the initial assumptions. Simultaneously, a physical model is constructed that links the characteristics of the object and information about the observation, which making it possible to identify the properties of the object. Such information is based on the processing of signals received using special control sensors. These signals are digitized to provide data on the coverage areas of the sensors. Thus, the physical model is associated with measuring the ability and quality of perception of control sensors, fixing the geometric relationship between them and points in space. The specified physical model corresponds to the geometric statement of the problem of covering the monitoring area with a set of geometric objects, the shape and size of which is determined by the coverage areas of the sensors. With a limited number of sensors, the problem arises of the maximum possible coverage of the area. In this article, we digress from the type of monitoring object and consider the geometric features of coverage problems that arise when designing systems for monitoring a space of various purposes. The current article presents constructive means of mathematical modeling for solving geometric problems of maximum coverage. To formalize the coverage conditions, the concept of constructing the configuration space of geometric objects and a special class of functions are used to establish the dependence of the measure (area, volume) of the coverage configuration on the placement parameters of the covering objects. Since it is extremely difficult to obtain an analytical form of these functions, an algorithmic approach to their calculation is proposed. The approach was implemented on the Pyton algorithm using the Shapely library. A computational experiment was planned and carried out to establish the dependence of the computation time on the number of geometric objects that make up the coverage configuration. To find the maximum coverage, the BFGS local optimization method of the Scipy.optimize package is used. Numerous examples of the implemenation of the proposed approach are given. Conclusions. The article substantiates the use of a software-algorithmic approach for formalization, calculation and optimization of maximum coverage configurations, which makes it possible to effectively solve complex problems of monitoring space and territories.

Keywords

• моніторинг простору
• сенсорна мережа
• покриття
• геометричний об'єкт
• математична модель
• оптимізація