Gebruiker:Kevin Jacobs/Kladblok

Het Vector Field Histogram (VFH) is een real time algoritme dat werd voorgesteld door Johann Borenstein en Yoram Koren in 1991. 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 hernoemt tot VFH+ en later nog geüpdate tot VFH*.

VFF

Deze afbeelding toont de werking van het VFF algoritme. Ft vormt de aantrekkingkracht 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 sensor data 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 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 omberekent naar een afstotende kracht raakt vorige data van de omgeving verloren waardoor het algoritme zeer gevoelig is aan 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 histogram grid gebruikt die data verzameld van de omgeving om een voorstelling van de obstakels te kunnen maken.
• Er wordt een eendimensionaal polair histogram aangemaakt die bestaat uit sectors met een bepaalde hoek elk met polar obstacle density waarde. Deze waardes 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 histogram grid worden bij VFH echter behandeld als een obstakel vector. Voor alle berekeningen wordt de afstand gebruikt tussen het middelpunt van het de robot en de actieve cel. De magnitude van het obstakel vector wordt dan bepaald met behulp van deze afstand en de zekerheidwaarde 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})$

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. 

Sturing controle

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 moet naartoe sturen wordt bepaald door te kijken naar de sector die het dichts bij de target ligt $k_{n}$ en de sector die een bepaalde maximum afstand 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 der 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 methodes

VFH+

In 1998 is het VFH algoritme aangepast en hernoemd tot 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 paramaters 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

• Bewegingsplanning
• Virtual force field-algoritme

Bronnen, noten en/of referenties

[[Categorie:Robotica]] [[Categorie:Algoritme]]