Vector Field Histogram

Het Vector Field Histogram (VFH) is een real time algoritme dat werd voorgesteld door Johann Borenstein en Yoram Koren in 1991.^[1] Dit algoritme is oorspronkelijk gebaseerd op de VFF-methode (Virtual force field-algoritme). Deze methode is uiteindelijk ontwikkeld omdat er tekortkomingen waren aan de VFF-methode. De VFF-methode is namelijk minder resistent tegen foutieve waarnemingen van sensoren. De VFH-methode daarentegen houdt ook rekening met vorige waarnemingen waardoor de kans kleiner is dat foutieve metingen de richting van de robot beïnvloeden. In 1998 is VFH nog aangepast door Iwan Ulrich en Johann Borenstein en is hernoemd naar VFH+ ^[2] en later nog geüpdatet tot VFH*.

VFF

Deze afbeelding toont de werking van het VFF-algoritme. Ft vormt de aantrekkingskracht van de robot tot het doelwit. De zekerheidswaarden van objecten in bepaalde cellen worden opgeteld om een afstotende kracht Fr. De route van de robot, R, wordt dan berekend door het samenvoegen van deze krachten.

Het Virtual force field-algoritme is de voorloper van de VFH-methode en vormt hiervoor ook de basis. De eerste stap is het aanmaken van een Cartesiaanse histogram grid waarin sensordata zal bepalen in welke cellen de meeste kans is om een object tegen te komen. Vervolgens zal de robot van dit histogram een aantal cellen selecteren, het “active window”. Elk van deze cellen zal een bepaalde afstotende kracht krijgen bepaald door de zekerheid van een object in die cel en de afstand van de robot tot die cel. De opsomming van al deze krachten levert een totale afstotende kracht op. Tegelijkertijd wordt ook rekening gehouden met de aantrekkende kracht die de robot naar het doelwit toetrekt. Wanneer deze krachten gecombineerd worden, wordt de richting die de robot moet rijden bekomen. Het probleem met deze methode was dat een robot die dit algoritme volgde niet in staat was om door smalle deuren en doorgangen te rijden. Anderzijds is het algoritme ook zeer gevoelig voor foutieve metingen waardoor de robot grote afwijkingen kan krijgen op de optimale route.

VFH

Omdat het VFF-algoritme de data die het verkrijgt van het histogram direct omrekent naar een afstotende kracht, raakt vorige data van de omgeving verloren waardoor het algoritme zeer gevoelig is voor foutieve metingen. Hierdoor zal de robot bij foutieve metingen sterk afwijken en vaak veilige smallere routes vermijden waardoor deze niet kan gebruikt worden om door een deur te rijden. Daarom is de VFH-methode ontwikkeld die werkt met 3 lagen van data in plaats van de 2 lagen van de VFF-methode.

De eerste laag van data is identiek aan dat van de VFF-methode. Bij VFH wordt ook een Cartesiaans histogramgrid gebruikt die data verzamelt van de omgeving om een voorstelling van de obstakels te kunnen maken.
Er wordt een eendimensionaal polair histogram aangemaakt dat bestaat uit sectors met een bepaalde hoek elk met polar obstacle density-waarde. Deze waarden worden bepaald met behulp van het vorige histogram.
De laatste laag bestaat eruit om de richting en snelheid van de robot te bepalen met behulp van de vorige lagen.

Polair histogram

Net zoals bij VFF wordt er een gebied rondom de robot gebruikt om berekeningen te maken. De cellen van het histogramgrid worden bij VFH echter behandeld als een obstakelvector. Voor alle berekeningen wordt de afstand gebruikt tussen het robotcentrumpunt (RCP) en de actieve cel. De magnitude van de obstakelvector wordt dan bepaald met behulp van deze afstand en de zekerheidswaarde van de actieve cel. De volgende formule wordt gebruikt om deze magnitude te bepalen.

$m_{i,j}=(c_{i,j})^{2}(a-bd_{i,j})$

Waarbij:

$a,b$ positieve constanten zijn
$c_{i,j}$ Zekerheid van actieve cel(i,j).
$d_{i,j}$ Afstand tussen de cel(i,j) en de RCP
$m_{i,j}$ Grootte van de obstakel vector in cel (i,j).

Hoe groter de afstand d is van het middelpunt van de robot tot de actieve cel, hoe kleiner de resulterende obstakel vector is. De richting van deze vector wordt weergegeven door:

$\beta _{i,j}=tan^{-1}{\frac {y_{0}-y_{j}}{x_{i}-x_{0}}}$

Waarbij:

$x_{0},y_{0}$ : De coördinaten van de RCP

$x_{i},y_{j}$ : Coördinaten van de actieve cel $C_{i,j}$ .

Voor elke sector van een bepaalde hoek α wordt een som gemaakt van alle magnitudes om zo een polar obstacle density (POD) te bekomen die als volgt bepaald wordt:

$h_{k}=\sum _{i,j}{m_{i,j}}$

Om de sturing van de robot in de volgende fase te optimaliseren wordt hierna nog een smoothing uitgevoerd.

Sturingcontrole

Deze afbeelding toont hoe de robot door een smalle gang zal rijden. De richting wordt altijd aangepast zodat de robot niet te dicht tegen objecten rijdt.

Met behulp van de POD's wordt bepaald welke gebieden geschikt zijn voor de robot om te rijden. Hiervoor wordt een bepaalde threshold gebruikt; wanneer de POD-waarde van een sector onder deze waarde zit, wordt de sector als veilig beschouwd. De robot zal zo verschillende veilige gebieden vinden om te rijden en kiest dan uiteindelijk het gebied dat hem het snelste naar het doel brengt. De richting θ waar de robot naartoe moet sturen, wordt bepaald door te kijken naar de sector die het dichtst bij de target ligt $k_{n}$ en de sector die een bepaalde maximumafstand of minder hiervandaan ligt $k_{f}$ . Wanneer de robot dan te dicht of te ver van de dichtstbijzijnde sector rijdt, wordt θ aangepast en zal de robot bijsturen. Omdat de maximum afstand tussen de dichtstbijzijnde sector en de uiterste sector kan gevarieerd worden is de robot met behulp van VFH in staat om door smalle doorgangen en deuren te gaan. De richting wordt bepaald met deze formule:

$\theta ={\frac {k_{n}+k_{f}}{2}}$

Deze techniek zorgt er ook voor dat de robot in smalle doorgangen ook een stabiele route behoudt.

Problemen

Omdat de VFH-methode slechts lokaal werkt en geen data van de gehele omgeving heeft kan de robot vast komen te zitten. In dit geval er een ander algoritme moeten overnemen om een nieuwe route te bepalen met de al verzamelde data van de histogrammen.

Latere methoden

VFH+

In 1998 is het VFH-algoritme aangepast en hernoemd naar VFH+. De volgende verbeteringen zijn ingevoerd:

Threshold hysteresis: hysteresis zorgt ervoor dat het geplande traject van de robot minder ruw is.
Robot grootte: Er moeten geen parameters meer handmatig worden aangepast bij robots van verschillende de grootte. De grootte van de robot kan worden ingegeven en de parameters zullen in proportie worden aangepast door het algoritme.
Obstacle look-ahead: Er wordt al op het voorhand gekeken waar objecten gelegen zijn waardoor de robot nooit in de richting van een object zal sturen. Dit zorgt voor een efficiëntere route.

Zie ook

Bronnen, noten en/of referenties

↑ Borenstein, J., Koren, Y. (1991). The vector field histogram-fast obstacle avoidance for mobilerobots. Robotics and Automation, IEEE Transactions on 7 (3): 278–288. DOI: 10.1109/70.88137. Geraadpleegd op 30 juni 2008.
↑ Ulrich, I., Borenstein, J. (1998). VFH+: reliable obstacle avoidance for fast mobile robots 2.

[Borenstein1991-1] Borenstein, J., Koren, Y. (1991). The vector field histogram-fast obstacle avoidance for mobilerobots. Robotics and Automation, IEEE Transactions on 7 (3): 278–288. DOI: 10.1109/70.88137. Geraadpleegd op 30 juni 2008.

[VFH+-2] Ulrich, I., Borenstein, J. (1998). VFH+: reliable obstacle avoidance for fast mobile robots 2.

[1]

[2]