Bevegelsesplanlegging

lavdimensjonale problemer kan løses med gridbaserte algoritmer som legger et rutenett på toppen av konfigurasjonsområdet, eller geometriske algoritmer som beregner formen og tilkoblingen Til Cfree.

Eksakt bevegelsesplanlegging for høydimensjonale systemer under komplekse begrensninger er beregningsmessig ugjennomtrengelig. Potensielle feltalgoritmer er effektive, men faller byttedyr til lokale minima (et unntak er de harmoniske potensielle feltene). Sampling-baserte algoritmer unngå problemet med lokale minima, og løse mange problemer ganske raskt.De kan ikke bestemme at ingen bane eksisterer, men de har en sannsynlighet for feil som reduseres til null når mer tid blir brukt.

Sampling-baserte algoritmer er i dag ansett state-of-the-art for bevegelsesplanlegging i høydimensjonale rom, og har blitt brukt på problemer som har dusinvis eller hundrevis av dimensjoner (robot manipulatorer, biologiske molekyler, animerte digitale tegn, og legged roboter).

det er bevegelse planlegging parallell algoritme (A1-A2) for objekter manipulasjon (for å fange flygende objekt).

Gridbasert searchEdit

Gridbaserte tilnærminger overlapper et rutenett på konfigurasjonsområdet, og antar at hver konfigurasjon er identifisert med et gridpunkt. På hvert gridpunkt kan roboten flytte til tilstøtende gridpunkter så lenge linjen mellom dem er helt inneholdt I Cfree (dette testes med kollisjonsdeteksjon). Dette diskretiserer settet med handlinger, og søkealgoritmer (Som a*) brukes til å finne en sti fra start til mål.

disse tilnærmingene krever at du angir en rutenettoppløsning. Søk er raskere med grovere nett, men algoritmen vil ikke finne stier gjennom smale deler Av Cfree. Videre vokser antall poeng på rutenettet eksponentielt i konfigurasjonsplassdimensjonen, noe som gjør dem upassende for høydimensjonale problemer.

Tradisjonelle gridbaserte tilnærminger produserer baner hvis overskriftsendringer er begrenset til multipler av en gitt basevinkel, noe som ofte resulterer i suboptimale baner. Any-angle bane planlegging tilnærminger finne kortere baner ved å spre informasjon langs grid kanter (for å søke raskt) uten å begrense sine baner til grid kanter (for å finne korte baner).

Grid-baserte tilnærminger må ofte søke gjentatte ganger, for eksempel når kunnskapen om roboten om konfigurasjonsområdet endres eller konfigurasjonsområdet selv endres under banefølging. Inkrementelle heuristiske søkealgoritmer replaneres raskt ved å bruke erfaring med tidligere lignende baneplanleggingsproblemer for å øke søket etter den nåværende.

Intervallbasert searchEdit

disse tilnærmingene ligner på gridbaserte søketilnærminger, bortsett fra at de genererer en asfaltering som helt dekker konfigurasjonsområdet i stedet for et rutenett. Asfaltering er dekomponert I To subpavings X -, X + laget med bokser slik At X – ⊂ Cfree ⊂ X+. Karakterisere Cfree beløp for å løse et sett inversjon problem. Intervallanalyse kan dermed brukes når Cfree ikke kan beskrives ved lineære ulikheter for å få en garantert innkapsling.

roboten får dermed bevege seg fritt I X -, og kan ikke gå utenfor X+. Til begge subpavings, en nabo graf er bygget og baner kan bli funnet ved hjelp av algoritmer Som Dijkstra eller a*. Når en bane er mulig I X−, er Den også mulig I Cfree. Når ingen bane eksisterer I X+ fra en innledende konfigurasjon til målet, har vi garanti for at ingen mulig bane eksisterer I Cfree. Når det gjelder den gridbaserte tilnærmingen, er intervalltilnærmingen upassende for høydimensjonale problemer, på grunn av at antall bokser som skal genereres vokser eksponentielt med hensyn til dimensjonen av konfigurasjonsrom.

en illustrasjon er gitt av de tre figurene til høyre der en krok med to frihetsgrader må bevege seg fra venstre til høyre, og unngår to horisontale små segmenter.

dekomponeringen med subpavings ved hjelp av intervallanalyse gjør det også mulig å karakterisere topologien Til Cfree som å telle antall tilkoblede komponenter.

Geometriske algoritmerrediger

Punktroboter blant polygonale hindringer

• Synlighetsgraf
• celledbrytning

Oversette objekter blant hindringer

• Minkowski sum

finne veien Ut Av en bygning

• lengst strålespor

gitt en bunt stråler rundt den nåværende posisjonen som tilskrives med lengden som treffer En Vegg, beveger roboten seg i retning av den lengste strålen, med mindre en dør er identifisert. En slik algoritme ble brukt til modellering av nødutgang fra bygninger.

Kunstige potensielle feltrediger

en tilnærming er å behandle robotens konfigurasjon som et punkt i et potensielt felt som kombinerer tiltrekning til målet, og frastøting fra hindringer. Den resulterende bane er utgang som banen. Denne tilnærmingen har fordeler ved at banen er produsert med liten beregning. Imidlertid kan de bli fanget i lokale minima av det potensielle feltet og ikke finne en bane, eller kan finne en ikke-optimal bane. De kunstige potensielle feltene kan behandles som kontinuumligninger som ligner på elektrostatiske potensielle felt (behandler roboten som en punktladning), eller bevegelse gjennom feltet kan diskretiseres ved hjelp av et sett med språklige regler.En navigasjonsfunksjon eller en probabilistisk Navigasjonsfunksjon er typer kunstige potensielle funksjoner som har kvaliteten på å ikke ha minimumspunkter unntatt målpunktet.

Samplingsbaserte algoritmerrediger

Samplingsbaserte algoritmer representerer konfigurasjonsområdet med et veikart over samplede konfigurasjoner.En grunnleggende algoritme prøver N konfigurasjoner I C, og beholder de I Cfree å bruke som milepæler. Et veikart er da konstruert som forbinder to milepæler P og Q hvis linjesegmentet PQ er helt I Cfree. Igjen, dueller brukes til å teste inkludering I Cfree. For å finne en sti som forbinder S Og G, legges de til veikartet. Hvis en bane i veikartet kobler S Og G, lykkes planleggeren, og returnerer den banen. Hvis ikke, er årsaken ikke endelig: enten er det ingen bane I Cfree, eller planleggeren har ikke prøvd nok milepæler.

disse algoritmene fungerer bra for høydimensjonale konfigurasjonsrom, fordi i motsetning til kombinatoriske algoritmer, er deres kjøretid ikke (eksplisitt) eksponentielt avhengig Av dimensjonen Av C. de er også (generelt) vesentlig enklere å implementere. De er probabilistisk komplette, noe som betyr at sannsynligheten for at de vil produsere en løsning nærmer seg 1 ettersom mer tid blir brukt. De kan imidlertid ikke avgjøre om det ikke finnes noen løsning.

Gitt grunnleggende siktforhold på Cfree, har det vist seg at når antall konfigurasjoner N vokser høyere, er sannsynligheten for at ovennevnte algoritme finner en løsning nærmer seg 1 eksponentielt. Synlighet er ikke eksplisitt avhengig Av dimensjonen Av C; det er mulig å ha et høydimensjonalt rom med» god «synlighet eller et lavdimensjonalt rom med» dårlig » synlighet. Den eksperimentelle suksessen til prøvebaserte metoder antyder at mest sett mellomrom har god synlighet.

det finnes mange varianter av denne grunnleggende ordningen:

• det er vanligvis mye raskere å bare teste segmenter mellom nærliggende par milepæler, i stedet for alle par.
• Nonuniform samplingsdistribusjoner forsøker å plassere flere milepæler i områder som forbedrer tilkoblingen til veikartet.
• Kvasirandomprøver gir vanligvis en bedre dekning av konfigurasjonsrom enn pseudorandom, selv om noen nyere arbeid hevder at effekten av tilfeldighetskilden er minimal sammenlignet med effekten av prøvetakingsfordelingen.
• Benytter lokal prøvetaking ved å utføre en retningsbestemt Markov kjede Monte Carlo tilfeldig tur med noen lokale forslaget distribusjon.
• det er mulig å redusere antall milepæler som trengs for å løse et gitt problem ved å tillate buede øyesikter (for eksempel ved å krype på hindringene som blokkerer veien mellom to milepæler).
• hvis bare ett eller noen få planleggingsspørsmål er nødvendig, er det ikke alltid nødvendig å konstruere et veikart over hele rommet. Tre voksende varianter er vanligvis raskere for denne saken (single-spørring planlegging). Veikart er fortsatt nyttig hvis mange spørringer skal gjøres på samme plass (multi-spørring planlegging)

liste over kjente algoritmerrediger

• A*
• D*
• raskt utforskende tilfeldig tre
• Probabilistisk veikart