《追狗，從入門到精通》

作者：望墨溢（西北工業(yè)大學(xué) 航海學(xué)院）

文章來源于科學(xué)大院公眾號（ID：kexuedayuan）

——

你是否好奇過，人類的機(jī)器（飛船、導(dǎo)彈、魚雷）是怎么“看”到目標(biāo)的？是像吃雞中那樣用“眼睛”瞄目標(biāo)么？最初的機(jī)器是這樣看世界的，可從阿波羅飛船開始，借助一些新奇的“眼睛”，人類開始看到了一個(gè)又一個(gè)不一樣的世界。機(jī)器的眼睛，就是目標(biāo)跟蹤算法了。

算法是怎么回事？為了關(guān)愛沒學(xué)過算法的朋友，我們將用故事《追狗，從入門到精通》來說明~

（圖片來源：作者繪制）

追狗入門篇:“瞄”哪打哪——尾追法

如果你要提著菜刀去收拾一條剛拆完家的二哈，你會采取什么方法追上它呢？大概會是這樣的策略（算法，Algorithm）：

(1)你用眼睛看它在什么位置（量測，Measurement。對，搞科研的喜歡把AB叫BA，以顯得高大上，例如還有把“簡約”叫“約簡”，把“積累”叫“累積”），你就朝向它跑；

(2)如果它也在動，你每隔一段時(shí)間，根據(jù)它最新的位置，調(diào)整自己的方向（更新，Update）；

(3)如果它跑步是有規(guī)律的（先驗(yàn)信息，Priori Information，也就是已知的信息），例如勻速直線地朝狗窩跑，你還可以直接到它的必經(jīng)之路去堵它（預(yù)測，Prediction）。

（圖片來源：作者繪制）

(4)如果你倆一直在靠近（收斂，Converge），當(dāng)某項(xiàng)數(shù)值（追狗這件事是看距離）低于預(yù)先設(shè)定好的指標(biāo)（門限，Threshold），直接撲過去或者扔菜刀（結(jié)束）。

你用來追殺兇狗的算法，曾經(jīng)被人類用在了最初的導(dǎo)彈、魚雷上，這就是目標(biāo)跟蹤中最簡單的“尾追法”。那時(shí)人類的機(jī)器跟蹤目標(biāo)，就跟吃雞時(shí)我們用倍鏡鎖定對手一樣：瞄。

（圖片來源：作者繪制）

追狗提高篇:已知狗的路線——Kalman濾波器

隨著技術(shù)的進(jìn)步，對目標(biāo)跟蹤精度的要求越來越高，尤其是在航空航天領(lǐng)域，例如在太空執(zhí)行任務(wù)，幾厘米的差距就可能會造成嚴(yán)重的后果（你也想遠(yuǎn)遠(yuǎn)地鏢那條狗18刀，刀刀避開要害，但差1厘米可能就要了你的狗的命）。

這里有個(gè)問題，看到了就是看到了，怎么還有精度這一說法？實(shí)際上，任何量測都有誤差（量測噪聲，Measurement Noise），且誤差還是隨機(jī)數(shù)，我們只可能知道誤差的概率分布，卻不知道誤差具體的值（否則用量測值減去誤差不就完了，還研究什么算法？）。

例如，你突然想起平日里買狗糧，包裝袋上寫著“10Kg±500g”，就是在講：一袋狗糧重10Kg，但由于各種因素，實(shí)際可能剛夠，也可能少了若干g，也可能多若干g，但多與少都不會大于500g。

（圖片來源：作者繪制）

同時(shí)，目標(biāo)運(yùn)動也是有噪聲的（狗以為它逃跑路線是直線，但其實(shí)也有誤差的），通常把這個(gè)誤差叫過程噪聲（Process Noise）。若已知狗的潛逃路線（運(yùn)動模型，Motion Model）以及過程噪聲和量測噪聲的概率分布，那么就可以改進(jìn)追狗的算法：

(1)上一時(shí)刻：如果已知上一時(shí)刻狗跑到了狗窩處，但就像狗糧的“10Kg±500g”一樣，這一位置是有誤差的，比如說方差為1cm2的誤差（具體值是多少不知道，但概率分布知道）；

(2)預(yù)測：按照運(yùn)動模型（假設(shè)勻速直線運(yùn)動），它當(dāng)前時(shí)刻應(yīng)該跑到冰箱處，但由于它腦子不好使，其實(shí)這一過程是有方差為5cm2的誤差（依舊具體值是多少不知道，但概率分布知道）。由于上一時(shí)刻狗窩的方差是1cm2，因此冰箱處實(shí)際方差應(yīng)該是1+5=6 cm2；

（圖片來源：作者繪制）

(3)量測：若人眼看到它在電視處，但這個(gè)量測是有方差為10cm2的誤差（同上）；

(4)狀態(tài)更新：這兩個(gè)信息（預(yù)測和量測）都不完全可信，但可以知道，預(yù)測相對于量測更可信，因?yàn)轭A(yù)測的誤差方差?。?cm2