最近的研究表明，85%的女性會(huì)在外出時(shí)特意避開(kāi)危險(xiǎn)區(qū)域，選擇相對(duì)安全的道路，防止受到騷擾或傷害。盡管如此，現(xiàn)有的導(dǎo)航工具并不能給用戶提供安全性指數(shù)。在這篇論文中，研究人員們提出了一種新的導(dǎo)航工具SafeRoute，它借助深度強(qiáng)化學(xué)習(xí)工具，能顯示城市街道中潛在的犯罪概率。以下是論智對(duì)論文的介紹：

康奈爾大學(xué)和Hollaback公司2014年調(diào)查了美國(guó)4872名女性，其中85%的人會(huì)為了避免潛在的危險(xiǎn)而選擇繞路，67%的調(diào)查對(duì)象會(huì)改變出行時(shí)間確保安全?；蛟S當(dāng)?shù)厝藭?huì)熟悉他們的居住環(huán)境，知道哪里危險(xiǎn)、哪里相對(duì)安全?？墒菍?duì)第一次來(lái)某地的人來(lái)說(shuō)，環(huán)境的陌生會(huì)大大增加危險(xiǎn)發(fā)生的概率。隨著犯罪率的上升，我們?cè)谙?，是否能?chuàng)建一款安全道路導(dǎo)航應(yīng)用，讓更多人能保護(hù)自己呢？

在這篇論文中，我們的研究對(duì)象僅限于非機(jī)動(dòng)車道（例如可以走路或騎自行車的區(qū)域）。在美國(guó)，想紐約、波士頓、舊金山這樣的城市，通常有很多步行街道。我們想計(jì)算出到達(dá)目的地的最短距離，并且危險(xiǎn)系數(shù)低的步行方案?，F(xiàn)有的導(dǎo)航方法也能覆蓋大城市，但他們沒(méi)有考慮犯罪率的問(wèn)題，忽略了小范圍的犯罪區(qū)域。

另外，最接近也有很多有關(guān)深度強(qiáng)化學(xué)習(xí)進(jìn)行最短路徑導(dǎo)航的成果出現(xiàn)，但我們的模型不僅僅是為了規(guī)劃路徑，而是要加入安全因素。于是我們選擇了基于深度強(qiáng)化學(xué)習(xí)的解決方案，這在很多數(shù)據(jù)挖掘問(wèn)題中都是常用方法。

SafeRoute介紹

我們可以將路徑選擇的過(guò)程看作是馬爾科夫決策過(guò)程，在每個(gè)步驟，智能體都要決定下一步的方向，最終到達(dá)目的地。首先會(huì)向模型輸入開(kāi)始和結(jié)束點(diǎn)的坐標(biāo)，模型會(huì)返回智能體做出的決策坐標(biāo)列表，同時(shí)對(duì)智能體進(jìn)行獎(jiǎng)勵(lì)，避免道路上遇到犯罪事件。

模型架構(gòu)

SafeRoute系統(tǒng)主要有兩大部分：強(qiáng)化學(xué)習(xí)智能體可以交互的環(huán)境，以及智能體進(jìn)行表示并做決定的策略網(wǎng)絡(luò)。主要架構(gòu)如下圖：

環(huán)境是用具有< S, A, P, R >元組的馬爾科夫決策過(guò)程表示。S表示環(huán)境持續(xù)的狀態(tài)，A={a1,a2,…,aN}，定義了智能體可能做出的所有動(dòng)作。P(St+1= s0|St= s,At= a)表示從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率。R(s, a)是智能體在狀態(tài)s下做出動(dòng)作a時(shí)的獎(jiǎng)勵(lì)函數(shù)。

在我們的模型中，智能體的狀態(tài)表示目前在地圖上的位置以及目標(biāo)位置。如果目標(biāo)位置和此前訓(xùn)練時(shí)的目標(biāo)位置很接近，那么智能體會(huì)采取相似行動(dòng)靠近該目標(biāo)。為了表示狀態(tài)，地圖信息被轉(zhuǎn)換成有節(jié)點(diǎn)和線條的圖，其中圖嵌入用來(lái)表示強(qiáng)化學(xué)習(xí)智能體的連續(xù)狀態(tài)，這些嵌入用node2vec來(lái)生成。用圖嵌入而不用坐標(biāo)的原因是，坐標(biāo)不能體現(xiàn)地圖上的交互是如何連接的任何信息。狀態(tài)從智能體目前的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)中使用的嵌入如下所示：

其中et表示當(dāng)前節(jié)點(diǎn)的嵌入，etarget表示目標(biāo)節(jié)點(diǎn)的嵌入。

另外，策略網(wǎng)絡(luò)表示強(qiáng)化學(xué)習(xí)智能體使用的隨機(jī)策略，用πθ(s, a) = p(a|s;θ)表示，其中θ是神經(jīng)網(wǎng)絡(luò)的參數(shù)列表，會(huì)用Adam優(yōu)化器進(jìn)行更新。系統(tǒng)使用隨機(jī)梯度而不是貪婪策略，是為了防止智能體在地圖上循環(huán)前進(jìn)，停滯不前。運(yùn)用隨機(jī)梯度，智能體可以打破循環(huán)（例如向死路前進(jìn)或選擇可能會(huì)通向死路的道路）。神經(jīng)網(wǎng)絡(luò)包含兩個(gè)隱藏層，每一層都有一個(gè)ReLU激活函數(shù)。輸出使用一個(gè)softmax函數(shù)，可以返回所有行為的概率分布。

至于獎(jiǎng)勵(lì)，智能體要考慮多方面優(yōu)化，所以獎(jiǎng)勵(lì)函數(shù)也必須包含多種因素。由于SafeRoute的一個(gè)重要特征就是躲避犯罪區(qū)域，所以我們將安全性添加到獎(jiǎng)勵(lì)中，用函數(shù)表示坐標(biāo)到此前有過(guò)犯罪記錄坐標(biāo)的平均距離。

雖然SafeRoute的主要目標(biāo)是增加安全性，但是我們還想盡量選擇較短路線。路徑沿線距離犯罪現(xiàn)場(chǎng)的所有平均距離都要計(jì)算，如果附近沒(méi)有發(fā)生過(guò)犯罪事件，那么就得到獎(jiǎng)勵(lì)k。最終的獎(jiǎng)勵(lì)函數(shù)定義如下：

其中n是路徑中線條的數(shù)量，m是每個(gè)節(jié)點(diǎn)一定半徑內(nèi)的犯罪事件數(shù)量，x是路線中線段的中點(diǎn)，c是每個(gè)半徑上發(fā)生的犯罪事件，p是路線，k是超參數(shù)。

訓(xùn)練

訓(xùn)練SafeRoute也分為兩部分：監(jiān)督訓(xùn)練和用獎(jiǎng)勵(lì)進(jìn)行重復(fù)訓(xùn)練。在最初不使用監(jiān)督訓(xùn)練的情況下，智能體在找尋目標(biāo)節(jié)點(diǎn)時(shí)很困難，最終可能會(huì)隨意尋找方向。AlphaGo在訓(xùn)練時(shí)用了模擬學(xué)習(xí)的方法，讓智能體在最初能夠找到正確方法。同樣，我們也在訓(xùn)練開(kāi)始時(shí)用監(jiān)督學(xué)習(xí)進(jìn)行模擬學(xué)習(xí)。經(jīng)過(guò)監(jiān)督學(xué)習(xí)之后，智能體還會(huì)再次訓(xùn)練，避開(kāi)犯罪率高的區(qū)域。再次訓(xùn)練的算法過(guò)程如下：

實(shí)驗(yàn)過(guò)程

由于此前沒(méi)有類似的實(shí)驗(yàn)，所以我們創(chuàng)建了自己的SafeRoute數(shù)據(jù)集。我們從OpenStreetMap中收集了地圖信息，這是一個(gè)免費(fèi)的協(xié)作世界地圖，我們選擇了波士頓、紐約和舊金山的市區(qū)，這是很多游客會(huì)去的地方，也是繁華的市中心。最終，波士頓和舊金山的圖在訓(xùn)練時(shí)每個(gè)epoch會(huì)歐2000個(gè)episode，而紐約的更大，可以達(dá)到4000個(gè)episode。三個(gè)模型都經(jīng)過(guò)了60epoch的訓(xùn)練。

犯罪數(shù)據(jù)從Spotcrime中收集，其中包括了最近有關(guān)犯罪的類型和地理坐標(biāo)。我們只選擇了槍擊、騷擾和搶劫三類。

另外，我們?cè)诙喾N尺度上對(duì)SafeRoute進(jìn)行了評(píng)估，路線的質(zhì)量有三個(gè)方面：距離犯罪點(diǎn)的平均距離（包括局部和全局兩種）以及路線長(zhǎng)短。局部犯罪平均距離只考慮當(dāng)智能體走在路上時(shí)，附近的犯罪活動(dòng)。而全局的平均距離會(huì)考慮該路線上所有發(fā)生過(guò)的犯罪活動(dòng)。其中局部平均距離是重點(diǎn)考量因素。

可以看到，在我們的評(píng)估前兩個(gè)因素的值越高并且路線距離越短的選擇更好。并且在波士頓遵循了離犯罪地點(diǎn)距離最短的原則，但是紐約的案例中，離犯罪地點(diǎn)遠(yuǎn)的路線卻很長(zhǎng)。

為了減少我們模型結(jié)果的多樣性，我們?yōu)槊總€(gè)城市創(chuàng)建了三種模型，并對(duì)結(jié)果進(jìn)行了平均。下表表現(xiàn)了SafeRoute和SafePath最安全的路線相比，增加或減少的百分比。

經(jīng)過(guò)測(cè)試，SafeRoute能在大多情況下生成合適的結(jié)果，未來(lái)，我們打算讓SafeRoute作用于更長(zhǎng)路徑和更大的地圖。除此之外，我們還會(huì)研究模型的可攜帶型。