Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

План частичного заказа [ править ]

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

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

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

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

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

Пример [ править ]

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

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

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

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

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

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

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

План пространства [ править ]

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

Угрозы [ править ]

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

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

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

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

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

Аномалия Сассмана [ править ]

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

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

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

Ссылки [ править ]

  • Искусственный интеллект: современный подход Стюарта Рассела, Питера Норвига
  • Введение в планирование наименьших обязательств , Дэниел Уэлд
  • Камбхампати, С., Ноблок, Калифорния, Ян, К. (1994). Планирование как поиск уточнения: унифицированная структура для оценки компромиссов при проектировании при частичном планировании. Elsevier Science.
  • Пул, Д., Макворт, А. (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