Язык задач планирования
Как следует из приведенного выше описания, сам способ представления задач планирования (состояний, действий и целей) должен обеспечивать возможность для алгоритмов планирования воспользоваться логической структурой задачи. Весь секрет состоит в том, чтобы найти язык, достаточно выразительный для описания широкого круга задач, но вместе с тем достаточно ограничительный для обеспечения функционирования на его основе эффективных алгоритмов. В этом разделе вначале рассматривается основной язык представления классических планировщиков, известный под названием2 Strips. Затем кратко представлены некоторые из многих возможных вариантов языков, подобных Strips.
• Представление состояний. В планировщиках применяется декомпозиция мира на логические условия, а состояние представляется в виде конъюнкции положительных литералов. Мы будем рассматривать пропозициональные литералы; например, выражение Poor л Unknown может представлять состояние агента-неудачника (бедного и безвестного). В этой главе будут также использоваться литералы первого порядка; например, выражение At {Planelt Melbourne) л At{Plane2f Sydney) может представлять одно из состояний в задаче доставки пакетов. Литералы в описаниях состояния первого порядка должны быть базовыми и не содержащими функций. Такие литералы, как At{x,y) или At {Father {Fred) , Sydney), не допускаются. Кроме того, используется предположение о замкнутом мире, которое означает, что любые условия, не упомянутые в описании состояния, считаются ложными.
• Представление целей. Цель — это частично заданное состояние, представленное в виде конъюнкции положительных базовых литералов, таких как Ri ch л Famous или At {Р2, Tahiti). Пропозициональное состояние s удовлетворяет цели д, если s содержит все атомы из д (и, возможно, другие атомы). Например, состояние Rich A Famous A Miserable (богатый, знаменитый и несчастный) удовлетворяет цели Rich A Famous.
• Представление действий. Любое действие задается в терминах предусловий, которые должны соблюдаться до того, как оно может быть выполнено, и результатов, которые становятся следствием его выполнения. Например, действие, состоящее в перелете самолета из одного места в другое, можно записать следующим образом:
Action(Fly{p, from, to), Precond: At{p, from) A Plane{p) A Airport(from) A Airport{to), Effect: -nAt(p, from) A At(p, to))
где Precond обозначает предусловие, a Effect — результат.
Такое выражение следовало бы называть не просто действием, а схемой действия, в том смысле, что в нем представлен целый ряд различных действий, которые могут явиться следствием конкретизации переменных р, from и to различными константами. Вообще говоря, любая схема действия состоит из перечисленных ниже трех частей.
• Имя действия и список параметров (например, Fly{p, from, to)) служат для обозначения действия.
• Предусловием называется конъюнкция не содержащих функций положительных литералов, регламентирующая то, что должно быть истинным в некотором состоянии, прежде чем можно будет выполнить рассматриваемое действие. Любые переменные, заданные в предусловии, должны также присутствовать в списке параметров действия.
• Результатом является конъюнкция не содержащих функций литералов, представляющая собой описание того, как изменится состояние после выполнения действия. В состоянии, ставшем результатом действия, подтверждается истинность положительного литерала Р в результате, тогда как применительно к отрицательному литералу -нР подтверждается его ложность. Переменные, присутствующие в результате, должны также присутствовать в списке параметров действия.
Для повышения удобства чтения в некоторых системах планирования предусмотрено разделение результата на список добавления для положительных литералов и список удаления для отрицательных литералов.
Определив синтаксис представлений задач планирования, можно приступить к определению семантики. Наиболее простой способ выполнения этой задачи состоит в том, чтобы описать, как действия влияют на состояния. (Альтернативный метод предусматривает определение непосредственного преобразования в аксиомы состояния-преемника, семантика которых основана на логике первого порядка; см. упр. 11.3.) Вначале необходимо отметить, что действие применимо в любом состоянии, в котором выполняется предусловие; в противном случае действие не имеет эффекта. Для схемы действий первого порядка задача определения применимости связана с поиском подстановки 0 для переменных в предусловии. Например, предположим, что текущее состояние описано следующим образом:
At(Plf JFK) л At{P2l SFO) л Plane (Pi) л Plane (P2) A Airport{JFK) A Airport(SFO)
Это состояние удовлетворяет такому предусловию:
At{p, from) A Plane(р) л Airport(from) л Airport(to)
с подстановкой {р/Plt from/JFK, to/SFO} (кроме всего прочего; см. упр. 11.2). Поэтому конкретное действие FlyiP-, JFK, SFO) является применимым.
Начиная с состояния s, результатом выполнения применимого действия а является состояние s1, представляющее собой то же самое, что и s, за исключением того, что любой положительный литерал Р в результате а добавляется к s', а любой отрицательный литерал -iP удаляется из s'. Таким образом, после выполнения действия Fly{P±, JFK, SFO) показанное выше текущее состояние принимает вид
At{Plr SFO) A At(P2, SFO) A PlaneiPx) л Plane(P2) A Airport{JFK) A Airport{SFO)
Следует отметить, что если какой-то положительный результат уже находится в состоянии s, то не добавляется повторно, а если какой-то отрицательный результат отсутствует в состоянии s, эта часть результата игнорируется. Такое определение воплощает в себе так называемое предположение Strips, что каждый литерал, не упомянутый в результате, остается неизменным. Благодаря этому язык Strips позволяет избежать возникновения проблемы представительного окружения, описанной в главе 10.
Наконец, можно определить решение для задачи планирования. В своей простейшей форме это всего лишь последовательность действий, которая, будучи выполненной в начальном состоянии, приводит к состоянию, удовлетворяющему цели. Далее в этой главе будет показано, как обеспечить возможность использовать решение, представляющее собой частично упорядоченные множества действий, при условии, что каждая последовательность действий, которая отвечает этому частичному упорядочению, является решением.