A Randomized ArtGallery Algorithm for Sensor Placement.
Risab Biswas
Jalpaiguri, West Bengal
- 0 Collaborators
This project describes a placement strategy to compute a set of “good” locations where visual sensing will be most effective. ...learn more
Robotics, RealSense™, Internet of Things, Artificial Intelligence
Overview / Usage
This project describes a placement strategy to compute a set of “good” locations where visual sensing will be most effective. Throughout this project, it is assumed that a polygon 3-D map of the workspace is given as input. This polygon map - is also known as a floor plan or layout – is used to compute a set of locations where expensive sensing tasks such as 3-D image acquisition could be executed. A map building robot, for example, can visit these locations in order to build a full 3-D model of the workspace.
The sensor placement strategy relies on a randomized algorithm that solves a variant of the art-gallery problem: Find the minimum set of guards inside a polygon workspace from which the entire workspace boundary is visible. To better take into the limitations of the physical sensors, the algorithm computes a set of guards that satisfies incidence and range constraints. Although the computed set of guards is not guaranteed to have minimum size, the algorithm does compute with high probability a set whose size is at most a factor O (log (n + h) * log (clog (n + h))) from the optimal size c, where the number of edges is n in the input polygon map and h is the number of obstacles in its interior (holes).
The main objective of the project is to find a set of points or locations where the placement of visual sensing devices and sensors will lead to the most optimal result. This may be inferred from finding the locations for placement of CCTV cameras in a big network of streets in such a way that visual sensing will be most effective and optimal.
The solution building involves both software and hardware support.
The project basically will help us to understand how autonomous robots can be used to solve complex problems of the computer science and how that could be further extended in solving real-world problems.
The project ends up in an autonomous robot that could generate a 3-D map of a region i.e. the workspace which will be given as input to the algorithm. The algorithm will take the map as input and generate the locations or points where the visual sensing devices should be placed. The robot, in the end, will go to those locations and mark the regions.