基于逆強(qiáng)化學(xué)習(xí)的電動(dòng)汽車出行規(guī)劃方法研究*

李繁菀，張 瑩，華云鵬，李沐陽(yáng)，陳元暢

(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院，北京 102206)

隨著社會(huì)經(jīng)濟(jì)的發(fā)展和生活水平的提高，人們對(duì)汽車的需求量逐年大幅度上漲，環(huán)境問(wèn)題也隨之而來(lái)，汽車尾氣的排放對(duì)環(huán)境造成極其嚴(yán)重的影響。面對(duì)嚴(yán)峻的環(huán)境問(wèn)題，我國(guó)大力推動(dòng)碳達(dá)峰、碳中和各項(xiàng)工作，電動(dòng)汽車產(chǎn)業(yè)普及率不斷提升[1]。電動(dòng)汽車一方面滿足人們的短距離出行需求，另一方面它以電作為主要?jiǎng)恿υ?，相比以燃油為?qū)動(dòng)的汽車更加節(jié)能和環(huán)保。目前對(duì)于路徑規(guī)劃的研究主要針對(duì)燃油汽車，而對(duì)燃油汽車的路徑規(guī)劃無(wú)須考慮電量的因素，該場(chǎng)景不適用于電動(dòng)汽車。隨著電動(dòng)汽車的普及，由于電動(dòng)汽車的特殊屬性以及“里程焦慮”[2]，電動(dòng)汽車的出行規(guī)劃顯得尤為重要。若能有效引導(dǎo)電動(dòng)汽車用戶選擇可達(dá)目的地、能及時(shí)充電、行駛時(shí)間短、充電時(shí)間短的路線行走，出行效率就能有效提高。

本文提出了一種基于逆強(qiáng)化學(xué)習(xí)(Inverse Reinforcement Learning，IRL)的電動(dòng)汽車出行規(guī)劃(Electric Vehicle Travel Planning,EVTP)方法，將考慮充電行為的Dijkstra算法作為專家示例以保證專家策略的優(yōu)越性，在對(duì)電動(dòng)汽車進(jìn)行出行規(guī)劃時(shí)須同時(shí)考慮電量和路徑兩方面因素，從而得到一條滿足電量可達(dá)條件的最優(yōu)路徑。此外，本文還對(duì)充電策略進(jìn)行考慮，在充電時(shí)采用部分充電策略以提高充電效率，使充電時(shí)間盡可能短。逆強(qiáng)化學(xué)習(xí)算法旨在對(duì)尋找路徑的策略進(jìn)行學(xué)習(xí)，因此有別于傳統(tǒng)路徑規(guī)劃算法依賴于路網(wǎng)結(jié)構(gòu)的特性。

1 相關(guān)工作

電動(dòng)汽車出行規(guī)劃(EVTP)問(wèn)題可以拆分為電動(dòng)汽車路徑規(guī)劃問(wèn)題(Electric Vehicle Routing Problem,EVRP)以及充電策略問(wèn)題。電動(dòng)汽車的路徑規(guī)劃問(wèn)題會(huì)受到電動(dòng)汽車電池容量的限制，即電動(dòng)汽車的電量不能低于某個(gè)限定最小值。因此，EVRP也可以被建模為受約束的最短路徑規(guī)劃問(wèn)題，此類問(wèn)題與經(jīng)典的最短路徑問(wèn)題的不同之處在于解決方案必須滿足附加約束，這是典型的NP-hard問(wèn)題[3]。目前，求解受約束的最短路徑問(wèn)題大體上可分為兩類方法：精確方法和啟發(fā)式方法。

精確方法通過(guò)嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型或數(shù)據(jù)結(jié)構(gòu)規(guī)劃問(wèn)題，利用數(shù)學(xué)法則或數(shù)據(jù)結(jié)構(gòu)搜尋的方式求得問(wèn)題最優(yōu)解[4]。Lu等[5]提出了一種運(yùn)用整數(shù)線性規(guī)劃來(lái)求解電動(dòng)汽車最優(yōu)路線問(wèn)題的方法，該方法以最小化電動(dòng)汽車行駛時(shí)間為優(yōu)化目標(biāo)，然而線性規(guī)劃的方法計(jì)算復(fù)雜度較高，僅在小型實(shí)例中有很好的表現(xiàn)，一旦應(yīng)用在大型路網(wǎng)中往往需要很大的存儲(chǔ)空間而導(dǎo)致方法不可用，因而其效率取決于實(shí)際路網(wǎng)的規(guī)模且不可直接遷移到其他未經(jīng)預(yù)處理的路網(wǎng)中。

由于精確方法有較高的計(jì)算復(fù)雜度而不便應(yīng)用于實(shí)際情況，在此方面有一定改善的啟發(fā)式方法是EVRP中更為常用的一種求解方法。啟發(fā)式方法[4]的主要思想是以當(dāng)前解為基點(diǎn)，在當(dāng)前解的鄰域中尋找較優(yōu)解賦給當(dāng)前解，并繼續(xù)尋找，直到?jīng)]有更優(yōu)解為止。Lebeau等[6]對(duì)每條路徑計(jì)算合并一條新路徑的成本，對(duì)可行路徑按成本量排序，再以貪心方式進(jìn)行歸并得到路徑集。Felipe等[7]采用兩階段啟發(fā)法，在得到初始可行解的基礎(chǔ)上不斷對(duì)路徑進(jìn)行調(diào)整，以逐漸靠近最優(yōu)目標(biāo)，并在每一步更新目標(biāo)函數(shù)的值，反復(fù)迭代直到目標(biāo)函數(shù)的值收斂為止。類似地，Dijkstra算法和A*算法[8]在路徑規(guī)劃問(wèn)題中也被廣泛運(yùn)用，對(duì)其稍加修改也可以運(yùn)用到EVRP中。Cuch等[3]提出了一種基于A*算法計(jì)算電動(dòng)汽車最優(yōu)路線的方法，并將減少充電行為中的等待時(shí)間作為優(yōu)化的一部分。Kobayashi等[9]提出了一種基于Dijkstra算法的電動(dòng)汽車路線搜索方法，這種方法對(duì)于充電行為也有一定的考慮，但未對(duì)充電時(shí)間作出優(yōu)化。雖然啟發(fā)式方法能有效減少運(yùn)行時(shí)間，但是此類方法仍然不能獨(dú)立于實(shí)際路網(wǎng)，即其運(yùn)行效率仍與路網(wǎng)規(guī)模相關(guān)，且應(yīng)用在不同路網(wǎng)時(shí)需要重新進(jìn)行生成鄰接矩陣等數(shù)據(jù)預(yù)處理工作。而本文提出的基于逆強(qiáng)化學(xué)習(xí)的方法與具體路網(wǎng)結(jié)構(gòu)無(wú)關(guān)，即在某個(gè)路網(wǎng)中訓(xùn)練得到的模型也能在其他路網(wǎng)中有較優(yōu)的性能。

對(duì)于EVTP問(wèn)題，為得到一條最優(yōu)路徑，除了路徑最短之外，充電策略也是需要重點(diǎn)考慮的因素。Wang等[10]提出了一個(gè)基于電量驅(qū)動(dòng)的上下文感知路徑規(guī)劃框架，該算法通過(guò)電量的約束限制A*算法對(duì)路徑進(jìn)行搜索，并且對(duì)于需要充電而繞路的情況給出了最佳方案。然而，此類方法在到達(dá)充電站時(shí)仍假設(shè)電動(dòng)汽車會(huì)將電量充滿，這并不適用于實(shí)際情況。在現(xiàn)實(shí)生活中，電動(dòng)汽車通常只需要使其電量在接下來(lái)的路程中不會(huì)低于限定值即可，這樣既可以減少充電時(shí)間又能滿足可達(dá)性。此外，電動(dòng)汽車的充電函數(shù)并不是線性的，電動(dòng)汽車的充電效率會(huì)隨著電量的變化而變化[11]。因此，本文提出了一種更接近于真實(shí)情況的充電策略，即分段充電以及部分充電策略。

2 方法

2.1 問(wèn)題定義

對(duì)于EVTP問(wèn)題，電動(dòng)汽車車主通常希望得到一條行駛時(shí)間短、充電時(shí)間短、充電次數(shù)少的可達(dá)路徑。因此，目標(biāo)可形式化表達(dá)為

此外，在尋找路徑的過(guò)程中還應(yīng)滿足以下條件：(1)電動(dòng)汽車選擇的每一個(gè)節(jié)點(diǎn)都在路網(wǎng)的點(diǎn)集G中，選擇行走的每一條路徑都在邊集E中；(2)路網(wǎng)中的邊為無(wú)向圖，選擇邊(i,j)等價(jià)于選擇邊(j,i)，即xij=xji；(3)選擇的任意兩個(gè)連續(xù)的充電樁之間的電量消耗要小于限制條件，即到達(dá)充電樁時(shí)的電量大于限定的最小電量；(4)充電次數(shù)盡可能少。充電次數(shù)越多，充電樁總計(jì)服務(wù)時(shí)間越長(zhǎng)[12]，從而會(huì)降低電動(dòng)汽車的出行效率。

2.2 馬爾可夫決策過(guò)程

為將逆強(qiáng)化學(xué)習(xí)(IRL)算法應(yīng)用到EVTP問(wèn)題中，EVTP問(wèn)題可被建模為馬爾可夫決策過(guò)程[13,14]。在此場(chǎng)景中的馬爾可夫決策過(guò)程可由以下5元組表示。

(1)狀態(tài)集S。在EVTP問(wèn)題中，狀態(tài)集S中的每一個(gè)狀態(tài)s由當(dāng)前電動(dòng)汽車的電量(pow)、與終點(diǎn)的距離比例(distance_ratio)、行走的角度(degree)、繞路情況(loop)組成。通過(guò)pow可以判斷當(dāng)前狀態(tài)是否滿足可達(dá)性條件，即行走時(shí)電動(dòng)汽車的電量是否在限定值以上。另外，狀態(tài)值的其他組成部分也是電動(dòng)汽車選擇路徑過(guò)程中需要特別關(guān)注的因素，狀態(tài)值中不包含具體位置信息，使得訓(xùn)練得到的模型在新的路網(wǎng)中也能有較好的表現(xiàn)。

(2)動(dòng)作集A。由于電動(dòng)汽車的特性，動(dòng)作集A中的動(dòng)作a包含兩類：行走行為和充電行為。在本文的設(shè)定中，動(dòng)作集中共包含10個(gè)動(dòng)作，前8個(gè)動(dòng)作表示行走行為(假設(shè)所有的節(jié)點(diǎn)最多有4個(gè)鄰接節(jié)點(diǎn))，后2個(gè)動(dòng)作表示充電行為，集中離散化的動(dòng)作用one-hot編碼[15]表示。在行走行為中，電動(dòng)汽車的目標(biāo)是向更接近終點(diǎn)的方向行駛，且需要為之后可能出現(xiàn)的充電行為做準(zhǔn)備。因此，行走行為中的前4個(gè)動(dòng)作對(duì)某一位置的相鄰點(diǎn)按照(degree,distance_ratio)升序排列，即先按照degree升序排列，若degree相同再按照distance_ratio升序排列；行走行為中的后4個(gè)動(dòng)作對(duì)某一位置的相鄰充電站按照上述規(guī)則排序，以便之后選擇充電行為。若選擇動(dòng)作集中后2個(gè)動(dòng)作，即電動(dòng)汽車選擇充電行為，在充電行為中本文對(duì)于充電量進(jìn)行了區(qū)分，其中一個(gè)動(dòng)作表示電量充到80%，而另一個(gè)動(dòng)作表示電量充到100%，這種部分充電的策略有利于節(jié)省充電時(shí)間。

(3)獎(jiǎng)勵(lì)r。傳統(tǒng)強(qiáng)化學(xué)習(xí)算法中的即時(shí)獎(jiǎng)勵(lì)r往往是人為設(shè)定的，然而在復(fù)雜問(wèn)題中僅憑經(jīng)驗(yàn)通常無(wú)法設(shè)置最優(yōu)的獎(jiǎng)勵(lì)值。例如，本文的場(chǎng)景需要同時(shí)考慮行走行為以及充電行為，難以人為設(shè)置兼顧二者的最優(yōu)獎(jiǎng)勵(lì)。獎(jiǎng)勵(lì)是影響強(qiáng)化學(xué)習(xí)算法性能的重要因素，因此，本文采用基于逆強(qiáng)化學(xué)習(xí)的方法對(duì)獎(jiǎng)勵(lì)值進(jìn)行設(shè)定[16]，通過(guò)專家示例以及學(xué)習(xí)策略過(guò)程中得到的軌跡間的交互，求得最優(yōu)的獎(jiǎng)勵(lì)值。

(4)動(dòng)作價(jià)值Q。Q(s,a)表示選擇了動(dòng)作a之后直到到達(dá)終點(diǎn)的獎(jiǎng)勵(lì)總和的期望，即

本文用Dueling DQN算法[17]近似動(dòng)作價(jià)值Q，即將某一時(shí)刻的狀態(tài)st作為輸入，輸出對(duì)每個(gè)動(dòng)作a的價(jià)值預(yù)測(cè)。此時(shí)Q值被定義為Q(s,a;θ)，其中θ為神經(jīng)網(wǎng)絡(luò)中的參數(shù)。

(5)策略π。策略π(st)依據(jù)當(dāng)前狀態(tài)對(duì)動(dòng)作進(jìn)行選擇。在本文中使用ε-greedy以一定的概率進(jìn)行探索，即大概率選擇動(dòng)作價(jià)值最大的動(dòng)作，以極小的概率對(duì)動(dòng)作進(jìn)行隨機(jī)選擇來(lái)避免陷入局部最優(yōu)。ε-greedy的計(jì)算公式如下：

π(st)=

根據(jù)上述5元組，對(duì)算法整體流程表示如圖1所示。

圖1 算法整體流程圖

2.3 狀態(tài)特征選擇

狀態(tài)是馬爾可夫決策過(guò)程中的重要組成部分，狀態(tài)的選擇尤為重要。特征是狀態(tài)到真實(shí)值的映射，包含一些重要的屬性，且與獎(jiǎng)勵(lì)值有密切關(guān)系。在本文中將EVTP問(wèn)題的特征定義為5個(gè)方面。

(1)電量pow。pow表示電動(dòng)汽車是否迫切需要充電。此特征用當(dāng)前狀態(tài)下電動(dòng)汽車的剩余電量來(lái)定義，剩余電量越少越迫切需要充電。

fpow(st)=Soct。

(2)充電時(shí)間charge_time。充電時(shí)間是電動(dòng)汽車需要重點(diǎn)考慮的特征之一。充電時(shí)間過(guò)長(zhǎng)會(huì)導(dǎo)致旅程時(shí)間過(guò)長(zhǎng)，從而導(dǎo)致效率過(guò)低；充電時(shí)間過(guò)短可能會(huì)使電量不能滿足接下來(lái)旅程的需要，從而導(dǎo)致目的地不可達(dá)。電動(dòng)汽車的充電時(shí)間需要在滿足可達(dá)的條件下盡可能短。

fcharge_time(st)=

式中，C表示充電樁節(jié)點(diǎn)的集合；location(t)表示t步所在位置，location(t)∈C即t步時(shí)所在節(jié)點(diǎn)為充電樁節(jié)點(diǎn)；charge_index表示充電指示，由t步時(shí)選擇的動(dòng)作決定，charge_index(t)=1即表示在t步時(shí)需要充電；ct表示計(jì)算得到的在t步時(shí)的充電時(shí)間。

(3)角度degree。degree表示當(dāng)前狀態(tài)所在位置與終點(diǎn)的連線以及起點(diǎn)與終點(diǎn)的連線之間的夾角，夾角越小說(shuō)明電動(dòng)汽車行駛的方向與終點(diǎn)方向越接近。

fdegree(st)=|getdegree(origin,destination)-getdegree(location(t),destination)|，

fdegree(st)=min(fdegree(st),360-fdegree(st))，

式中，getdegree表示得到兩點(diǎn)之間方位角的函數(shù)；origin表示路徑的起點(diǎn)；destination表示路徑的終點(diǎn)。

(4)距離比例distance_ratio。distance_ratio表示當(dāng)前所在位置與終點(diǎn)的距離以及起點(diǎn)與終點(diǎn)的距離之間的比例關(guān)系，比例越小則越接近終點(diǎn)，所有距離均用haversine公式[18]進(jìn)行計(jì)算：

fdistance_ratio(st)=

式中，haversine (A,B)表示點(diǎn)A與點(diǎn)B之間的haversine距離。

(5)繞路loop。loop表示尋找某起點(diǎn)終點(diǎn)對(duì)的路徑過(guò)程中是否重復(fù)訪問(wèn)某一位置。

式中，runway_history表示電動(dòng)汽車走過(guò)的節(jié)點(diǎn)位置的集合，若當(dāng)前位置已經(jīng)在runway_history中，則說(shuō)明電動(dòng)汽車已經(jīng)訪問(wèn)過(guò)該節(jié)點(diǎn)，即出現(xiàn)了繞路。若出現(xiàn)繞路往往說(shuō)明某步的決策不是最優(yōu)，因此并不希望路徑中出現(xiàn)繞路的情況。繞路情況如圖2所示。

圖2 繞路情況

給定起點(diǎn)、終點(diǎn)對(duì)(A,H)，電動(dòng)汽車由E到達(dá)D后，在D點(diǎn)若根據(jù)角度選擇下一個(gè)點(diǎn)，極有可能選擇點(diǎn)E，此時(shí)便出現(xiàn)了繞路，虛線表示可能出現(xiàn)的繞路情況。

在上述特征中，電量對(duì)逆強(qiáng)化學(xué)習(xí)算法得到的獎(jiǎng)勵(lì)產(chǎn)生正向影響，充電時(shí)間、角度、距離比例、繞路均對(duì)獎(jiǎng)勵(lì)產(chǎn)生負(fù)向影響。

在對(duì)特征進(jìn)行選擇時(shí)，路徑因素以及充電因素都需要被考慮以適用于EVTP問(wèn)題，從而得到一條兼顧行駛和充電的最優(yōu)路徑。

2.4 Dueling DQN

除了對(duì)特征的選擇外，對(duì)動(dòng)作的選擇在逆強(qiáng)化學(xué)習(xí)中也十分重要。逆強(qiáng)化學(xué)習(xí)算法與傳統(tǒng)強(qiáng)化學(xué)習(xí)算法的區(qū)別僅在于獎(jiǎng)勵(lì)函數(shù)，雖然其算法流程與傳統(tǒng)強(qiáng)化學(xué)習(xí)相似，但是在得到獎(jiǎng)勵(lì)函數(shù)之后仍需要正向訓(xùn)練更新Q值來(lái)學(xué)習(xí)策略?？捎肣(s,a)近似累計(jì)獎(jiǎng)勵(lì)，即

Q(s,a)=E[rt+γ·rt+1+γ2·rt+2+…|st=s,at=a,μ]。

根據(jù)上述設(shè)定，需要求得最優(yōu)動(dòng)作值Q*，最優(yōu)動(dòng)作值函數(shù)基于貝爾曼方程[19]，表示如下：

Q*(s,a)=Es′[r+γ·maxa′Q*(s′,

a′)|s,a]。

式中，α和β分別為價(jià)值函數(shù)和優(yōu)勢(shì)函數(shù)的參數(shù)。

在普通DQN算法中，若想更新某個(gè)動(dòng)作的Q值會(huì)直接更新Q網(wǎng)絡(luò)，使得該動(dòng)作的Q值改變。然而在Dueling DQN算法中，由于所有動(dòng)作的優(yōu)勢(shì)函數(shù)A值的和為0，不便于對(duì)優(yōu)勢(shì)函數(shù)進(jìn)行更新，因此Q網(wǎng)絡(luò)將優(yōu)先對(duì)價(jià)值函數(shù)進(jìn)行更新，即相當(dāng)于對(duì)所有動(dòng)作的Q值均進(jìn)行更新，從而提升學(xué)習(xí)效果。Dueling DQN的網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。在得到所有動(dòng)作的Q值后，ε-greedy可被應(yīng)用于動(dòng)作的選擇中。

圖3 Dueling DQN的網(wǎng)絡(luò)結(jié)構(gòu)

2.5 逆強(qiáng)化學(xué)習(xí)

在馬爾可夫決策過(guò)程中，除狀態(tài)和動(dòng)作外，獎(jiǎng)勵(lì)也尤為重要。無(wú)論是傳統(tǒng)強(qiáng)化學(xué)習(xí)還是逆強(qiáng)化學(xué)習(xí)，最基本的假設(shè)都是最大化累積的獎(jiǎng)勵(lì)，因此獎(jiǎng)勵(lì)的設(shè)計(jì)非常關(guān)鍵。傳統(tǒng)強(qiáng)化學(xué)習(xí)的即時(shí)獎(jiǎng)勵(lì)通常憑借經(jīng)驗(yàn)人為設(shè)定，然而像電動(dòng)汽車出行規(guī)劃等復(fù)雜問(wèn)題，僅憑經(jīng)驗(yàn)設(shè)置獎(jiǎng)勵(lì)往往難以精準(zhǔn)量化，因此，逆強(qiáng)化學(xué)習(xí)算法應(yīng)運(yùn)而生。本文將逆強(qiáng)化學(xué)習(xí)方法應(yīng)用到電動(dòng)汽車出行規(guī)劃中以得到最優(yōu)的獎(jiǎng)勵(lì)函數(shù)。

逆強(qiáng)化學(xué)習(xí)的思想與模仿學(xué)習(xí)有一定的相似之處，均需要借助專家示例庫(kù)對(duì)問(wèn)題進(jìn)行優(yōu)化。行為克隆是最早的模仿學(xué)習(xí)形式，與行為克隆簡(jiǎn)單學(xué)習(xí)一個(gè)狀態(tài)到動(dòng)作的映射不同，逆強(qiáng)化學(xué)習(xí)算法中獎(jiǎng)勵(lì)函數(shù)的學(xué)習(xí)方法原理如下：假設(shè)專家策略本身是根據(jù)某種獎(jiǎng)勵(lì)學(xué)到的最優(yōu)策略，那么專家示例即可取得最優(yōu)獎(jiǎng)勵(lì)值。根據(jù)此假設(shè)，設(shè)置參數(shù)化的獎(jiǎng)勵(lì)函數(shù)，并且尋找參數(shù)使得專家示例的獎(jiǎng)勵(lì)優(yōu)于其他任意數(shù)據(jù)，這樣即可求解出獎(jiǎng)勵(lì)函數(shù)。然而，上述“其他任意數(shù)據(jù)”并不具備可操作性，因此常采用迭代過(guò)程：根據(jù)當(dāng)下學(xué)到的獎(jiǎng)勵(lì)函數(shù)學(xué)習(xí)策略并生成軌跡數(shù)據(jù)，該軌跡數(shù)據(jù)替代“其他任意數(shù)據(jù)”，對(duì)比專家示例和生成的軌跡數(shù)據(jù)，來(lái)學(xué)習(xí)下一輪獎(jiǎng)勵(lì)函數(shù)。逆強(qiáng)化學(xué)習(xí)的流程如圖4所示。

圖4 逆強(qiáng)化學(xué)習(xí)流程圖

獎(jiǎng)勵(lì)被定義為線性結(jié)構(gòu)，即特征向量的加權(quán)和，表示如下：

r(st)=θTf(st)，

式中，θ=[θ1,θ2,…,θK]為K維權(quán)值向量，K為特征向量維度；f(st)=[f1(st),f2(st),…,fK(st)]為根據(jù)狀態(tài)定義的與獎(jiǎng)勵(lì)相關(guān)的特征向量。因此，一條軌跡ζ的獎(jiǎng)勵(lì)可以表示為

R(ζ)=∑tr(st)=θTfζ=θT∑st∈ζf(st)，

給定Dijkstra算法得到的專家示例集D={ζ1,ζ2,ζ3,…,ζM}，其中M為專家示例軌跡的數(shù)目，問(wèn)題轉(zhuǎn)化為找到參數(shù)θ使得專家示例的獎(jiǎng)勵(lì)最優(yōu)。因此，目標(biāo)函數(shù)如下：

由上述獎(jiǎng)勵(lì)函數(shù)的表示方式，目標(biāo)函數(shù)轉(zhuǎn)化為

獎(jiǎng)勵(lì)函數(shù)參數(shù)θ的更新使用了梯度上升的方法，直到其收斂。為防止過(guò)擬合，本文引入了參數(shù)θ的L2正則化，目標(biāo)函數(shù)改寫為

式中，λ為正則化參數(shù)，且滿足λ>0。

因此，梯度公式變?yōu)閮绍壽E集間特征期望的差異加上正則化項(xiàng)的梯度：

參數(shù)θ的更新公式為

θ=θ+α?θJ(θ)，

式中，α表示學(xué)習(xí)率。

經(jīng)過(guò)上述過(guò)程的迭代，即可求得最優(yōu)參數(shù)θ，從而得到最優(yōu)的獎(jiǎng)勵(lì)函數(shù)。然而，上述算法如果被運(yùn)用，還需要得到專家示例庫(kù)，才可通過(guò)與專家策略進(jìn)行對(duì)比求得獎(jiǎng)勵(lì)函數(shù)的參數(shù)。

2.6 構(gòu)建IRL專家示例

在逆強(qiáng)化學(xué)習(xí)中，專家示例的選擇會(huì)直接影響策略的學(xué)習(xí)，因此，如何構(gòu)建專家示例十分關(guān)鍵。Dijkstra算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無(wú)向圖的單源最短路徑的問(wèn)題，在路徑規(guī)劃問(wèn)題中得到了廣泛的應(yīng)用[23,24]?？紤]到Dijkstra算法能生成最短路徑的特點(diǎn)，本文將Dijkstra算法生成的路徑設(shè)置為專家示例。然而，傳統(tǒng)的Dijkstra算法只考慮最短路徑的問(wèn)題，而無(wú)法同時(shí)考慮選擇充電點(diǎn)以及計(jì)算充電時(shí)間等充電相關(guān)動(dòng)作，因此需要在傳統(tǒng)Dijkstra算法上做出一定改進(jìn)。在本文中，給定起點(diǎn)、終點(diǎn)對(duì)，需要先利用傳統(tǒng)Dijkstra算法得到最短路徑，再考慮該條最短路徑有哪些點(diǎn)在充電樁節(jié)點(diǎn)的集合中，由這些點(diǎn)作為分割點(diǎn)得到子路徑Sub_path。對(duì)于每條子路徑Sub_pathi的耗電量情況進(jìn)行分析，充電指示charge_index取值如下：

charge_index=

式中，use_power(Sub_pathi)表示子路徑Sub_pathi的耗電量；Soci-1表示電動(dòng)汽車在最短路徑中第i-1個(gè)充電樁節(jié)點(diǎn)時(shí)的剩余電量；limitbatt表示電動(dòng)汽車的最低電量，本文設(shè)定limitbatt=0.1。charge_index=1時(shí)表示需要充電，即對(duì)于某一個(gè)路徑中的充電樁節(jié)點(diǎn)，若下一條子路徑耗電量大于剩余電量與最低電量之間的差值，則在該充電樁節(jié)點(diǎn)需要充電。

對(duì)于充電的目標(biāo)電量，本文采取部分充電的策略[25]：若下一條子路徑的耗電量小于等于0.7，則在此充電樁將電量充到0.8；若下一條子路徑的耗電量大于0.7，則此次充電需要將電量充到1。此外，為了更接近現(xiàn)實(shí)中的情況，本文也考慮了分段充電的策略，從電量0充到目標(biāo)電量x的充電時(shí)間charge_time如下：

charge_time=

式中，電動(dòng)汽車的電量達(dá)到0.8之前的充電效率高于其電量達(dá)到0.8之后的充電效率，這與現(xiàn)實(shí)中的設(shè)定相同。為簡(jiǎn)化運(yùn)算，本文將電量達(dá)到0.8之后所需的充電時(shí)間也用線性函數(shù)表示。關(guān)于電量的充電時(shí)間函數(shù)如圖5所示。

圖5 充電時(shí)間函數(shù)

因此，一條包含充電策略的最短路徑可被求得，并將此路徑作為專家示例。Dijkstra算法在較小的路網(wǎng)中有較好的性能，然而當(dāng)其運(yùn)用在大型路網(wǎng)中，該算法需要花費(fèi)很長(zhǎng)的時(shí)間得到鄰接矩陣，且它的運(yùn)行效率與路網(wǎng)規(guī)模成正比。而本文基于逆強(qiáng)化學(xué)習(xí)的方法是在專家示例中學(xué)習(xí)其行走與充電的策略，這種策略對(duì)于不同的路網(wǎng)或大型路網(wǎng)也同樣適用，而無(wú)需對(duì)模型重新進(jìn)行訓(xùn)練。

3 實(shí)驗(yàn)驗(yàn)證

3.1 數(shù)據(jù)集

選用兩個(gè)路網(wǎng)分別對(duì)模型進(jìn)行訓(xùn)練，兩個(gè)路網(wǎng)均是北京市路網(wǎng)中的一部分。路網(wǎng)Ⅰ包含76個(gè)節(jié)點(diǎn)以及105條邊，緯度為39.893°-39.898° N，經(jīng)度為116.390°-116.405° E。路網(wǎng)Ⅱ包含75 956個(gè)節(jié)點(diǎn)以及101 052條邊，緯度為39.4°-40.4° N，經(jīng)度為115.8°-117.0° E。路網(wǎng)的數(shù)據(jù)集由兩部分構(gòu)成：點(diǎn)集與邊集，其中點(diǎn)集中包含各點(diǎn)的經(jīng)緯度信息，邊集中包含每條路徑起點(diǎn)、終點(diǎn)的經(jīng)緯度以及起點(diǎn)、終點(diǎn)之間的距離，由點(diǎn)集與邊集構(gòu)成的路網(wǎng)如圖6所示。由于充電樁節(jié)點(diǎn)的數(shù)據(jù)集未公開，且關(guān)于充電樁的布局不是本文的研究重點(diǎn)，因此隨機(jī)選擇點(diǎn)集中的點(diǎn)作為充電樁，這對(duì)實(shí)驗(yàn)結(jié)果并不影響。

圖6 北京市部分路網(wǎng)

3.2 基準(zhǔn)方法

通過(guò)將所提出的方法與以下基準(zhǔn)方法進(jìn)行比較，開展性能驗(yàn)證。

(1)Dijkstra &完全充電策略(Dijkstra & Full charge)。Dijkstra算法在小型路網(wǎng)中能夠高效地得到最短路徑，但未考慮充電策略。如2.6節(jié)所示，此基準(zhǔn)方法對(duì)Dijkstra進(jìn)行改進(jìn)并采用完全充電策略，即每次在充電樁節(jié)點(diǎn)充電時(shí)都將電量充滿，以驗(yàn)證部分充電策略的有效性。

(2)RL & Dueling DQN。與本文相同，此方法結(jié)合Dueling DQN算法對(duì)Q值進(jìn)行近似。然而，強(qiáng)化學(xué)習(xí)中的獎(jiǎng)勵(lì)憑借人為經(jīng)驗(yàn)進(jìn)行設(shè)置，用此基準(zhǔn)方法可驗(yàn)證逆強(qiáng)化學(xué)習(xí)算法獲得的獎(jiǎng)勵(lì)函數(shù)的優(yōu)越性。

(3)RL & DQN。與方法(2)相同，此方法的獎(jiǎng)勵(lì)同樣人為給定,且與方法(2)設(shè)置相同的獎(jiǎng)勵(lì)，并通過(guò)經(jīng)典的DQN算法對(duì)Q值進(jìn)行近似，此方法用來(lái)驗(yàn)證Dueling DQN算法的有效性。

3.3 評(píng)價(jià)標(biāo)準(zhǔn)

本文從有效性和高效性兩方面對(duì)模型進(jìn)行評(píng)價(jià)。在有效性評(píng)估方面，對(duì)于電動(dòng)汽車的出行規(guī)劃，行駛時(shí)間(Tpath)以及充電時(shí)間(Tch)兩個(gè)基本評(píng)價(jià)指標(biāo)尤為重要，直接影響電動(dòng)汽車的出行效率。此外，充電頻率(Frqch)高會(huì)導(dǎo)致充電服務(wù)時(shí)間長(zhǎng)，因此充電頻率也是一個(gè)重要的評(píng)價(jià)指標(biāo)，本文用路徑中包含的充電次數(shù)對(duì)該指標(biāo)進(jìn)行衡量。除上述3個(gè)評(píng)價(jià)指標(biāo)外，由于用戶在行駛過(guò)程中希望盡可能避免繞路，因此繞路次數(shù)也值得關(guān)注，這一指標(biāo)用loop值衡量。因此本文對(duì)于有效性的評(píng)價(jià)指標(biāo)包括：行駛時(shí)間、充電時(shí)間、充電頻率、繞路次數(shù)。本文用Gap來(lái)量化所提出的方法與基準(zhǔn)方法之間的差異，前兩個(gè)指標(biāo)的Gap表示為

式中，ExistF表示基準(zhǔn)方法的性能，PropF表示本文提出的方法的性能；GapTpath和GapTch分別表示兩種方法之間行駛時(shí)間以及充電時(shí)間的差異。由于后面兩個(gè)指標(biāo)中PropF的值可能為0，因而直接用兩種方法的差值表示Gap，類似地可表示為

Gap(Frqch)=ExistF(Frqch)-PropF(Frqch)，

Gap(loop)=ExistF(loop)-PropF(loop)。

Gap的值越大，說(shuō)明本文提出的方法性能相對(duì)基準(zhǔn)方法越好。

對(duì)于高效性的評(píng)估，使用運(yùn)行模型所需的時(shí)間作為評(píng)價(jià)指標(biāo)在不同的模型之間進(jìn)行比較。模型運(yùn)行時(shí)間越短，說(shuō)明模型越高效。

3.4 實(shí)驗(yàn)結(jié)果

表1 路網(wǎng)Ⅰ及路網(wǎng)Ⅱ中本文方法與基準(zhǔn)方法的效果比較

通過(guò)Gap詳細(xì)對(duì)比不同方法生成的每條路徑，將起點(diǎn)、終點(diǎn)對(duì)相同的路徑歸為一組，路網(wǎng)Ⅰ中的結(jié)果對(duì)比如圖7所示，路網(wǎng)Ⅱ中的結(jié)果對(duì)比如圖8所示。本文模型在絕大多數(shù)路徑中表現(xiàn)最為優(yōu)秀。

圖7 路網(wǎng)Ⅰ中不同方法生成的路徑結(jié)果對(duì)比

圖8 路網(wǎng)Ⅱ中不同方法生成的路徑結(jié)果對(duì)比

為驗(yàn)證模型的高效性，對(duì)路網(wǎng)Ⅰ、Ⅱ模型的運(yùn)行時(shí)間進(jìn)行對(duì)比，如圖9所示。在高效性驗(yàn)證中，Dijkstra算法在較小的路網(wǎng)中運(yùn)行時(shí)間略微短于強(qiáng)化學(xué)習(xí)以及逆強(qiáng)化學(xué)習(xí)模型。然而Dijkstra算法的運(yùn)行時(shí)間與路網(wǎng)規(guī)模強(qiáng)相關(guān)，因此在大型路網(wǎng)中，Dijkstra算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)長(zhǎng)于強(qiáng)化學(xué)習(xí)模型與逆強(qiáng)化學(xué)習(xí)模型。這也證明了本文模型在大型路網(wǎng)中的高效性。

圖9 模型運(yùn)行時(shí)間對(duì)比

該模型的收斂性如圖10所示，在訓(xùn)練一定輪數(shù)后每一輪獲得的獎(jiǎng)勵(lì)值趨于穩(wěn)定且神經(jīng)網(wǎng)絡(luò)的參數(shù)也逐漸收斂。

圖10 模型收斂性

此外，訓(xùn)練出來(lái)的模型也能較好地直接應(yīng)用在其他路網(wǎng)上而無(wú)需重新訓(xùn)練，而Dijkstra算法不具備此特點(diǎn)。處理不同的路網(wǎng)時(shí)，Dijkstra算法需要重新進(jìn)行數(shù)據(jù)預(yù)處理而不能將原有模型直接應(yīng)用在新路網(wǎng)中，即不具備遷移性。本文在兩個(gè)未經(jīng)訓(xùn)練的新路網(wǎng)中運(yùn)行模型用以驗(yàn)證遷移性，在路網(wǎng)Ⅲ和路網(wǎng)Ⅳ中隨機(jī)設(shè)置起點(diǎn)、終點(diǎn)對(duì)運(yùn)行模型，觀察能否得到可達(dá)路徑，利用可達(dá)路徑的比例評(píng)估不同模型的遷移性。在兩個(gè)路網(wǎng)中各模型的可達(dá)路徑比例如表2所示，本文模型在兩個(gè)路網(wǎng)中均表現(xiàn)最佳。

表2 模型遷移性對(duì)比

4 結(jié)論

本文將考慮充電行為的Dijkstra算法生成的軌跡作為專家示例，使用Dueling DQN算法對(duì)Q值近似，提出了一種基于逆強(qiáng)化學(xué)習(xí)的電動(dòng)汽車出行規(guī)劃方法。該方法能夠有效引導(dǎo)電動(dòng)汽車用戶選擇一條可達(dá)目的地，并且行駛時(shí)間短、充電時(shí)間短、充電頻率少的路線行走。通過(guò)引入分段充電以及部分充電策略，使研究場(chǎng)景更接近現(xiàn)實(shí)情況，從而有效地提高了充電效率；并利用北京市真實(shí)路網(wǎng)中的部分路網(wǎng)圖對(duì)模型進(jìn)行評(píng)估，結(jié)果表明，本文提出的方法優(yōu)于其他基準(zhǔn)方法。此外，本文方法具有很好的遷移性，可以有效地應(yīng)用在其他未經(jīng)訓(xùn)練的路網(wǎng)中。在后續(xù)的研究中，基于現(xiàn)有方法策略以及實(shí)驗(yàn)結(jié)果，本文模型可引入非線性獎(jiǎng)勵(lì)函數(shù)形式，進(jìn)一步挖掘特征向量之間的聯(lián)系以得到更適用的獎(jiǎng)勵(lì)函數(shù)，從而提升模型的性能。