目標(biāo)搜索中的步長(zhǎng)改變比率臨界值仿真研究

張國(guó)超，王儉

（1.蘇州中軟國(guó)際科技服務(wù)有限公司，江蘇蘇州215123；2.蘇州科技學(xué)院電子與信息工程學(xué)院，江蘇蘇州215009）

目標(biāo)搜索中的步長(zhǎng)改變比率臨界值仿真研究

張國(guó)超1，王儉2

（1.蘇州中軟國(guó)際科技服務(wù)有限公司，江蘇蘇州215123；2.蘇州科技學(xué)院電子與信息工程學(xué)院，江蘇蘇州215009）

針對(duì)變步長(zhǎng)目標(biāo)搜索任務(wù)中的步長(zhǎng)改變比率的確定問(wèn)題，采用計(jì)算機(jī)仿真手段，在均勻和非均勻兩種土質(zhì)對(duì)應(yīng)的氣味源擴(kuò)散及氣味濃度場(chǎng)分布情況下，驗(yàn)證了機(jī)器人六邊形變步長(zhǎng)目標(biāo)搜索問(wèn)題中初始步長(zhǎng)改變比率滿足的一個(gè)約束不等式，進(jìn)而找到一個(gè)新的更準(zhǔn)確的聯(lián)立不等式約束關(guān)系，最后給出一個(gè)可計(jì)算的修正公式。

目標(biāo)；搜索；跟蹤；信號(hào)強(qiáng)度；步長(zhǎng)；臨界值

探測(cè)目標(biāo)發(fā)出信號(hào)的強(qiáng)度并根據(jù)測(cè)量值進(jìn)行目標(biāo)搜索、跟蹤以及定位有著越來(lái)越廣泛的應(yīng)用[1-4]?，F(xiàn)以機(jī)器人對(duì)土壤中氣味源的搜索為例，通過(guò)計(jì)算機(jī)仿真，研究搜索過(guò)程中步長(zhǎng)改變比率的取值。步長(zhǎng)改變比率指后一步與前一步兩者長(zhǎng)度之比，比率大于1，意味步長(zhǎng)增加；比率小于1，意味步長(zhǎng)較小，比率等于1，意味步長(zhǎng)不變。

Russell最早提出移動(dòng)機(jī)器人攜帶傳感器并測(cè)量自身當(dāng)前位置下土壤表層中的氣味濃度，進(jìn)而跟隨氣味濃度增大的方向?qū)ふ业叵職馕对吹亩ú介L(zhǎng)六邊形搜索策略[1]，其主要特點(diǎn)之一就是機(jī)器人自點(diǎn)n-1來(lái)到點(diǎn)n后，將根據(jù)過(guò)往測(cè)得的氣味濃度，向左或者向右轉(zhuǎn)60°，繼而行走一步的距離，前往點(diǎn)n+1或點(diǎn)n+1’（圖1a）。

圖1 六邊形搜索策略示意

文獻(xiàn)[3]對(duì)定步長(zhǎng)六邊形搜索策略進(jìn)行了改進(jìn)，提出途中階段和結(jié)束階段變步長(zhǎng)的搜索策略（圖1b），給出了具體的途中步長(zhǎng)改變比率的計(jì)算方法和公式，即機(jī)器人根據(jù)當(dāng)前（點(diǎn)n）的氣味濃度測(cè)量值和過(guò)去（點(diǎn)n-1及以往諸點(diǎn)），決定下一步行進(jìn)的方向（點(diǎn)n+1或點(diǎn)n+1'）和步長(zhǎng)（mn或mn'），改進(jìn)了搜索效果。

至于步長(zhǎng)改變比率取值的范圍，或者說(shuō)步長(zhǎng)改變比率的臨界值，文獻(xiàn)[3]通過(guò)推導(dǎo)給出了兩個(gè)不等式約束。但是，受限于參數(shù)值無(wú)法確定和預(yù)知，在實(shí)際的搜索中無(wú)法實(shí)時(shí)地精確計(jì)算兩個(gè)不等式的值，因而兩式都沒(méi)有在變步長(zhǎng)策略中得到實(shí)際應(yīng)用。所以，從理論上講機(jī)器人可能由于實(shí)際的步長(zhǎng)衰減過(guò)快而中途停止，即收斂速度過(guò)快導(dǎo)致

的問(wèn)題仍沒(méi)有徹底解決。式（1）中，d（s）表示機(jī)器人與目標(biāo)的歐氏距離，dth為目標(biāo)鄰域的半徑，s為步數(shù)。圖2清楚地表達(dá)了步長(zhǎng)改變比率過(guò)小而極易導(dǎo)致機(jī)器人在搜索途中停止的潛在可能性。

圖2 步長(zhǎng)逐步減小

文中將通過(guò)計(jì)算機(jī)仿真驗(yàn)證一個(gè)約束關(guān)系，并根據(jù)仿真對(duì)其進(jìn)行修正，從而對(duì)搜索起始步長(zhǎng)和初始步長(zhǎng)改變比率的取值有更明確的范圍，為優(yōu)化搜索策略及算法做準(zhǔn)備。

1 不等式約束的分析

文獻(xiàn)[3]給出的步長(zhǎng)改變比率k的臨界約束的兩個(gè)不等式，一個(gè)通過(guò)即時(shí)的位置和信號(hào)源強(qiáng)度表達(dá)

其中，N(·)為即時(shí)信號(hào)強(qiáng)度，N0為目標(biāo)信號(hào)強(qiáng)度，x為機(jī)器人或者說(shuō)是測(cè)量點(diǎn)與目標(biāo)的距離。另一個(gè)通過(guò)初始距離和初始步長(zhǎng)表達(dá)（見(jiàn)圖2）。

其中，m0是初始步長(zhǎng)，l是起點(diǎn)至氣味源的距離。不難看出，式（2）適用于確定搜索途中實(shí)時(shí)的步長(zhǎng)改變比率，而式（3）適用于確定搜索開(kāi)始階段的初始步長(zhǎng)改變比率。

特別地，式（3）的物理意義非常明確，就是如果初始距離越遠(yuǎn)，初始步長(zhǎng)可以越大，同時(shí)意味著初始步長(zhǎng)改變比率可以越小。而且顯然，如果假設(shè)起點(diǎn)至氣味源的初始距離已知，那么嘗試不同的初始步長(zhǎng)，則式（3）是可以驗(yàn)證的。對(duì)于式（2），由于其驗(yàn)證研究需要更多的準(zhǔn)備工作，故將留待今后適當(dāng)時(shí)機(jī)。

2 仿真工作

氣體分子在均勻土質(zhì)中的擴(kuò)散是各向一致的，形成的氣味場(chǎng)是均勻的，等強(qiáng)度線是同心圓。而非均勻土質(zhì)中的氣味場(chǎng)分布則要復(fù)雜得多[5]（見(jiàn)圖3）。

在均勻土質(zhì)和非均勻土質(zhì)兩種環(huán)境進(jìn)行仿真，統(tǒng)計(jì)得出在每種環(huán)境下，不同起始點(diǎn)和不同初始步長(zhǎng)情況下，步長(zhǎng)改變比率的臨界值，最終要證實(shí)一般非均勻土質(zhì)中機(jī)器人任意起點(diǎn)、任意方向開(kāi)始的變步長(zhǎng)搜索行為，其步長(zhǎng)改變比率確實(shí)由式（3）所約束。

圖3 非均勻土質(zhì)中的氣味場(chǎng)分布示意

2.1 仿真方案的設(shè)計(jì)

搜索策略：從任意起點(diǎn)開(kāi)始。每當(dāng)途中每?jī)刹街g的停留點(diǎn)，在左前方60°方向一個(gè)探測(cè)臂長(zhǎng)度處和右前方60°方向一個(gè)探測(cè)臂長(zhǎng)度處，各測(cè)量得到一個(gè)濃度值，然后朝濃度值較大的那個(gè)方向行進(jìn)一步。如此重復(fù)，直至與目標(biāo)距離小于預(yù)設(shè)的目標(biāo)鄰域半徑時(shí)停止搜索。

仿真方案：隨機(jī)給定起點(diǎn)坐標(biāo)、初始步長(zhǎng)、鄰域半徑（取等于初始步長(zhǎng)值），給定步長(zhǎng)改變比率。開(kāi)始搜索，同時(shí)繪制機(jī)器人搜索的軌跡，并統(tǒng)計(jì)每次搜索過(guò)程的步數(shù)、路程、最終與目標(biāo)的距離等等數(shù)據(jù)。在不同步長(zhǎng)改變比率下，多次重復(fù)。

數(shù)據(jù)記錄：需要統(tǒng)計(jì)記錄的仿真數(shù)據(jù)包括“初始距離”、“初始步長(zhǎng)”、“預(yù)設(shè)鄰域半徑”、“理論臨界值”、“步長(zhǎng)變比”、“步數(shù)”、“最終記錄”。

分析項(xiàng)目：根據(jù)式（3）計(jì)算出在氣味分布場(chǎng)中的步長(zhǎng)改變比率臨界值。根據(jù)仿真數(shù)據(jù)計(jì)算得到不同步長(zhǎng)改變比率對(duì)應(yīng)的“步數(shù)增幅”，并比較記錄的各次“步數(shù)”、“路程”和“最終距離”。

仿真步驟：任意選定起始點(diǎn)即任意給定初始距離，設(shè)定初始步長(zhǎng)，完成搜索并記錄相關(guān)數(shù)據(jù)；改變初始距離，初始步長(zhǎng)，完成搜索并記錄相關(guān)數(shù)據(jù)；重復(fù)以上步驟（見(jiàn)圖4）。

圖4 仿真流程圖

2.2 搜索的路徑及其特征

滿足式（3）的步長(zhǎng)改變比率可以保證機(jī)器人無(wú)限接近目標(biāo)，即進(jìn)入鄰域以內(nèi)（圖5a），而不滿足式（3）的步長(zhǎng)改變比率使機(jī)器人最終止步于鄰域之外（圖5b）。仿真證實(shí)，一般情況——非均勻土質(zhì)任意起點(diǎn)任意方向下的搜索均存在這一現(xiàn)象。圖6是在同一個(gè)給定的鄰域半徑下，步長(zhǎng)改變比率大于某一數(shù)值時(shí)機(jī)器人與目標(biāo)距離可以足夠接近，和步長(zhǎng)改變比率小于某一數(shù)值時(shí)機(jī)器人與目標(biāo)距離無(wú)法進(jìn)入鄰域以內(nèi)。

圖5 均勻土質(zhì)不同步長(zhǎng)改變比率的兩個(gè)搜索路徑

圖6 非均勻土質(zhì)不同步長(zhǎng)改變比率的兩個(gè)搜索路徑

3 數(shù)據(jù)分析

3.1 仿真過(guò)程與數(shù)據(jù)

3.1.1 均勻土質(zhì)仿真表1是一個(gè)仿真例數(shù)據(jù)，圖7是其中兩個(gè)關(guān)鍵數(shù)據(jù)“步數(shù)”和“最終距離”隨“步長(zhǎng)變比”的變化曲線。在該例中，初始距離取371.07個(gè)單位長(zhǎng)度，初始步長(zhǎng)和鄰域半徑均為30個(gè)單位長(zhǎng)度。

表1 均勻土質(zhì)仿真例的關(guān)鍵數(shù)據(jù)

圖7 均勻土質(zhì)中步長(zhǎng)改變比率對(duì)應(yīng)的搜索步數(shù)和最終距離

3.1.2 非均勻土質(zhì)仿真表2是一個(gè)仿真例數(shù)據(jù)，圖8是該例中“步數(shù)”和“最終距離”隨“步長(zhǎng)變比”的變化曲線。

表2 非均勻土質(zhì)仿真例關(guān)鍵數(shù)據(jù)

圖8 非均勻土質(zhì)中步長(zhǎng)改變比率對(duì)應(yīng)的搜索步數(shù)和最終距離

3.2 仿真數(shù)據(jù)分析

在文中全部仿真中，目標(biāo)氣味源的源濃度取5，起始點(diǎn)在距離目標(biāo)476.34范圍內(nèi)任意選取，初始步長(zhǎng)在30～50之間任意選取，濃度偏差在2.180 715以內(nèi)任意選取，所有仿真結(jié)果呈現(xiàn)完全一致的規(guī)律，所以文中僅對(duì)上節(jié)所舉均勻和非均勻土質(zhì)氣味源擴(kuò)散的兩例仿真結(jié)果及數(shù)據(jù)進(jìn)行分析。

3.2.1 均勻土質(zhì)仿真例分析從表1和圖7看，當(dāng)“步長(zhǎng)變比”減至0.931時(shí)，“最終距離”——搜索的最終停止地點(diǎn)離目標(biāo)的距離——就大于鄰域半徑了。同時(shí)，“步數(shù)”也從97躍增到216。也就是說(shuō)，行進(jìn)了極大的步數(shù)值也無(wú)法足夠接近目標(biāo)。結(jié)論是：實(shí)際的步長(zhǎng)變比值必須大于0.931。

考慮到鄰域半徑的選取具有人為因素，因此再觀察“最終距離”從0.52激增至13.99所對(duì)應(yīng)的“步長(zhǎng)變比”值，可看出，鄰域半徑取1個(gè)單位長(zhǎng)度是一個(gè)足夠小的值，可以認(rèn)為選取鄰域半徑為1就是消除了人為因素。于是得結(jié)論：實(shí)際的步長(zhǎng)變比值必須大于0.935。

3.2.2 非均勻土質(zhì)仿真例分析從表2和圖8看，當(dāng)“步長(zhǎng)變比”從0.949減至0.948時(shí)，“最終距離”相應(yīng)地從24.24增加為39.63，即大于鄰域半徑。但是，僅憑借是否停止于鄰域以內(nèi)（或以外）作為判斷步長(zhǎng)變比臨界值的理由，顯然是不夠有力的。且不說(shuō)鄰域半徑的選取是人為因素，剛剛跑進(jìn)鄰域就停止和止步于鄰域外咫尺之遙，其實(shí)并沒(méi)有根本差異。即0.948作為臨界值的理由不充分。

同時(shí)注意到，當(dāng)“步長(zhǎng)變比”從0.95減至0.949時(shí)，“步數(shù)”和“最終距離”兩者有一個(gè)同步的較大幅度躍增，尤其是“最終距離”從一直小于3躍增到24.24。換言之，此例中鄰域半徑選取為3是合理的。結(jié)論是：實(shí)際的步長(zhǎng)變比值必須大于0.949。

4 新的約束關(guān)系

前述分析表明，無(wú)論均勻或非均勻土質(zhì)中，普遍存在一個(gè)關(guān)于幾個(gè)臨界值大小關(guān)系的聯(lián)立不等式如下

其中，ksub是依據(jù)“最終距離”數(shù)據(jù)是否大于人為選取鄰域半徑得出的臨界值，kobj是依據(jù)“最終距離”數(shù)據(jù)是否出現(xiàn)顯著永久性躍增得出的臨界值。kobj根據(jù)實(shí)際數(shù)據(jù)的客觀規(guī)律，不受人為主觀因素影響。

在表1和圖7對(duì)應(yīng)的均勻土質(zhì)仿真例中，k為0.929，ksub為0.931，kobj為0.935，滿足式（4）。在表2和圖8對(duì)應(yīng)的非均勻土質(zhì)仿真例中，k為0.941，ksub為0.948，kobj為0.949，也滿足式（4）。

合理的解釋是：仿真獲得的搜索路徑不可能是徑直走向目標(biāo)的，會(huì)有一定的曲折即通俗所說(shuō)的彎路，且越是實(shí)際濃度分布場(chǎng)則彎路越明顯，所需步數(shù)比理論假設(shè)徑直走向目標(biāo)路徑的步數(shù)要多，步長(zhǎng)自然要經(jīng)過(guò)更多次的縮短，將會(huì)更快地趨于零，更容易導(dǎo)致搜索中途停止。換言之，要保證搜索不會(huì)停止在中途，必須取更大的步長(zhǎng)變比值。可以說(shuō)，式（4）是比式（3）更準(zhǔn)確的約束不等式。

但是，式（4）存在不便于計(jì)算的缺陷。實(shí)用上要想預(yù)先通過(guò)計(jì)算得到實(shí)際濃度場(chǎng)分布下的步長(zhǎng)變比臨界值，仍然是對(duì)式（3）進(jìn)行修正，見(jiàn)式（5）。

在文中所設(shè)條件下及相應(yīng)的全部仿真數(shù)據(jù)，修正系數(shù)ρ取1.1是保險(xiǎn)的。

5 結(jié)語(yǔ)

文中通過(guò)計(jì)算機(jī)仿真，證實(shí)了在均勻和非均勻兩種土質(zhì)對(duì)應(yīng)的氣味源擴(kuò)散及氣味濃度場(chǎng)分布情況下，機(jī)器人六邊形變步長(zhǎng)目標(biāo)搜索問(wèn)題中初始步長(zhǎng)改變比率滿足的一個(gè)約束不等式的基本正確性，并根據(jù)仿真結(jié)果對(duì)該不等式進(jìn)行了拓展，得到新的聯(lián)立不等式約束，最后根據(jù)仿真數(shù)據(jù)，給出了實(shí)用的臨界值修正公式。

這個(gè)結(jié)果與目標(biāo)距離預(yù)估的結(jié)果相結(jié)合，將會(huì)對(duì)搜索初始階段的初始步長(zhǎng)選擇和步長(zhǎng)變比選擇有指導(dǎo)作用，為搜索的優(yōu)化起到幫助。該文后續(xù)工作將包括：參考有關(guān)研究者的成果[4，6]，對(duì)目標(biāo)距離進(jìn)行預(yù)估；尋找具有普適性的修正系數(shù)取值；對(duì)式（2）刻畫的臨界值不等式約束進(jìn)行研究。

參考文獻(xiàn)：

[1]Russell R A.Robotic location of underground chemical sources[J].Robotic，2004，22（1）：109-115.

[2]孟慶浩，李飛.主動(dòng)嗅覺(jué)研究現(xiàn)狀[J].機(jī)器人，2006，28（1）：89-96.

[3]王儉，季劍嵐，陳衛(wèi)東.基于行為特征的機(jī)器人變步長(zhǎng)氣味源搜索算法[J].系統(tǒng)仿真學(xué)報(bào)，2009，21（17）：5427-5430，5435.

[4]孟慶浩，李飛，張明路，等.湍流煙羽環(huán)境下多機(jī)器人主動(dòng)嗅覺(jué)實(shí)現(xiàn)方法研究[J].自動(dòng)化學(xué)報(bào)，2008，34（10）：1281-1290.

[5]葛衛(wèi)龍，華良洪，張曉輝，等.等步長(zhǎng)目標(biāo)搜索算法中步長(zhǎng)對(duì)搜索結(jié)果的影響[J].海軍工程大學(xué)學(xué)報(bào)，2014，26（2）：25-28.

[6]謝彥春，潘欣裕，王儉.基于場(chǎng)分布探測(cè)值多邊形匹配的搜索策略[J].計(jì)算機(jī)科學(xué)，2015，42（6A）：112-114.

Simulation of critical ratio of variant step-size in source searching

ZHANG Guochao1，WANG Jian2
（1.ChinaSoft International Technology Services Ltd.,Suzhou 215123,China;2.School of Electronic and Information Engineering,SUST,Suzhou 215009,China）

Aiming at how to determine the variant ratio of step-size in hexagon strategy for source searching,the computer simulation was used to firstly verify an inequality which constraints the initial value of the ratio of stepsize under a diffusing of odor-source in the uniform soil or non-uniform soil and the distribution of odor-concentration field,secondly a new more accurate simultaneous inequality was found,finally a calculable correction formula was given.

target;searching;tracing;signal strength;step-size;critical value

TP242.6

A

1672-0679（2015）04-0076-05

（責(zé)任編輯：盧文君）

2015-07-26

國(guó)家自然科學(xué)基金項(xiàng)目（61372146）；江蘇省高等教育教學(xué)改革研究基金（2013JSJG063）

張國(guó)超（1992-），男，江蘇丹陽(yáng)人，工程師。

王儉（1956-），男，教授，碩士，從事智能體與智能信息處理的研究，Email:wangjiansuzhou@sina.com。