Pianificazione del movimento

I problemi a bassa dimensione possono essere risolti con algoritmi basati su griglia che sovrappongono una griglia sullo spazio di configurazione o algoritmi geometrici che calcolano la forma e la connettività di Cfree.

La pianificazione esatta del movimento per sistemi ad alta dimensione sotto vincoli complessi è computazionalmente intrattabile. Gli algoritmi di campo potenziale sono efficienti, ma cadono preda dei minimi locali (un’eccezione sono i campi potenziali armonici). Gli algoritmi basati sul campionamento evitano il problema dei minimi locali e risolvono molti problemi abbastanza rapidamente.Non sono in grado di determinare che non esiste alcun percorso, ma hanno una probabilità di errore che diminuisce a zero man mano che viene speso più tempo.

Gli algoritmi basati sul campionamento sono attualmente considerati all’avanguardia per la pianificazione del movimento in spazi ad alta dimensione e sono stati applicati a problemi che hanno dozzine o addirittura centinaia di dimensioni (manipolatori robotici, molecole biologiche, personaggi digitali animati e robot con gambe).

Esiste l’algoritmo parallelo di pianificazione del movimento (A1-A2) per la manipolazione degli oggetti (per catturare l’oggetto volante).

Ricerca basata su gridedit

Gli approcci basati su grid sovrappongono una griglia sullo spazio di configurazione e presuppongono che ogni configurazione sia identificata con un punto della griglia. Ad ogni punto della griglia, il robot può spostarsi in punti della griglia adiacenti finché la linea tra di loro è completamente contenuta all’interno di Cfree (questo è testato con il rilevamento delle collisioni). Questo discretizza l’insieme di azioni e gli algoritmi di ricerca (come A*) vengono utilizzati per trovare un percorso dall’inizio all’obiettivo.

Questi approcci richiedono l’impostazione di una risoluzione della griglia. La ricerca è più veloce con griglie più grossolane, ma l’algoritmo non riuscirà a trovare percorsi attraverso porzioni strette di Cfree. Inoltre, il numero di punti sulla griglia cresce esponenzialmente nella dimensione dello spazio di configurazione, il che li rende inappropriati per problemi ad alta dimensione.

Gli approcci tradizionali basati sulla griglia producono percorsi le cui modifiche di intestazione sono vincolate a multipli di un determinato angolo di base, spesso con conseguente percorsi non ottimali. Gli approcci di pianificazione del percorso a qualsiasi angolo trovano percorsi più brevi propagando le informazioni lungo i bordi della griglia (per cercare velocemente) senza vincolare i loro percorsi ai bordi della griglia (per trovare percorsi brevi).

Gli approcci basati sulla griglia spesso devono cercare ripetutamente, ad esempio, quando la conoscenza del robot sullo spazio di configurazione cambia o lo spazio di configurazione stesso cambia durante il percorso successivo. Gli algoritmi di ricerca euristica incrementali si riprendono velocemente utilizzando l’esperienza con i precedenti problemi di pianificazione del percorso simili per accelerare la ricerca di quello corrente.

Ricerca basata su intervaledit

Questi approcci sono simili agli approcci di ricerca basati su griglia, tranne per il fatto che generano una pavimentazione che copre interamente lo spazio di configurazione anziché una griglia. La pavimentazione è scomposta in due sottopavings X−,X+ realizzati con scatole tali che X-Cf Cfree X X+. Caratterizzare Cfree equivale a risolvere un problema di inversione dell’insieme. L’analisi dell’intervallo potrebbe quindi essere utilizzata quando Cfree non può essere descritto da disuguaglianze lineari per avere un recinto garantito.

Il robot può quindi muoversi liberamente in X-e non può uscire da X+. Per entrambi i sottopavings, viene creato un grafico vicino e i percorsi possono essere trovati utilizzando algoritmi come Dijkstra o A*. Quando un percorso è fattibile in X -, è anche fattibile in Cfree. Quando non esiste alcun percorso in X + da una configurazione iniziale all’obiettivo, abbiamo la garanzia che non esiste alcun percorso fattibile in Cfree. Per quanto riguarda l’approccio basato sulla griglia, l’approccio dell’intervallo è inappropriato per problemi ad alta dimensione, a causa del fatto che il numero di caselle da generare cresce esponenzialmente rispetto alla dimensione dello spazio di configurazione.

Un’illustrazione è fornita dalle tre figure a destra dove un gancio con due gradi di libertà deve spostarsi da sinistra a destra, evitando due piccoli segmenti orizzontali.

La decomposizione con sottopavings utilizzando l’analisi dell’intervallo consente anche di caratterizzare la topologia di Cfree come il conteggio del suo numero di componenti collegati.

Geometrici algorithmsEdit

Punto di robot tra poligonale ostacoli

• Visibilità grafico
• Cella di decomposizione

Traduzione degli oggetti tra gli ostacoli

• Minkowski somma

Trovare la via d’uscita di un edificio

• più lontano ray-trace

Dato un fascio di raggi intorno alla posizione corrente attribuita con la loro lunghezza colpendo un muro, il robot si muove in direzione del raggio più lungo, a meno che una porta è identificata. Tale algoritmo è stato utilizzato per modellare l’uscita di emergenza dagli edifici.

Campi potenziali artificialimodifica

Un approccio consiste nel trattare la configurazione del robot come un punto in un campo potenziale che combina attrazione per l’obiettivo e repulsione dagli ostacoli. La traiettoria risultante viene emessa come percorso. Questo approccio ha vantaggi in quanto la traiettoria è prodotta con poco calcolo. Tuttavia, possono rimanere intrappolati nei minimi locali del campo potenziale e non riescono a trovare un percorso o possono trovare un percorso non ottimale. I campi potenziali artificiali possono essere trattati come equazioni continue simili ai campi potenziali elettrostatici (trattando il robot come una carica puntiforme), o il movimento attraverso il campo può essere discretizzato utilizzando un insieme di regole linguistiche.Una funzione di navigazione o una funzione di navigazione probabilistica sono tipi di funzioni potenziali artificiali che hanno la qualità di non avere punti minimi tranne il punto di destinazione.

Algoritmi basati sul campionamentomodifica

Gli algoritmi basati sul campionamento rappresentano lo spazio di configurazione con una tabella di marcia delle configurazioni campionate.Un algoritmo di base campiona le configurazioni N in C e mantiene quelle in Cfree da utilizzare come pietre miliari. Viene quindi costruita una tabella di marcia che collega due pietre miliari P e Q se il segmento di linea PQ è completamente in Cfree. Ancora una volta, il rilevamento delle collisioni viene utilizzato per testare l’inclusione in Cfree. Per trovare un percorso che collega S e G, vengono aggiunti alla tabella di marcia. Se un percorso nella tabella di marcia collega S e G, il pianificatore riesce e restituisce quel percorso. In caso contrario, il motivo non è definitivo: o non c’è percorso in Cfree, o il pianificatore non ha campione abbastanza pietre miliari.

Questi algoritmi funzionano bene per spazi di configurazione ad alta dimensione, perché a differenza degli algoritmi combinatori, il loro tempo di esecuzione non dipende (esplicitamente) in modo esponenziale dalla dimensione di C. Sono anche (generalmente) sostanzialmente più facili da implementare. Sono probabilisticamente completi, il che significa che la probabilità che produrranno una soluzione si avvicina a 1 man mano che viene speso più tempo. Tuttavia, non possono determinare se non esiste una soluzione.

Date le condizioni di visibilità di base su Cfree, è stato dimostrato che man mano che il numero di configurazioni N aumenta, la probabilità che l’algoritmo di cui sopra trovi una soluzione si avvicina a 1 in modo esponenziale. La visibilità non dipende esplicitamente dalla dimensione di C; è possibile avere uno spazio ad alta dimensione con visibilità “buona” o uno spazio a bassa dimensione con visibilità “scarsa”. Il successo sperimentale dei metodi basati su campioni suggerisce che gli spazi più comunemente visti hanno una buona visibilità.

Ci sono molte varianti di questo schema di base:

• In genere è molto più veloce testare solo segmenti tra coppie vicine di pietre miliari, piuttosto che tutte le coppie.
• Le distribuzioni di campionamento non uniformi tentano di porre più pietre miliari in aree che migliorano la connettività della tabella di marcia.
• I campioni quasirandom in genere producono una migliore copertura dello spazio di configurazione rispetto a quelli pseudorandom, anche se alcuni lavori recenti sostengono che l’effetto della fonte di casualità è minimo rispetto all’effetto della distribuzione di campionamento.
• Impiega il campionamento locale eseguendo una catena di Markov direzionale Monte Carlo random walk con una distribuzione di proposte locali.
• È possibile ridurre in modo sostanziale il numero di pietre miliari necessarie per risolvere un dato problema consentendo mirini curvi (ad esempio strisciando sugli ostacoli che bloccano la strada tra due pietre miliari).
• Se sono necessarie solo una o poche query di pianificazione, non è sempre necessario costruire una tabella di marcia dell’intero spazio. Le varianti ad albero sono in genere più veloci per questo caso (pianificazione a query singola). Le roadmap sono ancora utili se si devono effettuare molte query sullo stesso spazio (pianificazione multi-query)

Elenco degli ALGORITMI notevolimodifica

• A*
• D*
• Albero casuale ad esplorazione rapida
• Roadmap probabilistica