Come evitare che il robot venga intrappolato nel minimo locale?

Question

Mi dedico un po 'di tempo alla pianificazione del movimento per i robot e da tempo desidero esplorare la possibilità di migliorare le opportunità offerte dal metodo del "potenziale campo". La mia sfida è evitare che il robot venga intrappolato in "minimo locale" quando si utilizza il metodo del "campo potenziale". Invece di usare un approccio "random walk" per evitare che il robot rimanga intrappolato, ho pensato se sia possibile implementare una variazione di A * che potrebbe fungere da una sorta di guida per evitare esattamente che il robot venga intrappolato in " minimo locale ".

Esiste qualche esperienza di questo tipo o può fare riferimento alla letteratura, che evita il minimo locale in modo più efficace rispetto a quello utilizzato nell'approccio "random walk".

Answer 1

A * e campi potenziali sono tutte le strategie di ricerca. Il problema che stai vivendo è che alcune strategie di ricerca sono più "avide" di altre e, il più delle volte, gli algoritmi troppo avidi vengono intrappolati nel minimo locale.

Ci sono alcune alternative in cui la tensione tra l'avidità (la principale causa di intrappolamento sul minimo locale) e la diversità (provare nuove alternative che non sembrano essere una buona scelta a breve termine) sono parametrizzate.

Alcuni anni fa ho studiato un po 'gli algoritmi delle formiche (ricerca di Marco Dorigo, ACS, ACO) e hanno una famiglia di algoritmi di ricerca che possono essere applicati praticamente a qualsiasi cosa, e possono controllare l'avidità vs. esplorazione del tuo spazio di ricerca. In una delle loro carte, hanno anche confrontato le prestazioni di ricerca che risolvevano il TSP (il problema canonico del venditore ambulante) usando algoritmi genetici, ricottura simulata e altri. Ant ha vinto.

Ho risolto il TSP in passato utilizzando algoritmi genetici e ho ancora il codice sorgente in delphi, se lo desideri.

Answer 2

Utilizzare la pianificazione del percorso della funzione armonica. Le funzioni armoniche sono funzioni potenziali che descrivono il flusso del fluido e altri fenomeni naturali. Se sono impostati correttamente utilizzando condizioni al contorno, non hanno minimi locali. Questi sono stati in uso fin dai primi anni '90 dal Rod Grupen and Chris Connolly. Queste funzioni hanno dimostrato di essere una forma specifica di controllo ottimale che minimizza le probabilità di collisione. Possono essere calcolati efficientemente in spazi a bassa dimensione usando le equazioni alle differenze (cioè Gauss-seidel, sovrappressione successiva, ecc.).