Algoritmo di esplorazione

Question

Modificata in modo massiccio questa domanda per renderla più facile da capire.

Dato un ambiente con dimensioni arbitrarie e posizionamento arbitrario di un numero arbitrario di ostacoli, ho un agente che esplora l'ambiente con un campo visivo limitato (gli ostacoli non bloccano la vista). Può muoversi nelle quattro direzioni cardinali di NSEW, una cella alla volta, e il grafico non è pesato (ogni passo ha un costo di 1). Collegato sotto è una mappa che rappresenta la credenza corrente dell'agente (ragazzo giallo) dell'ambiente nell'istante della pianificazione. Il tempo non passa nella simulazione mentre l'agente sta pianificando.

http://imagizer.imageshack.us/a/img913/9274/qRsazT.jpg

Che algoritmo di esplorazione posso usare per ottimizzare il rapporto costo-efficacia del programma di utilità, dato che rivisitando le cellule sono permessi? Ogni cella contiene un valore di utilità. Idealmente, cercherò di massimizzare la somma dell'utilità di tutte le celle SEEN (non visitate) divise per la lunghezza del percorso, sebbene se ciò sia troppo complesso per qualsiasi algoritmo adatto, il numero di celle viste sarà sufficiente. C'è una lunghezza massima del percorso ma generalmente è di centinaia o superiore. (Gli attuali ambienti di test utilizzati sul mio agente sono almeno 4x più grandi, anche se teoricamente non esiste un limite superiore per le dimensioni che è possibile impostare e la lunghezza massima del percorso aumenterebbe di conseguenza)

Ritengo BFS e DFS a essere intrattabile, A * essere non ottimale data la mancanza di un'euristica adeguata, e l'inadeguatezza di Dijkstra nel generare un singolo percorso ininterrotto. C'è qualche algoritmo che riesci a pensare? Inoltre, ho bisogno di aiuto con il rilevamento del loop, come non l'ho mai fatto prima, dato che consentire le revisitazioni è la mia prima volta.

Un approccio che ho considerato è quello di ridurre la mappa in uno spanning tree, tranne che invece di definirlo come un albero che collega tutte le celle, è definito come un albero che può vedere tutte le celle. Il mio approccio comporterebbe la seguente:

http://imagizer.imageshack.us/a/img910/3050/HGu40d.jpg

Nella struttura risultante, l'agente può andare da un nodo a tutti i nodi adiacenti sotto 0-1 sua volta via agli incroci. Questo è il mio pensiero fino adesso. Una soluzione generata usando questo albero potrebbe non essere ottimale, ma dovrebbe essere almeno quasi ottimale con molte meno celle elaborate dall'algoritmo, quindi se questo renderebbe l'algoritmo più facilmente trattabile, allora suppongo che sia accettabile scambio. Sono ancora bloccato pensando come esattamente generare un percorso per questo tuttavia.

Answer 1

Il tuo problema è molto simile a un problema di Reinforcement Learning (RL), il Grid World. Lo formalizzerei come standard Markov Decision Process (MDP) e userei qualsiasi algoritmo RL per risolverlo.

La formalizzazione sarebbe:

• Uniti s: il tuo NxM discreta griglia.
• Azioni a: UP, DOWN, LEFT, RIGHT.
• Premio r: il valore delle celle che l'agente può vedere dalla cella di destinazione s', ad esempio r(s,a,s') = sum(value(seen(s')).
• Funzione di transizione: P(s' | s, a) = 1 se s' non è fuori dai limiti o una cella nera, 0 in caso contrario.

Dal momento che siete interessati al premio medio, il fattore di sconto è 1 e si deve normalizzare il cumulo dei premi per il numero di passaggi. Hai anche detto che ogni passaggio è costato uno, in modo da poter sottrarre 1 alla ricompensa immediata r ad ogni passo temporale, ma questo non aggiungerebbe nulla dato che avrai già una media per il numero di passaggi.

Poiché il problema è discreto, la politica potrebbe essere una semplice distribuzione di softmax (o di Gibbs).

Come algoritmo di risoluzione è possibile utilizzare Q-learning, che garantisce l'ottimalità della soluzione fornita un numero sufficiente di campioni. Tuttavia, se la tua griglia è troppo grande (e hai detto che non vi è alcun limite) suggerirei algoritmi di ricerca di policy, come il gradiente di policy o l'entropia relativa (sebbene garantiscano la convergenza solo agli optima locali). Puoi trovare qualcosa sul Q-learning praticamente ovunque su Internet. Per un recente sondaggio sulla ricerca della politica suggerisco this.

La cosa interessante di questi approcci è che codificano l'esplorazione nella politica (ad esempio, la temperatura in una politica di softmax, la varianza in una distribuzione gaussiana) e cercheranno di massimizzare la ricompensa a lungo termine come descritto dal MDP. Quindi, di solito, si inizializza la politica con un'alta esplorazione (ad es. Una politica casuale completa) e, per tentativi ed errori, l'algoritmo lo renderà deterministico e convergerà a quello ottimale (tuttavia, a volte anche una politica stocastica è ottimale). La differenza principale tra tutti gli algoritmi RL è il modo in cui eseguono l'aggiornamento della politica ad ogni iterazione e gestiscono lo sfruttamento-esplorazione del tradeoff (quanto dovrei esplorare VS quanto dovrei sfruttare le informazioni che ho già).

Come suggerito da Demplo, è anche possibile utilizzare gli Algoritmi genetici (GA), ma di solito sono più lenti e richiedono una maggiore sintonizzazione (elitismo, crossover, mutazione ...).

Ho anche provato alcuni algoritmi di ricerca di criteri sul problema e sembrano funzionare bene, anche se ho inizializzato la griglia in modo casuale e non conosco la soluzione ottimale esatta. Se fornisci alcuni dettagli aggiuntivi (una griglia di test, il numero massimo di passaggi e se la posizione iniziale è fissa o casuale) posso testarli con maggiore precisione.