張國超，王儉

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

目標搜索中的步長改變比率臨界值仿真研究

張國超1，王儉2

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

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

目標；搜索；跟蹤；信號強度；步長；臨界值

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

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

圖1 六邊形搜索策略示意

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

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

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

圖2 步長逐步減小

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

1 不等式約束的分析

文獻[3]給出的步長改變比率k的臨界約束的兩個不等式，一個通過即時的位置和信號源強度表達

其中，N(·)為即時信號強度，N0為目標信號強度，x為機器人或者說是測量點與目標的距離。另一個通過初始距離和初始步長表達（見圖2）。

其中，m0是初始步長，l是起點至氣味源的距離。不難看出，式（2）適用于確定搜索途中實時的步長改變比率，而式（3）適用于確定搜索開始階段的初始步長改變比率。

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

2 仿真工作

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

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

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

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

搜索策略：從任意起點開始。每當途中每兩步之間的停留點，在左前方60°方向一個探測臂長度處和右前方60°方向一個探測臂長度處，各測量得到一個濃度值，然后朝濃度值較大的那個方向行進一步。如此重復，直至與目標距離小于預設(shè)的目標鄰域半徑時停止搜索。

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

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

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

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

圖4 仿真流程圖

2.2 搜索的路徑及其特征

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

但是，式（4）存在不便于計算的缺陷。實用上要想預先通過計算得到實際濃度場分布下的步長變比臨界值，仍然是對式（3）進行修正，見式（5）。

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

5 結(jié)語

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

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

參考文獻：

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

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

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

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

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

[6]謝彥春，潘欣裕，王儉.基于場分布探測值多邊形匹配的搜索策略[J].計算機科學，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

（責任編輯：盧文君）

2015-07-26

國家自然科學基金項目（61372146）；江蘇省高等教育教學改革研究基金（2013JSJG063）

張國超（1992-），男，江蘇丹陽人，工程師。

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