Войти
Планирование с частичным порядком - это подход к автоматическому планированию, который поддерживает частичное упорядочение между действиями и фиксирует упорядочение между действиями только тогда, когда оно принудительно, то есть упорядочение действий является частичным. Также в этом планировании не указано, какое действие будет выполнено первым при обработке двух действий. Напротив, планирование с полным порядком поддерживает общий порядок между всеми действиями на каждом этапе планирования. Учитывая проблему, в которой для достижения цели требуется некоторая последовательность действий, план частичного порядка определяет все действия, которые необходимо предпринять, но определяет порядок между действиями только там, где это необходимо.
Рассмотрим следующую ситуацию: человек должен пройти от начала до конца полосы препятствий. Эта полоса препятствий состоит из моста, качелей и качелей. Чтобы добраться до качелей и качелей, необходимо пройти по мосту. Как только они достигнуты, качели и качели можно перемещать в любом порядке, после чего становится доступен конец. В плане с частичным порядком упорядочение между этими препятствиями указывается только при необходимости. Сначала нужно пройти по мосту. Во-вторых, можно перемещать качели или качели. В-третьих, оставшееся препятствие можно преодолеть. Тогда можно будет пройти до конца. Планирование частичного заказа основывается на принципе наименьших обязательств для своей эффективности.
План частичного порядка или частичный план представляет собой план, который определяет все действия, которые должны быть приняты, но только определяет порядок между действиями в случае необходимости. Это результат планировщика частичного заказа. План частичного заказа состоит из четырех компонентов:
Чтобы возможные последовательности действий оставались максимально открытыми, набор условий порядка и причинно-следственных связей должен быть как можно меньше.
План - это решение, если набор открытых предварительных условий пуст.
Линеаризация плана частичного порядка является общим планом для того, полученным из конкретного плана частичного порядка; другими словами, оба плана заказов состоят из одних и тех же действий, причем порядок в линеаризации является линейным продолжением частичного порядка в исходном плане частичного заказа.
Например, план выпечки торта может начинаться:
Это частичный план, потому что порядок поиска яиц, муки и молока не указан, агент может бродить по магазину, реактивно накапливая все предметы в своем списке покупок, пока список не будет завершен.
Планировщик частичного порядка - это алгоритм или программа, которые построят план частичного порядка и будут искать решение. Входными данными является описание проблемы, состоящее из описаний начального состояния, цели и возможных действий.
Проблему можно интерпретировать как задачу поиска, где набор возможных планов частичного порядка является пространством поиска. Начальным состоянием будет план с открытыми предпосылками, равными целевым условиям. Конечным состоянием может быть любой план без открытых предварительных условий, то есть решение.
Начальное состояние - это начальные условия, и его можно рассматривать как предварительные условия для выполнения поставленной задачи. Для задачи сервировки стола начальным состоянием может быть чистый стол. Цель - это просто последнее действие, которое необходимо выполнить, например, накрытие стола. Операторы алгоритма - это действия, с помощью которых решается задача. В этом примере может быть два оператора: накрыть (скатерть) и разместить (стаканы, тарелки и столовое серебро).
Пространство плана алгоритма ограничено между его началом и концом. Алгоритм запускается, создавая начальное состояние, и заканчивается, когда все части цели были достигнуты. В примере настройки таблицы необходимо рассмотреть два типа действий - операторы размещения и размещения. Есть также четыре нерешенных оператора: действие 1, разложить скатерть, действие 2, тушение (тарелки), действие 3, тушение (столовое серебро) и действие 4, тушение (стаканы). Однако существует угроза, которая возникает, если действие 2, 3 или 4 предшествует действию 1. Эта угроза заключается в том, что предварительное условие для запуска алгоритма не будет выполнено, поскольку таблица больше не будет очищена. Таким образом, есть ограничения, которые необходимо добавить к алгоритму, заставляющие Действия 2, 3 и 4 следовать после Действия 1. Как только эти шаги будут выполнены, алгоритм завершится, и цель будет достигнута.
Как видно из представленных выше алгоритма, планирование частичного порядка может возникнуть определенные угрозы, то есть упорядоченности, которые угрожают разорвать подсоединенные действия, таким образом, потенциально разрушив весь план. Есть два способа устранения угроз:
Поощрение заказывает возможную угрозу после соединения, которое оно угрожает. Понижение в должности упорядочивает возможную угрозу до соединения, которое она угрожает.
Алгоритмы частичного планирования известны своей надежностью и полнотой, при этом звук определяется как полное упорядочение алгоритма, а полный определяется как способность найти решение при условии, что решение действительно существует.
Планирование частичного заказа противоположно планированию полного заказа, при котором действия выполняются сразу и для всей задачи. Возникает вопрос, когда есть два конкурирующих процесса, какой из них лучше? Энтони Баррет и Дэниел Велд в своей книге 1993 года утверждали, что частичное планирование превосходит планирование полного порядка, поскольку оно быстрее и, следовательно, более эффективно. Они проверили эту теорию, используя таксономию коллекций подцелей Корфа, в которой обнаружили, что частичное планирование работает лучше, потому что оно обеспечивает более тривиальную сериализуемость, чем планирование полного порядка. Тривиальная сериализуемость облегчает планировщику возможность быстро работать с целями, содержащими подцели. Планировщики работают медленнее, когда имеют дело с кропотливо сериализуемыми или несериализуемыми подцелями. Определяющим фактором, делающим подцель тривиально или кропотливо сериализуемой, является пространство поиска различных планов. Они обнаружили, что частичное планирование лучше подходит для поиска наиболее быстрого пути и, следовательно, является более эффективным из этих двух основных типов планирования.
Известно, что планы частичного порядка легко и оптимально разрешают аномалию Сассмана. Использование этого типа системы инкрементального планирования решает эту проблему быстро и эффективно. Это было результатом частичного планирования, которое укрепило свое место в качестве эффективной системы планирования.
Одним из недостатков этого типа системы планирования является то, что она требует гораздо большей вычислительной мощности для каждого узла. Эта более высокая стоимость на узел возникает из-за того, что алгоритм частичного планирования более сложен, чем другие. Это имеет важные последствия для искусственного интеллекта. Кодируя робота для выполнения определенной задачи, создатель должен учитывать, сколько энергии требуется. Хотя план частичного заказа может быть быстрее, он может не окупить затраты энергии на робота. Создатель должен знать и взвешивать эти два варианта, чтобы создать эффективного робота.
