Sensor Placement Optimization using Chama¶

Continuous or regularly scheduled monitoring has the potential to quickly identify changes in the environment. However, even with low-cost sensors, only a limited number of sensors can be deployed. The physical placement of these sensors, along with the sensor technology and operating conditions, can have a large impact on the performance of a monitoring strategy.

Chama is an open source Python package which includes mixed-integer linear programming formulations to determine sensor locations and technology that maximize monitoring effectiveness. Chama is currently being used to design sensor networks to monitor airborne pollutants and to monitor water quality in water distribution systems, however the methods in Chama are general and can be applied to a wide range of applications.

Contents¶

Overview¶

Chama is an open source Python package which includes sensor placement optimization methods for a wide range of applications. Some of the methods in Chama were originally developed by Sandia National Laboratories and the U.S. Environmental Protection Agency to design sensor networks to detect contamination in water distribution systems [BHPU06] [USEPA12] [USEPA15]. In this context, contamination scenarios are precomputed using a water distribution system model, feasible sensor locations and thresholds are defined, and the optimization method selects a set of sensors to minimize a given objective.

Chama was developed to be a general purpose sensor placement optimization software tool. The software includes mixed-integer linear programming formulations to determine sensor locations and technology that maximize monitoring effectiveness. The optimization formulations in Chama can be used to minimize impact or maximize coverage. Chama includes functionality to define point and camera sensors that can be stationary or mobile. Furthermore, third party system models can be integrated into the software to determine sensor placement for a wide range of applications. The software is intended to be used by regulatory agencies, industry, and the research community. Example applications are included in Figure 1.

Example sensor placement applications¶

For each application, an appropriate model must be selected to represent the system. For example, atmospheric dispersion models can be used to place sensors to monitor oil and gas emissions, while water distribution system models can be used to place sensors to monitor drinking water quality.

The basic steps required for sensor placement optimization using Chama are shown in Figure 2.

Basic steps in sensor placement optimization using Chama¶

Simulation: Generate an ensemble of simulations representative of the system in which sensors will be deployed.
Sensor technology: Define a set of feasible sensor technologies, including stationary and mobile sensors, point detectors and cameras.
Impact assessment: Extract the impact of detecting each simulation given a set of sensor technologies.
Optimization: Optimize sensor location and type given a sensor budget.
Graphics: Generate maps of the site that include the optimal sensor layout and information about scenarios that were and were not detected.

The user can enter the workflow at any stage. For example, if the impact assessment was determined using other methods, Chama can still be used to optimize sensor placement. The following documentation includes additional information on these steps, along with installation instructions, software application programming interface (API), and software license. It is assumed that the reader is familiar with the Python Programming Language. References are included for additional background on software components.

Installation¶

Chama requires Python (tested on 3.7, 3.8, and 3.9) along with several Python package dependencies. Information on installing and using Python can be found at https://www.python.org/. Python distributions, such as Anaconda, are recommended to manage the Python interface.

To install the latest stable version of Chama using pip:

pip install chama

To install the development branch of Chama from source using git:

git clone https://github.com/sandialabs/chama
cd chama
python setup.py install

Developers should build Chama using the setup.py ‘develop’ option.

Dependencies¶

Required Python package dependencies include:

Pyomo [HLWW12]: Used to formulate optimization problems and call solvers, https://github.com/pyomo.
Pandas [Mcki13]: Used to analyze and store dataframes, http://pandas.pydata.org.
Numpy [VaCV11]: Used to analyze large, multi-dimensional arrays and matrices, http://www.numpy.org.
Scipy [VaCV11]: Used to support efficient routines for numerical analysis, http://www.scipy.org.

Optional Python package dependencies include:

Matplotlib [Hunt07]: Used to produce graphics, http://matplotlib.org.
nose: Used to run software tests, http://nose.readthedocs.io.

Required Pyomo supported MIP solver:

In addition to the Python package dependencies, a Pyomo supported MIP solver is required to solve the optimization problems formulated in Chama. Examples of solvers that meet this requirement include GLPK [Makh10], Gurobi [GUROBI], and CPLEX [CPLEX].
GLPK can be installed through conda-forge, conda install -c conda-forge glpk

Simulation¶

Chama uses a set of precomputed simulations to extract the data needed for sensor placement optimization. The type of simulation depends on several factors including the application, scale of interest, and the sensor placement objective. In many cases, multiple scenarios should be generated to capture uncertainty in the system. Steady state or transient simulations can be used. For example, while transient simulations are required to minimize time to detection, steady state simulations are sufficient to maximize scenario coverage. Note that if the sensor placement objective is to maximize geographic coverage, simulations are not required.

The following examples illustrate simulations that can be used in a sensor placement optimization problem. For each simulation, the signal of interest is recorded.

To place sensors to detect a gas leak, an atmospheric dispersion model can be used to simulate gas concentrations. Multiple scenarios capture uncertainty in the leak rate, leak location, wind speed and direction. Depending on the region of interest and the complexity of the system, very detailed or simple models can be used. In this case, the signal is gas concentration.
To place sensors to detect contaminant in a water distribution system, a water distribution network model can be used to simulate hydraulics and water quality. Multiple scenarios capture uncertainty in the location, rate, start time, and duration of the injection along with uncertainty in customer demands. EPANET [Ross00], WNTR [KHMB17], or similar water network simulators, can be used to run this type of analysis. In this case, the signal is contaminant concentration.
To place sensors to detect a seismic event, a wave propagation model can be used to simulate displacement. Multiple scenarios capture uncertainty in the location and magnitude of the seismic event along with subsurface heterogeneity. Depending on the region of interest and the complexity of the system, very detailed or simple models can be used. In this case, the signal is displacement.

Chama uses Pandas DataFrames [Mcki13] to store simulation data. Pandas includes many functions to easily populate DataFrames from a wide range of file formats. For example, DataFrames can be generated from Excel, CSV, and SQL files. Simulation data can be stored in XYZ or Node format, as described below.

For each scenario, the time, location, and signal are recorded. The time can be set to a uniform value when using steady state simulations. The points used to record time and location can be sparse to help reduce data size.

XYZ format¶

In XYZ format, the X, Y, and Z location is stored for each entry. In the DataFrame, columns X, Y, and Z describe the location, T is the simulation time, and Sn is the signal for scenario n. Exact column names must be used for X, Y, Z, and T. The scenario names can be defined by the user. When using this format, Chama can interpolate sensor measurements that are not represented in the signal data. An example signal DataFrame in XYZ format is shown below using a simple 2x2x2 system with three time steps and fabricated data for three scenarios.

>>> print(signal)
    X  Y  Z   T    S1    S2    S3
 1  1  1   0  0.00  0.00  0.00
 1  1  1  10  0.00  0.00  0.01
 1  1  1  20  0.00  0.00  0.00
 2  1  1   0  0.25  0.21  0.20
 2  1  1  10  0.32  0.14  0.25
 2  1  1  20  0.45  0.58  0.61
 1  2  1   0  0.23  0.47  0.32
 1  2  1  10  0.64  0.12  0.15
 1  2  1  20  0.25  0.54  0.24
 2  2  1   0  0.44  0.15  0.45
2  2  1  10  0.25  0.28  0.68
2  2  1  20  0.82  0.12  0.13
1  1  2   0  0.96  0.53  0.64
1  1  2  10  0.61  0.23  0.21
1  1  2  20  0.92  0.82  0.92
2  1  2   0  0.41  0.84  0.75
2  1  2  10  0.42  0.87  0.98
2  1  2  20  0.00  0.51  0.55
1  2  2   0  0.00  0.00  0.13
1  2  2  10  0.00  0.00  0.00
1  2  2  20  0.00  0.00  0.00
2  2  2   0  0.00  0.00  0.00
2  2  2  10  0.00  0.00  0.00
2  2  2  20  0.00  0.00  0.00

Node format¶

In Node format, a location index is stored for each entry. The index can be a string, integer, or float. This format is useful when working with sparse systems, such as nodes in a networks. In the DataFrame, column Node is the location index, T is the simulation time, and Sn is the signal for scenario n. Exact column names must be used for Node and T. The scenario names can be defined by the user. When using this format, Chama does not interpolate sensor measurements and only stationary point sensors can be used to extract detection time. An example signal DataFrame in Node format is shown below using four nodes with three time steps and fabricated data for three scenarios.

>>> print(signal)
   Node   T    S1    S2    S3
  n1   0  0.00  0.00  0.00
  n1  10  0.32  0.14  0.25
  n1  20  0.25  0.54  0.24
  n2   0  0.00  0.00  0.01
  n2  10  0.45  0.58  0.61
  n2  20  0.44  0.15  0.45
  n3   0  0.00  0.00  0.00
  n3  10  0.23  0.47  0.32
  n3  20  0.25  0.28  0.68
  n4   0  0.25  0.21  0.20
 n4  10  0.64  0.12  0.15
 n4  20  0.82  0.12  0.13

Internal simulation engines¶

Chama includes methods to run simple Gaussian plume and Gaussian puff atmospheric dispersion models [Arya99]. Both models assume that atmospheric dispersion follows a Gaussian distribution. Gaussian plume models are typically used to model steady state plumes, while Gaussian puff models are used to model non-continuous sources. The chama.simulation module has additional information on running the Gaussian plume and Gaussian puff models. Note that many atmospheric dispersion applications require more sophisticated models.

The following simple example runs a single Gaussian plume model for a given receptor grid, source, and atmospheric conditions.

Import the required Python packages:

>>> import numpy as np
>>> import pandas as pd
>>> import chama

Define the receptor grid:

>>> x_grid = np.linspace(-100, 100, 21)
>>> y_grid = np.linspace(-100, 100, 21)
>>> z_grid = np.linspace(0, 40, 21)
>>> grid = chama.simulation.Grid(x_grid, y_grid, z_grid)

Define the source:

>>> source = chama.simulation.Source(-20, 20, 1, 1.5)

Define the atmospheric conditions:

>>> atm = pd.DataFrame({'Wind Direction': [45, 60],
...                     'Wind Speed': [1.2, 1],
...                     'Stability Class': ['A', 'A']}, index=[0, 10])

Initialize the Gaussian plume model and run (the first 5 rows of the signal DataFrame are printed):

>>> gauss_plume = chama.simulation.GaussianPlume(grid, source, atm)
>>> gauss_plume.run()
>>> signal = gauss_plume.conc
>>> print(signal.head(5))
       X      Y    Z  T    S
0 -100.0 -100.0  0.0  0  0.0
1 -100.0 -100.0  2.0  0  0.0
2 -100.0 -100.0  4.0  0  0.0
3 -100.0 -100.0  6.0  0  0.0
4 -100.0 -100.0  8.0  0  0.0

The Gaussian Puff model is run in a similar manner. The time between puffs (tpuff) and time at the end of the simulation (tend) must be defined.

Initialize the Gaussian puff model and run:

>>> gauss_puff = chama.simulation.GaussianPuff(grid, source, atm, tpuff=1, tend=10)
>>> gauss_puff.run(grid, 10)
>>> signal = gauss_puff.conc

External simulation engines¶

Simulations can also be generated from a wide range of external simulation engines, for example, atmospheric dispersion can be simulated using AERMOD [USEPA04] or CALPUFF [ScSY00] or using detailed CFD models, transport in pipe networks can be simulated using EPANET [Ross00] or WNTR [KHMB17], and groundwater transport can be simulated using MODFLOW [McHa88]. Output from external simulation engines can be easily formatted and imported into Chama.

Sensor technology¶

Many different sensor technologies exist. For example, in the context of gas detection, sensors can monitor the concentration at a fixed point or they can be based on optical gas imaging technology and monitor an area within a field of view. Sensors can monitor continuously or at defined sampling times. Sensors can also be mounted on vehicles or drones and move through a specified region. Furthermore, sensors can have different operating conditions which can change detectability. In order to understand the tradeoffs between different sensor technologies and operating conditions and to select an optimal subset of sensors, these different options should be considered simultaneously within an optimal sensor placement problem.

The chama.sensors module can be used to define sensor technologies in Chama. The module is used to represent a variety of sensor properties including detector type, detection threshold, location, and sampling times. Additionally, every sensor object includes a function that accepts a signal, described in the Simulation section, and returns the subset of that signal that is detected by the sensor. This information is then used to extract the impact of each sensor on each scenario, as described in the Impact assessment section. The sensor placement optimization uses this information to select sensors.

Each sensor is declared by specifying a position and a detector. The following options are available in Chama (additional sensor technologies could easily be incorporated).

Position options¶

Stationary: A stationary sensor that is fixed at a single location.
Mobile: A mobile sensor that moves according to defined waypoints and speed. It can also be defined to repeat its path or start moving at a particular time. A mobile sensor is assumed to be at its first waypoint for all times before its starting time and is assumed to be at its final waypoint if it has completed its path and the repeat path option was not set.

Detector options¶

Point: A point detector. This type of detector determines detection by comparing a signal to the detector’s threshold.
Camera: A camera detector using the camera model from [RaWB16]. This type of detector determines detection by collecting the signal within the camera’s field of view, converting that signal to pixels, and comparing that to the detector’s threshold in terms of pixels.

When using signal data in XYZ format, Chama can interpolate sensor measurements that are not represented in the signal data. However, the sample times of a Camera detector must be included in the signal data (i.e. only X, Y, and Z can be interpolated).

For example, a stationary point sensor, can be defined as follows:

>>> pos1 = chama.sensors.Stationary(location=(1,2,3))
>>> det1 = chama.sensors.Point(threshold=0.001, sample_times=[0,2,4,6,8,10])
>>> stationary_pt_sensor = chama.sensors.Sensor(position=pos1, detector=det1)

A mobile point sensor, can be defined as follows:

>>> pos2 = chama.sensors.Mobile(locations=[(0,0,0),(1,0,0),(1,3,0),(1,2,1)],speed=1.2)
>>> det2 = chama.sensors.Point(threshold=0.001, sample_times=[0,1,2,3,4,5,6,7,8,9,10])
>>> mobile_pt_sensor = chama.sensors.Sensor(position=pos2, detector=det2)

A stationary camera sensor, can be defined as follows:

>>> pos3 = chama.sensors.Stationary(location=(2,2,1))
>>> det3 = chama.sensors.Camera(threshold=400, sample_times=[0,5,10], direction=(1,1,1))
>>> stationary_camera_sensor = chama.sensors.Sensor(position=pos3, detector=det3)

A mobile camera sensor, can be defined as follows:

>>> pos4 = chama.sensors.Mobile(locations=[(0,1,1),(0.1,1.2,1),(1,3,0),(1,2,1)],speed=0.5)
>>> det4 = chama.sensors.Camera(threshold=100, sample_times=[0,3,6,9], direction=(1,1,1))
>>> mobile_camera_sensor = chama.sensors.Sensor(position=pos4, detector=det4)

When using signal data in Node format, Chama does not interpolate sensor measurements that are not represented in the signal data and only stationary point sensors can be used.

When using Node format, a stationary point sensor, can be defined as follows:

>>> pos1 = chama.sensors.Stationary(location='Node1')
>>> det1 = chama.sensors.Point(threshold=0.001, sample_times=[0,2,4,6,8,10])
>>> stationary_pt_sensor = chama.sensors.Sensor(position=pos1, detector=det1)

Note that the units for time, location, speed, and threshold need to match the units from the simulation.

Impact assessment¶

Impact assessment extracts the impact of a particular sensor detecting a particular scenario. Impact can be measured using a variety of metrics such as time to detection, population impacted, or volume of contaminant released before detection. Additionally, these impact metrics can be used to define when a sensor covers a particular scenario for use in coverage-based optimization formulations.

The chama.impact module converts information about the signal and sensors, described in the Simulation and Sensor technology sections, into the input needed for the sensor placement optimization formulations described in the Optimization section. Impact assessment starts by extracting the times when each sensor detects a scenario. After that, detection times can be converted into other impact metrics used in the Impact Formulation or coverage-based formats used in the Coverage Formulation.

Extract detection times¶

The ability for a sensor to detect a scenario depends on several factors, including the scenario environmental conditions, sensor location, and sensor operating parameters. While some scenarios might be detected multiple times by a single sensor, other scenarios can go undetected by all sensors. The following example demonstrates how to extract detection times using a predefined signal, and a set of predefined sensors.

Obtain a signal DataFrame and group sensors (defined in the Sensor technology section) in a dictionary:

>>> print(signal.head())
   S1  S2    S3   T  X  Y  Z
0   0   0     0   0  1  1  1
1  10  10     0  10  1  1  1
2  20  20   200  20  1  1  1
3  30  30   600  30  1  1  1
4  40  40  1200  40  1  1  1

>>> sensors = dict()
>>> sensors['A'] = stationary_pt_sensor
>>> sensors['B'] = mobile_pt_sensor
>>> sensors['C'] = stationary_camera_sensor
>>> sensors['D'] = mobile_camera_sensor

Extract detection times:

>>> det_times = chama.impact.extract_detection_times(signal, sensors)

>>> print(det_times)
  Scenario Sensor   Detection Times
     S1      A              [30]
     S1      B              [30]
     S1      C  [10, 20, 30, 40]
     S2      A      [10, 20, 30]
     S2      B          [20, 30]
     S2      C  [10, 20, 30, 40]
     S3      A          [20, 30]
     S3      B          [20, 30]
     S3      C      [20, 30, 40]

The example shows that Scenario S1 was detected by Sensor A at time 30 (units of time depend on the simulation). Scenario S1 was also detected by Sensor B and time 30 and Sensor C at times 10, 20, 30 and 40. Scenario S2 was detected by Sensors A, B, and C. Scenario S3 was detected by Sensors A, B, and C. Sensor D did not detect any scenarios.

The detection times DataFrame can be converted into the required input format for the Impact Formulation or Coverage Formulation as described below.

Convert detection times to input for the Impact Formulation¶

The Impact Formulation requires as input a DataFrame with three columns: ‘Scenario’, ‘Sensor’, and ‘Impact’, where the ‘Impact’ is a single numerical value for each row. This means that the list of detection times in the DataFrame produced above must be reduced to a single numerical value representing the impact to be minimized.

Minimum detection time¶

The example below shows how to build an input DataFrame for the Impact Formulation to optimize a sensor layout that minimizes detection time.

Extract detection time statistics:

>>> det_time_stats = chama.impact.detection_time_stats(det_times)
>>> print(det_time_stats)
  Scenario Sensor  Min  Mean  Median  Max  Count
     S1      A   30  30.0    30.0   30      1
     S1      B   30  30.0    30.0   30      1
     S1      C   10  25.0    25.0   40      4
     S2      A   10  20.0    20.0   30      3
     S2      B   20  25.0    25.0   30      2
     S2      C   10  25.0    25.0   40      4
     S3      A   20  25.0    25.0   30      2
     S3      B   20  25.0    25.0   30      2
     S3      C   20  30.0    30.0   40      3

Extract the minimum detection time from the statistics computed above:

>>> min_det_time = det_time_stats[['Scenario','Sensor','Min']]
>>> min_det_time = min_det_time.rename(columns={'Min':'Impact'})
>>> print(min_det_time)
  Scenario Sensor  Impact
0       S1      A      30
1       S1      B      30
2       S1      C      10
3       S2      A      10
4       S2      B      20
5       S2      C      10
6       S3      A      20
7       S3      B      20
8       S3      C      20

Other impact metrics¶

Depending on the information available from the simulation, detection time can be converted to other measures of impact, such as damage cost, extent of contamination, or ability to protect critical assets and populations. For example, if the cost of detecting scenario S1 at time 30 is $80,000, then the impact metric for that scenario can be translated from a detection time of 30 to a cost of $80,000. The data associated with the new impact metric is stored in a Pandas DataFrame with one column for time, ‘T’, and one column for each scenario (name specified by the user).

Example impact costs associated with each scenario and time:

>>> print(impact_cost)
    T      S1     S2      S3
 0       0      0       0
10   10000   5000   15000
20   40000  20000   50000
30   80000  75000   95000
40  100000  90000  150000

Rename the time column in min_det_time to ‘T’:

>>> det_time = min_det_time.rename(columns={'Impact':'T'}, inplace=False)
>>> print(det_time)
  Scenario Sensor   T
     S1      A  30
     S1      B  30
     S1      C  10
     S2      A  10
     S2      B  20
     S2      C  10
     S3      A  20
     S3      B  20
     S3      C  20

Convert minimum detection time to damage cost:

>>> impact_metric = chama.impact.detection_time_to_impact(det_time, impact_cost)
>>> print(impact_metric)
  Scenario Sensor  Impact
     S1      A   80000
     S1      B   80000
     S1      C   10000
     S2      A    5000
     S2      B   20000
     S2      C    5000
     S3      A   50000
     S3      B   50000
     S3      C   50000

Note that the detection_time_to_impact function interpolates based on time, if needed.

Convert detection times to input for the Coverage Formulation¶

The Coverage Formulation requires as input a DataFrame with two columns: ‘Sensor’, and ‘Coverage’, where the ‘Coverage’ is a list of entities covered by each sensor. The formulation optimizes a sensor layout that maximizes the coverage of the entities contained in this DataFrame. An entity to be covered might include scenarios, scenario-time pairs, or geographic locations.

Scenario coverage¶

The following example converts detection times to scenario coverage. With scenario coverage, a scenario is the entity to be covered. A scenario is considered covered by a sensor if that sensor detects that scenario at any time.

Recall the detection times DataFrame from above:

>>> print(det_times)
  Scenario Sensor   Detection Times
     S1      A              [30]
     S1      B              [30]
     S1      C  [10, 20, 30, 40]
     S2      A      [10, 20, 30]
     S2      B          [20, 30]
     S2      C  [10, 20, 30, 40]
     S3      A          [20, 30]
     S3      B          [20, 30]
     S3      C      [20, 30, 40]

Convert detection times to scenario coverage:

>>> scenario_cov = chama.impact.detection_times_to_coverage(det_times, coverage_type='scenario')
>>> print(scenario_cov)
  Sensor      Coverage
0      A  [S1, S2, S3]
1      B  [S1, S2, S3]
2      C  [S1, S2, S3]

This example shows that sensor A covers the scenarios S1, S2, and S3. Sensors B and C also cover all three scenarios.

Scenario-time coverage¶

The next example converts detection times to scenario-time coverage. With scenario-time coverage, the entities to be covered are all combinations of the scenarios and the detection times. This type of coverage gives more weight to sensors that detect scenarios for longer periods of time. The same detection_times_to_coverage function can be used to convert detection times to scenario-time coverage with one major difference to the previous case. With scenario coverage the scenarios themselves become the entities to be covered. This means that if there is additional data available for the scenarios such as weights/probabilities or undetected impact, these values can be used directly in the coverage solver. With scenario-time coverage, we are essentially defining new entities/scenarios. So any data corresponding to the original scenarios must be translated to the new entities before they can be passed to the coverage solver. The detection_times_to_coverage function does this by accepting an optional ‘scenario’ keyword argument containing a DataFrame with scenario probabilities and undetected impact. These values are then propagated to the new scenario-time entities and a new DataFrame is returned with this information.

Convert detection times to scenario-time coverage and propagate scenario information to new scenario-time pairs:

>>> print(scenario)
   Probability Scenario  Undetected Impact
0         0.25       S1                100
1         0.50       S2                100
2         0.75       S3                100

>>> scen_time_cov, new_scenario = chama.impact.detection_times_to_coverage(
...                                          det_times,
...                                          coverage_type='scenario-time',
...                                          scenario=scenario)

>>> print(scen_time_cov)
  Sensor                                           Coverage
0      A  [S1-30.0, S2-10.0, S2-20.0, S2-30.0, S3-20.0, ...
1      B      [S1-30.0, S2-20.0, S2-30.0, S3-20.0, S3-30.0]
2      C  [S1-10.0, S1-20.0, S1-30.0, S1-40.0, S2-10.0, ...

>>> print(new_scenario)
   Scenario  Probability  Undetected Impact
0   S1-30.0         0.25                100
2   S1-10.0         0.25                100
3   S1-20.0         0.25                100
5   S1-40.0         0.25                100
6   S2-10.0         0.50                100
7   S2-20.0         0.50                100
8   S2-30.0         0.50                100
14  S2-40.0         0.50                100
15  S3-20.0         0.75                100
16  S3-30.0         0.75                100
21  S3-40.0         0.75                100

This example shows that sensor A covers the scenario-time pairs S1-30.0, S2-10.0, and S2-20.0 among others. In addition, notice that the probability and undetected impact for scenario S1 is propagated to all scenario-time pairs containing S1 in the new_scenario DataFrame.

Convert input for the Impact Formulation to the Coverage Formulation¶

Users can also convert the input DataFrame for the Impact Formulation to the input DataFrame for the Coverage Formulation. This is especially convenient in cases where the user is solving optimization problems using both solver classes and the DataFrame for the impact solver was generated outside of the standard Chama workflow (i.e. the signal, sensors, or detection_times DataFrames are unavailable). In the following example, an impact DataFrame is converted to a scenario coverage DataFrame.

Recall the impact DataFrame containing minimum detection time from above:

>>> print(min_det_time)
  Scenario Sensor  Impact
     S1      A      30
     S1      B      30
     S1      C      10
     S2      A      10
     S2      B      20
     S2      C      10
     S3      A      20
     S3      B      20
     S3      C      20

Convert the impact DataFrame to a coverage DataFrame:

>>> scenario_cov = chama.impact.impact_to_coverage(min_det_time)
>>> print(scenario_cov)
  Sensor      Coverage
0      A  [S1, S2, S3]
1      B  [S1, S2, S3]
2      C  [S1, S2, S3]

Notice that we end up with the same scenario coverage DataFrame as before but using different input.

Optimization¶

The chama.optimize module contains Impact and Coverage sensor placement optimization formulations. The formulations are written in Pyomo [HLWW12] and solved using an open source or commercial solver such as GLPK [Makh10], Gurobi [GUROBI], or CPLEX [CPLEX]. The open source GLPK solver is used by default. Additional optimization formulations could be added to this module.

Impact Formulation¶

The Impact formulation is used to determine optimal sensor placement and type that minimizes impact, where impact can be the sensor’s detection time or some other measure of damage. The Impact formulation, which is based on the p-median facility location problem, is described below:

\[\begin{split}\text{minimize} \qquad &\sum_{a \in A} \alpha_a \sum_{i \in {\cal L}_a} d_{ai} x_{ai}\\ \text{subject to} \qquad &\sum_{i\in {\cal L}_a} x_{ai} = 1 \hspace{1.2in} \forall a \in A\\ &x_{ai} \le s_i \hspace{1.47in} \forall a \in A, i \in {\cal L}_a\\ &\sum_{i \in L} c_i s_i \le p\\ &s_i \in \{0,1\} \hspace{1.3in} \forall i \in L\\ &0 \leq x_{ai} \leq 1 \hspace{1.23in} \forall a \in A, i \in {\cal L}_a\end{split}\]

where:

$A$ is the set of all scenarios
$L$ is the set of all candidate sensors
${\cal L_a}$ is the set of all sensors that are capable of detecting scenario $a$
$\alpha_a$ is the probability of occurrence for scenario $a$
$d_{ai}$ is the impact assessment, and represents some measure of the impact that will be incurred if scenario $a$ is first detected by sensor $i$
$x_{ai}$ is an indicator variable that will be 1 if sensor $i$ is installed and that sensor is the first to detect scenario $a$ (where first is defined as the minimum possible impact, usually defined as time to detection)
$s_i$ is a binary variable that will be 1 if sensor $i$ is selected, and 0 otherwise
$c_i$ is the cost of sensor $i$
$p$ is the sensor budget

The size of the Impact formulation is determined by the number of binary variables. Although $x_{ai}$ is a binary indicator variable, it is relaxed to be continuous between 0 and 1, and yet it always converges to a value of 0 or 1. Therefore, the number of binary variables that need to be considered by the solver is a function of the number of candidate sensors alone, and not the number of scenarios considered. This formulation has been used to place sensors in large water distribution networks [BHPU06] [USEPA12] [USEPA15] and for gas detection in petrochemical facilities [LBSW12].

To use this formulation in Chama, create an ImpactFormulation object and specify the impact assessment, $d_{ai}$, sensor budget, $p$, and (optionally) sensor cost, $c_i$ and the scenario probability, $\alpha_a$, as described below:

Impact assessment: A single value of impact (detection time or other measure of damage) for each sensor that detects a scenario. Impact is stored as a Pandas DataFrame, as described in the Impact assessment section.
Sensor budget: The number of sensors to place, or total budget for sensors. If the ‘use_sensor_cost’ flag is True, the sensor budget is a dollar amount and the optimization uses the cost of individual sensors. If the ‘use_sensor_cost’ flag is False (default), the sensor budget is a number of sensors and the optimization does not use sensor cost.
Sensor characteristics: Sensor characteristics include the cost of each sensor. Sensor characteristics are stored as a Pandas DataFrame with columns ‘Sensor’ and ‘Cost’. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
Scenario characteristics: Scenario characteristics include scenario probability and the impact for undetected scenarios. Scenario characteristics are stored as a Pandas DataFrame with columns ‘Scenario’, ‘Undetected Impact’ , and ‘Probability’. Undetected Impact is required for each scenario. When minimizing detection time, the undetected impact value can be set to a value larger than time horizon used for the study. Individual scenarios can also be given different undetected impact values. Probability is used if the ‘use_scenario_probability’ flag is set to True.

Results are stored in a dictionary with the following information:

Sensors: A list of selected sensors
Objective: The expected (mean) impact based on the selected sensors
FractionDetected: The fraction of scenarios that were detected
TotalSensorCost: Total cost of the selected sensors
Assessment: The impact value for each sensor-scenario pair. The assessment is stored as a Pandas DataFrame with columns ‘Scenario’, ‘Sensor’, and ‘Impact’ (same format as the input Impact assessment’) If the selected sensors did not detect a particular scenario, the impact is set to the Undetected Impact.

The following example demonstrates the use of the Impact Formulation.

>>> print(min_det_time)
  Scenario Sensor  Impact
0       S1      A     2.0
1       S2      A     3.0
2       S3      B     4.0
3       S4      C     1.0
4       S5      D     2.0
>>> print(sensor)
  Sensor   Cost
0      A  100.0
1      B  200.0
2      C  400.0
3      D  500.0
>>> print(scenario)
  Scenario  Undetected Impact  Probability
0       S1               50.0         0.15
1       S2              250.0         0.50
2       S3              100.0         0.05
3       S4               75.0         0.20
4       S5              225.0         0.10

>>> impactform = chama.optimize.ImpactFormulation()
>>> results = impactform.solve(impact=min_det_time, sensor_budget=1000,
...                              sensor=sensor, scenario=scenario,
...                              use_scenario_probability=True,
...                              use_sensor_cost=True)

>>> print(results['Sensors'])
['A', 'C', 'D']
>>> print(results['Objective'])
7.2
>>> print(results['Assessment'])
  Scenario Sensor  Impact
0       S1      A     2.0
1       S2      A     3.0
2       S4      C     1.0
3       S5      D     2.0
4       S3   None   100.0

Coverage Formulation¶

The Coverage formulation is used to place sensors that maximize the coverage of a set of entities, where an entity can be a scenario, scenario-time pair, or geographic location. The Coverage formulation is described below:

\[\begin{split}\text{maximize} \qquad &\sum_{a \in A} \alpha_a x_a \\ \text{subject to} \qquad &x_{a} \le \sum_{i \in {\cal L}_a} s_i \hspace{1.15in} \forall a \in A\\ &\sum_{i \in L} c_i s_i \le p\\ &s_i \in \{0,1\} \hspace{1.3in} \forall i \in L\\ &0 \leq x_{a} \leq 1 \hspace{1.25in} \forall a \in A\end{split}\]

where:

$A$ is the set of all entities
$L$ is the set of all candidate sensors
${\cal L_a}$ is the set of all sensors that cover entity $a$
$\alpha_a$ is the objective weight of entity $a$
$x_{a}$ is an indicator variable that will be 1 if entity $a$ is covered
$s_i$ is a binary variable that will be 1 if sensor $i$ is selected, and 0 otherwise
$c_i$ is the cost of sensor $i$
$p$ is the sensor budget

This formulation is similar to the Impact formulation in that the number of binary variables is a function of the number of candidate sensors and not the number of entities considered.

To use this formulation in Chama, create a CoverageFormulation object and specify the coverage, ${\cal L_a}$, sensor budget, $p$, and (optionally) sensor cost, $c_i$ and the entity weights, $\alpha_a$, as described below:

Coverage: A list of entities that are covered by a single sensor. Coverage is stored as a Pandas DataFrame, as described in the Impact assessment section.
Sensor budget: The number of sensors to place, or total budget for sensors. If the ‘use_sensor_cost’ flag is True, the sensor budget is a dollar amount and the optimization uses the cost of individual sensors. If the ‘use_sensor_cost’ flag is False (default), the sensor budget is a number of sensors and the optimization does not use sensor cost.
Sensor characteristics: Sensor characteristics include the cost of each sensor. Sensor characteristics are stored as a Pandas DataFrame with columns ‘Sensor’ and ‘Cost’. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
Entity characteristics: Entity weights stored as a Pandas DataFrame with columns ‘Entity’ and ‘Weight’. Weight is used if the ‘use_entity_weight’ flag is set to True.

Results are stored in a dictionary with the following information:

Sensors: A list of selected sensors
Objective: The mean coverage based on the selected sensors
FractionDetected: The fraction of entities that are detected
TotalSensorCost: Total cost of selected sensors
EntityAssessment: A dictionary whose keys are the entity names and values are a list of sensors that detect that entity
SensorAssessment: A dictionary whose keys are the sensor names and values are the list of entities that are detected by that sensor

The following example demonstrates the use of the Coverage Formulation to solve for scenario-time coverage. The results list scenario-time pairs that were detected by the sensor placement (listed as ‘scenario-time’).

>>> print(det_times)
  Scenario Sensor Detection Times
0       S1      A       [2, 3, 4]
1       S2      A             [3]
2       S3      B    [4, 5, 6, 7]
3       S4      C          [1, 3]
4       S5      B             [6]
5       S5      D       [2, 4, 6]
>>> print(sensor)
  Sensor   Cost
0      A  100.0
1      B  200.0
2      C  400.0
3      D  500.0
>>> print(scenario)
  Scenario  Undetected Impact  Probability
0       S1               50.0         0.15
1       S2              250.0         0.50
2       S3              100.0         0.05
3       S4               75.0         0.20
4       S5              225.0         0.10
>>> scenario_time, new_scenario = chama.impact.detection_times_to_coverage(
...                                         det_times,
...                                         coverage_type='scenario-time',
...                                         scenario=scenario)

>>> print(scenario_time)
  Sensor                                  Coverage
0      A          [S1-2.0, S1-3.0, S1-4.0, S2-3.0]
1      B  [S3-4.0, S3-5.0, S3-6.0, S3-7.0, S5-6.0]
2      C                          [S4-1.0, S4-3.0]
3      D                  [S5-2.0, S5-4.0, S5-6.0]
>>> print(new_scenario)
   Scenario  Undetected Impact  Probability
0    S1-2.0               50.0         0.15
1    S1-3.0               50.0         0.15
2    S1-4.0               50.0         0.15
3    S2-3.0              250.0         0.50
4    S3-4.0              100.0         0.05
5    S3-5.0              100.0         0.05
6    S3-6.0              100.0         0.05
7    S3-7.0              100.0         0.05
8    S4-1.0               75.0         0.20
9    S4-3.0               75.0         0.20
10   S5-6.0              225.0         0.10
11   S5-2.0              225.0         0.10
12   S5-4.0              225.0         0.10

>>> new_scenario = new_scenario.rename(columns={'Scenario':'Entity',
...                                             'Probability':'Weight'})
>>> coverageform = chama.optimize.CoverageFormulation()
>>> results = coverageform.solve(coverage=scenario_time, sensor_budget=1000,
...                          sensor=sensor, entity=new_scenario,
...                          use_sensor_cost=True)

>>> print(results['Sensors'])
['A', 'B', 'D']
>>> print(results['Objective'])
11.0
>>> print(round(results['FractionDetected'],2))
0.85

Grouping Constraints¶

Constraints can be added to both the Impact and Coverage formulations to enforce or restrict the number of sensors allowed from certain sets. These grouping constraints take the following general form:

\[g_{min} \le \sum_{i \in L_g} s_i \le g_{max}\]

where:

$L_g$ is a subset of all candidate sensors
$s_i$ is a binary variable that will be 1 if sensor $i$ is selected, and 0 otherwise
$g_{min}$ is the minimum number of sensors that must be selected from the subset $L_g$
$g_{max}$ is the maximum number of sensors that may be selected from the subset $L_g$

Grouping constraints can be used to ensure that an optimal sensor placement follows required policies or meets practical limitations. For example, you might want to determine the optimal sensor placement, while also ensuring that there is at least one sensor in every 10 m x 10 m subvolume of the space. This can be formulated by defining sensor subsets $L_g$ containing the candidate sensors within each subvolume and adding a grouping constraint over each of these subsets with $g_{min}$ set to 1.

Another example where grouping constraints might be used is when you have different categories of sensors and you want to make sure that an optimal placement has a certain number of each category. In this case, you would define a sensor subset $L_g$ for each category of sensor and then set $g_{min}$ and $g_{max}$ according to how many sensors you want in each category.

While grouping constraints are very useful, it should be noted that it is possible to formulate infeasible optimization problems if these constraints are not used carefully.

The following example adds grouping constraints to the Impact formulation. This requires the user to 1) create the Pyomo model, 2) add the grouping constraints, 3) solve the model, and 4) extract the solution summary.

>>> impactform = chama.optimize.ImpactFormulation()

>>> model = impactform.create_pyomo_model(impact=min_det_time, sensor=sensor, scenario=scenario)
>>> impactform.add_grouping_constraint(['A', 'B'], min_select=1)
>>> impactform.add_grouping_constraint(['C', 'D'], min_select=1)
>>> impactform.solve_pyomo_model(sensor_budget=2)
>>> results = impactform.create_solution_summary()

>>> print(results['Sensors'])
['A', 'D']

Grouping constraints can be added to the Coverage formulation in a similar manner.

Graphics¶

The chama.graphics module provides methods to help visualize results.

Signal graphics¶

Chama provides several functions to visualize signals described in the Simulation section (XYZ format only). Visualization is useful to verify that the signal was loaded/generated as expected, compare scenarios, and to better understand optimal sensor placement.

The convex hull of several scenarios can be generated as follows (Figure 3):

>>> chama.graphics.signal_convexhull(signal, scenarios=['S1', 'S2', 'S3'], threshold=0.01)

Convex hull plot¶

The cross section of a single scenarios can be generated as follows (Figure 4):

>>> chama.graphics.signal_xsection(signal, 'S1', threshold=0.01)

Cross section plot¶

Sensor graphics¶

The position of fixed and mobile sensors, described in the Sensor technology section, can be plotted. After grouping sensors in a dictionary, the locations can be plotted as follows (Figure 5):

>>> chama.graphics.sensor_locations(sensors)

Mobile and stationary sensor locations plot¶

Tradeoff curves¶

After running a series of sensor placement optimizations with increasing sensor budget, a tradeoff curve can be generated using the objective value and fraction of detected scenarios. Figure 6 compares the expected time to detection and scenario coverage as the sensor budget increases.

Optimization tradeoff curve¶

Scenario analysis¶

The impact of individual scenarios can also be analyzed for a single sensor placement using the optimization assessment. Figure 7 compares time to detection from several scenarios, given an optimal placement.

>>> print(results['Assessment'])
  Scenario Sensor  Impact
0       S1      A       4
1       S2      A       5
2       S3      B      10
3       S4      C       3
4       S5      A       1
>>> results['Assessment'].plot(kind='bar') 

Scenario impact values based on optimal placement¶

Examples¶

The following examples are included in the examples directory of the Chama repository.

Copyright and license¶

Chama is copyright through National Technology & Engineering Solutions of Sandia. The software is distributed under the Revised BSD License. Chama also leverages a variety of third-party software packages, which have separate licensing policies.

Copyright¶

Copyright 2016 National Technology & Engineering Solutions of Sandia,
LLC (NTESS). Under the terms of Contract DE-NA0003525 with NTESS, the U.S.
Government retains certain rights in this software.

Revised BSD license¶

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

* Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of Sandia National Laboratories, nor the names of
  its contributors may be used to endorse or promote products derived from
  this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Release notes¶

v0.2.0 (October 5, 2022)¶

Bug fix in type checking for impact assessment dataframes
Minor changes to the optimization formulations to account for updates in Pyomo
Minor changes to account for updates in Pandas
Dropped Python 3.5 and 3.6 tests, added Python 3.8 and 3.9 tests
Added GitHub Actions for testing
Added a Gaussian plume and water network example
Updated documentation

v0.1.3 (February 28, 2020)¶

Updated methods to be compatible with Pandas 1.0
Added required dependencies to setup.py
Dropped Python 2.7 tests
Updated documentation

v0.1.2 (September 27, 2019)¶

Added grouping constraints to the Coverage formulation
Dropped Python 3.4 tests, added Python 3.7 tests
Updated documentation

v0.1.1 (June 2, 2018)¶

Added new optimization formulation for coverage (API change, see CoverageFormulation)
Renamed the Pmedian formulation (API change, see ImpactFormulation)
Added functionality to return the Pyomo model for both Coverage and Impact formulations
Added functionality to add grouping constraints to the Impact formulation
Added additional methods to transform data for use in the Impact and Coverage formulations (see methods in impact)
Renamed transport module to simulation module (API change)
Updated documentation

v0.1.0 (October 9, 2017)¶

This is the first release of Chama. Features include basic functionality to:

Run atmospheric dispersion simulations or import simulations from external software
Define point or camera sensors that can be stationary and mobile
Extract detection times for each sensor and scenario
Solve sensor placement optimization using coverage or p-median formulations
Analyze and graph results

Software development¶

The following section includes information on resources associated with the Chama software project, including the GitHub repository, the Python Package Index (PyPI), software tests, documentation, bug reports, feature requests, and information on contributing.

GitHub: The Chama software repository is hosted on GitHub at https://github.com/sandialabs/chama.

PyPI: The latest stable version is hosted on PyPI at https://pypi.python.org/pypi/chama.

Testing: Automated testing is run using TravisCI at https://travis-ci.org/sandialabs/chama. Test coverage statistics are collected using Coveralls at https://coveralls.io/github/sandialabs/chama. Tests can be run locally using nosetests:

nosetests -v --with-coverage --cover-package=chama chama

Documentation: Documentation is built using Read the Docs and hosted at https://chama.readthedocs.io.

Bug reports and feature requests: Bug reports and feature requests can be submitted to https://github.com/sandialabs/chama/issues. The core development team will prioritize requests.

Contributing: Software developers are expected to follow standard practices to document and test new code. Pull requests will be reviewed by the core development team. See https://github.com/sandialabs/chama/graphs/contributors for a list of contributors.

API documentation¶

Submodules¶

chama.simulation module¶

The simulation module contains methods to run Gaussian air dispersion models. Chama can also integrate simulations from third party software for additional sensor placement applications.

Contents

`Grid`(x, y, z)	Defines the receptor grid.
`Source`(x, y, z, rate)	Defines the source location and leak rate.
`GaussianPlume`(grid, source, atm[, gravity, ...])	Defines the Gaussian plume model.
`GaussianPuff`([grid, source, atm, tpuff, ...])	Defines the Gaussian puff model.

class chama.simulation.Grid(x, y, z)[source]¶

Bases: object

Defines the receptor grid.

Parameters

x (numpy array) – x values in the grid (m)
y (numpy array) – y values in the grid (m)
z (numpy array) – z values in the grid (m)

class chama.simulation.Source(x, y, z, rate)[source]¶

Bases: object

Defines the source location and leak rate.

Parameters

x (float) – x location of the source (m)
y (float) – y location of the source (m)
z (float) – z location of the source (m)
rate (float) – source leak rate (kg/s)

class chama.simulation.GaussianPlume(grid, source, atm, gravity=9.81, density_eff=0.769, density_air=1.225)[source]¶

Bases: object

Defines the Gaussian plume model.

Parameters

grid (chama Grid) – Grid points at which concentrations should be calculated
source (chama Source) – Source location and leak rate
atm (pandas DataFrame) – Atmospheric conditions for the simulation. Columns include ‘Wind Direction’, ‘Wind Speed’, and ‘Stability Class’ indexed by the time that changes occur.
gravity (float) – Gravity (m2/s), default = 9.81 m2/s
density_eff (float) – Effective density of the leaked species (kg/m3), default = 0.769 kg/m3
density_eff – Effective density of air (kg/m3), default = 1.225 kg/m3

run()[source]¶: Computes the concentrations of a Gaussian plume.

class chama.simulation.GaussianPuff(grid=None, source=None, atm=None, tpuff=1, tend=None, tstep=10, gravity=9.81, density_eff=0.769, density_air=1.225)[source]¶

Bases: object

Defines the Gaussian puff model.

Parameters

grid (chama Grid) – Grid points at which concentrations should be calculated
source (chama Source) – Source location and leak rate
atm (pandas DataFrame) – Atmospheric conditions for the simulation. Columns include ‘Wind Direction’,’Wind Speed’, and ‘Stability Class’ indexed by the time that changes occur.
tpuff (float) – Time between puffs (s)
tend (float) – Total time to run the simulation (s). Must be divisible by tpuff
tstep (float) – Time step for reporting concentration information (s)
gravity (float) – Gravity (m2/s), default = 9.81 m2/s
density_eff (float) – Effective density of the leaked species (kg/m3), default = 0.769 kg/m3
density_air (float) – Effective density of air (kg/m3), default = 1.225 kg/m3

run(grid, tstep)[source]¶

Computes the concentrations of a Gaussian puff model.

Parameters

grid (chama Grid) – Grid points at which concentrations should be calculated
tstep (float) – Time step for reporting concentration information (s)

chama.sensors module¶

The sensor module contains classes to define point or camera sensors that can either be stationary and mobile.

Contents

`Sensor`([position, detector])	Defines a sensor object and methods to calculate detection.
`Position`([location])	Defines a sensor's position.
`Stationary`([location])	Defines a stationary sensor's position.
`Mobile`([locations, speed, start_time, repeat])	Defines a mobile sensor's position.
`Detector`([threshold, sample_times])	Defines a sensor's detector.
`Point`([threshold, sample_times])	Defines a point sensor.
`Camera`([threshold, sample_times, direction])	Defines a camera sensor.

class chama.sensors.Sensor(position=None, detector=None)[source]¶

Bases: object

Defines a sensor object and methods to calculate detection.

Parameters

position (chama Position) – Sensor position
detector (chama Detector) – Sensor detector, determines the method used to calculate detection

get_detected_signal(signal, interp_method=None, min_distance=10.0)[source]¶: Returns the detected signal.

class chama.sensors.Position(location=None)[source]¶

Bases: object

Defines a sensor’s position.

Parameters: location ((x,y,z) tuple or index) – The location of the Position object defined as an (x,y,z) tuple or location index, which can be a string or integer

class chama.sensors.Stationary(location=None)[source]¶

Bases: Position

Defines a stationary sensor’s position.

Defines a sensor’s position.

Parameters: location ((x,y,z) tuple or index) – The location of the Position object defined as an (x,y,z) tuple or location index, which can be a string or integer

class chama.sensors.Mobile(locations=None, speed=1, start_time=0, repeat=False)[source]¶

Bases: Position

Defines a mobile sensor’s position. A mobile position moves according to defined waypoints and speed. The mobile position is assumed to move in a straight line between waypoints and will repeat its path if needed.

Parameters

locations (list of (x,y,z) tuples) – List of (x,y,z) tuples defining the waypoints of the mobile sensor’s path.
speed (int or float) – The speed of the mobile sensor in units consistent with the waypoints and sensor sample_times
repeat (bool) – Boolean indicating if the path should repeat

Defines a sensor’s position.

Parameters: location ((x,y,z) tuple or index) – The location of the Position object defined as an (x,y,z) tuple or location index, which can be a string or integer

class chama.sensors.Detector(threshold=None, sample_times=None)[source]¶

Bases: object

Defines a sensor’s detector.

Parameters

threshold (int) – The minimum signal that can be detected by the sensor
sample_times (list of ints or floats) – List of the sensor’s sample/measurement times

get_sample_points(position)[source]¶

Returns the sensor sample points in the form (t,x,y,z) or (t,j)

Parameters: position (chama Position) – The position of the sensor
Returns: A list of sample points in the form (t,x,y,z) or (t,j)

get_detected_signal(signal, position, interp_method, min_distance)[source]¶

Returns the signal detected by the sensor.

Parameters

signal (pandas DataFrame) – DataFrame with the multi-index (T, X, Y, Z) or (T, Node) and columns containing the concentrations for different scenarios
position (chama Position) – The position of the sensor
interp_method ('linear', 'nearest', or None) – Method used to interpolate the signal if needed. A value of ‘linear’ will use griddata to interpolate missing sample points. A value of ‘nearest’ will set the sample point to the nearest signal point within a minimum distance of min_distance. If there are no signal points within this distance then the signal will be set to zero at the sample point.
min_distance (float) – The minimum distance when using the ‘nearest’ interp_method

Returns

A pandas Series with multi-index (T, Scenario) and signal values above
the sensor threshold.

class chama.sensors.Point(threshold=None, sample_times=None)[source]¶

Bases: Detector

Defines a point sensor.

class chama.sensors.Camera(threshold=None, sample_times=None, direction=(1, 1, 1), **kwds)[source]¶

Bases: Detector

Defines a camera sensor.

Parameters

threshold (int) – The minimum number of pixels that must detect something in order for the camera to detect.
sample_times (list of ints or floats) – List of the sensor’s sample/measurement times
direction ((x, y, z) tuple) – Tuple representing the direction that the camera is pointing in (x, y, z) coordinates relative to the origin
**kwds (dictionary) – Keyword arguments for setting parameter values in the camera model

chama.impact module¶

The impact module contains methods to extract detection times from a set of simulations and sensor technologies along with methods to convert detection times to impact and coverage metrics.

Contents

`extract_detection_times`(signal, sensors[, ...])	Returns detection times from a signal and group of sensors.
`detection_time_stats`(detection_times)	Returns detection times statistics (min, mean, median, max, and count).
`detection_time_to_impact`(detection_time, ...)	Coverts detection time to an impact/damage metric.
`detection_times_to_coverage`(detection_times)	Converts a detection times DataFrame to a coverage DataFrame
`impact_to_coverage`(impact[, impact_col_name])	Convert an impact DataFrame to a coverage DataFrame

chama.impact.extract_detection_times(signal, sensors, interp_method=None, min_distance=10.0)[source]¶

Returns detection times from a signal and group of sensors.

Parameters

signal (pandas DataFrame) – Signal data from the simulation. The DataFrame can be in XYZ format (with columns named ‘X’,’Y’,’Z’,’T’) or Node format (with columns named ‘Node’,’T’) along with one column for each scenario (user defined names).
sensors (dict) – A dictionary of sensors with key:value pairs containing {‘sensor name’: chama Sensor object}
interp_method ('linear', 'nearest', or None) – Method used to interpolate the signal if needed. A value of ‘linear’ will use griddata to interpolate missing sample points. A value of ‘nearest’ will set the sample point to the nearest signal point within a minimum distance of min_distance. If there are no signal points within this distance then the signal will be set to zero at the sample point. Note that interpolation is not used when the signal is in Node format.
min_distance (float) – The minimum distance when using the ‘nearest’ interp_method

Returns

det_times (pandas DataFrame) – DataFrame with columns ‘Scenario’, ‘Sensor’, and ‘Detection Times’.

chama.impact.detection_time_stats(detection_times)[source]¶

Returns detection times statistics (min, mean, median, max, and count).

The minimum detection time is often used as input to an impact-based sensor placement solver.

Parameters: detection_times (pandas DataFrame) – Detection times for each scenario-sensor pair. The DataFrame has columns ‘Scenario’, ‘Sensor’, and ‘Detection Times’, see detection_times.
Returns: det_t (pandas DataFrame) – DataFrame with columns ‘Scenario’, ‘Sensor’, ‘Min’, ‘Mean’, ‘Median’, ‘Max’, and ‘Count’.

chama.impact.detection_time_to_impact(detection_time, impact_data)[source]¶

Coverts detection time to an impact/damage metric.

The impact DataFrame returned from this function can be used as input to ImpactFormulation.

Parameters

detection_time (pandas DataFrame) – Detection time for each scenario-sensor pair. The DataFrame has columns ‘Scenario’, ‘Sensor’, and ‘T’. Note the ‘T’ column here is a single time and not a list of detection times.
impact_data (pandas DataFrame) – Impact data for each scenario and time. The DataFrame has columns ‘T’ and one column for each scenario (user defined names) containing the impact/damage if each scenario was first detected at the times in ‘T’.

Returns

det_damage (pandas DataFrame) – DataFrame with columns ‘Scenario’, ‘Sensor’, and ‘Impact’.

chama.impact.detection_times_to_coverage(detection_times, coverage_type='scenario', scenario=None)[source]¶

Converts a detection times DataFrame to a coverage DataFrame

The returned coverage DataFrame can be used for input to a CoverageFormulation.

Parameters

detection_times (pandas DataFrame) – Detection times for each scenario-sensor pair. The DataFrame has columns ‘Scenario’, ‘Sensor’, and ‘Detection Times’, see detection_times.
coverage_type ('scenario' or 'scenario-time') – Sets the coverage type: ‘scenario’ (the default value) builds lists of which scenarios are detected/covered by each sensor ignoring the time it was detected, ‘scenario-time’ treats every scenario-time pair as a new scenario and builds lists of which of these new scenarios are detected/covered by each sensor thereby calculating coverage over all scenarios and times.
scenario (pandas DataFrame) – This is an optional argument which should be provided only if the coverage_type is ‘scenario-time’ and the user wants to propagate a scenario’s undetected impact and probability to the new ‘scenario-time’ scenarios. This DataFrame contains three columns, ‘Scenario` is the name of the scenarios, ‘Undetected Impact’ is the impact if the scenario goes undetected and ‘Probability’ is the probability or weighting of each scenario.

Returns

coverage (pandas DataFrame) – DataFrame with columns ‘Sensor’ and ‘Coverage’ where the ‘Coverage’ column contains a list of the scenarios/entities detected by a sensor.
new_scenario (pandas DataFrame) – DataFrame returned if coverage_type is ‘scenario-time’ and a ‘scenario’ DataFrame was provided. The columns in this DataFrame match those in the provided ‘scenario’ DataFrame

chama.impact.impact_to_coverage(impact, impact_col_name='Impact')[source]¶

Convert an impact DataFrame to a coverage DataFrame

The returned coverage DataFrame can be used for input to a CoverageFormulation.

Parameters

impact (pandas DataFrame) – DataFrame containing three columns. ‘Scenario’ is the name of the scenarios, ‘Sensor’ is the name of the sensors, and a third column (called impact_col_name) contains an impact value.
impact_col_name (str) – The name of the column containing the impact data (default = ‘Impact’)

Returns

coverage (pandas DataFrame) – DataFrame with columns ‘Sensor’ and ‘Coverage’ to be used as input to a coverage-based sensor placement solver.

chama.optimize module¶

The optimize module contains high-level solvers for sensor placement optimization.

Contents

`ImpactFormulation`()	Sensor placement based on minimizing average impact across a set of scenarios.
`CoverageFormulation`()	Sensor placement based on maximizing coverage of a set of entities.

class chama.optimize.ImpactFormulation[source]¶

Bases: object

Sensor placement based on minimizing average impact across a set of scenarios.

solve(impact=None, sensor=None, scenario=None, sensor_budget=None, use_sensor_cost=False, use_scenario_probability=False, impact_col_name='Impact', mip_solver_name='glpk', pyomo_options=None, solver_options=None)[source]¶

Solves the sensor placement optimization by minimizing impact.

Parameters

impact (pandas DataFrame) – Impact assessment. Impact is stored as a pandas DataFrame with columns Scenario, Sensor, and Impact. Each row contains a single detection time (or other measure of impact/damage) for a sensor that detects a scenario. The column name for Impact can also be specified by the user using the argument ‘impact_col_name’.
sensor (pandas DataFrame) – Sensor characteristics. Contains sensor cost for each sensor. Sensor characteristics are stored as a pandas DataFrame with columns Sensor and Cost. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
scenario (pandas DataFrame) – Scenario characteristics. Contains scenario probability and the impact for undetected scenarios. Scenario characteristics are stored as a pandas DataFrame with columns Scenario, Undetected Impact, and Probability. Undetected Impact is required for each scenario. Probability is used if the ‘use_scenario_probability’ flag is set to True.
sensor_budget (float) – The total budget available for purchase/installation of sensors. Solution will select a family of sensors whose combined cost is below the sensor_budget. For a simple sensor budget of N sensors, set this to N and the ‘use_sensor_cost’ to False.
use_sensor_cost (bool) – Boolean indicating if sensor cost should be used in the optimization. If False, sensors have equal cost of 1.
use_scenario_probability (bool) – Boolean indicating if scenario probability should be used in the optimization. If False, scenarios have equal probability.
impact_col_name (str) – The name of the column containing the impact data to be used in the objective function.
mip_solver_name (str) – Optimization solver name passed to Pyomo. The solver must be supported by Pyomo and support solution of mixed-integer programming problems.
pyomo_options (dict) – Keyword arguments to be passed to the Pyomo solver .solve method Defaults to an empty dictionary.
solver_options (dict) – Solver specific options to pass through Pyomo to the underlying solver. Defaults to an empty dictionary.

Returns

A dictionary with the following keys –

Sensors: A list of the selected sensors
Objective: The mean impact based on the selected sensors
FractionDetected: The fraction of scenarios that were detected
TotalSensorCost: Total cost of the selected sensors
Assessment: The impact value for each sensor-scenario pair. The assessment is stored as a pandas DataFrame with columns Scenario, Sensor, and Impact (same format as the input Impact assessment). If the selected sensors did not detect a particular scenario, the impact is set to the Undetected Impact.

create_pyomo_model(impact=None, sensor=None, scenario=None, sensor_budget=None, use_sensor_cost=False, use_scenario_probability=False, impact_col_name='Impact')[source]¶

Returns the Pyomo model.

See ImpactFormulation.solve() for more information on parameters.

Returns: Pyomo ConcreteModel ready to be solved

add_grouping_constraint(sensor_list, select=None, min_select=None, max_select=None)[source]¶

Adds a sensor grouping constraint to the sensor placement model. This constraint forces a certain number of sensors to be selected from a particular subset of all the possible sensors.

The keyword argument ‘select’ enforces an equality constraint, while ‘min_select’ and ‘max_select’ correspond to lower and upper bounds on the grouping constraints, respectively. You can specify one or both of ‘min_select’ and ‘max_select’ OR use ‘select’

Parameters

sensor_list (list of strings) – List containing the string names of a subset of the sensors
select (positive integer or None) – The exact number of sensors from the sensor_list that should be selected
min_select (positive integer or None) – The minimum number of sensors from the sensor_list that should be selected
max_select (positive integer or None) – The maximum number of sensors from the sensor_list that should be selected

solve_pyomo_model(sensor_budget=None, mip_solver_name='glpk', pyomo_options=None, solver_options=None)[source]¶

Solves the Pyomo model created to perform the sensor placement.

See ImpactFormulation.solve() for more information on parameters.

create_solution_summary()[source]¶

Creates a dictionary representing common summary information about the solution from a Pyomo model object that has already been solved.

See ImpactFormulation.solve() for more information on the solution summary.

Returns: Dictionary containing a summary of results.

class chama.optimize.CoverageFormulation[source]¶

Bases: object

Sensor placement based on maximizing coverage of a set of entities. An ‘entity’ can represent geographic areas, scenarios, or scenario-time pairs.

solve(coverage, sensor=None, entity=None, sensor_budget=None, use_sensor_cost=None, use_entity_weight=False, redundancy=0, coverage_col_name='Coverage', mip_solver_name='glpk', pyomo_options=None, solver_options=None)[source]¶

Solves the sensor placement optimization by maximizing coverage.

Parameters

coverage (pandas DataFrame) – Coverage data. Coverage is stored as a pandas DataFrame with columns Sensor and Coverage. Each row contains a list of entities that are covered by single sensor. The column name for Coverage can also be specified by the user using the argument ‘coverage_col_name’.
sensor (pandas DataFrame) – Sensor characteristics. Contains sensor cost for each sensor. Sensor characteristics are stored as a pandas DataFrame with columns Sensor and Cost. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
entity (pandas DataFrame) – Entity characteristics. Contains entity weights. Entity characteristics are stored as a pandas DataFrame with columns Entity and Weight. Weight is used if the ‘use_entity_weight’ flag is set to True.
sensor_budget (float) – The total budget available for purchase/installation of sensors. Solution will select a family of sensors whose combined cost is below the sensor_budget. For a simple sensor budget of N sensors, set this to N and the ‘use_sensor_cost’ to False.
use_sensor_cost (bool) – Boolean indicating if sensor cost should be used in the optimization. If False, sensors have equal cost of 1.
use_entity_weight (bool) – Boolean indicating if entity weights should be used in the optimization. If False, entities have equal weight.
redundancy (int) – Redundancy level. A value of 0 means only one sensor is required to covered an entity, whereas a value of 1 means two sensors must cover an entity before it considered covered.
coverage_col_name (str) – The name of the column containing the coverage data to be used in the objective function.
mip_solver_name (str) – Optimization solver name passed to Pyomo. The solver must be supported by Pyomo and support solution of mixed-integer programming problems.
pyomo_options (dict) – Keyword arguments to be passed to the Pyomo solver .solve method. Defaults to an empty dictionary.
solver_options (dict) – Solver specific options to pass through Pyomo to the underlying solver. Defaults to an empty dictionary.

Returns

A dictionary with the following keys –

Sensors: A list of the selected sensors
Objective: The mean coverage based on the selected sensors
FractionDetected: the fraction of entities that are detected
TotalSensorCost: Total cost of the selected sensors
EntityAssessment: a dictionary whose keys are the entity names, and values are a list of sensors that detect that entity
SensorAssessment: a dictionary whose keys are the sensor names, and values are the list of entities that are detected by that sensor

create_pyomo_model(coverage, sensor=None, entity=None, sensor_budget=None, use_sensor_cost=False, use_entity_weight=False, redundancy=0, coverage_col_name='Coverage')[source]¶

Returns the Pyomo model.

See CoverageFormulation.solve() for more information on parameters.

Returns: Pyomo ConcreteModel ready to be solved

add_grouping_constraint(sensor_list, select=None, min_select=None, max_select=None)[source]¶

Adds a sensor grouping constraint to the sensor placement model. This constraint forces a certain number of sensors to be selected from a particular subset of all the possible sensors.

The keyword argument ‘select’ enforces an equality constraint, while ‘min_select’ and ‘max_select’ correspond to lower and upper bounds on the grouping constraints, respectively. You can specify one or both of ‘min_select’ and ‘max_select’ OR use ‘select’

Parameters

sensor_list (list of strings) – List containing the string names of a subset of the sensors
select (positive integer or None) – The exact number of sensors from the sensor_list that should be selected
min_select (positive integer or None) – The minimum number of sensors from the sensor_list that should be selected
max_select (positive integer or None) – The maximum number of sensors from the sensor_list that should be selected

solve_pyomo_model(sensor_budget=None, mip_solver_name='glpk', pyomo_options=None, solver_options=None)[source]¶

Solves the Pyomo model created to perform the sensor placement.

See CoverageFormulation.solve() for more information on parameters.

create_solution_summary()[source]¶

Creates a dictionary representing common summary information about the solution from a Pyomo model object that has already been solved.

See CoverageFormulation.solve() for more information on the solution summary.

Returns: Dictionary containing a summary of results.

chama.graphics module¶

The graphics module contains graphic functions.

Contents

`signal_convexhull`(signal, scenarios, threshold)	Plots of the signal's 3D convex hull.
`signal_xsection`(signal, signal_name[, ...])	Plots x-y, x-z, and y-z cross sections.
`animate_puffs`(puff[, x_range, y_range])	Plots the horizontal movement of puffs from a GaussianPuff simulation over time.
`sensor_locations`(sensors[, x_range, ...])	Plots sensor locations.

chama.graphics.signal_convexhull(signal, scenarios, threshold, timesteps=None, colormap=<matplotlib.colors.ListedColormap object>, x_range=(None, None), y_range=(None, None), z_range=(None, None))[source]¶

Plots of the signal’s 3D convex hull.

Parameters

signal (pandas DataFrame) – Signal data from the simulation. The DataFrame contains columns ‘X’, ‘Y’, ‘Z’, ‘T’, and one column for each scenario.
scenarios (list) – Column names for the scenarios to be plotted
threshold (float) – The minimum value of the signal to be included
timesteps (list (optional)) – List of the time steps to include in the plot
colormap (matplotlib.pyplot ColorMap (optional)) – A ColorMap object sent to the contourf function
x_range (tuple (optional)) – The x-axis limits for the plot
y_range (tuple (optional)) – The y-axis limits for the plot
z_range (tuple (optional)) – The z-axis limits for the plot

chama.graphics.signal_xsection(signal, signal_name, threshold=None, timesteps=None, x_value=None, y_value=None, z_value=None, log_flag=False, colormap=<matplotlib.colors.ListedColormap object>, alpha=0.7, N=5, x_range=(None, None), y_range=(None, None), z_range=(None, None))[source]¶

Plots x-y, x-z, and y-z cross sections. The signal is summed over all desired time steps and summed across the axis not included in the plot unless a value for the third access is specified.

Parameters

signal (pandas DataFrame) – Signal data from the simulation. The DataFrame contains columns ‘X’, ‘Y’, ‘Z’, ‘T’, and one column for each scenario.
signal_name (string) – Column name for the signal to be plotted
threshold (float (optional)) – The minimum value of the signal to be plotted
timesteps (list (optional)) – List of the time steps to include in the plot
x_value (list (optional)) – List of the x locations to include in the plot
y_value (list (optional)) – List of the y locations to include in the plot
z_value (list (optional)) – List of the z locations to include in the plot
log_flag (boolean (optional)) – Flag specifying whether the signal should be plotted on a log scale
colormap (matplotlib.pyplot ColorMap (optional)) – A ColorMap object sent to the contourf function
alpha (float (optional)) – Value between 0 and 1 representing the alpha blending value passed to the contourf function
N (int (optional)) – The number of levels to include in the plot, passed to the contourf function
x_range (tuple (optional)) – The x-axis limits for the plot
y_range (tuple (optional)) – The y-axis limits for the plot
z_range (tuple (optional)) – The z-axis limits for the plot

chama.graphics.animate_puffs(puff, x_range=(None, None), y_range=(None, None))[source]¶

Plots the horizontal movement of puffs from a GaussianPuff simulation over time. Each puff is represented as a circle centered at the puff center location with radius equal to the standard deviation in the horizontal direction (sigmaY).

Parameters

puff (pandas DataFrame) – The puff DataFrame created by a GaussianPuff object
x_range (tuple (xmin, xmax) (optional)) – The x-axis limits for the plot
y_range (tuple (ymin, ymax) (optional)) – The y-axis limits for the plot

chama.graphics.sensor_locations(sensors, x_range=(None, None), y_range=(None, None), z_range=(None, None), legend=False, colors=None, markers=None)[source]¶

Plots sensor locations.

Parameters

sensors (dict) – A dictionary of sensors with key:value pairs containing {‘sensor name’: chama Sensor object}
x_range (tuple (optional)) – The x-axis limits for the plot
y_range (tuple (optional)) – The y-axis limits for the plot
z_range (tuple (optional)) – The z-axis limits for the plot
legend (Boolean (optional)) – Indicates if legend should be added to the plot
colors (dict (optional)) – A dictionary containing the color string to be used when plotting each sensor. The key:value pairs are {‘sensor name’ : String representing the color to be passed to the plot function)
markers (dict (optional)) – A dictionary containing the marker to be used when plotting each sensor. The key:value pairs are {‘sensor name’ : String representing the marker to be passed to the plot function)

chama.utils module¶

The utils module contains a collection of utility functions.

References¶

Arya99: Arya, S.P. (1999). Air pollution meteorology and dispersion (Vol. 6). New York: Oxford University Press.
CPLEX: CPLEX. Home page. http://www.cplex.com, 2017
BHPU06: Berry, J., Hart, W. E., Phillips, C. E., Uber, J. G., & Watson, J.-P. (2006). Sensor placement in municipal water networks with temporal integer programming models. J. Water Resources Planning and Management, 132(4), 218-224.
GUROBI: GUROBI. Gurobi Optimization, Inc. http://www.gurobi.com, 2017
HLWW12: Hart, W.E., Laird, C, Watson, J.P., & Woodruff D.L. (2012). Pyomo – Optimization Modeling in Python, Volume 67 of Springer Optimization and Its Applications, Springer Science & Business Media.
Hunt07: Hunter, J.D. (2007). Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 3(9), 90-95.
KHMB17: Klise, K.A., Hart, D.B., Moriarty, D., Bynum, M., Murray, R., Burkhardt, J., Haxton, T. (2017). Water Network Tool for Resilience (WNTR) User Manual, U.S. Environmental Protection Agency Technical Report, EPA/600/R-17/264, 47p.
LBSW12: Legg, S.W., Benavides-Serrano, A.J., Siirola, J.D., Watson, J.P., Davis, S.G., Bratteteig, A., & Laird, C.D. (2012) A Stochastic Programming Approach for Gas Detector Placement Using CFD-Based Dispersion Simulations, Computers & Chemical Engineering, Volume 47, Pages 194-201.
Makh10: Makhorin, A. (2010). GNU Linear Programming Kit Reference Manual for GLPK Version 4.45, Department for Applied Informatics, Moscow Aviation Institute, Moscow, Russia.
McHa88: McDonald, M.G., & Harbaugh, A.W. (1988). A Modular Three-dimensional Finite-Difference Groundwater Flow Model: U.S. Geological Survey Techniques of Water-Resources Investigations, Book 6, Chap. A1, 586p.
Mcki13: McKinney W. (2013). Python for Data Analysis: Data Wrangling with Pandas, NumPy, and IPython. O’Reilly Media, 1 edition, 466P.
RaWB16: Ravikumar, A.P., Wang, J., Brandt, A.R. (2016). Are Optical Gas Imaging Technologies Effective For Methane Leak Detection? Environmental science and technology 51 (1), 718-724.
Ross00: Rossman, L.A. (2000). EPANET 2 Users Manual. U. S. Environmental Protection Agency Technical Report, EPA/600/R–00/057, 200p.
ScSY00: Scire, J., Strimaitis, D.G., & Yamartino, R.J. (2000). A User’s Guide for the CALPUFF Dispersion Model (Version 5), Earth Tech, Inc.
USEPA04: United States Environmental Protection Agency. (2004). User’s Guide for the AMS/EPA Regulatory Model - AERMOD, U. S. Environmental Protection Agency Technical Report, EPA-454/B-03-001.
USEPA12: United States Environmental Protection Agency. (2012). TEVA-SPOT Toolkit User Manual, U. S. Environmental Protection Agency Technical Report, EPA/600/R-08/041B.
USEPA15: United States Environmental Protection Agency. (2015). Water Security Toolkit User Manual, U. S. Environmental Protection Agency Technical Report, EPA/600/R-14/338, 187p.
VaCV11: van der Walt, S., Colbert, S.C., & Varoquaux, G. (2011). The NumPy array: A structure for efficient numerical computation. Computing in Science & Engineering, 13, 22-30.

Citing Chama¶

To cite Chama, use the following reference:

Klise, K.A., Nicholson, B., and Laird, C.D. (2017). Sensor Placement Optimization using Chama, Sandia Report SAND2017-11472, Sandia National Laboratories.

Indices and tables¶

Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525.