Планирование частичного заказа - Википедия - Partial-order planning

Планирование частичного заказа это подход к автоматизированное планирование который поддерживает частичный порядок между действиями и фиксирует порядок между действиями только тогда, когда принудительно, т.е. упорядочение действий является частичным. Также в этом планировании не указано, какое действие будет выполнено первым при обработке двух действий. Напротив, планирование полного заказа поддерживает полный порядок между всеми действиями на каждом этапе планирования. Учитывая проблему, в которой требуется некоторая последовательность действий для достижения цели, план частичного заказа определяет все действия, которые необходимо выполнить, но определяет порядок между действиями только там, где это необходимо.

Рассмотрим следующую ситуацию: человек должен пройти от начала до конца полосы препятствий. Эта полоса препятствий состоит из моста, качелей и качелей. Чтобы добраться до качелей и качелей, необходимо пройти по мосту. Как только они достигнуты, качели и качели можно перемещать в любом порядке, после чего становится доступен конец. В плане с частичным порядком упорядочение между этими препятствиями указывается только при необходимости. Сначала нужно пройти по мосту. Во-вторых, можно перемещать качели или качели. В-третьих, оставшееся препятствие можно преодолеть. Тогда можно будет пройти до конца. Планирование частичного заказа опирается на Принцип наименьшего обязательства за его эффективность.

План частичного заказа

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

Набор действия (также известен как операторы).
А частичный заказ за действия. Он определяет условия порядка некоторых действий.
Набор причинно-следственные связи. Он определяет, какие действия соответствуют каким предварительным условиям других действий. Как вариант, набор привязки между переменными в действиях.
Набор открытые предварительные условия. Он указывает, какие предварительные условия не выполняются ни одним действием в плане частичного порядка.

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

План - это решение, если набор открытых предварительных условий пуст.

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

Пример

Например, план выпечки торта может начинаться:

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

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

Планировщик частичных заказов

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

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

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

Планируйте пространство

В планировать пространство алгоритма ограничено между его началом и концом. Алгоритм запускается, создавая начальное состояние, и заканчивается, когда все части цели были достигнуты. В примере настройки таблицы необходимо рассмотреть два типа действий - операторы размещения и размещения. Есть также четыре нерешенных оператора: действие 1, разложить скатерть, действие 2, тушение (тарелки), действие 3, тушение (столовое серебро) и действие 4, тушение (стаканы). Однако существует угроза, которая возникает, если действие 2, 3 или 4 предшествует действию 1. Эта угроза состоит в том, что предварительное условие для запуска алгоритма не будет выполнено, поскольку таблица больше не будет очищена. Таким образом, есть ограничения, которые необходимо добавить к алгоритму, заставляющие Действия 2, 3 и 4 следовать после Действия 1. Как только эти шаги будут выполнены, алгоритм завершится и цель будет достигнута.

Угрозы

Как видно из алгоритма, представленного выше, частичное планирование может столкнуться с определенными угрозами, что означает: заказы которые угрожают нарушить связанные действия, потенциально разрушая весь план. Есть два способа устранения угроз:

Повышение заказывает возможную угрозу после того, как соединение угрожает. Понижение заказывает возможную угрозу до соединения, которое она угрожает.

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

Планирование частичного заказа или общего заказа

Планирование частичного заказа противоположно планирование полного заказа, в котором действия упорядочиваются сразу и для всей задачи. Возникает вопрос, когда есть два конкурирующих процесса, какой из них лучше? Энтони Баррет и Дэниел Велд в своей книге 1993 года утверждали, что частичное планирование превосходит планирование полного заказа, поскольку он быстрее и, следовательно, эффективнее. Они проверили эту теорию, используя Таксономия коллекций подцелей Корфа, в котором они обнаружили, что частичное планирование работает лучше, потому что оно дает больше тривиальная сериализуемость чем планирование полного заказа. Тривиальная сериализуемость упрощает способность планировщика быстро работать с целями, содержащими подцели. Планировщики работают медленнее при работе с кропотливо сериализуемый или же несериализуемые подцели. Определяющим фактором, делающим подцель тривиально или кропотливо сериализуемой, является пространство поиска различных планов. Они обнаружили, что частичное планирование лучше помогает найти самый быстрый путь и, следовательно, является более эффективным из этих двух основных типов планирования.

Аномалия Сассмана

Известно, что планы частичного заказа легко и оптимально решают Аномалия Сассмана. Использование этого типа системы инкрементального планирования решает эту проблему быстро и эффективно. Это было результатом частичного планирования, которое укрепило свое место в качестве эффективной системы планирования.

Недостатки частичного планирования

Одним из недостатков системы планирования этого типа является то, что она требует гораздо большей вычислительной мощности для каждого узла. Эта более высокая стоимость на узел возникает из-за того, что алгоритм частичного планирования более сложен, чем другие. Это важно искусственный интеллект подразумеваемое. Кодируя робота для выполнения определенной задачи, создатель должен учитывать, сколько энергии требуется. Хотя план частичного заказа может быть быстрее, он может не окупить затраты энергии для робота. Создатель должен знать и взвешивать эти два варианта, чтобы создать эффективного робота.