Государственное пространственное планирование

В искусственном интеллекте и компьютерном программировании планирование пространства состояний — это процесс, используемый при разработке программ для поиска данных или решений проблем. В компьютерном алгоритме, который ищет часть данных в структуре данных, например в программе, которая ищет слово в компьютерном словаре, пространство состояний является собирательным термином для всех данных, которые необходимо найти. Аналогичным образом, программы искусственного интеллекта часто используют процесс поиска в конечной вселенной возможных процедур для достижения цели, чтобы найти процедуру или лучшую процедуру для достижения цели. Вселенная возможных решений, которые необходимо найти, называется пространством состояний. Планирование пространства состояний — это процесс принятия решения, в каких частях пространства состояний программа будет осуществлять поиск и в каком порядке.

Определение

Простейшие алгоритмы классического планирования (см. Автоматизированное планирование ) — это алгоритмы поиска в пространстве состояний. Эти — это алгоритмы поиска, в которых пространство поиска является подмножеством пространства состояний: каждый узел соответствует состоянию мира, каждая дуга соответствует переходу состояний, и текущий план соответствует текущему пути в пространстве поиска. Прямой поиск и обратный поиск являются двумя основными примерами государственного пространственного планирования .

Прямой поиск

Прямой поиск — это алгоритм, который выполняет поиск вперед от начальное состояние мира, чтобы попытаться найти состояние, удовлетворяющее формуле цели.

Прямой поиск(O, s ₀ , g)

 s = s0
 P = the empty plan
 loop
     if s satisfies g then return P
     applicable = {a | a is a ground instance of an operator in O,and precond(a) is true in s}
     if applicable = ∅ then return failure 
     nondeterministically choose an action a from applicable
     s = γ(s, a)
     P = P.a

Обратный поиск

Обратный поиск — это алгоритм, который начинается с целевого состояния и возвращается к исходному состоянию. Этот метод иногда называют «обратным распространением».

Обратный поиск(O, s ₀ , g)

 s = s0
 P = the empty plan
 loop
     if s satisfies g then return P
     relevant = {a | a is a ground instance of an operator in O that is relevant for g}
     if relevant = ∅ then return failure 
     nondeterministically choose an action a from relevant
     P = a.P  
     s = γ−1(s, a)

См. также

• Государственное пространство
• Государственный космический поиск

Ссылки

• Галлаб, Малик; Нау, Дана С.; Траверсо, Паоло (2004). Автоматизированное планирование: теория и практика . Морган Кауфманн . ISBN  1-55860-856-7 .