Планирование с частичным порядком

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

• Множество действий (операторов).
• Частичный порядок для действий — определяет условия порядка между некоторыми действиями.
• Множество каузальных связей — показывает, какие действия удовлетворяют предусловия других. Альтернативно, это множество связок между переменными в действиях.
• Множество открытых предусловий — описывает предусловия, не выполненные ни одним действием в данном плане.

Чтобы оставить максимальное количество вариантов поочерёдности действий, число условий порядка и каузальных связей должно быть минимальным.

План считается решением, если множество открытых предусловий пусто.

Линеаризация плана с частичным порядком — это получение плана с полным порядком на его основе: оба плана содержат те же действия, но порядок действий в линеаризации представляет собой линейное расширение исходного частичного порядка.

План по приготовлению пирога может выглядеть так:

• сходить в магазин
• взять яйца; взять муку; взять молоко
• оплатить все покупки
• вернуться на кухню

Это частичный план, потому что порядок покупки яиц, муки и молока не задан — агент может собирать необходимые продукты в любом порядке, пока не завершит список^[3].

Планировщик с частичным порядком (англ. partial-order planner) — это алгоритм или программа, которая строит план с частичным порядком и ищет решение. Входные данные включают описание первоначального состояния, цели и возможных действий.

Задача формулируется как поисковая задача, где пространство поиска составляют возможные планы с частичным порядком. Начальное состояние — это план, открытые предусловия которого совпадают с целевыми условиями. Конечное состояние — любой план без открытых предусловий, то есть искомое решение^[3].

Начальное состояние определяет исходные условия (например, пустой стол для задачи сервировки). Цель — это результат, который требуется получить, например сервированный стол. Операторами называются действия, с помощью которых достигается цель (в приведённом примере — разложить скатерть и расставить бокалы, тарелки и приборы).

Пространство планов алгоритма ограничено начальным и конечным состояниями. Алгоритм начинается с формирования начального состояния и завершается, когда выполнены все части цели. Для задачи сервировки стола есть, например, такие действия: разложить скатерть, разложить тарелки, приборы и бокалы. Возникает ‘‘угроза’’, если разложить тарелки, приборы или бокалы до скатерти. В этом случае предусловие, что стол пуст, больше не выполнено. Поэтому алгоритм должен ввести ограничение: все действия после разложения скатерти. После всех этих шагов задача считается решённой^[4].

Планирование с частичным порядком может сталкиваться с ‘‘угрозами’’: это такие порядки действий, при которых нарушается связь между предусловием и действием, что может разрушить весь план. Для устранения угроз применяются два подхода:

• Повышение
• Понижение

Повышение означает размещение действия-угрозы после связанного события; понижение — до него.

Алгоритмы такого типа считаются корректными и полными: корректность гарантирует, что все действия можно полностью упорядочить, а полнота — что решение будет найдено, если оно существует^[5].

Планирование с частичным порядком противопоставляется планированию с полным порядком, при котором все действия полностью упорядочиваются для решения задачи. Вопрос эффективности двух подходов изучен в работе Энтони Барретта и Даниэла Уэлда (1993); они показали, что планирование с частичным порядком быстрее и, следовательно, эффективнее. Используя таксономию Корфа для подцелей, исследователи показали, что такие алгоритмы эффективнее за счёт большей ‘‘тривиальной сериализуемости’’ (trivial serializability) по сравнению с полным порядком. ‘‘Тривиальная сериализуемость’’ облегчает быстрый поиск решений, если цель состоит из подцелей; затруднения возникают при ‘‘трудной сериализации’’ (laboriously serializable) или ‘‘несериализуемости’’ (nonserializable subgoals) целей^[6].

Планы с частичным порядком легко и эффективно решают аномалию Сассмана — хорошо известную проблему в области автоматического планирования. Эта особенность таких планировщиков сыграла значимую роль в их развитии^[7].

Главный недостаток таких методов — высокий вычислительный расход на каждый узел поиска: алгоритм сложнее, и на каждый шаг требуется больше вычислительных ресурсов. Это важно учитывать в области искусственного интеллекта: если, например, требуется реализовать задачу для робота, нужно учитывать энергозатраты. Хотя такие планы сокращают время поиска, иногда они неоправданно увеличивают потребление энергии^[4].