# Towards the Real-World Deployment of a Smart Home EMS: A DP Implementation on the Raspberry Pi
## 4 Embedded Implementation of the Chosen EMS
### Dynamic Programming Algorithm
The pseudo-code of the _Planning_ algorithm is shown in Algorithm 2. The computed optimal path represents the sequence of actions that the system plans, i.e., the profile of power reference values for the battery. From this profile, the _Planning_ stage calculates the planned GEPP and finally transmits it to the utility. ```
1:functionbuildGraph(\(t_{0},genForecast,loadForecast,soc,currGen,currDemand\))
2:\(G(V,E)\leftarrow\{\}\)\(\triangleright\) Create empty graph
3:\(v_{0}\leftarrow\textit{createVertex}(soc,t_{0})\)\(\triangleright\) vertex for the initial SOC
4:addVertex(\(G,v_{0}\))
5:for\(t\gets t_{0}+1\), \(N+1\)do\(\triangleright\) repeats for N time steps starting from the second
6:for\(\textit{next\_soc\_val}\) in \(\textit{discrete\_soc\_values}\)do\(\triangleright\) repeats for all the discretized values of SOC
7:\(v\leftarrow\textit{createVertex}(next\_soc\_val,t)\)
8:addVertex(\(G,v\))
9:for\(\textit{prev\_v}\) in \(\textit{getTimeStepNodes}(t-1)\)do\(\triangleright\) repeats for all the vertices of \(t-1\)
10:\(\Delta_{soc}\leftarrow\textit{next\_soc\_val}-\textit{getSoc}(\textit{prev\_v})\)\(\triangleright\) calculates difference of SOC
11:\(pBatt\leftarrow\textit{batteryModel}(\Delta_{soc})\)\(\triangleright\) and corresponding power
12:if\(t==t_{0}+1\) & \(\textit{replanning}\)then
13:\(pGrid\gets pBatt+currDemand-currGen\)
14:else
15:\(pGrid\gets pBatt+loadForecast[t-1]-genForecast[t-1]\)
16:if\(\textit{checkConstraints}(pBatt,pGrid)\)then\(\triangleright\) if all constraints are satisfied
17:\(\triangleright\) calculates weight and adds edge
18:if\(planning\)then
19:\(w\leftarrow\textit{calcChalFlow}(pGrid)\)
20:else
21:\(w\gets abs(pGrid-plannedGepp[t-1])\)
22:\(addEdge((\textit{prev\_v},v),w)\)
23:return\(G(V,E),v_{0}\)
```  
**Algorithm 1** Pseudo-code of graph building function. It builds a graph such as the one in Figure 3.  
```
1:\(t_{0}\gets 0\)
2:\((genForecast,loadForecast)\gets getForecasts()\)
3:\(init\_soc\gets getInitSoc()\)\(\triangleright\) retrieves SOC measurement at \(t_{0}\)
4:\(G(\overline{V},E),v_{0}\leftarrow\)buildGraph(\(t_{0}\),\(genForecast,loadForecast,init\_soc,NULL,NULL\))
5:\((distances,predecessors)\leftarrow bellmanFordAlg(v_{0},G)\)\(\triangleright\) shortest paths from \(v_{0}\) to all other vertices
6:\(final\_states\gets getTimeStepNodes(N+1)\)\(\triangleright\) retrieves vertices of final time step
7:\(target\leftarrow\text{argmin}\,distances(x)\) for \(x\in final\_states\)
8:\(path\leftarrow\textit{getPath}(predecessors,target)\)\(\triangleright\) reconstructs path from \(V_{0}\) to \(target\)
9:\(pBattProfile\leftarrow\textit{calcPBattProfile}(path)\)\(\triangleright\) calculates power corresponding to SOC sequence
10:\(gepp\gets pBattProfile+loadForecast-genForecast\)
11:\(\textsc{sENDGepPToUtility}(gepp)\)\(\triangleright\) sends the GEPP to the data aggregator The same approach can be used to formulate the _Online Replanning_ stage as a DP problem. Algorithm 3 reports the pseudo-code of the algorithm. Each time the _Online Replanning_ task is executed, a new graph is built. However, the objective function in Equation (3) cannot be expressed as a sum of state transition costs. Thus, the problem cannot be formulated as a shortest path problem. Instead, the cost of each state transition, i.e., the weight of the edges of the graph, corresponds to the deviation of the planned GEPP from the GEPP that results from the state transition. Therefore, the cost of a path is the maximum weight of the edges composing it. The problem corresponds to the single source minmax path search problem. This is the dual of the single source bottleneck path problem [45], and it can be solved executing a modified version of [PERSON]'s algorithm [46]. After this execution, the target node and the best path are chosen as in the _Planning_ stage. From the obtained optimal path, at each execution of the _Online Replanning_ task, only the first edge is used to compute the power reference values to be sent to hardware devices.