Skip to main content
Engineering LibreTexts

2.1.2: Motivation - An Example

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    A museum has enlisted a camera-equipped mobile robot for surveillance purposes. The robot will navigate the museum’s premises, pausing to take one or more 360 degree scans in each room. Figure 8.1 shows a typical room filled with various stationary obstructions (in black). We wish to determine the vantage point in each room from which the robot will have the most unobstructed view for its scan by estimating the visible area (in white) for each candidate vantage point. We may also wish to provide the robot with an "onboard" visible area estimator for purposes of real-time adaptivity, for example, if the room configuration is temporarily modified. This is a good candidate for Monte Carlo: the domain is complex and non-smooth; we would like quick results based on relatively few evaluations; and we wish to somehow certify the accuracy of our prediction. (In actual practice, the computation would be performed over a three-dimensional museum room - a further reason to consider Monte Carlo.)

    We first define, for any vantage point \(\boldsymbol{x}_{V}\) and any surveillance point (to be watched) in the room \(\boldsymbol{x}_{W}\), the line segment \(S\left(\boldsymbol{x}_{V}, \boldsymbol{x}_{W}\right)\) that connects \(\boldsymbol{x}_{V}\) and \(\boldsymbol{x}_{W}\). We can then express the area visible from a vantage point \(x_{V}\) as the integral \[A\left(\boldsymbol{x}_{V}\right)=\int_{\boldsymbol{x}_{W} \in R \text { such that } S\left(\boldsymbol{x}_{V}, \boldsymbol{x}_{W}\right) \cap O=\varnothing} \mathrm{d} \boldsymbol{x}_{W}\] where \(R\) is the room and \(O\) is the collection of obstructions. The visible area is thus defined as the integral over all points in the room such that the line segment \(S\left(\boldsymbol{x}_{V}, \boldsymbol{x}_{W}\right)\) between \(\boldsymbol{x}_{V}\) and \(\boldsymbol{x}_{W}\) does not intersect an obstruction (or, equivalently, such that the intersection of sets \(S\) and \(O\) is the null set).

    There are many ways to do the visibility test \(S\left(\boldsymbol{x}_{V}, \boldsymbol{x}_{W}\right) \cap O \stackrel{?}{=} \varnothing\), but perhaps the method most amenable to mobile robotics is to use an "occupancy grid," a discretization of the map in which

    Screen Shot 2022-03-27 at 7.53.06 PM.png
    Figure 8.1: A surveillance robot scanning a room. Obstructions (in black) divide the space into visible area (in white) and non-visible area (in gray).
    Screen Shot 2022-03-27 at 7.54.16 PM.png
    Figure 8.2: Occupancy grid.

    each cell’s value corresponds to the likelihood that the cell is empty or occupied. We begin by converting our map of the room to an "occupancy grid," a discretization of the map in which each cell’s value corresponds to the likelihood that the cell is empty or occupied. In our case, because we know ahead of time the layout of the room, a given cell contains either a zero if the cell is empty, or a one if it is occupied. Figure \(8.2\) shows a visualization of a fairly low-resolution occupancy grid for our map, where occupied cells are shown in black.

    We can use the occupancy grid to determine the visibility of a point \(x_{W}\) in the room from a given vantage point \(\boldsymbol{x}_{V}\). To do this, we draw a line between the two points, determine through which cells the line passes and then check the occupancy condition of each of the intervening cells. If all of the cells are empty, the point is visible. If any of the cells are occupied, the point is not visible. Figure \(8.3\) shows examples of visible and non-visible cells. Once we have a method for determining if a point is visible or non-visible, we can directly apply our Monte Carlo methods for the estimation of area.

    Screen Shot 2022-03-27 at 7.55.25 PM.png
    Figure 8.3: Visibility checking of two points from a single vantage point. Visible cells marked in blue, non-visible cells marked in red.

    This page titled 2.1.2: Motivation - An Example is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Masayuki Yano, James Douglass Penn, George Konidaris, & Anthony T Patera (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.