Planowanie przestrzeni państwowej
W sztucznej inteligencji i programowaniu komputerowym planowanie przestrzeni stanów to proces wykorzystywany przy projektowaniu programów do wyszukiwania danych lub rozwiązań problemów . W algorytmie komputerowym przeszukującym strukturę danych w poszukiwaniu fragmentu danych, na przykład w programie wyszukującym słowo w słowniku komputerowym, przestrzeń stanów to zbiorcze określenie wszystkich danych, które mają być przeszukane. Podobnie programy sztucznej inteligencji często wykorzystują proces przeszukiwania skończonego wszechświata możliwych procedur osiągnięcia celu, aby znaleźć procedurę lub najlepszą procedurę do osiągnięcia celu. Wszechświat możliwych rozwiązań do przeszukania nazywa się przestrzenią stanów. Planowanie przestrzeni stanów to proces decydowania, które części przestrzeni stanów program będzie przeszukiwał iw jakiej kolejności.
Definicja
Najprostsze algorytmy planowania klasycznego (patrz Planowanie automatyczne ) to algorytmy przeszukiwania przestrzeni stanów. Są to algorytmy wyszukiwania, w których przestrzeń poszukiwań jest podzbiorem przestrzeni stanów: każdy węzeł odpowiada stanowi świata, każdy łuk odpowiada zmianie stanu, a bieżący plan odpowiada bieżącej ścieżce w przestrzeni poszukiwań. Wyszukiwanie do przodu i wyszukiwanie do tyłu to dwa główne przykłady planowania przestrzeni stanów .
Wyszukiwanie do przodu
Wyszukiwanie do przodu to algorytm, który wyszukuje w przód od początkowego stanu świata, próbując znaleźć stan, który spełnia formułę celu.
0 Wyszukiwanie do przodu (O, s , g)
0 s = s P = pusta pętla planu, jeśli s spełnia g, to zwróć P ma zastosowanie = {a | a jest podstawową instancją operatora w O, a warunek wstępny(a) jest prawdziwy w s} jeśli ma zastosowanie = ∅ wtedy błąd powrotu niedeterministycznie wybierz akcję a spośród odpowiednich s = γ(s, a) P = Pa
Wyszukiwanie wstecz
Wyszukiwanie wstecz to algorytm, który rozpoczyna się od stanu docelowego i wraca do stanu początkowego. Ta metoda jest czasami nazywana „propagacją wsteczną”.
0 Wyszukiwanie wstecz (O, s , g)
0 s = s P = pusta pętla planu, jeśli s spełnia g, to zwróć P istotne = {a | a jest podstawową instancją operatora w O, która jest istotna dla g} jeśli jest istotna = ∅ to powrót niepowodzenie niedeterministycznie wybierz akcję a spośród odpowiednich P = aP s = γ −1 (s, a )
Zobacz też
- Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automatyczne planowanie: teoria i praktyka , Morgan Kaufmann , ISBN 1-55860-856-7