Spazio di stato - State space

Vacuum World, un problema di cammino minimo con uno spazio degli stati finito

Uno spazio degli stati è l'insieme di tutte le possibili configurazioni di un sistema. È un'astrazione utile per ragionare sul comportamento di un dato sistema ed è ampiamente utilizzata nei campi dell'intelligenza artificiale e della teoria dei giochi .

Ad esempio, il problema del giocattolo Vacuum World ha uno spazio di stato finito discreto in cui esiste un insieme limitato di configurazioni in cui possono trovarsi il vuoto e la sporcizia. Un sistema "contatore", in cui gli stati sono i numeri naturali che iniziano da 1 e vengono incrementati nel tempo ha uno spazio di stati discreto infinito. La posizione angolare di un pendolo non smorzato è uno spazio di stati continuo (e quindi infinito).

Definizione

Nella teoria dei sistemi dinamici , un sistema discreto definito da una funzione ƒ , lo spazio degli stati del sistema può essere modellato come un grafo orientato dove ogni possibile stato di un sistema dinamico è rappresentato da un vertice, e c'è un arco orientato da da a a b se e solo se ƒ ( a ) =  b . Questo è noto come diagramma di stato .

Per un sistema dinamico continuo definito da una funzione ƒ , lo spazio degli stati del sistema è l' immagine di ƒ .

Gli spazi di stato sono utili in informatica come semplice modello di macchine. Formalmente, uno spazio degli stati può essere definito come una tupla [ N ,  A ,  S ,  G ] dove:

• N è un insieme di stati
• A è un insieme di archi che collegano gli stati
• S è un sottoinsieme non vuoto di N che contiene stati di inizio
• G è un sottoinsieme non vuoto di N che contiene gli stati obiettivo.

Proprietà

	un	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	un	b	c	d	e	f	g	h

Uno stato valido nello spazio degli stati delle otto regine puzzle

Uno spazio degli stati ha alcune proprietà comuni:

• complessità, dove il fattore di ramificazione è importante
• struttura dello spazio, vedi anche teoria dei grafi :
  • direzionalità degli archi
  • albero
  • grafo radicato

Ad esempio, Vacuum World ha un fattore di ramificazione di 4, poiché l'aspirapolvere può finire in 1 di 4 caselle adiacenti dopo essersi spostate (supponendo che non possa rimanere nella stessa casella né muoversi in diagonale). Gli archi di Vacuum World sono bidirezionali, poiché qualsiasi quadrato può essere raggiunto da qualsiasi quadrato adiacente e lo spazio degli stati non è un albero poiché è possibile entrare in un ciclo spostandosi tra 4 quadrati adiacenti qualsiasi.

Gli spazi di stato possono essere infiniti o finiti, discreti o continui.

Dimensione

La dimensione dello spazio degli stati per un dato sistema è il numero di possibili configurazioni dello spazio.

Finito

Se la dimensione dello spazio degli stati è finita, calcolare la dimensione dello spazio degli stati è un problema combinatorio . Ad esempio, nel puzzle delle otto regine , lo spazio degli stati può essere calcolato contando tutti i modi possibili per posizionare 8 pezzi su una scacchiera 8x8. Equivale a scegliere 8 posizioni senza sostituzione da un set di 64, oppure

${\displaystyle {\binom {64}{8}}=4.426.165.368}$

Questo è significativamente maggiore del numero di configurazioni legali delle regine, 92. In molti giochi lo spazio effettivo dello stato è piccolo rispetto a tutti gli stati raggiungibili / legali. Questa proprietà si osserva anche in Chess , dove lo spazio degli stati effettivo è l'insieme delle posizioni che possono essere raggiunte da mosse legali di gioco. Questo è molto più piccolo dell'insieme di posizioni che si possono ottenere piazzando le combinazioni dei pezzi degli scacchi disponibili direttamente sulla scacchiera.

Infinito

Tutti gli spazi di stato continui possono essere descritti da una corrispondente funzione continua e sono quindi infiniti. Gli spazi di stato discreti possono anche avere ( numerabilmente ) dimensioni infinite, come lo spazio di stato del sistema "contatore" dipendente dal tempo, simile al sistema nella teoria delle code che definisce il numero di clienti in una linea, che avrebbe lo spazio degli stati {0 , 1, 2, 3, ...}.

Esplorazione

L'esplorazione di uno spazio degli stati è il processo di enumerazione di possibili stati alla ricerca di uno stato obiettivo. Lo spazio di stato di Pacman , ad esempio, contiene uno stato obiettivo ogni volta che tutti i pellet di cibo sono stati mangiati e viene esplorato spostando Pacman sul tabellone.

Cerca Stati

Uno stato di ricerca è una rappresentazione compressa di uno stato mondiale in uno spazio degli stati e viene utilizzato per l'esplorazione. Gli stati di ricerca vengono utilizzati perché uno spazio degli stati spesso codifica più informazioni di quelle necessarie per esplorare lo spazio. La compressione di ogni stato del mondo alle sole informazioni necessarie per l'esplorazione migliora l'efficienza riducendo il numero di stati nella ricerca. Ad esempio, uno stato nello spazio Pacman include informazioni sulla direzione in cui è rivolto Pacman (su, giù, sinistra o destra). Poiché non costa nulla cambiare direzione in Pacman, gli stati di ricerca per Pacman non includerebbero queste informazioni e ridurrebbero le dimensioni dello spazio di ricerca di un fattore 4, uno per ogni direzione in cui Pacman potrebbe essere rivolto.

metodi

Gli algoritmi di ricerca standard sono efficaci nell'esplorazione di spazi di stato discreti. I seguenti algoritmi mostrano sia la completezza che l'ottimalità nella ricerca di uno spazio degli stati.

• Ricerca in ampiezza
• Una ricerca
• Ricerca dei costi uniformi

Questi metodi non si estendono naturalmente all'esplorazione di spazi di stato continui. Esplorare uno spazio degli stati continuo alla ricerca di un dato stato obiettivo equivale a ottimizzare una funzione continua arbitraria che non è sempre possibile, vedi ottimizzazione matematica .

Guarda anche

Riferimenti