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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

Угрозы

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

• Повышение
• Понижение в должности

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

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

Планирование частичного заказа и планирования полного заказа

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

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

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

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

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

Ссылки

• Искусственный интеллект: современный подход Стюарт Рассел, Питер Норвиг
• Введение в планирование с наименьшими обязательствами Дэниел Уэлд
• Камбхампати, С., Ноблок, Калифорния, Ян, К. (1994). Планирование как поиск уточнений: унифицированная основа для оценки компромиссов при проектировании при планировании частичного порядка. Эльзевир Наука.
• Пул Д., Макворт А. (2010). Планирование частичного порядка в основах искусственного интеллекта вычислительных агентов. Издательство Кембриджского университета.
• Дайер, CR «Планирование частичного порядка (глава 11)». (2003) CS 540. Университет Висконсина-Мэдисона. Мэдисон, Висконсин.
• Барретт А. и Уэлд Д. (1993). Планирование частичного порядка: оценка возможного повышения эффективности. Вашингтонский университет: факультет компьютерных наук и инженерии. Примечания .
• Симмонс, Рид. (2001). «Планирование, выполнение и обучение 1. Планирование частичного заказа». Университет Карнеги-Меллон. Питтсбург. Примечания.
• http://pdf.aminer.org/000/744/302/partial_order_planning_evaluating_possible_efficiency_gains.pdf
• http://pdf.aminer.org/000/037/660/decomposition_and_causality_in_partial_order_planning.pdf
• http://dl.acm.org/citation.cfm?id=1867345
• http://arxiv.org/pdf/1106.0249.pdf
• http://www.grastien.net/ban/teaching/06-planning4.pdf