VFH+ – Wikipedia

De opmaak van dit artikel is nog niet in overeenstemming met de conventies van Wikipedia. Mogelijk is ook de spelling of het taalgebruik niet in orde. Men wordt uitgenodigd deze pagina aan te passen.

Het Vector Field Histogram Plus (VFH+)[1] algoritme is een real time obstacle avoidance algoritme, en is de opvolger van het VFH (Vector Field Histogram).[2] algoritme. VFH+ is ontwikkeld voor een speciaal type mobiele robot, genaamd de GuideCane. De GuideCane is een nieuwe geleidingsinrichting voor blinden waarbij de gebruiker de GuideCane voor zich uit duwt. Wanneer de GuideCane een obstakel opmerkt, stuurt het eromheen. De gebruiker merkt de verandering van de GuideCane en kan het apparaat blindelings volgen zonder enige bewuste inspanning. Vanwege de overeenkomst in functie tussen de GuideCane en andere conventionele mobiele robots, wordt obstacle ovoidance met de VFH+ methode evengoed voor andere mobiele robots gebruikt.

Het concept van het VFH + obstacle avoidance algoritme is vergelijkbaar met het oorspronkelijke VFH algoritme. De output van dit algoritme is een map grid van de lokale omgeving, het zogenaamde histogram grid, welke is gebaseerd op de eerdere certainty grid -en de occupancy grid methoden. De VFH+ -methode maakt gebruik van een vier-fase datareductieproces om de nieuwe richting te berekenen. In de eerste drie fasen, wordt de tweedimensionale map grid gereduceerd tot eendimensionale polaire histogrammen die zijn opgebouwd rond de robot zijn locatie. In de vierde fase selecteert het algoritme de meest geschikte richting gebaseerd op het masked polar histogram en een kostenfunctie.

Het primaire Polaire Histogram[bewerken | brontekst bewerken]

De eerste data-reductiefase mapped het actieve gebied van het map grid op het primaire polaire histogram. De actieve regio is een rond venster met een diameter

ws{displaystyle w_{s}}

dat met de robot meebeweegt. De inhoud van elke actieve cel in het map grid wordt behandeld als een obstacle vector. De vector richting

bi,j{displaystyle b_{i,j}}

wordt bepaald door de richting van de actieve cel naar het robot centrum punt (RCP):

bi,j=tan1y0yjxix0{displaystyle b_{i,j}=tan^{-1}{frac {y_{0}-y_{j}}{x_{i}-x_{0}}}}

Waar :

De vector magnitude van een actieve cel

Ci,j{displaystyle C_{i,j}}

is gegeven door:

mi,j=(ci,j)2(abdi,j2){displaystyle m_{i,j}=(c_{i,j})^{2}(a-bd_{i,j}^{2})}

Waar :

En de parameters a en b worden gekozen op basis van :

abws12=1{displaystyle a-b{frac {w_{s}-1}{2}}=1}

Merk op dat

ci,j{displaystyle c_{i,j}}

exponentieel zal stijgen of dalen. Dit geeft een betrouwbaardere reeks lezingen. Hoge

ci,j{displaystyle c_{i,j}}

waarden staan voor daadwerkelijke obstakels, in tegenstelling tot lage

ci,j{displaystyle c_{i,j}}

waarden, die veroorzaakt kunnen worden door noise. De vector magnitude is ook een functie van de afstand

(di,j)2{displaystyle (d_{i,j})^{2}}

. Indien de bezette cellen dicht bij de robot zijn, zullen ze grotere vector grootheden aannemen. Een handige eigenschap van deze functie is dat deze rotatiesymmetrisch is ten opzichte van de RCP. Hierdoor is het gedrag van de robot onafhankelijk van de richting waarin obstakels worden ontmoet. Gebaseerd op de obstacle vectoren wordt het primaire polaire histogram

Hp{displaystyle H_{p}}

opgebouwd.

De oorspronkelijke VFH methode hield niet expliciet rekening met de breedte van de robot. In plaats daarvan werd een empirisch bepaalde laagdoorlaatfilter gebruikt om de breedte van de robot te compenseren. Maar zelfs met een goede afgestemde filter had de robot toch de neiging om hoeken af te snijden. De VFH+ methode daarentegen gebruikt een theoretisch bepaalde laagdoorlaatfilter ter compensatie. Obstacle-cellen worden vergroot op de map met de robot radius

rr{displaystyle r_{r}}

. Deze radius wordt gedefinieerd als de afstand van het centrum van de robot naar haar verste punt. Voor verdere veiligheid zijn de obstakel-cellen daadwerkelijk vergroot door een straal

rr+s=rr+ds{displaystyle r_{r+s}=r_{r}+d_{s}}

waarbij

ds{displaystyle d_{s}}

de minimum afstand tussen de robot en een obstakel is. Met de obstakels vergroot door

rr+s{displaystyle r_{r}+s}

, kan de robot worden behandeld als een point-achtige auto. Deze methode werkt goed voor mobiele robots waarvan de vorm kan worden benaderd door een disk. Als vorm van de robot zeer asymmetrisch is, zullen de obstacle-cellen moeten worden uitgebreid naar de afmetingen en oriëntatie van de robot. Deze breedte compensatie methode wordt zeer efficiënt geïmplementeerd door het vergroten van de obstakels.

Voor elke cel wordt de uitbreidingshoek

gi{displaystyle g_{i}}

gedefinieerd door :

Yi,j=arcsinrr+sdi,j{displaystyle Y_{i,j}=arcsin{frac {r_{r+s}}{d_{i,j}}}}

Voor elke sector k wordt de polaire obstacle density berekend door:

Hkp=i,jCami,j.hi,j{displaystyle H_{k}^{p}=sum _{i,jin Ca}{m_{i,j}.h’_{i,j}}}

Met:

hi,j=1{displaystyle h’_{i,j}=1}

if

k.α[bi,jYi,j,bi,j+Yi,j]{displaystyle k.alpha in [b_{i,j}-Y_{i,j},b_{i,j}+Y_{i,j}]}

hi,j=0{displaystyle h’_{i,j}=0}

otherwise

Het resultaat van dit proces is een polair histogram dat rekening houdt met de breedte van de robot. De h’ functie dient ook als een low-pass filter en “smooth” het polaire histogram. Een andere belangrijke verbetering is het proces dat de moeilijke afstemming van de VFH lowpass Filter elimineert.

Het Binaire Polaire Histogram[bewerken | brontekst bewerken]

Voor de meeste toepassingen is een vlot traject gewenst en moeten oscillaties in het stuurcommando worden vermeden. De oorspronkelijke VFH methode geeft meestal een zeer smooth traject aan. De vaste drempelwaarde in de oorspronkelijke VFH methode kan echter een probleem veroorzaken bij omgevingen met meerdere smalle openingen. Zo kan bijvoorbeeld een overeenkomstige opening in het histogram meerdere malen afwisselen tussen een open en een geblokkeerde toestand tijdens een paar bemonsteringstijden. In een dergelijke situatie, kan de robot zijn keuze meermaals wisselen tussen deze smalle opening en een opening. Het resultaat is een besluiteloos gedrag, waarbij de mobiele robot problemen kan krijgen dicht bij een obstakel. Dit probleem kan eenvoudig worden verminderd door een hysteresis toe te voegen op basis van twee drempels, namelijk

tlaag{displaystyle t_{laag}}

en

thoog{displaystyle t_{hoog}}

. Op basis van het primaire polaire histogram

Hp{displaystyle H_{p}}

en de twee drempels, wordt een binair polair histogram

Hb{displaystyle H_{b}}

opgebouwd. In plaats van polaire densiteitswaarden, zijn de sectoren van

Hb{displaystyle H_{b}}

ofwel vrij (0) ofwel geblokkeerd (1). Het binaire polaire histogram wordt bijgewerkt door de volgende regels:

Hk,jb=1{displaystyle H_{k,j}^{b}=1}

if

Hk,jp>Thigh{displaystyle H_{k,j}^{p}>T_{high}}

Hk,jb=0{displaystyle H_{k,j}^{b}=0}

if

Hk,jp<Tlow{displaystyle H_{k,j}^{p}

Hk,jb=Hk,j1b{displaystyle H_{k,j}^{b}=H_{k,j-1}^{b}}

otherwise

Het masked Polar Histogram[bewerken | brontekst bewerken]

De oorspronkelijke VFH methode verwaarloost de dynamiek en de kinematica van de robot. Het veronderstelt impliciet dat de robot in staat is om de rijrichting direct te veranderen. Tenzij de robot stopt bij elke bemonstering tijd, wordt deze veronderstelling duidelijk geschonden. De VFH+ methode maakt gebruik van een eenvoudige, maar betere benadering van het traject van de meeste mobiele robots. Het gaat ervan uit dat de baan van de robot is gebaseerd op cirkelvormige bogen (constante kromming curves) en rechte lijnen. De kromming van de curve wordt gedefinieerd met k = 1 / r. De maximale traject kromming van een mobiele robot is vaak afhankelijk van de robot snelheid. Hoe sneller de robot verplaatst, hoe kleiner de maximale kromming. In bijzondere gevallen, bijvoorbeeld bij de GuideCane, kunnen de meest gebogen waarden verschillen voor bochten naar rechts en bochten naar links. De waarden voor de minimale draaicirkel als functie van de robot snelheid kunnen gemakkelijk worden gemeten. Deze radius wordt voor beide partijen gedefinieerd als

rr=1/kr{displaystyle r_{r}=1/k_{r}}

en

rl=1/kl{displaystyle r_{l}=1/k_{l}}

. Met deze parameters en het map grid, kunnen sectoren bereikt worden welke geblokkeerd zijn door obstakels.

Als een traject cirkel en een vergrote obstakel cel overlappen, zullen alle richtingen van het obstakel tot de contraire richting van de beweging, worden geblokkeerd. In een gegeven opstelling zal bijvoorbeeld obstakel A alle richtingen aan de linkerkant blokkeren vanwege de robot dynamiek. Anderzijds, zal hindernis B niet de rechterkant blokkeren. Met de originele VFH methode zou de routebeschrijving naar links van obstakel A worden beschouwd als geschikte aanwijzingen van de beweging. Met de VFH+ methode zou de robot tussen obstakels A en B gaan en zou hij een bocht naar links maken nadat hindernis A werd ontruimd.

De posities van het rechter -en linker trajectcentra ten opzichte van de huidige robot positie worden bepaald door :

Δxr=rr.sinϕ{displaystyle Delta x_{r}=r_{r}.sinphi }

Δyr=rr.cosϕ{displaystyle Delta y_{r}=r_{r}.cosphi }

Δxl=rl.sinϕ{displaystyle Delta x_{l}=-r_{l}.sinphi }

Δyl=rl.cosϕ{displaystyle Delta y_{l}=-r_{l}.cosphi }

De afstanden van een actieve cel

Ci,j{displaystyle C_{i,j}}

tot de twee traject centra worden gegeven door:

dr2(ΔxrΔx(j))2+(ΔyrΔy(i))2{displaystyle d_{r}^{2}-(Delta x_{r}-Delta x(j))^{2}+(Delta y_{r}-Delta y(i))^{2}}

dl2(ΔxlΔx(j))2+(ΔylΔy(i))2{displaystyle d_{l}^{2}-(Delta x_{l}-Delta x(j))^{2}+(Delta y_{l}-Delta y(i))^{2}}

Een obstakel blokkeert de routebeschrijving naar rechts indien:

dr2<(rr+rr+s){displaystyle d_{r}^{2}<(r_{r}+r_{r+s})}

En een obstakel blokkeert de routebeschrijving naar links indien:

dl2<(rl+rr+s){displaystyle d_{l}^{2}<(r_{l}+r_{r+s})}

Door elke actieve cel te controleren met deze twee voorwaarden, krijgen we twee maximale hoeken,

ϕr{displaystyle phi _{r}}

voor rechtse hoeken en

ϕl{displaystyle phi _{l}}

voor de linker hoeken. We definiëren ook

ϕb=θ+π{displaystyle phi _{b}=theta +pi }

als de omgekeerde bewegingsrichting. Deze methode kan zeer efficiënt worden doorgevoerd met een algoritme dat alleen rekening houdt met de cellen die een invloed hebben op beide

ϕr{displaystyle phi _{r}}

of

ϕl{displaystyle phi _{l}}

:

  • 1)Bepaal
  • 2)Voor elke cel