?
Особенности решения задачи геометрического мониторинга
The problem of limited space monitoring is formulated. The connection between the monitoring space and the detection of objects in this space sets up. After introducing some assumptions we conclude the necessity of solving the covering set (connected space) problem. The presence of obstacles in the monitoring area is the characteristic feature of the problem. “Obstacle” means a connected space area each point of which can not accommodate any object. However, as obstacles may lie in the monitoring area, the coverage of monitoring area should include the obstacles points. It is proposed to use an ad hoc network of mobile robots to solve the problem. The advantage of this approach is the high level of adaptability to changes in external parameters, as well as the resistance to failure of individual network elements. Coverage problem is described mathematically, the conclusion about necessity a sampling problem is made. All functions and parameters are replaced by digital analogues, the sampling steps are chosen to be small compared with the characteristic dimensions of the problem. We formulate and prove a couple of lemmas through which we study the properties and characteristics of various kinds of coverages. The smallest and minimum coverages are defined and ratio therebetween is set up. The mechanism of solution the covering problem by building a complete loaded graph according to certain rules, and the analysis of this graph is provided. We study the sufficient conditions for the construction of the smallest coverage. The algorithm for constructing the smallest coverage using a decentralized ad hoc network of mobile robots is developed. The efficiency of the algorithm follows from the lemmas and propositions set out above. The complexity of the algorithm is estimated. It is concluded that this algorithm is applicant and can solve the real problems related to space monitoring that arise.