Liikesuunnittelu

Pieniulotteiset ongelmat voidaan ratkaista ruudukkopohjaisilla algoritmeilla, jotka peittävät ruudukon konfiguraatioavaruuden päällä, tai geometrisilla algoritmeilla, jotka laskevat Cfreen muodon ja liitettävyyden.

suuriulotteisten järjestelmien tarkka liikesuunnittelu monimutkaisten rajoitteiden alaisena on laskennallisesti hankalaa. Potentiaalikenttäalgoritmit ovat tehokkaita, mutta joutuvat paikallisten minimien saaliiksi (poikkeuksena ovat harmoniset potentiaalikentät). Näytteenottoon perustuvat algoritmit välttävät paikallisten minimien ongelman ja ratkaisevat monet ongelmat melko nopeasti.He eivät pysty päättelemään, ettei polkua ole olemassa, mutta heillä on epäonnistumisen todennäköisyys, joka laskee nollaan, kun aikaa kuluu enemmän.

näytteenottoon perustuvia algoritmeja pidetään nykyisin huippumodernina liikesuunnittelussa suuriulotteisissa tiloissa, ja niitä on sovellettu ongelmiin, joilla on kymmeniä tai jopa satoja ulottuvuuksia (robottimanipulaattorit, Biologiset molekyylit, animoidut digitaaliset hahmot ja jalkaiset robotit).

on olemassa liikesuunnittelun rinnakkaisalgoritmi (A1-A2) objektien manipulointiin (lentävän esineen nappaamiseen).

Grid-based searchEdit

Grid-based approachs overlay a grid on configuration space, ja oletetaan, että jokainen konfiguraatio on samaistettu hilapisteellä. Jokaisessa ruudukon pisteessä robotti saa siirtyä viereisiin ruudukon pisteisiin, kunhan niiden välinen viiva on täysin Cfree: n sisällä (tätä testataan törmäystunnistuksella). Tämä discretizes joukon toimia, ja hakualgoritmeja (kuten*) käytetään löytää polku alusta maaliin.

nämä lähestymistavat edellyttävät hilaresoluution asettamista. Haku on nopeampaa karkeammilla ruudukoilla, mutta algoritmi ei löydä polkuja Cfree: n kapeiden osien läpi. Lisäksi ruudukon pisteiden määrä kasvaa eksponentiaalisesti konfiguraatioavaruusulottuvuudessa, minkä vuoksi ne eivät sovellu suuriulotteisiin ongelmiin.

perinteisissä ruudukkopohjaisissa lähestymistavoissa tuotetaan polkuja, joiden kulkusuunnan muutokset rajoittuvat tietyn peruskulman kerrannaisiin, mikä johtaa usein alioptimaalisiin polkuihin. Any-kulma polku suunnittelu lähestymistapoja löytää lyhyempiä polkuja lisäämällä tietoa pitkin grid reunat (etsiä nopeasti) rajoittamatta niiden polkuja grid reunat (löytää lyhyitä polkuja).

Ruutupohjaisia lähestymistapoja joudutaan usein etsimään toistuvasti esimerkiksi silloin, kun robotin tieto konfiguraatioavaruudesta muuttuu tai itse konfiguraatioavaruus muuttuu polun seuraamisen aikana. Inkrementaalinen heuristinen hakualgoritmeja replan nopeasti käyttämällä kokemusta edellisen samanlainen polku suunnittelu ongelmia nopeuttaa niiden haku nykyisen.

Intervallipohjaiset searchEdit

nämä lähestymiset ovat samanlaisia kuin ruutupohjaiset hakulähestymiset, paitsi että ne tuottavat ruudukon sijasta kokonaan konfiguraatiotilan peittävän päällysteen. Päällystys hajotetaan kahteen alapavings X -, X+ tehty laatikot siten, että X – ⊂ Cfree ⊂ X+. Luonnehtiminen Cfree merkitsee ratkaista joukko inversio ongelma. Intervallianalyysia voitaisiin siten käyttää, kun CFR: ää ei voida kuvata lineaarisilla epätasa-arvoilla taatun otoksen varmistamiseksi.

robotti saa siis liikkua vapaasti X− järjestelmässä, eikä se voi mennä X+: n ulkopuolelle. Molempiin alapavingeihin rakennetaan naapurigraafi ja polut löytyvät algoritmien, kuten Dijkstran tai A*: n avulla. Kun polku on toteutettavissa X−: ssä, se on toteutettavissa myös Cfree: ssä. Kun X+: ssa ei ole polkua yhdestä alkuperäisestä kokoonpanosta maaliin, takaamme, että cfree: ssä ei ole mahdollista polkua. Grid-based approach, intervalli appropriate for high-dimensional problems, koska määrä laatikot syntyy kasvaa eksponentiaalisesti suhteessa ulottuvuus tilaa.

kuvan antavat kolme oikealla olevaa lukua, joissa kahden vapausasteen koukun on liikuttava vasemmalta oikealle välttäen kahta vaakasuoraa pientä lohkoa.

intervallianalyysiä käyttäen tapahtuva hajoaminen subpavingeilla mahdollistaa myös Cfreen topologian karakterisoinnin, kuten sen yhdistettyjen komponenttien lukumäärän laskemisen.

geometriset algoritmit

Pisterobotit monikulmaisten esteiden joukossa

• Näkyvyysdiagrammi
• solujen hajoaminen

esineiden kääntäminen esteiden joukossa

• Minkowskin summa

kun löydetään ulospääsytie rakennuksesta

• kaukaisin sädejälki

kun otetaan huomioon nippu säteitä nykyisen sijainnin ympärillä, joka johtuu niiden pituuden osumisesta seinään, robotti siirtyy pisimmän säteen suuntaan, ellei ovea tunnisteta. Tällaista algoritmia käytettiin rakennuksista poistumisen mallintamiseen.

keinotekoiset potentiaalikentät

yksi lähestymistapa on käsitellä robotin konfiguraatiota potentiaalikentän pisteenä, joka yhdistää vetovoiman tavoitteeseen ja vastustuksen esteistä. Tuloksena liikerata on lähtö kuin polku. Tämä lähestymistapa on etuja, että liikerata on tuotettu vähän laskenta. Ne voivat kuitenkin jäädä loukkuun potentiaalisen kentän paikallisiin minimeihin ja epäonnistua polun löytämisessä tai löytää epäoptimaalisen polun. Keinotekoiset potentiaalikentät voidaan käsitellä jatkumoyhtälöinä, jotka muistuttavat sähköstaattisen potentiaalin kenttiä (käsittelevät robottia kuin pistevarausta), tai kentän läpi kulkeva liike voidaan diskretoida kielisääntöjen avulla.Navigointifunktio tai probabilistinen Navigointifunktio ovat eräänlaisia keinotekoisia potentiaalifunktioita, joiden laatu ei ole minimipisteitä lukuun ottamatta kohdepistettä.

näytteenottoon perustuvat algoritmit

näytteenottoon perustuvat algoritmit edustavat konfiguraatioavaruutta, jossa on etenemissuunnitelma otoksista konfiguraatioista.Perusalgoritmi näytteet n kokoonpanot C, ja säilyttää ne Cfree käyttää virstanpylväitä. Tämän jälkeen rakennetaan etenemissuunnitelma, joka yhdistää kaksi virstanpylvästä P ja Q, jos ratasegmentti PQ on kokonaan Cfree: ssä. Jälleen törmäyksen havaitsemista käytetään testaamaan sisällyttämistä Cfree: hen. Jos haluat löytää polun, joka yhdistää S: n ja G: n, ne lisätään Tiekarttaan. Jos etenemissuunnitelman polku yhdistää S: n ja G: n, suunnittelija onnistuu ja palauttaa polun. Jos ei, syy ei ole lopullinen: joko ei ole polkua Cfree, tai suunnittelija ei näyte tarpeeksi virstanpylväitä.

nämä algoritmit toimivat hyvin suuriulotteisissa konfiguraatioavaruuksissa, koska toisin kuin kombinatoriset algoritmit, niiden suoritusaika ei ole (eksplisiittisesti) eksponentiaalisesti riippuvainen C: n ulottuvuudesta.ne ovat myös (yleensä) huomattavasti helpompia toteuttaa. Ne ovat probabilistisesti täydellisiä, eli todennäköisyys, että ne tuottavat ratkaisun lähestyy 1, Kun aikaa kuluu enemmän. He eivät kuitenkaan pysty päättelemään, onko ratkaisua olemassa.

kun otetaan huomioon Perusnäkyvyysolosuhteet Cfree: llä, on todistettu, että kun konfiguraatioiden lukumäärä n kasvaa suuremmaksi, todennäköisyys, että edellä mainittu algoritmi löytää ratkaisun, lähestyy 1 eksponentiaalisesti. Näkyvyys ei ole yksiselitteisesti riippuvainen C: n ulottuvuudesta, vaan on mahdollista olla suuriulotteinen tila, jolla on ”hyvä” näkyvyys, tai matalaulotteinen tila, jolla on ”huono” näkyvyys. Näytteisiin perustuvien menetelmien kokeellinen menestys viittaa siihen, että yleisimmin nähdyillä tiloilla on hyvä näkyvyys.

tästä perusjärjestelmästä on monia muunnelmia:

• on tyypillisesti paljon nopeampaa testata vain läheisten virstanpylväsparien välisiä segmenttejä kuin kaikkia pareja.
• Ei-yhtenäisillä otantajakaumilla pyritään asettamaan useampia virstanpylväitä alueille, jotka parantavat etenemissuunnitelman liitettävyyttä.
• Kvasirandominäytteet tyypillisesti peittävät konfiguraatioavaruuden paremmin kuin pseudorandomit, joskin joidenkin viimeaikaisten tutkimusten mukaan satunnaislähteen vaikutus on vähäinen verrattuna otantajakauman vaikutukseen.
• käyttää paikallista näytteenottoa suorittamalla suunnatun Markovin ketjun Monte Carlon satunnaiskävelyn, jossa on jonkin verran paikallista kosintajakaumaa.
• tietyn ongelman ratkaisemiseen tarvittavien virstanpylväiden määrää on mahdollista vähentää huomattavasti sallimalla kaarevat tähtäimet (esimerkiksi ryömimällä esteillä, jotka tukkivat tien kahden virstanpylvään välillä).
• jos tarvitaan vain yksi tai muutama suunnittelukysely, ei aina tarvitse rakentaa koko tilan tiekarttaa. Puiden kasvatusvaihtoehdot ovat tyypillisesti nopeampia tässä tapauksessa (yhden kyselyn suunnittelu). Tiekartat ovat edelleen hyödyllisiä, jos samasta tilasta halutaan tehdä monta kyselyä (usean kyselyn suunnittelu)

luettelo merkittävistä algoritmeista

• A *
• D *
• nopeasti tutkiva satunnainen puu
• probabilistinen etenemissuunnitelma