[發(fā)明專利]一種面向城市規(guī)模交通仿真的分布式加速計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202111000787.8
• 申請(qǐng)日: 2021-08-27
• 公開（公告）號(hào): CN113761695B
• 公開（公告）日: 2022-04-22
• 發(fā)明（設(shè)計(jì)）人: 朱浩嘉;王之暢;朱越;黃啟越;金嘉暉
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): G06F30/18
• 分類號(hào): G06F30/18;G06F30/20;G08G1/01
• 代理公司: 南京眾聯(lián)專利代理有限公司 32206
• 代理人: 張?zhí)煺?/td>

本發(fā)明公開了一種面向城市規(guī)模交通仿真的分布式加速計(jì)算方法。強(qiáng)化學(xué)習(xí)領(lǐng)域需要交通仿真軟件為模型提供現(xiàn)實(shí)中不易得到的交通數(shù)據(jù)。在面對(duì)城市規(guī)模的車流量模擬與計(jì)算任務(wù)時(shí)，傳統(tǒng)平臺(tái)將所有計(jì)算任務(wù)分配給同一個(gè)核心或設(shè)備，導(dǎo)致單個(gè)核心或設(shè)備計(jì)算任務(wù)繁重。因此本發(fā)明公開一種方法來有效在城市規(guī)模下加速交通仿真速度。本發(fā)明首先根據(jù)真實(shí)路網(wǎng)數(shù)據(jù)，將大規(guī)模路網(wǎng)按區(qū)域切分成多個(gè)小路網(wǎng)，將不同區(qū)域的小路網(wǎng)均勻分配給分布式中不同的設(shè)備進(jìn)行結(jié)算；然后使用一種半同步的仿真方式，對(duì)路網(wǎng)上的車流進(jìn)行仿真，在加快城市規(guī)模的交通仿真速度的同時(shí)完成多個(gè)核心數(shù)據(jù)的同步。

技術(shù)領(lǐng)域

本發(fā)明涉及交通領(lǐng)域并服務(wù)于人工智能中的強(qiáng)化學(xué)習(xí)領(lǐng)域，尤其在設(shè)計(jì)分布式大規(guī)模交通仿真的場(chǎng)景下對(duì)計(jì)算與模型訓(xùn)練起到加速效果，具體涉及一種面向城市規(guī)模交通仿真的分布式加速計(jì)算方法。

背景技術(shù)

智慧城市的建設(shè)是中國(guó)城市化進(jìn)程的重要議題，在智慧城市的建設(shè)中對(duì)城市路網(wǎng)的研究則是最為重要的一環(huán)。如今強(qiáng)化學(xué)習(xí)等機(jī)器學(xué)習(xí)方法已經(jīng)在交通等領(lǐng)域被廣泛使用。強(qiáng)化學(xué)習(xí)依賴于大量數(shù)據(jù)，然而交通車流數(shù)據(jù)稀少且難以獲取，往往需要交通仿真平臺(tái)來生成大量數(shù)據(jù)。城市規(guī)模的仿真器具有很多衍生用途：用于估計(jì)城市的擁堵狀況，從而實(shí)時(shí)地調(diào)整交通引導(dǎo)的策略；用于確定地區(qū)出租車的實(shí)時(shí)需求，從而更好地派遣車輛；用于實(shí)驗(yàn)高價(jià)限牌法律制度，增加制度可靠性。因此，需要一個(gè)能夠進(jìn)行大規(guī)模車流量模擬與計(jì)算的仿真平臺(tái)。

然而現(xiàn)有的交通仿真平臺(tái)難以滿足需求。我們調(diào)研了主流的交通仿真平臺(tái)，發(fā)現(xiàn)它們雖然具有車流真實(shí)，對(duì)現(xiàn)實(shí)還原度高等優(yōu)點(diǎn)，但是均難以實(shí)現(xiàn)大規(guī)模的交通仿真。尤其在面對(duì)城市規(guī)模的車流量模擬與計(jì)算任務(wù)時(shí)，傳統(tǒng)平臺(tái)將所有計(jì)算任務(wù)分配給同一個(gè)核心或設(shè)備，導(dǎo)致單個(gè)核心或設(shè)備計(jì)算任務(wù)繁重。這也導(dǎo)致了傳統(tǒng)平臺(tái)在與強(qiáng)化學(xué)習(xí)等機(jī)器學(xué)習(xí)方法配合時(shí)，由于在強(qiáng)化學(xué)習(xí)模型訓(xùn)練中需要實(shí)時(shí)收到來自仿真環(huán)境的反饋，所以速度較慢的傳統(tǒng)平臺(tái)會(huì)拖慢模型訓(xùn)練速度。

因此，需要一種方法來有效加速交通仿真速度，尤其是在面臨城市規(guī)模的交通仿真任務(wù)的情況下。這一仿真方法需要在盡可能快速地完成仿真任務(wù)的同時(shí)要保證不同核心之間數(shù)據(jù)的同步。這對(duì)利用有限的計(jì)算資源模擬仿真真實(shí)的交通情況，同時(shí)高效地與機(jī)器學(xué)習(xí)模型進(jìn)行交互有著重要的作用。

發(fā)明內(nèi)容

發(fā)明目的：為解決以上問題，本發(fā)明提出了減少每個(gè)核心需要結(jié)算的數(shù)據(jù)量，并縮減同步數(shù)據(jù)類型的方法。以有效減少在路徑規(guī)劃，速度計(jì)算等計(jì)算任務(wù)和車輛數(shù)據(jù)同步上的時(shí)間開銷。

技術(shù)方案：為實(shí)現(xiàn)發(fā)明目的，本發(fā)明運(yùn)用分布式系統(tǒng)將路網(wǎng)分配給不同設(shè)備進(jìn)行并行結(jié)算，并行結(jié)算的時(shí)間開銷取決于結(jié)算耗時(shí)最長(zhǎng)的設(shè)備，因此需要均衡不同設(shè)備中路網(wǎng)的結(jié)算負(fù)擔(dān)。同時(shí)，分布式系統(tǒng)中跨設(shè)備傳輸?shù)拇鷥r(jià)較大，因此需要減少跨設(shè)備傳輸?shù)臄?shù)據(jù)量。本發(fā)明提出一種分布式加速計(jì)算方法以優(yōu)化以上兩個(gè)要求，其特征在于包括以下流程：

(1)建立路網(wǎng)到圖模型的映射f。圖模型可以被表示為G(V，E)，V為頂點(diǎn)集合，E為邊集。將路網(wǎng)簡(jiǎn)化為所有的十字路口Intersection和路Road，多個(gè)路段交匯的點(diǎn)被稱為十字路口，連接兩個(gè)十字路口的路段被視作一條路Road。所有的十字路口構(gòu)成點(diǎn)集V，所有的路構(gòu)成邊集E。

(2)使用多層k路劃分方法對(duì)圖進(jìn)行劃分。多層k路劃分的結(jié)果是使各子圖的頂點(diǎn)權(quán)值基本相同且劃分產(chǎn)生的邊截權(quán)數(shù)最小化。此處可以讓兩個(gè)頂點(diǎn)位于不同核心的路盡可能少，同時(shí)每個(gè)核心承擔(dān)的計(jì)算任務(wù)較接近。圖的多層k路劃分將圖的頂點(diǎn)集劃分為k個(gè)子集V₁，V₂，V₃...V_k。每個(gè)子集的頂點(diǎn)數(shù)目約為且

(3)通過f將分割好的圖映射回路網(wǎng)。對(duì)于i＝1，2，3...k將點(diǎn)集V_i中的所有點(diǎn)對(duì)應(yīng)的十字路口和與其相關(guān)的路網(wǎng)分配給同一個(gè)核心Engine_i。這樣可以得到k個(gè)核心，這些核心對(duì)路網(wǎng)進(jìn)行并行仿真。