Intelligent Electric Vehicle Charging Recommendation
Based on Multi-Agent Reinforcement Learning

We first present our MARL formulation for the EV Charging Recommendation task.

• •

  Agent $c^{i}$. In this paper, we regard each charging station $c^{i}\in C$ as an individual agent. Each agent will make timely recommendation decisions for a sequence of charging requests $Q$ that keep coming throughout a day with multiple long-term optimization goals.

• •

  Observation $o_{t}^{i}$. Given a charging request $q_{t}$, we define the observation $o_{t}^{i}$ of agent $c^{i}$ as a combination of the index of $c^{i}$, the real-world time $T_{t}$, the number of current available charging spots of $c^{i}$ (supply), the number of charging requests around $c^{i}$ in the near future (future demand), the charging power of $c^{i}$, the estimated time of arrival (ETA) from location $l_{t}$ to $c^{i}$, and the CP of $c^{i}$ at the next ETA. We further define $s_{t}=\{o_{t}^{1},o_{t}^{2},\dots,o_{t}^{N}\}$ as the state of all agents at step $t$.

• •

  Action $a_{t}^{i}$. Given an observation $o_{t}^{i}$, an intuitional design for the action of agent $c^{i}$ is a binary decision, i.e., recommending $q_{t}$ to itself for charging or not. However, because one $q_{t}$ can only choose one station for charging, multiple agents’ actions may be tied together and are difficult to coordinate. Inspired by the bidding mechanism (Zhao et al., 2018), we design each agent $c^{i}$ offers a scalar value to ”bid” for $q_{t}$ as its action $a_{t}^{i}$. By defining $u_{t}=\{a_{t}^{1},a_{t}^{2},\dots,a_{t}^{N}\}$ as the joint action, $q_{t}$ will be recommended to the agent with the highest ”bid” value, i.e., $rc_{t}=c^{i}$, where $i=\arg\max(u_{t})$.

• •

  Transition. For each agent $c^{i}$, its observation transition is defined as the transition from the current charging request $q_{t}$ to the next charging request $q_{t+j}$ after $q_{t}$ is finished. Let’s elaborate on this via an illustrative example as shown in Figure 2. Consider a charging request $q_{t}$ arises at $T_{t}$ (13:00). At this moment, each agent $c^{i}$ takes action $a_{t}^{i}$ based on its observation $o_{t}^{i}$ and jointly decide the recommended station $rc_{t}$. After the request finish time $T^{c}_{t}$ (13:18), the subsequent charging request $q_{t+j}$ will arise at $T_{t+j}$ (13:20). In this case, the observation transition of agent $c^{i}$ is defined as $(o_{t}^{i},a_{t}^{i},o_{t+j}^{i})$, where $o_{t}^{i}$ is the current observation, $o_{t+j}^{i}$ is the observation corresponding to $q_{t+j}$.

• •

  Reward. In our MARL formulation, we propose a lazy reward settlement scheme (i.e., return rewards when a charging request is finished), and integrate three goals into two natural reward functions. Specifically, if a charging request $q_{t}$ succeeds in charging, then the environment will return the negative of CWT and negative of CP as the part of reward $r^{cwt}(s_{t},u_{t})$ and reward $r^{cp}(s_{t},u_{t})$ respectively. For the case that the CWT of $q_{t}$ exceeds a threshold, the recommendation will be regarded as failure and environment will return much smaller rewards as penalty to stimulate agents reducing the CFR. Overall, we define two immediate rewards function for three goals as

  (1)

  $$r^{cwt}(s_{t},u_{t})=\left\{\begin{aligned} &-CWT,\quad charging~{}success\\ &\quad\,\,\epsilon_{cwt},\quad charging~{}failure\end{aligned}~{},\right.$$

  (2)

  $$r^{cp}(s_{t},u_{t})=\left\{\begin{aligned} &-CP,\quad charging~{}success\\ &\quad\epsilon_{cp},\quad charging~{}failure\end{aligned}~{},\right.$$

  where $\epsilon_{cwt}$ and $\epsilon_{cp}$ are penalty rewards. All agents in our model share the unified rewards, means agents make the recommendation decisions cooperatively. Since the observation transition from $o_{t}^{i}$ to $o_{t+j}^{i}$ may cross multiple lazy rewards (e.g., $T_{t-h}^{c}$ and $T_{t}^{c}$ as illustrated in Figure 2), we calculate the cumulative discounted reward by summing the rewards of all recommended charging requests $q_{t^{\prime}}$ (e.g., $q_{t-h}$ and $q_{t}$) whose $T_{t^{\prime}}^{c}$ is between $T_{t}$ and $T_{t+j}$, denoted by

  (3)

  $$R_{t:t+j}=\sum_{T_{t}<T_{t^{\prime}}^{c}\leq T_{t+j}}\gamma^{(T_{t^{\prime}}^{c}-T_{t}-1)}r(s_{t^{\prime}},u_{t^{\prime}}),$$

  where $\gamma$ is the discount factor, and $r(\cdot,\cdot)$ can be one of the two reward functions or the average of them depending on the learning objectives.

Centralized training decentralized execution is a class of methods in MARL to stimulate agents to learn coordinated policies and address the non-stationary environment problem (Lowe et al., 2017; Foerster et al., 2018; Iqbal and Sha, 2019). In Master, the CTDE consists of three modules, the centralized attentive critic, the delayed access information strategy to integrate future charging competition, and the decentralized execution process. The advantages of CTDE for EV charging recommendation are two folds. On one hand, the centralized training process can motivate multiple agents to learn cooperation and other specific policies by perceiving a more comprehensive landscape and exploiting future information in hindsight. On the other hand, the execution process is fully decentralized without requiring complete information in the training phase, which guarantees efficiency and flexibility in online recommendation.

The goal of Electric Vehicle Charging Recommendation task is to simultaneously minimize the overall CWT, average CP and the CFR. We integrate these goals into two objectives corresponding to two reward functions, i.e., $r^{cwt}$ and $r^{cp}$ as defined in Eq. (1) and Eq. (2). Figure 4 depicts the normalized reward distributions of $r^{cwt}$ and $r^{cp}$ by a random policy executing on a set of charging requests that charging success. As can be seen, the distribution of different objectives can be very different. More importantly, the optimal solution of different objectives may be divergent, e.g., a cheaper charging station may be very popular and need a longer CWT. The above facts imply one policy that performs well on one objective may get stuck on another objective. A recommender that is biased to a particular objective is risky to induce unsatisfactory experience to most users.

A simple way to optimize multiple objectives is to average the reward of multiple objectives with a set of prior weights and maximize the combined reward as a single objective. However, such a static approach is inefficient for convergence and may induce a biased solution to a particular objective. To this end, we develop a dynamic gradient re-weighting strategy to self-adjust the optimization direction to adapt different training stages and enforce the policy to perform well on multiple objectives. Specifically, we extend the centralized attentive critic to multi-critics, where each critic is corresponding to a particular objective. Particularly, in our task, we learn two centralized attentive critics, $Q_{\bm{b}}^{cwt}$ and $Q_{\bm{b}}^{cp}$, which correspond to the expected returns of reward $r^{cwt}$ and $r^{cp}$, respectively. Since the structure of two critics are identical, we only present $Q_{\bm{b}}^{cwt}$ for explanation, which is formulated as

where $E$ denotes the environment, and $R_{t:t+j}^{cwt}$ is the cumulative discounted reward (defined in Eq. (3)) with respect to $r^{cwt}$.

To quantify the convergence degree of different objectives, we further define two centralized attentive critics associated with two objective-specific optimal policies with respect to reward $r^{cwt}$ and $r^{cp}$, denoted as $Q_{\bm{b}_{cwt}^{{}^{*}}}^{cwt^{*}}$ and $Q_{\bm{b}_{cp}^{{}^{*}}}^{cp^{*}}$. The corresponding optimal policies of each $c^{i}$ are denoted as $\bm{b}_{cwt}^{{}^{*}i}$ and $\bm{b}_{cp}^{{}^{*}i}$, respectively. Above objective-specific optimal policies and critics can be obtained by pre-training Master on a single reward. Then, we quantify the gap ratio between multi-objective policy and objective-specific optimal policy by

The gap ratio $g_{t}^{cp}$ can be derived in the same way. Intuitively, a larger gap ratio indicates a poorly-optimized objective and should be reinforced with a larger update weight, while a small gap ratio indicates a well-optimized objective can be fine-tuned with a smaller step size. Thus, we derive dynamic update weights to adaptively adjust the step size of the two objectives, which is learned by the Boltzmann softmax function,

where $\sigma$ is the temperature controls the adjustment sensitivity.

With the above two critics and adaptive update weights, the goal of each agent $c^{i}\in C_{t}^{a}$ is to learn an actor policy to maximize the following return,

The complete learning procedure of Master is detailed in Algorithm 1. Note that for the consideration of scalability, we share the parameters of actor and critic networks by all agents.

Table 2 and Table 3 report the overall results of our methods and all the compared baselines on two datasets with respect to our four metrics. As can be seen, overall, Master achieves the most well-rounded performance among all the baselines. Specifically, Master reduces $(51.4\%,13.6\%,96.5\%)$ and $(38.9\%,16.2\%,91.0\%)$ for (MCWT, MCP, CFR) compared with the ground truth charging actions on Beijing and Shanghai, respectively. And through our recommendation algorithm, we totally help users saving $16,219$ and $12,497$ charging fees per day on Beijing and Shanghai. Besides, Master achieves $(21.1\%,4.5\%,42.9\%,59.1\%)$ and $(25.3\%,\\ 3.7\%,34.8\%,80.9\%)$ improvements for (MCWT, MCP, TSF, CFR) compared with two multi-agent baselines IDDPG and MADDPG on Beijing, and the improvements are $(15.8\%,4.2\%,28.6\%,42.3\%)$ and $(13.4\%,3.6\%,22.4\%,46.4\%)$ on Shanghai. All the above results demonstrate the effectiveness of Master. Look into Master-ATT and MADDPG, two MARL algorithms with centralized training decentralized execution. We can observe the Master-ATT with centralized attentive critic have all-sided improvements comparing with MADDPG, especially in the MCWT and CFR. This is because the critic in MADDPG integrates full state and joint action suffering from the large state and action space problem, while our centralized attentive critic can effectively avoid this problem in our task.

Looking further into the results, we observe centralized RL algorithms (i.e., CDQN and CPPO) consistently perform worse than multi-agent approaches (i.e., IDDPG, MADDPG, Master-ATT and Master), which validates our intuition that the centralized algorithms suffer from the high dimensional state and action space problem and hard to learn satisfying policies, while multi-agent approaches perform better because of their quantity-independent state action space in large-scale agents environment. We also observe that Greedy-P-10 has the best performance in MCP among all compared algorithms. This is no surprise, because it always recommends the least expensive charging stations without considering other goals, which causes that the Greedy-P-10 performs badly in MCWT and CFR. It is worth mentioning that Master unexpectedly exceeds Greedy-P-10 in TSF on Beijing for the reason that Master has a much lower CFR comparing with Greedy-P-10, more users are benefited from our recommendation.

In this section, we conduct ablation studies on Master to further verify the effectiveness of each component. We evaluate the performance of Master and it’s three variants for the four metrics on Beijing and Shanghai. Specifically, the three variants are (1) noATT removes centralized attentive critic, learning agents independently; (2) noCP removes the future potential charging competition information from centralized attentive critic; (3) noMC removes multi-critic architecture, learning policies by a single centralized attentive critic with the average combined reward. The ablation results are reported in Figure 6. As can be seen, removing centralized attentive critic (noATT) or charging competition information (noCP) have a greater impact on MCWT. This is because MCWT is highly related to the cooperation of agents and charging competition of EVs, whereas the removed modules exactly work on these two aspects. Removing multi-critic architecture (noMC) has a large performance degradation on MCP and TSF. This is because noMC suffers from the convergence problem and finally leads to performance variance on multiple objectives. All the above experimental results demonstrate the effectiveness of each component in Master.

In this section, we study the effect of the number of top-$k$ active agents for recommendations on Beijing. We vary $k$ from $20$ to the number of all the agents. The results are reported in Figure 7, where ”$*$” denotes all the agents are activated for recommendation decision. As can be seen, with relaxing the recommendation constraint $k$, the MCWT increases while the MCP and TSF decrease, further validating the divergence of the optimal solutions for different objectives. This is possible because a more relaxed candidate number will expose more alternative economic but distant charging stations for recommendations. Even so, we should notice that the performance under the most strict constraint (i.e., $k=20$) or without constraint (i.e., $k=*$) are varying in a small range, i.e., the (MCWT, MCP) are ($9.56,1.603$) and ($11.73,1.437$), respectively, are not extreme and still acceptable for the online recommendation. The above results demonstrate that our model are well-rounded with different candidate numbers. It also inspires us that we can explore to make diversified recommendations that are biased to different objectives to satisfy personalized preferences in the future.

In this section, we study the effect of our multi-objective optimization method by comparing the convergence of Master between the static and our adaptive strategy. Note the Master with static average updated weight is equivalent to Master-noMC (i.e., average two rewards as a single reward for training). More details can be found in proposition C.1 in the Appendix C. The gap ratios (Eq. (13)) and dynamic weights (Eq. (14)) are reported in Figure 8. As can be seen in Figure 8(a), at the beginning of training, the gap ratio of the CP critic is decreasing faster than the CWT one. This is because the distribution of CP reward is more concentrated  (as illustrated in Figure 4), it’s easier to accumulate rewards comparing with CWT when agents with poor policies. In such a case, the static method keeps invariant update weights and results in slow convergence for CWT. In contrast, as shown in Figure 8(b), the dynamic re-weighting method in Master assigns a higher weight to the CWT objective when it falls behind the optimization of CP, and adjust them to a synchronous convergence pace. As the training step increase, the convergence of CWT overtakes the CP. This is because the distribution of CWT reward is more even, having larger room for improvement. And the optimization of CWT drags the CP objective to a sub-optimal point since the divergences between two objectives. However, the static method is helpless for such asynchronous convergence, but Master with the dynamic gradient re-weighting strategy weakens such asynchronism, and finally adjust them to be synchronous (i.e., weight approaches 0.5) to learn well-rounded policies.

In this section, we visualize the correlation among the attention weights and some input features of two centralized attentive critics (i.e., $Q_{\bm{b}}^{cwt}$ and $Q_{\bm{b}}^{cp}$), to qualitatively analysis the effectiveness of Master. Two cases are depicted in Figure 9. We can observe these two critics pay more attention to the charging stations with high action values. This makes sense, since these charging stations are highly competitive bidding participants. The charging request will be recommended to the charging station with the highest action, then environment returns rewards depending on this recommended station. Furthermore, we observe the action is highly correlated with factors such as supply, future supply, future demand, ETA and CP. A charging station with low ETA, CP and sufficient available charging spots (supplies) always has a high action value. Conversely, the charging stations with few available charging spots but high future demands usually derive a low action value for avoiding future charging competitions. The above observations validate the effectiveness of our model to mediate the contradiction between the space-constrained charging capacity and spatiotemporally unbalanced charging demands.