Планирование на основе предпочтений - Preference-based planning

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

Планировщики, основанные на предпочтениях, принимают эти предпочтения во внимание при составлении плана решения данной проблемы. Примеры программного обеспечения для планирования на основе предпочтений включают: PPLAN[1] и HTNPlan-P[2] (на основе предпочтений Планирование HTN ).

Обзор

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

Использование предпочтений может также увеличить длину плана, чтобы удовлетворить больше предпочтений. Например, планируя поездку из дома в школу, пользователь может предпочесть купить чашку кофе по пути. Программное обеспечение для планирования теперь может планировать посещение Starbucks сначала а потом продолжай в школу.[3] Это увеличивает длину плана, но предпочтения пользователя удовлетворяются.

Планирование языка определения домена

В Планирование языка определения домена (начиная с версии 3.0[4]) поддерживает указание предпочтений через предпочтение заявления. Например, утверждение

(предпочтение (всегда (чистая комната1)))

указывает, что пользователь предпочитает, чтобы комната1 должен быть чистым на каждом этапе плана. Другими словами, планировщик не должен планировать действие, которое вызывает комната1 стать грязным. Как показывает этот пример, предпочтение оценивается в отношении всех состояний плана (если семантически требуется).

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

Качество плана

Помимо определения того, удовлетворено ли предпочтение, нам также необходимо вычислить качество плана на основе того, сколько предпочтений выполнено. Для этой цели PDDL 3.0 включает выражение, называемое нарушено <имя> что равно «количеству различных предпочтений с данным названием, которые не удовлетворяются в плане».[4] Для плана значение теперь можно вычислить с помощью метрической функции, которая указывается с помощью : метрика:

(: минимизация метрики (+ (* 5 (нарушено pref1)) (* 7 (нарушено pref2))))

Этот пример метрической функции указывает, что рассчитанное значение плана должно быть минимизировано (т. Е. План со значением v1 и план с ценностью v2 такой, что v1 < v2, предпочтение отдается первому плану). Стоимость плана вычисляется с помощью заданной функции, которая выражается в Польская нотация. В этом случае нарушение второго предпочтения, pref2, получил больший штраф, чем первое предпочтение, pref1.

Проблема удовлетворения ограничений

В районе проблемы удовлетворения ограничений существуют гибкие варианты, которые работают с мягкими ограничениями аналогично предпочтениям при планировании на основе предпочтений.

Рекомендации

  1. ^ PPLAN, Bienvenu et al.
  2. ^ Планирование HTN с предпочтениями, Сохраби и др.
  3. ^ Планирование с предпочтениями с использованием логического программирования, Сон и Понтелли
  4. ^ а б Детерминированное планирование в пятом международном конкурсе планировщиков: PDDL3 и экспериментальная оценка планировщиков, Геревини и др.