蟲仔演算法

出自維基百科,自由嘅百科全書

蟲仔演算法英文Bug algorithms)係統稱啲演算法係幫機械人或者話智能體運動規劃嘅,因爲係模仿啲蟲仔爬而得名。戥啲一般嘅路徑規劃演算法嘸同、啲一般需要假設到全局智識嘅,啲蟲仔演算法衹會考慮到啲從隻環境獲取嘅局部智識,再佮上一隻全局嘅目的地就可以進行得規劃。[1]

概述[編輯]

試惗睇隻機械人係喺一柵有界嘅工作空間、裏頭有一堆有限數厏埞嘢、堆嘢本身範圍亦都係有限噶,一噉隻機械人嘅自由空間佢得喺裏頭喐噶就係工作空間扣除啲厏埞嘢,而佢出發點到目的地條直線都衹會着有限隻厏埞嘢隔開;噉樣嘅空間就喊得做一隻合理嘅空間。對於機械人自身來講,首先全局來睇佢識得自己係喺隻目的地嘅乜嘢方向,同埋時時度到佢戥隻目的地有幾遠;同時佢啲感知能力又要幫佢睇(感測)得到四周圍啲厏埞嘢佢有可能會撞到嘅。喺撞到一䊆厏埞嘢嗰陣嘅粒點係「撞點」(hit point,),對應嘅行遠䊆厏埞嘢粒點就係「誃點」(leave point,)。根據處理啲厏埞嘢嘅嘸同策略,可以有幾種演算法嘅例。

Bug 0[編輯]

Bug 0演算法係作爲示例嘅最簡單演算法。簡單嚟講就係往隻目標行,撞親一個厏埞嘢就跟到個嘢嘅邊界(牆)行,直到再行近得到隻目標多啲。

個演算法嘅問題係對於一啲螺旋形嘅牆、目標喺牆裏頭嘅,隻機械人就可能有機會一直跟住個外牆行,而嘸會入到螺旋牆中心。

Bug 1[編輯]

Bug 1係遞種演算法,作爲對Bug 0 嘅補充,追求嘅係圍住個厏埞嘢廓一成圈返到原本撞點,當中檢測喺條路徑上高粒點係距離隻目標點最近嘅作爲誃點,然之後返到粒誃點嚟行開個厏埞嘢。喺一種特殊嘅情況下(譬如韞個機械人喺封閉牆入便、目標擺牆外),個機械人會撞返之前測過嘅路徑,噉樣理應畀到信息係「冇啱路徑」。個演算法可以避免略過一啲牆係局部檢測未必一次性就檢測得到嘅(似上文嗰種螺旋牆嘅內牆),但可能會拉長成條路徑嘅長度。由於最多個機械人會廓一個厏埞嘢一圈(畫路徑)加一半(返誃點),冇可能再多,所以總共路徑長度有返一條公式畀到個上限:

其中,

係開始點到目標嘅直線距離;
係嘸同厏埞嘢嘅週長。

Bug 2[編輯]

Bug 2又係一種演算法,係針對Bug 1 嘅模改。Bug 2演算法會根據同目標嘅方向設一條m直線(m-line)串埋當前點同目標。演算法要求嘅係跟返條m直線行,撞親厏埞嘢嗰陣就廓最多半圈䊆厏埞嘢,直至行返到條m直線上(可能會喺初始點同目標嘅對面),嗰陣距離目標要近過之前行離條m直線陣時(誃點要近目標近過撞點);噉直線同輪廓線嘅兩隻交點,查實就係機械人喺䊆厏埞嘢嘅撞點同埋誃點。由於有要求到每次嘅誃點至少都要离目標點要近過撞點,所以厏埞嘢厏唨m直線兩次嘅話,兩次撞點都會喺同一䊆好長嘅厏埞嘢上高,第二次搵誃點可能反而要廓長多啲嘅路廓過同一䊆厏埞嘢;噉樣雖然可以避免行外牆而嘸入內牆嘅問題(似Bug 0案例會有嘅),但會令到路徑長度估計公式當中會多一項記厏埞嘢同m直線相交嘅次數。所以,總共路徑長度上限公式係:

其中,

係開始點到目標嘅直線距離;
係嘸同厏埞嘢嘅週長。
係嘸同厏埞嘢同m直線相交嘅次數。

由於有呢個,所以喺某啲特殊情況下,Bug 2 條路徑反而可能長過Bug 1嘅。

切線Bug[編輯]

切線Bug(Tangential Bug)係描述啲更加現實嘅機械人嘅,其中有考慮到啲非觸覺、有一定範圍嘅傳感器似超聲波傳感器之類。喺一個圓範圍之內,機械人識檢測到視野當中啲厏埞結構嘅消失點(可以係結構嘅尖頂或者話牆角,亦可以係結構伸出視野之外),沿住條切線切過啲消失點佢可以透得過去行到視野邊界;喺向消失點亦即係局部目標行近嗰陣,佢可能可以直接廓得過隻厏埞結構,又可能會繼續睇到更加多啲牆嘅部份、同時更新啲結構訊息同埋個消失點位置作爲新嘅局部目標。噉樣佢就嘸使直直戾上啲結構先改變佢個方向,而可以提前獲得個牆角嘅方向、圓滑噉轉彎嚟廓過去。

[編輯]

  1. Choset, Howie. Robotic Motion Planning: Bug Algorithms (PDF). Carnegie Mellon University.