CrowdTracker：一種基于移動(dòng)群智感知的目標(biāo)跟蹤方法

景 瑤 郭 斌 陳薈慧 岳超剛 王 柱 於志文

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 西安 710072)

一直以來(lái)，公共安全問(wèn)題是城市生活面臨的一大挑戰(zhàn)，移動(dòng)目標(biāo)跟蹤技術(shù)作為公共安全領(lǐng)域中的一項(xiàng)重要技術(shù)更是研究者們關(guān)注的熱門(mén)課題.城市發(fā)生突發(fā)狀況后，政府和警察常常通過(guò)各種數(shù)據(jù)來(lái)追蹤可疑車(chē)輛和人，其中視頻監(jiān)控是最常用的數(shù)據(jù).現(xiàn)有的對(duì)于移動(dòng)目標(biāo)跟蹤的研究主要基于網(wǎng)絡(luò)視頻監(jiān)控?cái)?shù)據(jù)方式[1-2].該類研究主要針對(duì)如何部署攝像頭達(dá)到最大化道路覆蓋以及基于圖像的運(yùn)動(dòng)目標(biāo)檢測(cè)算法設(shè)計(jì).這種基于網(wǎng)絡(luò)視頻監(jiān)控的方法需要預(yù)先在廣泛的城市區(qū)域內(nèi)部署大量的攝像頭，設(shè)備成本高且覆蓋范圍有限.隨著可內(nèi)嵌多種傳感器的智能手機(jī)的快速普及和應(yīng)用，移動(dòng)群智感知技術(shù)[3]作為一種新的感知模式逐步發(fā)展起來(lái)，它依賴大量普通用戶的移動(dòng)設(shè)備及其具備的豐富的感知能力來(lái)完成大規(guī)模、復(fù)雜的城市與社會(huì)感知任務(wù)[4-5].大量的用戶通過(guò)智能手機(jī)隨時(shí)隨地感知著城市生活的韻律，這為解決城市生活中的公共安全問(wèn)題帶來(lái)了新的思路.人們可以隨時(shí)隨地使用智能手機(jī)拍攝視頻、照片，并在一定法律約束范圍內(nèi)作為證據(jù)使用.如果將人們手中的智能手機(jī)看做移動(dòng)的監(jiān)控?cái)z像頭，那么這就可以實(shí)現(xiàn)一種新的基于群智感知的視頻監(jiān)控系統(tǒng).

基于該思路，本文面向目標(biāo)跟蹤問(wèn)題提出一種基于移動(dòng)群智感知的解決方案CrowdTracker：通過(guò)多人協(xié)作拍照方式實(shí)現(xiàn)對(duì)移動(dòng)目標(biāo)的軌跡預(yù)測(cè)和跟蹤.本文主要針對(duì)移動(dòng)目標(biāo)中的車(chē)輛進(jìn)行群智跟蹤.CrowdTracker的示例如圖1所示.城市發(fā)生公共安全事件后，警察和政府在CrowdTracker平臺(tái)上發(fā)布待跟蹤的目標(biāo)車(chē)輛信息，包括車(chē)輛顏色、型號(hào)、車(chē)牌號(hào)碼等.CrowdTracker平臺(tái)上的用戶A在網(wǎng)格區(qū)域n1內(nèi)發(fā)現(xiàn)目標(biāo)車(chē)輛，對(duì)該車(chē)輛拍照并上傳照片信息以及位置信息，啟動(dòng)對(duì)該目標(biāo)的跟蹤任務(wù).CrowdTracker服務(wù)器端通過(guò)分析城市中大量的車(chē)輛軌跡數(shù)據(jù)，預(yù)測(cè)出該目標(biāo)車(chē)輛下一步可能往區(qū)域n2移動(dòng)，并提前在n2內(nèi)通知平臺(tái)參與者等待目標(biāo)出現(xiàn).當(dāng)參與者B和C再次發(fā)現(xiàn)目標(biāo)時(shí)同樣進(jìn)行拍照并上傳信息，如此循環(huán)，得到目標(biāo)車(chē)輛出現(xiàn)過(guò)的網(wǎng)格序列n1-n2-n3-n4即為車(chē)輛的移動(dòng)軌跡，最終實(shí)現(xiàn)基于群智感知的移動(dòng)目標(biāo)跟蹤.

Fig. 1 A scenario of CrowdTracker圖1 CrowdTracker示例

為了實(shí)現(xiàn)這個(gè)目標(biāo)，本文提出了預(yù)測(cè)目標(biāo)移動(dòng)模型的方法MPRE(movement prediction)和任務(wù)分配的方法T-centric，P-centric.MPRE首先通過(guò)分析大量的車(chē)輛歷史軌跡建立城市里車(chē)輛位置的移動(dòng)概率模型.當(dāng)目標(biāo)出現(xiàn)在城市某位置時(shí)，通過(guò)該移動(dòng)模型找到目標(biāo)下一步移動(dòng)概率最大的位置區(qū)域，進(jìn)而在該區(qū)域內(nèi)預(yù)先安排參與者.本文提出的T-centric和P-centric方法以實(shí)現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點(diǎn)優(yōu)選，要求達(dá)到參與者與任務(wù)地點(diǎn)最佳匹配，使參與者能在一定時(shí)間約束內(nèi)到達(dá)指定任務(wù)點(diǎn)的同時(shí)，所移動(dòng)的距離最短，激勵(lì)成本最少.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.本文通過(guò)成都市二環(huán)內(nèi)1個(gè)月的出租車(chē)軌跡數(shù)據(jù)集對(duì)以上3種算法進(jìn)行實(shí)驗(yàn)評(píng)估，實(shí)驗(yàn)結(jié)果表明，本文提出的CrowdTracker能有效地實(shí)現(xiàn)目標(biāo)實(shí)時(shí)跟蹤.

1 相關(guān)工作

目前常用的目標(biāo)跟蹤方法主要是通過(guò)預(yù)先部署的網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)進(jìn)行[1-2].現(xiàn)有的技術(shù)主要針對(duì)如何部署攝像頭達(dá)到最大化道路覆蓋、如何調(diào)用攝像頭來(lái)追蹤目標(biāo)以及基于圖像的目標(biāo)檢測(cè)算法設(shè)計(jì)等[6-8].與傳統(tǒng)的預(yù)先部署固定的網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)不同的是，本文旨在利用群智的思想將人們手中智能手機(jī)的攝像頭看作移動(dòng)的監(jiān)控?cái)z像頭，提出基于群智的多人協(xié)作拍照的方式對(duì)移動(dòng)目標(biāo)進(jìn)行實(shí)時(shí)跟蹤.下面就本文的相關(guān)工作進(jìn)行介紹.

1.1 移動(dòng)群智感知

基于移動(dòng)群智感知的工作包括數(shù)據(jù)采集、管理、分析到最終提供服務(wù)等.移動(dòng)群智感知的數(shù)據(jù)包括2種產(chǎn)生方式：移動(dòng)群智感知和移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù).移動(dòng)群智感知就是利用人們手中的智能手機(jī)感知周邊的信息.比如“哥本哈根車(chē)輪”項(xiàng)目在自行車(chē)車(chē)輪里安裝一些傳感器，并通過(guò)用戶手機(jī)將收集的數(shù)據(jù)發(fā)送至后臺(tái)服務(wù)器，這樣依靠群體的力量就可以感知整個(gè)城市不同角落的溫度、濕度和CO2濃度；利用手機(jī)拍照發(fā)現(xiàn)城市中被污染的河流[9]、損壞的建筑物[10]、感知生活中的社會(huì)熱點(diǎn)事件[11]、幫助城市進(jìn)行災(zāi)難救援等[12].與本文工作不同的是，這些感知任務(wù)主要關(guān)注靜態(tài)的目標(biāo).CrowdTracker是利用多人協(xié)作拍照的方式對(duì)移動(dòng)目標(biāo)進(jìn)行實(shí)時(shí)跟蹤，需要對(duì)群智參與者的行為進(jìn)行時(shí)間約束，在時(shí)間序列下，多個(gè)參與者完成拍照任務(wù)的位置序列即為目標(biāo)的移動(dòng)軌跡.

1.2 移動(dòng)軌跡預(yù)測(cè)

CrowdTracker旨在保證準(zhǔn)確實(shí)時(shí)地對(duì)目標(biāo)進(jìn)行跟蹤的同時(shí)盡可能地減少用戶激勵(lì)的成本.減少激勵(lì)成本首先要縮小跟蹤任務(wù)的范圍，減少參與者數(shù)量.因此需要通過(guò)目標(biāo)的當(dāng)前位置信息，預(yù)測(cè)目標(biāo)下一步的移動(dòng)模型.現(xiàn)有的很多研究通過(guò)分析城市車(chē)輛的軌跡數(shù)據(jù)挖掘車(chē)輛移動(dòng)的規(guī)律，預(yù)測(cè)車(chē)輛行駛的目的地.Xu等人[13]用純數(shù)據(jù)驅(qū)動(dòng)的方式分析城市車(chē)輛的軌跡數(shù)據(jù)進(jìn)行目的地預(yù)測(cè).與本文工作不同的是，文獻(xiàn)[13]研究的是長(zhǎng)距離的最終目的地預(yù)測(cè)，本文的移動(dòng)預(yù)測(cè)旨在通過(guò)目標(biāo)上一狀態(tài)預(yù)測(cè)下一時(shí)刻位置狀態(tài).Xue等人[14]和Gambs等人[15]用基于概率模型的Markov鏈進(jìn)行下一站預(yù)測(cè).Xue等人[14]將軌跡序列網(wǎng)格化的思想也為本文工作提供了思路.

1.3 群智感知任務(wù)分配

任務(wù)分配是移動(dòng)群智感知的關(guān)鍵挑戰(zhàn)之一，如何進(jìn)行任務(wù)分配對(duì)數(shù)據(jù)采集的全面性、任務(wù)完成率和數(shù)據(jù)采集質(zhì)量等都具有重要影響.面向移動(dòng)群智感知的參與者選擇是以物理空間位置為基礎(chǔ)進(jìn)行選擇，任務(wù)的類型分為單個(gè)群智感知任務(wù)和多個(gè)并發(fā)感知任務(wù)2種.在單任務(wù)分配問(wèn)題中，Papadias等人[16]研究在已知給定集合點(diǎn)的情況下，尋找其他的點(diǎn)使其到給定集合點(diǎn)的距離最小；Reddy等人[17]主要研究在考慮空間位置、時(shí)間要求以及參與者行為習(xí)慣的情況下，選擇出合適的參與者完成任務(wù)；Cardone等人[18]考慮在參與者個(gè)數(shù)一定的情況下，最大限度地提高感知任務(wù)的空間覆蓋范圍.Li等人[19]研究團(tuán)隊(duì)形成問(wèn)題，即尋找一個(gè)有特定技能的專家小組，每個(gè)人完成一個(gè)給定的任務(wù)，同時(shí)最小化團(tuán)隊(duì)之間的交流成本.Liu等人[20]研究了移動(dòng)群智感知中面向多任務(wù)并發(fā)的參與者選擇問(wèn)題，不同于其他參與者選擇問(wèn)題，該文選擇出的參與者不再局限于只能完成1個(gè)任務(wù)，參與者可以在規(guī)定時(shí)間內(nèi)盡可能的完成多個(gè)任務(wù)，由此降低群智平臺(tái)的成本.

本文提出的CrowdTracker首先對(duì)目標(biāo)下一步的移動(dòng)進(jìn)行預(yù)測(cè)，然后在預(yù)測(cè)的區(qū)域內(nèi)進(jìn)行跟蹤任務(wù)分配.在該區(qū)域內(nèi)的每一個(gè)任務(wù)點(diǎn)的任務(wù)是同時(shí)進(jìn)行且有時(shí)間限制的，每個(gè)參與者只能在規(guī)定的時(shí)間內(nèi)在1個(gè)任務(wù)點(diǎn)等待目標(biāo)的出現(xiàn).因此，本文的任務(wù)分配是一個(gè)并發(fā)的單任務(wù)分配問(wèn)題.針對(duì)該問(wèn)題，CrowdTracker提出了T-centric和P-centric方法實(shí)現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點(diǎn)優(yōu)選，使參與者能在一定時(shí)間約束內(nèi)到達(dá)指定任務(wù)點(diǎn)的同時(shí)所移動(dòng)的距離最短.

2 CrowdTracker系統(tǒng)框架

CrowdTracker的系統(tǒng)框架如圖2所示，主要包括客戶端APP和服務(wù)器端2部分.客戶端APP主要用于任務(wù)啟動(dòng)者和任務(wù)執(zhí)行者采集數(shù)據(jù).服務(wù)器端對(duì)客戶端上傳的數(shù)據(jù)進(jìn)行一系列分析處理后通知被選擇的參與者并給出下一步任務(wù)執(zhí)行的指示，保證跟蹤任務(wù)的持續(xù)執(zhí)行.

Fig. 2 The framework of CrowdTracker圖2 CrowdTracker系統(tǒng)框架

圖2中的數(shù)據(jù)采集模塊展示了使用客戶端進(jìn)行數(shù)據(jù)采集的基本流程.城市發(fā)生共公共安全事件后，警察和政府在CrowdTracker平臺(tái)上發(fā)布待跟蹤的目標(biāo)車(chē)輛信息，包括車(chē)輛的顏色、型號(hào)和車(chē)牌號(hào)碼等.CrowdTracker平臺(tái)上的用戶在城市某一位置發(fā)現(xiàn)目標(biāo)，立即對(duì)其拍攝1張照片用pic來(lái)表示.pic中保存了用戶拍照時(shí)刻的圖像、GPS位置坐標(biāo)和時(shí)間戳等信息，用一個(gè)五元組(id,img,lon,lat,t)表示.id是拍照用戶的唯一標(biāo)識(shí),img代表圖像信息，lon和lat分別表示用戶當(dāng)前位置的經(jīng)緯度，也代表了目標(biāo)當(dāng)前的位置信息,t表示拍照時(shí)間.上傳該五元組信息至服務(wù)器端，啟動(dòng)該目標(biāo)的跟蹤任務(wù).服務(wù)器對(duì)客戶端發(fā)起的任務(wù)請(qǐng)求分析處理后，給出該跟蹤任務(wù)下一步的計(jì)劃，并通知CrowdTracker平臺(tái)上被選中執(zhí)行下一步任務(wù)的參與者.參與者按照任務(wù)指示在一定的時(shí)間內(nèi)到達(dá)指定任務(wù)地點(diǎn)，等待目標(biāo)出現(xiàn)，在一定時(shí)間內(nèi)發(fā)現(xiàn)目標(biāo)后對(duì)目標(biāo)進(jìn)行拍照并再次上傳信息，完成該步跟蹤任務(wù).

具體地，CrowdTracker群智跟蹤方法的詳細(xì)內(nèi)容將在第4節(jié)進(jìn)行介紹.

3 群智跟蹤方法實(shí)現(xiàn)

圖2中的群智跟蹤方法模塊展示了服務(wù)器端對(duì)客戶端上傳的數(shù)據(jù)進(jìn)行分析的基本流程.該模塊主要分為3個(gè)部分：目標(biāo)車(chē)輛移動(dòng)預(yù)測(cè)模型、群智跟蹤任務(wù)分配以及最終的任務(wù)推送.

3.1 預(yù)測(cè)目標(biāo)車(chē)輛移動(dòng)模型

客戶端上傳數(shù)據(jù)中的經(jīng)緯度信息代表了目標(biāo)當(dāng)前的位置.基于該位置信息，預(yù)測(cè)目標(biāo)下一步的移動(dòng)，進(jìn)而有針對(duì)性地在預(yù)測(cè)的區(qū)域內(nèi)進(jìn)行跟蹤任務(wù)分配，準(zhǔn)確跟蹤目標(biāo)的同時(shí)減少平臺(tái)的激勵(lì)成本.

城市中車(chē)輛的移動(dòng)看似雜亂無(wú)序，實(shí)則存在潛在的模式.例如上班高峰期的車(chē)輛大都由住宅區(qū)流向商業(yè)區(qū)，而下班高峰期的車(chē)輛大都由商業(yè)區(qū)流向住宅區(qū).這種規(guī)律對(duì)于預(yù)測(cè)車(chē)輛的移動(dòng)模型具有一定的意義.本文提出了基于移動(dòng)Markov鏈(mobility Markov chain, MMC)的MPRE方法來(lái)預(yù)測(cè)車(chē)輛移動(dòng).Markov鏈?zhǔn)菙?shù)學(xué)中具有Markov性質(zhì)的離散時(shí)間隨機(jī)過(guò)程.在該過(guò)程中，在給定當(dāng)前知識(shí)或信息的情況下，過(guò)去(即當(dāng)前以前的歷史狀態(tài))對(duì)于預(yù)測(cè)將來(lái)(即當(dāng)前以后的未來(lái)狀態(tài))是無(wú)關(guān)的.X1,X2,…描述了Markov鏈中的一種狀態(tài)序列，Xn的值表示在時(shí)刻n的狀態(tài)，如果Xn+1對(duì)于過(guò)去狀態(tài)的條件概率分布僅是Xn的一個(gè)函數(shù)，則Xn+1時(shí)刻的狀態(tài)見(jiàn)式(1)：

P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=
P(Xn+1=x|Xn=xn).

(1)

移動(dòng)Markov鏈?zhǔn)悄Ｐ突貙⒂脩艋蛘哕?chē)輛等的移動(dòng)行為轉(zhuǎn)化為一系列離散隨機(jī)過(guò)程，如圖3所示，也就是Markov鏈中的狀態(tài)序列{n1,n2,…}，每個(gè)狀態(tài)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)位置區(qū)域.由Markov性質(zhì)可得，從一個(gè)狀態(tài)ni到另一個(gè)狀態(tài)nj的轉(zhuǎn)移概率Pi j是條件概率，只取決于狀態(tài)ni.利用MMC進(jìn)行下一狀態(tài)預(yù)測(cè)時(shí)，重要的是獲取轉(zhuǎn)移矩陣的參數(shù)，也就是不同位置狀態(tài)間的移動(dòng)概率Pi j，式(2)中Ni表示所有包含節(jié)點(diǎn)ni的軌跡數(shù)目,Ni,j表示從節(jié)點(diǎn)ni到nj的軌跡數(shù)目.Ni,j與Ni的商即為轉(zhuǎn)移概率Pi j的值.

(2)

Fig. 3 Mobility Markov chain圖3 移動(dòng)Markov鏈模型

具體地，基于MMC的思想，本文提出MPRE的方法對(duì)車(chē)輛的移動(dòng)進(jìn)行預(yù)測(cè).在進(jìn)行MPRE之前首先對(duì)城市區(qū)域進(jìn)行網(wǎng)格化處理，如圖4所示：

Fig. 4 Grid on the example圖4 城市區(qū)域網(wǎng)格化

將城市區(qū)域分為大小為g×g(單位m2)的單元格，每個(gè)單元格ni代表MMC中的一個(gè)位置狀態(tài).進(jìn)一步，為了更好地發(fā)現(xiàn)城市中車(chē)輛的移動(dòng)規(guī)律，構(gòu)建MMC中各個(gè)位置狀態(tài)之間的轉(zhuǎn)移概率矩陣，本文對(duì)大量的原始車(chē)輛軌跡序列進(jìn)行網(wǎng)格化處理.車(chē)輛的原始軌跡信息由一系列時(shí)間連續(xù)的GPS點(diǎn)形成，對(duì)這些軌跡信息進(jìn)行網(wǎng)格化即判斷每一個(gè)GPS點(diǎn)屬于哪一個(gè)網(wǎng)格區(qū)域，若連續(xù)時(shí)間的GPS點(diǎn)序列在同一網(wǎng)格位置，則記為1個(gè)網(wǎng)格位置.最終，網(wǎng)格序列即為軌跡序列Gi={n1,n2,…}.大量軌跡進(jìn)行網(wǎng)格化后得到軌跡序列集合G={G1,G2,…}.同樣地，當(dāng)目標(biāo)出現(xiàn)在城市某位置時(shí)，將經(jīng)緯度數(shù)據(jù)轉(zhuǎn)化為網(wǎng)格位置ni.車(chē)輛軌跡序列集合G和目標(biāo)位置ni作為MPRE的輸入.MPRE算法具體流程見(jiàn)算法1.

算法1. MPRE.

輸入：軌跡序列集合G、目標(biāo)位置ni；

輸出：Pmax對(duì)應(yīng)的位置點(diǎn)nj.

① 基于式(2)，從G中學(xué)習(xí)出各個(gè)位置狀態(tài)間的轉(zhuǎn)移矩陣P；

② 逐行搜索矩陣P，定位到目標(biāo)位置ni；

③ 在ni對(duì)應(yīng)的行里，查找出轉(zhuǎn)移概率最大的Pmax對(duì)應(yīng)的下一步位置nj；

④ 輸出Pmax對(duì)應(yīng)的位置點(diǎn)nj,即為目標(biāo)下一步可能移動(dòng)的位置；

⑤ 結(jié)束.

MPRE通過(guò)分析大量的車(chē)輛歷史軌跡序列計(jì)算出城市各個(gè)位置間的的轉(zhuǎn)移概率，遷出位置間的轉(zhuǎn)移概率矩陣P=(Pi j).如圖4所示，當(dāng)目標(biāo)出現(xiàn)在城市某位置n5時(shí)，搜索矩陣P，找到目標(biāo)下一步移動(dòng)概率最大P56對(duì)應(yīng)的位置區(qū)域n6，即為目標(biāo)下一步可能移動(dòng)的位置，進(jìn)而在該區(qū)域內(nèi)預(yù)先安排參與者.

3.2 群智跟蹤任務(wù)分配方法

通過(guò)預(yù)測(cè)車(chē)輛移動(dòng)模塊中的MPRE方法確定出目標(biāo)下一步移動(dòng)的位置范圍，在該區(qū)域內(nèi)預(yù)先安排參與者.每一個(gè)區(qū)域內(nèi)都有多條路，且1條路覆蓋一定的范圍，如何在1條路上進(jìn)行任務(wù)地點(diǎn)選擇是首先需要思考的問(wèn)題.分析路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，路網(wǎng)是由多條路連接形成，而每條路是由路網(wǎng)節(jié)點(diǎn)(起始點(diǎn)、終止點(diǎn))連接形成，路網(wǎng)節(jié)點(diǎn)就是形成整個(gè)道路網(wǎng)絡(luò)的關(guān)鍵位置.因此，本文考慮將OpenStreetMap路網(wǎng)數(shù)據(jù)中的節(jié)點(diǎn)數(shù)據(jù)作為1條路上的任務(wù)點(diǎn)，達(dá)到最大化道路覆蓋.在此基礎(chǔ)上，本文提出T-centric和P-centric方法以實(shí)現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點(diǎn)優(yōu)選，使參與者能在一定時(shí)間約束內(nèi)到達(dá)指定任務(wù)點(diǎn)的同時(shí)所移動(dòng)的距離最短.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.

對(duì)于每一步跟蹤任務(wù)T，即1個(gè)網(wǎng)格內(nèi)的任務(wù)分配問(wèn)題定義如下：城市網(wǎng)格化的步長(zhǎng)為g(單位m)，每個(gè)g×g(單位m2)的網(wǎng)格內(nèi)的路網(wǎng)節(jié)點(diǎn)數(shù)量為s，則設(shè)定s個(gè)并發(fā)任務(wù)T={t1,t2,…,ts}.每個(gè)任務(wù)ti需要1個(gè)人來(lái)完成，任務(wù)的位置為lti，每個(gè)網(wǎng)格的候選者集合C={c1,c2,…,cj,…}，候選者的位置為lci.ui表示完成任務(wù)ti的參與者，完成任務(wù)ti的參與者ui需要移動(dòng)的距離為di(見(jiàn)式(3))，完成1步跟蹤任務(wù)T，所有參與者所移動(dòng)的總距離為DT.假設(shè)每個(gè)用戶移動(dòng)平均速度為Vu(單位mmin)，城市中車(chē)輛移動(dòng)的平均速度為Vc(單位mmin).該問(wèn)題的目標(biāo)函數(shù)是安排參與者與任務(wù)的最佳匹配，使參與者能在一定時(shí)間約束內(nèi)(目標(biāo)進(jìn)入網(wǎng)格區(qū)域之前)到達(dá)指定任務(wù)點(diǎn)的同時(shí)所移動(dòng)的距離di最短，即所有參與者移動(dòng)的總距離DT最短(見(jiàn)式(4))，時(shí)間約束見(jiàn)式(5).具體地，針對(duì)該任務(wù)分配問(wèn)題，考慮系統(tǒng)的2個(gè)核心要素任務(wù)和人，分別提出以任務(wù)為中心的參與者選擇方法T-centric和以人為中心的任務(wù)選擇方法P-centric.

di=|lti-lci|，

(3)

(4)

滿足

(5)

3.2.1 T-centric任務(wù)分配算法

T-centric是以任務(wù)為中心的參與者選擇方法，采用貪心啟發(fā)算法的思想.首先在任務(wù)集合T中隨機(jī)選擇1個(gè)任務(wù)作為初始任務(wù)，然后從侯選者集合C中選出滿足時(shí)間約束的參與者集合.若該參與者集合為空，則表明沒(méi)有能夠完成該任務(wù)的參與者；若不為空，則存在能夠完成該任務(wù)的參與者，進(jìn)一步在該參與者集合中選出與任務(wù)點(diǎn)距離最短的參與者，形成1個(gè)參與者與任務(wù)點(diǎn)的最佳匹配.在原任務(wù)集合以及候選參與者集合中剔除掉已經(jīng)形成匹配的參與者和任務(wù)，接著對(duì)下一個(gè)任務(wù)進(jìn)行參與者選擇，以此類推，按照該方法，直到任務(wù)集合中的每一個(gè)任務(wù)都找到1個(gè)最佳的參與者.詳見(jiàn)算法2.

算法2. T-centric.

輸入：任務(wù)集合T、候選參與者集合C；

輸出：能被覆蓋的任務(wù)點(diǎn)集合t以及相應(yīng)的參與者集合u.

① 隨機(jī)選取初始任務(wù)ti；

③ 若集合ui.為空，則該任務(wù)點(diǎn)無(wú)法被覆蓋；若|ui.|≥1,則在該集合中選擇離任務(wù)距離最近的參與者ui覆蓋該任務(wù)點(diǎn)；

④ 在任務(wù)集合T中剔除ti，在參與者集合C中剔除ui對(duì)應(yīng)的ci；

⑤ 在剩余任務(wù)集合中隨機(jī)選取任務(wù)ti+1；

⑥ 循環(huán)執(zhí)行②～⑤步，直至所有任務(wù)執(zhí)行完；

⑦ 輸出能被覆蓋的所有任務(wù)點(diǎn)ti以及相應(yīng)的參與者ui；

⑧ 結(jié)束.

3.2.2 P-centric任務(wù)分配算法

P-centric是以人為中心的任務(wù)選擇方法.首先在候選參與者集合C中隨機(jī)選擇1個(gè)參與者，然后從任務(wù)集合T中選擇出該參與者能在一定時(shí)間約束內(nèi)到達(dá)的任務(wù)集合.若該任務(wù)集合為空，則表明該參與者沒(méi)有能力完成任何一個(gè)任務(wù)；若不為空，則存在能夠完成的任務(wù)，進(jìn)一步在該任務(wù)集合中選出與參與者距離最短的任務(wù)，形成1個(gè)參與者與任務(wù)點(diǎn)的最佳匹配.在原任務(wù)集合以及候選參與者集合中剔除掉已經(jīng)形成匹配的參與者和任務(wù)，接著對(duì)下一個(gè)參與者進(jìn)行任務(wù)選擇，以此類推，按照該方法，直到對(duì)于參與者集合中的每一個(gè)人都找到最佳的任務(wù)點(diǎn)，詳見(jiàn)算法3.

算法3. P-centric.

輸入：任務(wù)集合T、候選參與者集合C；

輸出：能被覆蓋的任務(wù)點(diǎn)集合t以及相應(yīng)的參與者集合c.

① 隨機(jī)選取候選參與者集合C中的1個(gè)ci；

③ 若集合ti.為空，則該用戶無(wú)法覆蓋任何任務(wù)點(diǎn)；若|ti.|≥1,則在該集合中選擇離參與者距離最近的任務(wù)點(diǎn)ti去完成；

④ 在候選參與者集合中剔除ci，在任務(wù)集合T中剔除ti；

⑤ 在剩余的候選參與者集合中隨機(jī)選取參與者ci+1；

⑥ 循環(huán)執(zhí)行②～⑤步，直至所有任務(wù)執(zhí)行完；

⑦ 輸出能被覆蓋的所有任務(wù)點(diǎn)ti以及相應(yīng)的參與者ci；

⑧ 結(jié)束.

4 實(shí)驗(yàn)評(píng)估

本文提出的基于群智的多人協(xié)作拍照方式實(shí)現(xiàn)對(duì)移動(dòng)目標(biāo)的實(shí)時(shí)跟蹤，旨在保證準(zhǔn)確實(shí)時(shí)地對(duì)目標(biāo)進(jìn)行跟蹤的同時(shí)盡可能地減少用戶激勵(lì)的成本.為了實(shí)現(xiàn)這個(gè)目標(biāo)，提出了預(yù)測(cè)目標(biāo)移動(dòng)模型的方法MPRE和任務(wù)分配的方法T-centric和P-centric.本節(jié)分別對(duì)每一個(gè)方法進(jìn)行實(shí)驗(yàn)驗(yàn)證.

4.1 MPRE方法評(píng)估

為了驗(yàn)證MPRE方法的精度，本文對(duì)成都市的出租車(chē)軌跡數(shù)據(jù)進(jìn)行了分析.表1展示了實(shí)驗(yàn)數(shù)據(jù)集的基本統(tǒng)計(jì)信息.本文選取了1個(gè)月內(nèi)成都市二環(huán)內(nèi)13 605輛出租車(chē)從6點(diǎn)到23點(diǎn)的GPS點(diǎn)序列.原始數(shù)據(jù)中包含車(chē)輛ID、經(jīng)緯度、載客狀態(tài)(1表示載客，0表示空車(chē))以及時(shí)間戳信息.根據(jù)原始軌跡數(shù)據(jù)中車(chē)輛載客狀態(tài)的變化，將每輛車(chē)1天內(nèi)連續(xù)的GPS點(diǎn)分割為多條軌跡.當(dāng)車(chē)輛狀態(tài)由0變?yōu)?則表明一條軌跡的開(kāi)始，車(chē)輛狀態(tài)由1變?yōu)?則表明這條軌跡結(jié)束.將城市區(qū)域分為大小為g×g(單位m2)的單元格，對(duì)每一條原始車(chē)輛軌跡進(jìn)行網(wǎng)格化，總共有大約4 010 960條軌跡，其中104條軌跡用于測(cè)試集，其余用做組建訓(xùn)練集.從訓(xùn)練集中學(xué)習(xí)出各個(gè)位置狀態(tài)間的轉(zhuǎn)移矩陣P.1條測(cè)試軌跡Gi={n1,n2,…}總共有|Gi|個(gè)位置狀態(tài)，對(duì)于除了最后一個(gè)位置狀態(tài)外的每一個(gè)ni，從轉(zhuǎn)移矩陣中得到概率最高的位置即為MPRE預(yù)測(cè)的下一位置.對(duì)于這條測(cè)試軌跡，預(yù)測(cè)正確的位置狀態(tài)數(shù)量mi占軌跡中|Gi|-1個(gè)位置數(shù)量的比率即為MPRE對(duì)該條軌跡預(yù)測(cè)的正確率.所有測(cè)試軌跡的正確率求平均得到MPRE預(yù)測(cè)的正確率Acc為

(6)

Table 1 Taxi Trajectory Dataset in Chengdu表1 成都市出租車(chē)軌跡實(shí)驗(yàn)數(shù)據(jù)集

Fig. 5 The result of MPRE圖5 MPRE結(jié)果

圖5展示了不同測(cè)試集、不同網(wǎng)格步長(zhǎng)情況下的實(shí)驗(yàn)結(jié)果.由于大量的訓(xùn)練集更能反映整體數(shù)據(jù)的規(guī)律，在同一網(wǎng)格粒度下，訓(xùn)練集數(shù)量越多，可能MPRE的準(zhǔn)確率越高.本文首先設(shè)置了4個(gè)不同大小的訓(xùn)練集.訓(xùn)練集1中有106條軌跡數(shù)據(jù)，訓(xùn)練集2有2×106條，訓(xùn)練集3有3×106條，訓(xùn)練集4中有4×106條軌跡數(shù)據(jù).在同一訓(xùn)練集下，改變網(wǎng)格粒度，對(duì)104條軌跡數(shù)據(jù)進(jìn)行測(cè)試.一方面，1個(gè)粗的網(wǎng)格粒度(例如g=500 m)，由于每個(gè)網(wǎng)格覆蓋的面積較大，可能會(huì)使預(yù)測(cè)精度降低.另一方面，由于覆蓋面積大，訓(xùn)練數(shù)據(jù)中更多的原始GPS軌跡點(diǎn)會(huì)落入相同的網(wǎng)格區(qū)域，匹配到的軌跡數(shù)目可能更高，從而提高M(jìn)PRE的準(zhǔn)確率.因此，需要找到一個(gè)平衡的網(wǎng)格粒度使得MPRE的準(zhǔn)確率達(dá)到最佳.圖5中的實(shí)驗(yàn)結(jié)果表明，隨著數(shù)據(jù)量的增加，MPRE的準(zhǔn)確率越來(lái)越高.在訓(xùn)練集4中，網(wǎng)格粒度在g=200 m和g=400 m下表現(xiàn)出較高的預(yù)測(cè)準(zhǔn)確率，能達(dá)到70%左右.對(duì)比MPRE算法在2種粒度下的運(yùn)行時(shí)間，越細(xì)粒度的網(wǎng)格，網(wǎng)格數(shù)量越多，算法的時(shí)間復(fù)雜度越高.因此，綜合考慮下本文選擇g=400 m的網(wǎng)格粒度，以下的實(shí)驗(yàn)如果沒(méi)有特別說(shuō)均在g=400 m的網(wǎng)格粒度下進(jìn)行.

4.2 任務(wù)分配的方法評(píng)估

通過(guò)預(yù)測(cè)車(chē)輛移動(dòng)模塊中的MPRE方法確定出目標(biāo)下一步移動(dòng)的位置范圍，在該區(qū)域內(nèi)預(yù)先安排參與者.在進(jìn)行任務(wù)分配之前，首先，確定區(qū)域內(nèi)的任務(wù)位置.本文從OpenStreetMap中得到成都市路網(wǎng)數(shù)據(jù)，將路網(wǎng)數(shù)據(jù)中的節(jié)點(diǎn)作為一條路上的任務(wù)點(diǎn).其次，確定用戶位置.本文有成都市出租車(chē)的載客狀態(tài)數(shù)據(jù)，考慮到出租車(chē)由載客狀態(tài)1轉(zhuǎn)變?yōu)榭哲?chē)狀態(tài)0則表明該位置有乘客下車(chē)，即可以認(rèn)為該位置有用戶.因此，本文使用出租車(chē)載客狀態(tài)發(fā)生變化時(shí)的位置作為候選參與者的位置.本文提出了T-centric和P-centric方法以在網(wǎng)格內(nèi)進(jìn)行參與者和任務(wù)點(diǎn)的優(yōu)選.T-centric是以任務(wù)為中心進(jìn)行參與者選擇，而P-centric是以人為中心進(jìn)行任務(wù)的選擇.2種方法的解決思路不同，選出的參與者與任務(wù)的最佳匹配也不同，因此需要通過(guò)實(shí)驗(yàn)驗(yàn)證2種方法的性能.為了降低CrowdTracker平臺(tái)的用戶激勵(lì)成本，在任務(wù)分配中要求參與者能在一定時(shí)間約束內(nèi)到達(dá)指定任務(wù)點(diǎn)的同時(shí)所移動(dòng)的距離最短.因此對(duì)比2種方法所選出的參與者的平均移動(dòng)距離.在任務(wù)個(gè)數(shù)以及參與者人數(shù)一定的情況下，選出的參與者與任務(wù)的最佳匹配數(shù)量越多，說(shuō)明能夠完成的任務(wù)越多.因此，另一個(gè)需要對(duì)比的指標(biāo)是任務(wù)的覆蓋率.最后針對(duì)該問(wèn)題選擇出性能較好的算法.

以下的實(shí)驗(yàn)均在400 m×400 m的網(wǎng)格粒度下進(jìn)行(g=400 m).由于該實(shí)驗(yàn)主要研究不同地點(diǎn)的任務(wù)對(duì)參與者選擇的影響，所以希望保持每個(gè)參與者完成任務(wù)的移動(dòng)方式相同，即本文認(rèn)為參與者都是通過(guò)步行的方式完成任務(wù)，每個(gè)參與者移動(dòng)的速度為60 mmin即Vu=60 mmin，車(chē)輛移動(dòng)的平均速度是30 kmh即Vc=500 mmin，則參與者要在(單位min)的時(shí)間約束內(nèi)能到達(dá)任務(wù)地點(diǎn)，即參與者與任務(wù)的距離約束在48 m以內(nèi).考慮到實(shí)驗(yàn)的準(zhǔn)確性，以下的實(shí)驗(yàn)數(shù)據(jù)都是通過(guò)多次實(shí)驗(yàn)平均而來(lái).

在任務(wù)分配問(wèn)題中，有2個(gè)因素對(duì)分配結(jié)果影響較大.一個(gè)是任務(wù)個(gè)數(shù)，另一個(gè)是候選者人數(shù).由于路網(wǎng)中節(jié)點(diǎn)的數(shù)量和位置是一定的，也就是說(shuō)任務(wù)的個(gè)數(shù)以及任務(wù)地點(diǎn)是一定的，因此本次實(shí)驗(yàn)主要研究不同候選參與者人數(shù)下的2種算法的性能.將成都市二環(huán)內(nèi)10 km×10 km范圍(625個(gè)網(wǎng)格)的1 017個(gè)路網(wǎng)節(jié)點(diǎn)作為任務(wù)地點(diǎn).保持其他因素不變，將完成任務(wù)的時(shí)間設(shè)為10:00—10:10，對(duì)于這625個(gè)網(wǎng)格中的每一個(gè)網(wǎng)格，以該段時(shí)間出現(xiàn)在區(qū)域內(nèi)的用戶為候選者，所有網(wǎng)格總共有40 700個(gè)候選者.改變候選者人數(shù)的總量，在每一個(gè)網(wǎng)格區(qū)域內(nèi)進(jìn)行任務(wù)分配，最終對(duì)每個(gè)網(wǎng)格得到一系列參與者與任務(wù)地點(diǎn)的最佳匹配.每個(gè)網(wǎng)格內(nèi)任務(wù)的覆蓋率定義為形成最佳匹配的任務(wù)點(diǎn)的個(gè)數(shù)與該網(wǎng)格所有任務(wù)點(diǎn)數(shù)量的比值，對(duì)所有網(wǎng)格的任務(wù)完成率求均值得到平均任務(wù)完成率.對(duì)所有參與者完成任務(wù)所移動(dòng)的距離DT求均值得到平均移動(dòng)距離，平均移動(dòng)距離越小，CrowdTracker平臺(tái)用戶激勵(lì)成本越小.

Fig. 6 Average task coverage圖6 候選參與者人數(shù)與平均任務(wù)覆蓋率的關(guān)系

圖6展示了候選參與者人數(shù)與平均任務(wù)覆蓋率的關(guān)系.實(shí)驗(yàn)結(jié)果表明，隨著候選參與者人數(shù)的增加，T-centric和P-centric的平均任務(wù)覆蓋率均呈現(xiàn)增長(zhǎng)趨勢(shì).該結(jié)果說(shuō)明了群智任務(wù)中的一個(gè)典型問(wèn)題，在一定程度上，參與者人數(shù)的多少?zèng)Q定了群智任務(wù)的完成率.對(duì)比2種算法的結(jié)果，同等參與者人數(shù)下，P-centric比T-centric的任務(wù)覆蓋率相對(duì)較高，但差別不是很大.圖7展示了算法對(duì)參與者平均移動(dòng)距離的影響，明顯看出，同等參與者人數(shù)下，P-centric比T-centric的平均移動(dòng)距離大.本文研究的問(wèn)題中，候選參與者的人數(shù)比任務(wù)的數(shù)量多，P-centric是以人為中心去選擇在時(shí)間約束內(nèi)且距離最近的任務(wù)，對(duì)于參與者來(lái)說(shuō)選出的任務(wù)是距離其最近的，但是對(duì)于任務(wù)來(lái)說(shuō)選出的參與者不一定是最近的，因此，P-centric的移動(dòng)距離較大.但是在算法運(yùn)行時(shí)間上如圖8所示，同樣的原因，由于候選參與者的人數(shù)比任務(wù)的數(shù)量要多，T-centric在以任務(wù)為中心選擇參與者時(shí)需要計(jì)算的參與者數(shù)據(jù)量大，計(jì)算時(shí)間長(zhǎng).因此，針對(duì)本文的問(wèn)題，為了更好地反映算法的性能，以參與者平均移動(dòng)距離與計(jì)算時(shí)間的乘積大小作為衡量算法性能的指標(biāo)，乘積越小，算法性能越好.如圖9所示，P-centric比T-centric的平均乘積小，P-centric以人為中心的方法更適合本文的任務(wù)分配問(wèn)題.

Fig. 7 Average traveled distance圖7 算法對(duì)參與者平均移動(dòng)距離的影響

Fig. 8 Running time圖8 算法運(yùn)行時(shí)間對(duì)比

Fig. 9 The product of average distance traveled and running time圖9 算法參與者平均移動(dòng)距離與計(jì)算時(shí)間的乘積對(duì)比

5 總結(jié)與展望

本文主要研究了基于移動(dòng)群智感知的目標(biāo)跟蹤，提出了一種新的解決方案CrowdTracker：通過(guò)基于群智的多人協(xié)作拍照方式實(shí)現(xiàn)對(duì)移動(dòng)目標(biāo)的實(shí)時(shí)跟蹤.CrowdTracker在保證準(zhǔn)確實(shí)時(shí)地對(duì)目標(biāo)進(jìn)行跟蹤的同時(shí)盡可能地減少用戶激勵(lì)的成本.為了實(shí)現(xiàn)這個(gè)目標(biāo)，本文提出了預(yù)測(cè)目標(biāo)移動(dòng)模型的方法MPRE和任務(wù)分配的方法T-centric，P-centric.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.MPRE首先通過(guò)分析大量的車(chē)輛歷史軌跡建立城市里車(chē)輛位置的移動(dòng)模型，進(jìn)而預(yù)測(cè)移動(dòng)目標(biāo)下一步的位置范圍，在該位置范圍內(nèi)通過(guò)T-centric或P-centric方法進(jìn)行跟蹤任務(wù)分配.最后，通過(guò)大規(guī)模的真實(shí)數(shù)據(jù)集對(duì)3種算法進(jìn)行實(shí)驗(yàn)評(píng)估，綜合考慮實(shí)驗(yàn)結(jié)果，MPRE在g=400 m的網(wǎng)格粒度下能保證預(yù)測(cè)準(zhǔn)確率較高且算法運(yùn)行時(shí)間較短，因此本文選擇在g=400 m的網(wǎng)格粒度下分配跟蹤任務(wù).結(jié)果表明以人為中心的任務(wù)選擇方法P-centric更適合本文提出的跟蹤任務(wù)分配問(wèn)題，保證任務(wù)覆蓋率的同時(shí)用戶激勵(lì)成本較小且算法的運(yùn)行時(shí)間更短，能有效地實(shí)現(xiàn)目標(biāo)實(shí)時(shí)跟蹤.

未來(lái)的工作主要包括2方面：1)考慮基于固定部署攝像頭與基于移動(dòng)群智感知的目標(biāo)跟蹤方法相結(jié)合，更好地利用城市中現(xiàn)有的資源，降低目標(biāo)跟蹤的成本；2)要結(jié)合圖像處理方法來(lái)輔助用戶快速定位目標(biāo)，降低用戶參與負(fù)擔(dān).