Эвристики для планирования с частичным упорядочением
В отличие от планирования с полным упорядочением, планирование с частичным упорядочением обладает явным преимуществом, поскольку позволяет выполнять декомпозицию задач на подзадачи. Оно имеет также определенный недостаток, который заключается в том, что состояния не представлены явно, поэтому труднее оценить, насколько далек план с частичным упорядочением от ситуации достижения цели. К тому же в настоящее время существует гораздо меньшее понимание того, как следует вычислять точные эвристики для планирования с частичным упорядочением, чем для планирования с полным упорядочением.
Наиболее очевидная эвристика состоит в подсчете количества различных открытых предусловий. Такая эвристика может быть улучшена путем вычитания из указанной величины количества открытых предусловий, которые согласуются с литералами в состоянии Start. Как и в случае с полным упорядочением, такая эвристика приводит к переоценке стоимости, если имеются действия, достигающие нескольких подцелей, и недооценке стоимости, если возникают отрицательные взаимодействия этапов плана. В следующем разделе представлен подход, позволяющий получать гораздо более точные эвристики из ослабленной задачи.
Эвристическая функция используется для выбора плана, подлежащего уточнению. При наличии такого выбора алгоритм вырабатывает преемников на основе определения единственного открытого предусловия, которое следует дополнительно проработать. Как и в случае выбора переменной в алгоритмах удовлетворения ограничений, такое решение оказывает большое влияние на эффективность. Для алгоритмов планирования может быть адаптирована эвристика с наиболее ограниченной переменной, применяемая в задачах CSP, и эта эвристика, по-видимому, неплохо действует. Ее идея состоит в том, чтобы определить открытое условие, которое может быть выполнено с помощью наименьшего количества способов. Возникают два особых случая применения этой эвристики. Во-первых, если какого-то открытого условия невозможно достичь с помощью любого действия, оно должно быть выбрано данной эвристикой; это — вполне целесообразно, поскольку раннее обнаружение неразрешимой ситуации позволяет сэкономить большой объем работы. Во-вторых, если открытое условие может быть достигнуто только одним способом, оно также должно быть выбрано, поскольку такое решение неизбежно и позволяет налагать дополнительные ограничения на другие варианты выбора, которые еще должны быть сделаны. Хотя процедура полного вычисления количества способов выполнения каждого открытого условия является дорогостоящей и не всегда оправданной, эксперименты показали, что применение этих двух частных случаев обеспечивает весьма существенное ускорение.