本报告由智东⻄西（公众号：zhidxcom）收集整理理，仅做⾏行行业交流学习之⽤用。
如有侵权，请在公众号告诉我们。
欲获取全部报告，微信扫描右侧⼆二维码，关注智东⻄西，回复“智东⻄西内参”，
获取下载指南。更更多报告每周更更新中...... 扫描⼆二维码获取报告
智东⻄2017年最新整理的行业报告资源包括：人工智能（140+篇）、无人机
（20+篇）、 VR/AR（20+篇）、智能出行（10+篇）、智能硬件（10+篇）、
物联网智能家居（60+篇）。
A Realistic Dataset for the Smart Home Device
Scheduling Problem for DCOPs
William Kluegel1, Muhammad Aamir Iqbal1, Ferdinando Fioretto2,
William Yeoh1, and Enrico Pontelli1
1 Department of Computer Science, New Mexico State University
2 Department of Industrial and Operations Engineering, University of Michigan
{wkluegel,miqbal,wyeoh,epontell}@,
{fioretto}@
Abstract. The field of Distributed Constraint Optimization has gained momen-
tum in recent years thanks to its ability to address various applications related to
multi-agent cooperation. While techniques to solve Distributed Constraint Opti-
mization Problems (DCOPs) are abundant and have matured substantially since
the field inception, the number of DCOP realistic applications and benchmark
used to asses the performance of DCOP algorithms is lagging behind. To contrast
this background we (i) introduce the Smart Home Device Scheduling (SHDS)
problem, which describe the problem of coordinating smart devices schedules
across multiple homes as a multi-agent system, (ii) detail the physical models
adopted to simulate smart sensors, smart actuators, and homes environments, and
(iii) introduce a DCOP realistic benchmark for SHDS problems.
1 Introduction
Distributed Constraint Optimization Problems (DCOPs) [11,15,18] have emerged as
one of the prominent agent models to govern the agents’ autonomous behavior, where
both algorithms and communication models are driven by the structure of the specific
problem. Since the research field inception a wide variety of algorithms have been pro-
posed to solve DCOPs and typically classified as being either complete or incomplete,
based on whether they can guarantee the optimal solution or they trade optimality for
shorter execution times. In addition, each of these classes can be categorized into sev-
eral groups, depending on the degree of locality exploited by the algorithms (., par-
tial centralization) [9,10,16], the way local information is updated (., synchronous
[10,14,15] or asynchronous [5,8,11]), and the type of exploration process adopted (.,
search-based [9,11,19], inference-based [15,5], or sampling-based [13,12,6]).
While techniques to solve DCOPs are abundant and have matured substantially
since the field inception, the number of DCOP realistic applications and benchmarks
used to assess the performance of DCOP algorithms is lagging behind. Typical DCOP
algorithms are evaluated on artificial random problems, or simplified problems that are
adapted to the often unrealistic assumptions made by DCOP algorithms (., that each
agent controls exactly one variable, and that all problem constraints are binary). To as-
sess the performance of DCOP algorithms it is necessary to introduce realistic problem
benchmark of deployable applications.
Motivated by these issues, we recently introduced the Smart Home Device Schedul-
ing (SHDS) problem [7], which formalizes the problem of coordinating smart devices
ar
X
iv
:1
70
2.
06
97
0v
1
[c
I]
22
Fe
b 2
01
7
(., smart thermostats, circulator heating, washing machines) schedules across mul-
tiple smart homes as a multi-agent system (MAS). The SHDS problem is suitable to
be modeled as a DCOP due to the presence of both complex individual agents’ goals,
describing homes’ energy price consumption, as well as a collective agents’ goal, cap-
turing the energy peaks reduction.
In this document we introduce a set of realistic synthetic benchmarks for the SHDS
problem for DCOPs. We report the details of the physical models adopted to simulate
smart home sensors and actuators, as well as home environments, and describe how
the actuator’s actions affects the environments of a home (., home’s temperature,
cleanliness, humidity). The datasets, models, and code adopted to generate the SHDS
datasets are available at:
DCOP A Distributed Constraint Optimization Problem (DCOP) [11,18] is described
by a tuple 〈X ,D,F ,A, α〉, where: X = {x1, . . . , xn} is a set of variables; D =
{D1, . . . , Dn} is a set of finite domains (., xi∈Di);F={f1, . . . , fe} is a set of utility
functions (also called constraints), where fi : "xj∈xfi Di → R+ ∪ {−∞} and xfi⊆X
is the set of the variables (also called the scope) relevant to fi;A={a1, . . . , ap} is a set
of agents; and α : X → A is a function that maps each variable to one agent. fi speci-
fies the utility of each combination of values assigned to the variables in xfi . A partial
assignment σ is a value assignment to a set of variables Xσ⊆X that is consistent with
the variables’ domains. The utilityF(σ)=∑f∈F,xf⊆Xσ f(σ) is the sum of the utilities
of all the applicable utility functions in σ. A solution is a partial assignment σ for all
the variables of the problem, ., with Xσ=X . We will denote with x a solution, while
xi is the value of xi in x. The goal is to find an optimal solution x∗ = argmaxx F(x).
2 Scheduling Device in Smart Homes
A Smart Home Device Scheduling (SHDS) problem is defined by the tuple
〈H,Z,L,PH ,PZ , H, θ〉, where:H = {h1, h2, . . .} is a neighborhood of smart homes,
capable of communicating with one another; Z = ∪hi∈HZi is a set of smart devices,
where Zi is the set of devices in the smart home hi (., vacuum cleaning robot, smart
thermostat). L = ∪hi∈HLi is a set of locations, where Li is the set of locations in
the smart home hi (., living room, kitchen); PH is the set of state properties of the
smart homes (., cleanliness, temperature); PZ is the set of devices state properties
(., battery charge for a vacuum robot); H is the planning horizon of the problem.
We denote with T = {1, . . . ,H} the set of time points; θ : T → R+ represents the
real-time pricing schema adopted by the energy utility company, which expresses the
cost per kWh of energy consumed by consumers. Finally, we use Ωp to denote the set
of all possible states for state property p ∈ PH ∪ PZ (., all the different levels
of cleanliness for the cleanliness property). Figure 1(right) shows an illustration of a
neighborhood of smart homes with each home controlling a set of smart devices.
Smart Devices
For each home hi ∈ H, the set of smart devices Zi is partitioned into a set of actuators
Ai and a set of sensors Si. Actuators can affect the states of the home (., heaters and
FIG. 1: Illustration of a Neighborhood of Smart Homes
ovens can affect the temperature in the home) and possibly their own states (., vac-
uum cleaning robots drain their battery power when running). On the other hand, sen-
sors monitor the states of the home. Each device z ∈ Zi of a home hi is defined by a
tuple 〈`z, Az, γHz , γZz 〉, where `z ∈ Li denotes the relevant location in the home that it
can act or sense, Az is the set of actions that it can perform, γHz : Az → 2PH maps the
actions of the device to the relevant state properties of the home, and γZz : Az → 2PZ
maps the actions of the device to its relevant state properties. We will use the following
running example throughout this paper.
Example 1. Consider a vacuum cleaning robot zv with location `zv = living room. The
set of possible actions is Azv = {run, charge, stop} and the mappings are:
γHzv: run→{cleanliness}; charge→∅; stop→∅
γZzv: run→{battery charge}; charge→{battery charge}; stop→∅
where ∅ represents a null state property.
Device Schedules
To control the energy profile of a smart home we need to describe the behavior of the
smart devices acting in the smart home during time. We formalize this concept with the
notion of device schedules.
We use ξtz ∈ Az to denote the action of device z at time step t, and ξtX = {ξtz | z ∈
X} to denote the set of actions of the devices in X ⊆ Z at time step t.
Definition 1 (Schedule).A schedule ξ[ta→tb]X = 〈ξtaX , . . . , ξtbX〉 is a sequence of actions
for the devices in X ⊆ Z within the time interval from ta to tb.
Consider the illustration of Figure 1(left). The top row of Figure 1(left) shows a
possible schedule 〈R,R,C,C,R,R,C,R〉 for a vacuum cleaning robot starting at time
1400 hrs, where each time step is 30 minutes. The robot’s actions at each time step are
shown in the colored boxes with letters in them: red with ‘S’ for stop, green with ‘R’
for run, and blue with ‘C’ for charge.
At a high-level, the goal of the SHDS problem is to find a schedule for each of the
devices in every smart home that achieve some user-defined objectives (., the home
is at a particular temperature within a time window, the home is at a certain cleanliness
level by some deadline) that may be personalized for each home. We refer to these
objectives as scheduling rules.
Scheduling Rules
We define two types of scheduling rules: Active scheduling rules (ASRs) that define
user-defined objectives on a desired state of the home (., the living room is cleaned
by 1800 hrs), and Passive scheduling rules (PSRs) that define implicit constraints on
devices that must hold at all times (., the battery charge on a vacuum cleaning robot
is always between 0% and 100%). We provide a formal description for the grammar of
scheduling rules in Section .
Example 2. The scheduling rule (1) describes an ASR defining a goal state where the
living room floor is at least 75% clean (., at least 75% of the floor is cleaned by a
vacuum cleaning robot) by 1800 hrs:
living room cleanliness ≥ 75 before 1800 (1)
zv battery charge ≥ 0 always (2)
zv battery charge ≤ 100 always (3)
and scheduling rules (2) and (3) describe PSRs stating that the battery charge of the
vacuum robot zv needs to be between 0 and 100 % of its full charge at all the times:
We denote with R[ta→tb]p a scheduling rule over a state property p∈PH∪PZ , and
time interval [ta, tb]. Each scheduling rule indicates a goal state at a location or on a
device `Rp ∈Li∪Zi of a particular state property p that must hold over the time interval
[ta, tb] ⊆ T. The scheduling rule goal state is either a desired state of a home, if it is
an ASR (., the cleanliness level of the room floor) or a required state of a device or a
home, if it is a PSR (., the battery charge of the vacuum cleaning robot).
Each rule is associated with a set of actuators Φp ⊆ Ai that can be used to reach
the goal state. For instance, in our Example (2), Φp correspond to the vacuum cleaning
robot zv , which can operate on the living room floor. Additionally, a rule is associated
with a sensor sp ∈ Si capable of sensing the state property p. Finally, in a PSRs the
device can also sense its own internal states.
The ASR of Equation (1) is illustrated in Figure 1(left) by dotted red lines on the
graph. The PSRs are not shown as they must hold for all time steps.
Feasibility of Schedules
To ensure that a goal state can be achieved across the desired time window the system
uses a predictive model of the various state properties. This predictive model captures
the evolution of a state property over time and how such state property is affected by
a given joint action of the relevant actuators. We describe the details of the physical
predictive models used to generate our benchmark set in Section .
Definition 2 (Predictive Model). A predictive model Γp for a state property p (of either
the home or a device) is a function Γp : Ωp × "z∈Φp Az ∪ {⊥} → Ωp ∪ {⊥}, where ⊥
denotes an infeasible state and ⊥+ (·) = ⊥.
In other words, the model describes the transition of state property p from state
ωp ∈ Ωp at time step t to time step t + 1 when it is affected by a set of actuators Φp
running joint actions ξtΦp :
Γ t+1p (ωp, ξ
t
Φp) = ωp +∆p(ωp, ξ
t
Φp) (4)
where ∆p(ωp, ξtΦp) is a function describing the effect of the actuators’ joint action ξ
t
Φp
on state property p. We assume here, . that the state of properties are numeric—
when this is not the case, a mapping to the possible states to a numeric representation
can be easily defined.
Notice that a recursive invocation of a predictive model allows us to predict the
trajectory of a state property p for future time steps, given a schedule of actions of the
relevant actuators Φp. Let us formally define this concept.
Definition 3 (Predicted State Trajectory). Given a state property p, its current state
ωp at time step ta, and a schedule ξ
[ta→tb]
Φp
of relevant actuators Φp, the predicted state
trajectory pip(ωp, ξ
[ta→tb]
Φp
) of that state property is defined as:
pip(ωp, ξ
[ta→tb]
Φp
) = Γ tbp (Γ
tb−1
p (. . . (Γ
ta
p (ωp, ξ
ta
Φp
), . . .), ξ
tb−1
Φp
), ξtbΦp) (5)
Consider the device scheduling example in Figure 1(left). The predicted state tra-
jectories of the battery charge and cleanliness state properties are shown in the second
and third rows of Figure 1(left). These trajectories are predicted given that the vacuum
cleaning robot will take on the schedule shown in the first row of the figure. The pre-
dicted trajectories of these state properties are also illustrated in the graph, where the
dark grey line shows the states for the robot’s battery charge and the black line shows
the states for the cleanliness of the room.
Notice that to verify if a schedule satisfies a scheduling rule it is sufficient to check
that the predicted state trajectories are within the set of feasible state trajectories of that
rule. Additionally, notice that each active and passive scheduling rule defines a set of
feasible state trajectories. For example, the active scheduling rule of Equation (1) allows
all possible state trajectories as long as the state at time step 1800 is no smaller than 75.
We use Rp[t] ⊆ Ωp to denote the set of states that are feasible according to rule Rp of
state property p at time step t. More formally, a schedule ξ[ta→tb]Φp satisfies a scheduling
rule R[ta→tb]p (written as ξ
[ta→tb]
Φp
|= R[ta→tb]p ) iff:
∀t ∈ [ta, tb] : pip(ωtap , ξ[ta→t]Φp ) ∈ Rp[t] (6)
where ωtap is the state of state property p at time step ta.
Definition 4 (Feasible Schedule). A schedule is feasible if it satisfies all the passive
and active scheduling rules of each home in the SHDS problem.
In the example of Figure 1, the evaluated schedule is a feasible schedule since the
trajectories of both the battery charge and cleanliness states satisfy both the active
scheduling rule (1) and the passive scheduling rules (2) and (3).
Optimization Objective
In addition to finding feasible schedules, the goal in the SHDS problem is to optimize
for the aggregated total cost of energy consumed.
Each action a ∈ Az of device z ∈ Zi in home hi ∈ H has an associated energy
consumption ρz : Az → R+, expressed in kWh. The aggregated energy Eti (ξ[0→H]Zi )
across all devices consumed by hi at time step t under trajectory ξ
[0→H]
Zi
is:
Eti (ξ
[0→H]
Zi
) =
∑
z∈Zi
ρz(ξ
t
z) (7)
where ξtz is the action of device z at time t in the schedule ξ
[0→H]
Zi
. The cost ci(ξ
[0→H]
Zi
)
associated to schedule ξ[0→H]Zi in home hi is:
ci(ξ
[0→H]
Zi
) =
∑
t∈T
(
`ti + E
t
i (ξ
[0→H]
Zi
)) · θ(t) (8)
where `ti is the home background load produced at time t, which includes all non-
schedulable devices (., TV, refrigerator), and sensor devices, which are always active,
and θ(t) is the real-time price of energy per kWh at time t.
The objective of an SHDS problem is that of minimizing the following weighted
bi-objective function:
min
ξ
[0→H]
Zi
αc ·Csum + αe ·Epeak (9)
subject to: ∀hi ∈ H, R[ta→tb]p ∈ Ri : ξ[ta→tb]Φp |= R[ta→tb]p (10)
where αc, αe ∈R are weights, Csum =
∑
hi∈H ci(ξ
[0→H]
Zi
) is the aggregated monetary
cost across all homes hi; and Epeak =
∑
t∈T
∑
Hj∈H
∑
hi∈Hj
(
Eti (ξ
[0→H]
Zi
)
)2
is a
quadratic penalty function on the aggregated energy consumption across all homes hi.
Since the SHDS problem is designed for distributed multi-agent systems, in a coopera-
tive approach optimizing Epeak may require each home to share its energy profile with
each other home. To take into account data privacy concerns and possible high network
loads, we decompose the set of homes H into neighboring subsets of homes H, so
that Epeak can be optimized independently within each subset. These coalitions can be
exploited by a distributed algorithm to (1) parallelize computations between multiple
groups and (2) avoid data exposure over long distances or sensitive areas. Finally, con-
straint (10) defines the valid trajectories for each scheduling rule r ∈ Ri, where Ri is
the set of all scheduling rules of home hi.
DCOP Mapping
One can map the SHDS problem to a DCOP as follows:
• AGENTS: Each agent ai ∈ A in the DCOP is mapped to a home hi ∈ H.
• VARIABLES and DOMAINS: Each agent ai controls the following set of variables:
FIG. 2: Floor plans for a small (left), medium (center), and large (right) house.
• For each actuator z ∈ Ai and each time step t ∈ T, a variable xti,z whose domain
is the set of actions in Az . The sensors in Si are considered to be always active,
and thus not directly controlled by the agent.
• An auxiliary interface variable xˆtj whose domain is the set
{0, . . . ,∑z∈Zi ρ(argmaxa∈Az ρz(a))}, which represents the aggregated en-
ergy consumed by all the devices in the home at each time step t.
• CONSTRAINTS: There are three types of constraints:
• Local soft constraints (., constraints that involve only variables controlled by the
agent) whose costs correspond to the weighted summation of monetary costs, as
defined in Equation (8).
• Local hard constraints that enforce Constraint (10). Feasible schedules incur a cost
of 0 while infeasible schedules incur a cost of∞.
• Global soft constraints (., constraints that involve variables controlled by differ-
ent agents) whose costs correspond to the peak energy consumption, as defined in
the second term in Equation (9).
3 Model Parameters and Realistic Data Set Generation
This section describes the parameters and models adopted in our SHDS datasets gener-
ation. We first describe the house structural parameters, which are used in turn to cal-
culate the house predictive models. Next, we report a detailed list of the smart devices
adopted in our datasets, discussing their power consumptions and effects on the house
environments. We then describe the predictive models adopted to capture changes in the
house’s environments and devices’ states. Finally, we report the BNF for the scheduling
rules introduced in Section , and the pricing scheme adopted in our experiments.
House Structural Parameters
We consider three house sizes (small, medium, and large). The floor plans for three
house structures are shown in Figure 2. Our house structural model simplifies the floor
plans shown in Figure 2 by ignoring internal walls. This abstraction is sufficient to cap-
ture the richness of the predictive models introduced in Section . Table 1 reports the
parameters of the houses adopted in our SHDS dataset. The house sizes are expressed
in meters (L ×W ). The walls height is assumed to be and the window area de-
notes the area of the walls covered by windows. The overall heat transfer coefficient
Structural Parameters small medium large Structural Parameters small medium large
house size (m) 6× 8 8× 12 12× 15 Uroof (W/m2C)
walls area (m2) 96 lights energy density (W/m3)
window area (m2) 10 16 background load (kW)
Uwalls (W/m
2C) background heat gain (W) 50 50 50
Uwindows (W/m
2C) people heat gain (Btu/h) 400 400 400
TABLE 1: House structural parameters.
ID State property Location ID State property Location
01 air temperature house room 08 dish cleanliness appliance
02 floor cleanliness (dust) house room 09 air humidity house room
03 temperature appliance 10 luminosity house room
04 battery charge appliance 11 occupancy house room
05 bake appliance 12 movement house room
06 laundry wash appliance 13 smoke detector house room
07 laundry dry appliance
TABLE 2: List of sensors.
(also referred to as U-value) describes how well a building element conducts heat. It is
defined as the rate of heat transfer (in watts) through one unit area (m2) of a structure
divided by the difference in temperature across the structure [17].
The walls material is considered to be a 150mm poured concrete (1280 kg/m3)
with a Heat-Transfer Coefficient (Uwalls) of Wm2· ◦ C . We consider vertical double
glazed windows, with distance between glasses 30− 60mm whose Heat-Transfer Co-
efficient (Uwindows) is Wm2· ◦ C . Additionally, we consider a cm wood roof with
cm insulation, with Heat-Transfer Coefficient (Uroof) of Wm2· ◦ C . Finally, we
consider a cm wood door, with Heat-Transfer Coefficient of Wm2· ◦ C . These are
commonly adopted materials in the US house construction industry [17]. We assume a
background load consumption which account of a medium-size refrigerator (120W ), a
wireless router (6W ), and a set of light bulbs (collectively 40W ) [17]. The heat gain
from the background house appliances is computed according to [17](Table ). We
consider the heat gain from people within the house, and computed as in [17](Table
), assuming a metabolic rate as light office work.
Smart Devices
In this section we report the complete list of smart devices (sensors and actuators)
adopted by the smart homes in our SHDS datasets.
Sensors Table 2 reports the sensors adopted in our SHDS problem. For each sensor, we
report an identifier (ID), the state property (see Section ) it senses, and its location
in the house. All sensors are considered to be constantly active, sensing a single state
property at a location (., an air temperature sensor is located in a house room, a
charge sensor is located on a device).
Actuators Table 3 reports the list of the actuators. It tabulates the type of actuator and
its model, its possible actions, the power consumption (in kWh), the state properties
affected by each of its action, and the effects (∆) on the associated predictive models
in the small, medium, and large house sizes. The latter represent the incremental quan-
tity which affects the physical system, given the action of the actuator, as defined in
Equation 4. We detail the calculation of the house and devices physical models below.
Actuator Model Actions Consumption (kWh) State properties (ID) Effects Small(∆) Effects Medium(∆) Effects Large(∆)
Heater Bryant 697CN030B
off 0 {01} − L˙h
·TA −
L˙h
·TA −
L˙h
·TA
fan {01} − L˙h
·TA −
L˙h
·TA −
L˙h
·TA
heat {01} L˙h
·|TZ−TA|
L˙h
·|TZ−TA|
L˙h
·|TZ−TA|
Cooler LG LW1212ER
off 0 {01} L˙h
·TA
L˙h
·TA
L˙h
·TA
fan {01} L˙h
·TA
L˙h
·TA
L˙h
·TA
cool {01} L˙h
·|TA−TZ |
L˙h
·|TA−TZ |
L˙h
·|TA−TZ |
Waterheater E52-50R-045DV
off 0 {03} {0} {0} {0}
on {03} {◦C} {◦C} {◦C}
Vacuum Bot iRobot Roomba 880
off 0 {02, 04} {%, %} {%, %} {%, %}
vacuum 0 {02, 04} {%, −%} {%, −%} {%, −%}
charge {04} {%} {%} {%}
Electric Vehicle Tesla Model S
off 0 {04} {0} {0} {0}
charge {04} {%} {%} {%}
Clothes Washer GE WSM2420D3WW
off 0 {06} {0} {0} {0}
wash (Regular) {06} {1} {1} {1}
spin (Regular) {06} {1} {1} {1}
rinse (Regular) {06} {1} {1} {1}
wash (Perm-Press) {06} {1} {1} {1}
spin (Perm-Press) {06} {1} {1} {1}
rinse (Perm-Press) {06} {1} {1} {1}
wash (Delicates) {06} {1} {1} {1}
spin (Delicates) {06} {1} {1} {1}
rinse (Delicates) {06} {1} {1} {1}
Clothes Dryer GE WSM2420D3WW
off 0 {07} {0} {0} {0}
on (Regular) {07} {1} {1} {1}
on (Perm-Press) {07} {1} {1} {1}
on (Timed) {07} {1} {1} {1}
Oven Kenmore
off 0 {05} {0} {0} {0}
bake {05, 01} {1, ◦C} {1, ◦C} {1, ◦C}
broil {05, 01} {, ◦C} {, ◦C} {, ◦C}
Dishwasher Kenmore
off 0 {08} {0} {0} {0}
wash {08} {1} {1} {1}
rinse {08} {1} {1} {1}
dry {08} {1} {1} {1}
TABLE 3: List of actuators.
Physical models
In this section we describe the physical models used to compute the effects values ∆
of the actuators’ actions on a predictive model (see Table 3). These values, in turn, are
adopted within the SHDS predictive models as described in Equation (4).
Battery (Dis)charge Model The battery charge/discharge model we adopt for our
battery-powered devices is as follows. For a given battery bwith capacityQb (expressed
in KWh), voltage Vb, and electric charge Eb = VbQb (expressed in ampere-hour (Ah)),
and assuming a 100% charging/discharging efficiency, the battery charge time b+α and
discharge time b−α are computed respectively as:
b+α =
Eb
C+
; b−α =
Eb
C−
, (11)
expressed in hours, where C+ and C− are, respectively, the charging amperage and the
in-use amperage. Following and
NmO0fY we report the battery parameters for our Electric Vehicle and robotic vacuum
cleaner in Table 4. The devices’ action effects ∆ for charging and discharging time are
computed by dividing the total charging and discharging times by |T|.
Air Temperature Model The air temperature predictive model is computed following
standard principle of heating and ventilation [17] and described as follows. Let G be
the ventilation conductance: G = V˙ ·ρa · h¯,where V˙ is the volume flow rate, set to 100,
ρa is the density of the air, set to , and h¯ is the specific heat of the air, set to
following [17]. The house heat loss coefficient hloss is:
hloss = Uwalls ·Awalls + Uroof ·Aroof + Uwindows ·Awindows +G (12)
Tesla Model S iRobot Roomba 880
Slow Charge Regular Charge Super Charger
Vb 240 240 240 120
Eb 354 Ah 354 Ah 354 Ah 3 Ah
C+ 48 A 72 A 500 A A
C− 60 A 60 A 60 A A
b+α 7 hr 22 min 5 hr 43 min 2 hr 24 min
b−α 6 hr 6 hr 6 hr 4 hr
TABLE 4: Electric vehicles [3] and robotic vacuum cleaner[1] batteries physical model.
where Uwalls, Uroof, and Uwindows are respectively, the heat transfer coefficients for the
walls, roof, and windows of the house, and Awalls, Aroof, and Awindows are respectively
the the areas for walls, roof, and windows. Their values are provided in Table 1. Let TA
and TZ be the current and a target temperatures; the heating load L˙h is given by:
L˙h = hloss|TZ − TA| (13)
The heating load defines the quantity of heat per unit time (in BTU) that must be sup-
plied in a building to reach the target temperature TZ , from the given temperature TA.
Given the heating load L˙h and the heater capacity C of a heater/cooler, the time the
device needs to run to reach the desired temperature is given by: LhC .
Heating or cooling load is also effected by the outdoor and indoor temperature differ-
ence. Consider the example where TA = 12◦C and TZ = 22◦C, and the outdoor tem-
perature changes from TA to TN = 8◦C. We can calculate the new load due to change
in temperature by the following relationship given below:
L˙n = L˙h · |TZ − TN ||TZ − TA| (14)
The above expression shows that an outdoor temperature drops of 4◦C, causes the heat-
ing load to increase by a factor of (. the previous heating load TA). In our model
we need to compute the change in temperature per time step (∆). This can be done using
the heat loss relationship:
∆ =
hloss
m · cp (15)
wherem is the mass of the air and cp is the specific heat of air. In our model,m depends
on volume flow rate of an air in the house, and cp = 1KJ/Kg ·K.
Water Temperature Model The rise in the water temperature per unit of time (∆
value) is dependent on the difference in the water temperature flowing into the water
heater and the amount of water flowing out of the water heater, as well as water us-
age We considered a gas-fired demand water heater(tankless). The water usage depends
on household size and multiple user activities To calculate the water temperature, in
our model, we used the highest potential peak water usage following [2,4], and corre-
sponding to liters/min (small house), liters/min (medium house), and
liters/min (large house). The rise in temperature is 39◦C for liters/minute of wa-
ter usage [2]. Thus the rise in temperature for our small, medium, and large house, are,
respectively, ◦C, ◦C, and ◦C.
time start 0:00 8:00 12:00 14:00 18:00 22:00
time end 7:59 11:59 13:59 17:59 21:59 23:59
price ($)
TABLE 5: Pacific Gas & Electric Co. pricing schema
Cleanliness Model Our floor cleanliness model is computed by using the equation:
T = where, A represents the area of the room (in m
2) and T is the amount
of time (in minutes) it takes the robotic vacuum cleaner to vacuum the entire room.
Consumer reports found that it took 57 minutes for the Roomba to clean a m2
room [1] (which is approximately In our experiment’s datasets we use
three different areas. Asmall = 48, Amedium = 96, and Alarge = 180. Thus the the
estimated times to cover a 100% floor for the small, medium, and large houses are,
repsectively: T = , , and minutes. The corresponding ∆ value of
Table 3 (which is a percentage) is computed as: ∆ = 100%T
All other predictive models (., laundry wash and dry, bake, dish cleanliness, etc.)
simply capture the time needed for a device to achieve the required goals by checking
that accumulated device effects achieves the desired property. This is discussed in the
dataset generation, in Section 4.
Scheduling Rules
We report, as follows, the complete Backus-Naur Form (BNF) for the scheduling rules
for a smart home hi ∈ H, introduced in Section
〈rules〉 ....= 〈simple rule〉 | 〈simple rule〉 ∧ 〈rules〉
〈simple rule〉 ....= 〈active rule〉 | 〈passive rule〉
〈active rule〉 ....= 〈location〉〈state property〉〈relation〉〈goal state〉〈time〉
〈passive rule〉 ....= 〈location〉〈state property〉〈relation〉〈goal state〉
〈location〉 ....= ` ∈ Li
〈state property〉 ....= s ∈ PH | s ∈ PZ
〈relation〉 ....= ≤ | < | = | 6= | > | ≥
〈goal state〉 ....= sensor state | actuator state
〈time〉 ....= at 〈T〉 | before 〈T〉 | after 〈T〉 | within [〈T〉, 〈T〉] | for 〈T〉 time units
〈T〉 ....= t ∈ T
In our dataset the device states are mapped to numeric values, ., Ωp = N, for all
p ∈ PH ∪PZ .
Pricing Schema
For the evaluation of our SHDS datasets we adopted a pricing schema used by the
Pacific Gas & Electric Co. for its customers in parts of California,3 which accounts for
7 tiers ranging from $ per kWh to $ per kWh, reported in Table 5
3
〈location〉 〈state property〉 〈relation〉 〈goal state〉 〈time〉
Room air temperature r ∈ {≤, <,=, >,≥} g1 ∈ [14, 28] 〈time〉
Room floor cleanliness r ∈ {=, >,≥} g2 ∈ [0, 100] 〈time〉
Electric Vehicle charge r ∈ {=, >,≥} g3 ∈ [0, 100] 〈time〉
Water heater temperature r ∈ {≤, <,=, >,≥} g4 ∈ [10, 45] 〈time〉
Clothes Washer laundry wash r ∈ {=} g5 ∈ {45, 60} 〈time〉
Clothes Drier laundry dry r ∈ {=} g6 ∈ {45, 60} 〈time〉
Oven bake r ∈ {=} g7 ∈ {30, 40, 60, 120} 〈time〉
Dishwasher dishes cleanliness r ∈ {=} g8 ∈ {45, 60} 〈time〉
TABLE 6: Scheduling (active) rules
〈location〉 〈state property〉 〈relation〉 〈goal state〉 〈location〉 〈state property〉 〈relation〉 〈goal state〉
Room air temperature ≥ 0 EV charge ≤ 100
Room air temperature ≤ 30 Water heater temperature ≥ 10
Room floor cleanliness ≥ 0 Water heater temperature ≤ 42
Ooom floor cleanliness ≤ 100 Oven bake ≤ g7
Roomba charge ≥ 0 Clothes Washer laundry wash ≤ g6
Roomba charge ≤ 100 Clothes Drier laundry dry ≤ g7
EV charge ≥ 0 Dishwasher dishes cleanliness ≤ g8
TABLE 7: Scheduling (active) rules
4 SHDS Dataset
We now introduce a dataset for the SHDS problem for DCOPs. We generate synthetic
microgrid instances sampling neighborhoods in three cities in the United States (Des
Moines, IA; Boston, MA; and San Francisco, CA) and estimate the density of houses in
each city. The average density (in houses per square kilometers) is 718 in Des Moines,
1357 in Boston, and 3766 in San Francisco. For each city, we created a 200m×200m
grid, where the distance between intersections is 20m, and randomly placed houses
in this grid until the density is the same as the sampled density. We then divided the
city into k (=|H|) coalitions, where each home can communicate with all homes in its
coalition. Finally, we ensure that there no two coalitions are disjoint. Tables 9, 10, and
11 report, respectively, the Des Moines, Boston, and San Francisco instances, where
we vary (i) the number of agents (n)—up to 1883 for the largest instances—, (ii) the
number of coalitions (k), and (iii) the number of actuators within each home m.
Each home device has an associated active scheduling rule that is randomly gener-
ated, and a number of passive rules that must always hold. The parameters to generate
active and passive rules are reported, respectively, in Table 6 and Table 7. The time
predicates for these rules are generated at random within the given horizon. Addition-
ally, the relations r and goals states gi are randomly generated sampling from the sets
corresponding, respectively, to the columns 〈relation〉 and 〈goal state〉 of Table 6.
We generate a total of 2351 problem instances (available at: https://github.
com/persoon/SHDS_dataset). We set H = 12, and report in Table 8 a summary
of the parameters’ settings for our smart homes physical models.
Additionally, we provide upper bounds (in the obj column) for each for the instances
(Tables 9, 10, and 11 report a subset of the SHDS dataset) by solving an uncoordinated
Physical model Parameter Value (small house) Value (medium house) Value (large house)
Air Temperature
V˙ 100 200 400
m
cp
ρa
h¯
h loss 544
TZ 22 22 22
TA 10 10 10
L˙n 6528 9177
Floor Cleanliness
A 48 m2 96 m2 180 m2
T min min min
∆ % % %
Water Temperature
household size 2 3 4
liters/min usage
∆ ◦C ◦C ◦C
TABLE 8: Physical models: Values and assumptions
DCOP, where each agent reports its best schedule found with a local Constraint Pro-
gramming solver4 as subroutine, within a 10 seconds timeout.
instance n k m sim. time (s) obj
avg price
($)
avg power
(kWh)
largest peak
(kW)
dm 7 1 3 7 1 3
dm 7 1 4 7 1 4
dm 7 1 5 7 1 5
dm 7 1 6 7 1 6
dm 7 4 6 7 4 6
dm 21 1 3 21 1 3
dm 21 1 4 21 1 4
dm 21 1 5 21 1 5
dm 21 1 6 21 1 6
dm 21 16 6 21 16 6
dm 35 1 3 35 1 3
dm 35 1 4 35 1 4
dm 35 1 5 35 1 5
dm 35 1 6 35 1 6
dm 35 32 6 35 32 6
dm 71 1 3 71 1 3
dm 71 1 4 71 1 4
dm 71 1 5 71 1 5
dm 71 1 6 71 1 6
dm 71 64 6 71 64 6
dm 251 1 3 251 1 3
dm 251 1 4 251 1 4
dm 251 1 5 251 1 5
dm 251 1 6 251 1 6
dm 251 128 6 251 128 6
TABLE 9: Des Moines
5 Conclusions
With the proliferation of smart devices, the automation of smart home scheduling can be
a powerful tool for demand-side management within the smart grid vision. In this paper
4 We adopt the JaCoP solver (
instance n k m sim. time (s) obj
avg price
($)
avg power
(kWh)
largest peak
(kW)
bo 13 1 3 13 1 3
bo 13 1 4 13 1 4
bo 13 1 5 13 1 5
bo 13 1 6 13 1 6
bo 13 8 6 13 8 6
bo 40 1 3 40 1 3
bo 40 1 4 40 1 4
bo 40 1 5 40 1 5
bo 40 1 6 40 1 6
bo 40 32 6 40 32 6
bo 67 1 3 67 1 3
bo 67 1 4 67 1 4
bo 67 1 5 67 1 5
bo 67 1 6 67 1 6
bo 67 64 6 67 64 6
bo 135 1 3 135 1 3
bo 135 1 4 135 1 4
bo 135 1 5 135 1 5
bo 135 1 6 135 1 6
bo 135 128 6 135 128 6
bo 474 1 3 474 1 3
bo 474 1 4 474 1 4
bo 474 1 5 474 1 5
bo 474 1 6 474 1 6
bo 474 256 6 474 256 6
TABLE 10: Boston
instance n k m sim. time (s) obj
avg price
($)
avg power
(kWh)
largest peak
(kW)
sf 37 1 3 37 1 3
sf 37 1 4 37 1 4
sf 37 1 5 37 1 5
sf 37 1 6 37 1 6
sf 37 32 6 37 32 6
sf 112 1 3 112 1 3
sf 112 1 4 112 1 4
sf 112 1 5 112 1 5
sf 112 1 6 112 1 6
sf 112 64 6 112 64 6
sf 188 1 3 188 1 3
sf 188 1 4 188 1 4
sf 188 1 5 188 1 5
sf 188 1 6 188 1 6
sf 188 128 6 188 128 6
sf 376 1 4 376 1 4
sf 376 1 5 376 1 5
sf 376 1 6 376 1 6
sf 376 256 6 376 256 6 28306328
TABLE 11: San Francisco
we proposed the Smart Home Device Scheduling (SHDS) problem, which formalizes the
device scheduling and coordination problem across multiple smart homes as a multi-
agent system, and its mapping to a DCOP. Furthermore, we described in great details the
physical models adopted to model the smart home’s sensors and actuators, as well as the
physical model regulating the effect of the devices actions on the house environments
properties (., temperature, cleanliness). Finally, we reported a realistic dataset for the
SHDS problem for DCOPs which includes 2351 instances of increasing difficulty.
References
1. Roomba 880 specs.
290102/specs/. [Online; accessed 18-February-2017].
2. Sizing a new water heater.
sizing-new-water-heater. [Online; accessed 18-February-2017].
3. Tesla model s specifics.
4. Typical water used in normal home activities.
DocumentCenter/View/285. [Online; accessed 18-February-2017].
5. A. Farinelli, A. Rogers, A. Petcu, and N. Jennings. Decentralised coordination of low-power
embedded devices using the Max-Sum algorithm. In AAMAS, pages 639–646, 2008.
6. F. Fioretto, W. Yeoh, and E. Pontelli. A dynamic programming-based MCMC framework for
solving DCOPs with GPUs. In Proceedings of the International Conference on Principles
and Practice of Constraint Programming (CP), pages 813–831, 2016.
7. F. Fioretto, W. Yeoh, and E. Pontelli. A multiagent system approach to scheduling devices
in smart homes. In AAMAS, page (to appear), 2017.
8. A. Gershman, A. Meisels, and R. Zivan. Asynchronous Forward-Bounding for distributed
COPs. JAIR, 34:61–88, 2009.
9. K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In CP, pages
222–236, 1997.
10. R. Mailler and V. Lesser. Solving distributed constraint optimization problems using coop-
erative mediation. In AAMAS, pages 438–445, 2004.
11. P. Modi, W.-M. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous distributed con-
straint optimization with quality guarantees. AIJ, 161(1–2):149–180, 2005.
12. D. T. Nguyen, W. Yeoh, and H. C. Lau. Distributed Gibbs: A memory-bounded sampling-
based DCOP algorithm. In AAMAS, pages 167–174, 2013.
13. B. Ottens, C. Dimitrakakis, and B. Faltings. DUCT: An upper confidence bound approach
to distributed constraint optimization problems. In AAAI, pages 528–534, 2012.
14. J. Pearce and M. Tambe. Quality guarantees on k-optimal solutions for distributed constraint
optimization problems. In IJCAI, pages 1446–1451, 2007.
15. A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In
IJCAI, pages 1413–1420, 2005.
16. A. Petcu, B. Faltings, and R. Mailler. PC-DPOP: A new partial centralization algorithm for
distributed optimization. In IJCAI, pages 167–172, 2007.
17. M. J. W and J. E. , Braun. Principles of Heating, Ventilation and Air Conditioning in
Buildingss. Wiley, 2012.
18. W. Yeoh and M. Yokoo. Distributed problem solving. AI Magazine, 33(3):53–65, 2012.
19. W. Zhang, G. Wang, Z. Xing, and L. Wittenberg. Distributed stochastic search and distributed
breakout: Properties, comparison and applications to constraint optimization problems in
sensor networks. AIJ, 161(1–2):55–87, 2005.
A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs -8pt
