蟲仔演算法

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

概述

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

Bug 0

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

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

Bug 1

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

$L_{Bug1}\leq d(q_{start},q)+1.5\cdot \sum _{i=1}^{n}p_{i}$

其中，

$d(q_{start},q)$係開始點到目標嘅直線距離；

$p_{i}$係嘸同厏埞嘢$WO_{i}$嘅週長。

Bug 2

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

$L_{Bug1}\leq d(q_{start},q)+0.5\cdot \sum _{i=1}^{n}n_{i}p_{i}$

其中，

$d(q_{start},q)$係開始點到目標嘅直線距離；

$p_{i}$係嘸同厏埞嘢$WO_{i}$嘅週長。

$n_{i}$係嘸同厏埞嘢$WO_{i}$同m直線相交嘅次數。

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

切線Bug

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