Wavefront algoritme

Dit artikel is vertaald van http://www.societyofrobots.com/programming_wavefront.shtml

Robot mapping en navigatie 
De theorieën achter robot doolhof navigatie zijn enorm. Dus om het simpel te houden leer je in deze tutorial  een van de meest elementaire, maar nog steeds krachtige methodes van de intelligente robot navigatie.

Stap 1: Maak een Kaart 
Maak een XY-grid-matrix om de lege ruimte, robot / doel locaties, en obstakels te markeren.

Bijvoorbeeld, dit is een foto van mijn keuken. De doos is een obstakel.

Vervolgens leggen we hier een raster overheen

Vervolgens heb ik de grenzen (rood) onbegaanbaar verklaard, evenals gebieden die zijn  geblokkeerd door rood.

Maar dit is natuurlijk niet wat het echt uit ziet in de robot geheugen. In plaats daarvan lijkt veel meer op deze matrix hieronder.  0=onbegaanbaar  R=robot .

Opmerking: In mijn broncode Ik gebruikte de onderstaande waarden. Mijn voorbeelden zijn hier net vereenvoudigingen, zodat u gemakkelijker kunt algoritme begrijpen van de golffront. 

 / / Wavefront Variabelen
 int niets = 0;
 int muur = 255;
 int doel = 1;
 int robot = 254;

Een voorbeeld van een kaart matrix in C ziet er als volgt uit: 

 / / X horizontaal is, Y is verticale int kaart [6] [6] = {{0,0,0,0,0,0}, {0,0,0,0,0,0}, {0, 0,0,0,0,0}, {0,0,0,0,0,0}, {0,0,0,0,0,0}, {0,0,0,0,0, 0}}; 

Stap 2: Voeg  Doel en Robot Locaties toe
Volgende moet de robot zijn doellocatie kiezen, G . We gaan ervan uit dat deze robot kan alleen 90 graden draaien.

In mijn broncode noem ik deze functie: 
new_state = propagate_wavefront (robot_x, robot_y, goal_x, goal_y);

robot_x en robot_y markeert de robots 'coördineert, en goal_x en goal_y is natuurlijk het doel locatie.

Stap 3: Vul Wavefront 
Dit is waar het wordt een beetje moeilijk zo kaal met mij hier. In een notendop het algoritme zal controleren node node, beginnend in de linkerbovenhoek, welke knooppunten het ligt naast.Negeer muren, kijk naar knooppunten rond uw doelgroep node, dan tellen op. Bijvoorbeeld, als een aangrenzend knooppunt heeft de nummer 5, en zijn de laagste grenzend node, maak doelnode een 6. Houd het scannen van de matrix tot de robot node grenst aan een nummer. Na deze pseudocode Ziek toon u grafische voorbeelden.

Pseudocode:

 check knooppunt A op [0] [0]

 Nu het noorden kijken, zuiden, oosten en westen van dit knooppunt
	 (Boundary nodes)

 if (grens knooppunt is een muur)
	 negeer dit knooppunt, ga naar de volgende node B

 else if (grens node is robot locatie & & heeft een aantal in)
	 pad gevonden!
	 vind de grens knoop met het kleinste aantal
	 rendement dat richting robotbesturing
	 robot wordt verplaatst naar dat nieuwe knooppunt

 else if (grens node heeft een doel)
	 Mark node A met de nummer 3

 else if (grens node is gemarkeerd met een nummer)
	 vind de grens knoop met het kleinste aantal
	 Mark node A met (kleinste getal + 1)

 if (pad vond geen)
	 Ga naar de volgende node B op [0] [1]
	 (Een soort door de gehele matrix in volgorde)

 if (geen pad nog steeds gevonden na een volledige scan)
	 Ga naar een knooppunt in [0] [0]
		 (Beginnen, maar niet duidelijk kaart)
	 (Een soort door de gehele matrix in volgorde)
	 Herhaal dit totdat het pad gevonden

 if (geen pad nog steeds gevonden & & matrix is vol)
	 Dit betekent dat er geen oplossing
	 duidelijke hele matrix van obstakels en opnieuw beginnen
	 Dit verklaart voor bewegende objecten!  adaptiviteit!

Hier is een grafisch voorbeeld. Het doel en de robot locaties zijn al gemarkeerd op de kaart. Nu door de matrix een knooppunt in een tijd, ik heb al gescand door de eerste 2 kolommen (X). Op kolom 3, gescande ik het over halverwege tot ik bereikte de 5e node. Het controleren van grenzen knooppunten is het naast het doel. Dus ik merk dit knooppunt met een 3, zoals afgebeeld.

Voortbordurend op de 3e kolom, blijf ik naar beneden node node. Ik check voor de aangrenzende knooppunten, en voeg +1 om de doelnode. Zoals je kunt zien, de rest van de kolom krijgt de ingevuld de 'wave' actie mededeling, maar toch? Dit is de reden waarom het is wel een golffront. Het is ook wel de Brushfire algoritme omdat het verspreidt zich als een Brushfire. . .

Ga nu naar de 4e kolom en controleert elk knooppunt. Wanneer je naar de 4e rij, je doelnode grenst aan het doel. Markeer deze met een 3. Dan blijven scannen naar beneden. Negeer het doel, en negeer muren. Op de 9e rij, zult u merken de doelnode de grenzen van de nummer 7 aan de linkerkant. Het is de laagste waarde grenzend node, dus 7 + 1 = 8. Markeer dit doelnode als 8.

Dan zal het de 10e rij u merkt dat de doelnode is de robot locatie. Als de robot locatie grenst aan een gevuld in aantal (in dit geval, het nummer 8) dan het algoritme is voltooid. Een volledige pad is gevonden!

Stap 4: Direct robot Count Down 
Nu er een oplossing bestaat, vertel uw robot vierkante rijden naar het met het huidige aantal min een. In dit geval, de huidige nummer was 9, dus de robot moet rijden om 8 vierkante. Er zijn meerdere pleinen gelabeld 8, zodat de robot kan gaan om een van beide. In dit geval de 8 vierkante aan de linkerkant is meer optimaal omdat het resulteert in minder rotaties van de robot. Maar voor de eenvoud, het maakt echt niet uit.

Dan hebben je robot naar vak 7, dan vak 6, dan 5, en zo verder. Je robot zal rechtdoor naar het doel zo.

Adaptieve Mapping 
Voor adaptieve mapping, je robot niet altijd weet waar alle hindernissen zich bevinden. In dit geval, zal het vinden van werk een 'oplossing' zou dat eigenlijk niet. Misschien is het niet zie alle obstakels, of misschien iets in de omgeving verplaatst? dus wat je doet is:

1) heb je robot te scannen na elke zet het maakt 
2) update van de kaart met nieuwe of verwijderd obstakels 
3) re-run van de golffront algoritme 
4) en vervolgens reageren op de nieuwe, bijgewerkte oplossing.

Als er geen oplossing wordt gevonden bij alle, obstakels te verwijderen van uw kaart tot een oplossing is gevonden. - In mijn broncode, de robot verwijdert alle belemmeringen wanneer er geen oplossing wordt gevonden niet altijd wenselijk, maar het werkt.