Bevægelsesplanlægning

lavdimensionelle problemer kan løses med gitterbaserede algoritmer, der overlejrer et gitter oven på konfigurationsrummet, eller geometriske algoritmer, der beregner Cfree ‘ s form og forbindelse.

præcis bevægelsesplanlægning for højdimensionelle systemer under komplekse begrænsninger er beregningsmæssigt uhåndterlig. Potentielle feltalgoritmer er effektive, men bliver bytte for lokale minima (en undtagelse er de harmoniske potentielle felter). Prøveudtagningsbaserede algoritmer undgår problemet med lokale minima og løser mange problemer ganske hurtigt.De er ikke i stand til at bestemme, at der ikke findes nogen sti, men de har en sandsynlighed for fiasko, der falder til nul, efterhånden som der bruges mere tid.

Prøveudtagningsbaserede algoritmer betragtes i øjeblikket som avancerede til bevægelsesplanlægning i højdimensionelle rum og er blevet anvendt på problemer, der har snesevis eller endda hundreder af dimensioner (robotmanipulatorer, biologiske molekyler, animerede digitale tegn og benede robotter).

der er bevægelse planlægning parallel algoritme (A1-A2) for objekter manipulation (for at fange den flyvende objekt).

Grid-based searchEdit

Grid-baserede tilgange overlejrer et gitter på konfigurationsrummet og antager, at hver konfiguration er identificeret med et gitterpunkt. Ved hvert gitterpunkt får robotten lov til at bevæge sig til tilstødende gitterpunkter, så længe linjen mellem dem er helt indeholdt i Cfree (dette testes med kollisionsdetektion). Dette diskretiserer sæt af handlinger, og søgealgoritmer (som en*) bruges til at finde en sti fra starten til målet.

disse tilgange kræver indstilling af en gitteropløsning. Søgningen er hurtigere med grovere gitre, men algoritmen vil ikke finde stier gennem smalle dele af Cfree. Desuden vokser antallet af punkter på gitteret eksponentielt i konfigurationsrumdimensionen, hvilket gør dem upassende til højdimensionelle problemer.

traditionelle gitterbaserede tilgange producerer stier, hvis overskriftsændringer er begrænset til multipler af en given basisvinkel, hvilket ofte resulterer i suboptimale stier. Any-vinkel sti planlægning tilgange finde kortere stier ved at udbrede oplysninger langs grid kanter (for at søge hurtigt) uden at begrænse deres stier til grid kanter (for at finde korte stier).

Gitterbaserede tilgange skal ofte søge gentagne gange, for eksempel når robotens viden om konfigurationsrummet ændres, eller selve konfigurationsrummet ændres under stien efter. Inkrementelle heuristiske søgealgoritmer genplanlægges hurtigt ved at bruge erfaring med de tidligere lignende stiplanlægningsproblemer for at fremskynde deres søgning efter den nuværende.

intervalbaseret søgning

disse tilgange ligner gitterbaserede søgemetoder, bortset fra at de genererer en brolægning, der helt dækker konfigurationsrummet i stedet for et gitter. Brolægningen er opdelt i to underlagsbelægninger. Karakterisering af Cfree beløber sig til at løse et sæt inversionsproblem. Intervalanalyse kunne således anvendes, når Cfree ikke kan beskrives ved lineære uligheder for at have en garanteret indkapsling.

robotten har således lov til at bevæge sig frit i H−, og kan ikke gå udenfor h+. Til begge subpavings er der bygget en nabo graf, og stier kan findes ved hjælp af algoritmer som Dijkstra eller a*. Når en sti er mulig i K -, er det også muligt i Cfree. Når der ikke findes en sti fra en indledende konfiguration til målet, har vi garantien for, at der ikke findes nogen mulig sti i Cfree. Hvad angår den gitterbaserede tilgang, er intervalltilgangen upassende for højdimensionelle problemer på grund af det faktum, at antallet af kasser, der skal genereres, vokser eksponentielt med hensyn til dimensionen af konfigurationsrummet.

en illustration leveres af de tre figurer til højre, hvor en krog med to frihedsgrader skal bevæge sig fra venstre mod højre og undgå to vandrette små segmenter.

nedbrydningen med subpavings ved hjælp af intervalanalyse gør det også muligt at karakterisere topologien for Cfree, såsom at tælle antallet af tilsluttede komponenter.

geometriske algoritmerrediger

Punktrobotter blandt polygonale forhindringer

• Synlighedsgraf
• celledeling

oversættelse af objekter blandt forhindringer

• Minkovski sum

find vej ud af en bygning

• fjerneste strålespor

givet et bundt stråler omkring den aktuelle position, der tilskrives deres længde, der rammer en væg, bevæger robotten sig i retning af den længste stråle, medmindre en dør identificeres. En sådan algoritme blev brugt til modellering af nødudgang fra bygninger.

kunstig potentiel fieldsEdit

en tilgang er at behandle robotens konfiguration som et punkt i et potentielt felt, der kombinerer tiltrækning til målet, og frastødning fra forhindringer. Den resulterende bane udsendes som stien. Denne tilgang har fordele ved, at banen er produceret med lidt beregning. De kan dog blive fanget i lokale minima af det potentielle felt og undlader at finde en sti eller kan finde en ikke-optimal sti. De kunstige potentielle felter kan behandles som kontinuumligninger svarende til elektrostatiske potentielle felter (behandling af robotten som en punktladning), eller bevægelse gennem feltet kan diskretiseres ved hjælp af et sæt sproglige regler.En Navigationsfunktion eller en probabilistisk Navigationsfunktion er slags kunstige potentielle funktioner, der har kvaliteten af ikke at have minimumspunkter undtagen målpunktet.

sampling-baserede algoritmerredit

Sampling-baserede algoritmer repræsenterer konfigurationsrummet med en køreplan for samplede konfigurationer.En grundlæggende algoritme prøver N konfigurationer i C, og bevarer dem i Cfree at bruge som milepæle. Derefter konstrueres en køreplan, der forbinder to milepæle P og K, hvis linjesegmentet PK er helt i Cfree. Igen bruges kollisionsdetektion til at teste inklusion i Cfree. For at finde en sti, der forbinder S og G, føjes de til køreplanen. Hvis en sti i køreplanen forbinder S og G, lykkes planlæggeren og returnerer den sti. Hvis ikke, er årsagen ikke endelig: enten er der ingen sti i Cfree, eller planlæggeren prøvede ikke nok milepæle.

disse algoritmer fungerer godt for højdimensionelle konfigurationsrum, fordi i modsætning til kombinatoriske algoritmer er deres driftstid ikke (eksplicit) eksponentielt afhængig af dimensionen af C. De er også (generelt) væsentligt lettere at implementere. De er probabilistisk komplette, hvilket betyder sandsynligheden for, at de vil producere en løsning nærmer sig 1 efterhånden som der bruges mere tid. De kan dog ikke afgøre, om der ikke findes nogen løsning.

i betragtning af grundlæggende synlighedsforhold på Cfree er det bevist, at når antallet af konfigurationer N vokser højere, nærmer sandsynligheden for, at ovenstående algoritme finder en løsning, 1 eksponentielt. Synlighed er ikke eksplicit afhængig af dimensionen af C; det er muligt at have et højdimensionelt rum med “god” synlighed eller et lavdimensionelt rum med “dårlig” synlighed. Den eksperimentelle succes med prøvebaserede metoder antyder, at de mest almindeligt set rum har god synlighed.

der er mange varianter af denne grundlæggende ordning:

• det er typisk meget hurtigere at kun teste segmenter mellem nærliggende par af milepæle, snarere end alle par.
• ikke-ensartede prøveudtagningsfordelinger forsøger at placere flere milepæle i områder, der forbedrer køreplanens forbindelse.
• Kvasirandom-prøver producerer typisk en bedre dækning af konfigurationsrum end pseudorandom-prøver, selvom nogle nylige værker hævder, at effekten af tilfældighedskilden er minimal sammenlignet med effekten af prøveudtagningsfordelingen.
• beskæftiger lokal-prøveudtagning ved at udføre en retningsbestemt Markov kæde Monte Carlo tilfældig gåtur med nogle lokale forslag distribution.
• det er muligt at reducere antallet af milepæle, der er nødvendige for at løse et givet problem, væsentligt ved at tillade buede Øjesyn (for eksempel ved at kravle på hindringerne, der blokerer vejen mellem to milepæle).
• hvis der kun er behov for en eller få planlægningsforespørgsler, er det ikke altid nødvendigt at konstruere en køreplan for hele rummet. Trævoksende varianter er typisk hurtigere i denne sag (planlægning med en forespørgsel). Køreplaner er stadig nyttige, hvis der skal foretages mange forespørgsler på det samme rum (planlægning af flere forespørgsler)

liste over bemærkelsesværdige algoritmerrediger

• A *
• D *
• hurtigt udforske tilfældigt træ
• probabilistisk køreplan