В области искусственного интеллекта , предпочтение на основе планирования является одной из форм автоматизированного планирования и планирования , которая сосредоточена на производстве планов , которые дополнительно удовлетворяют как много заданных пользователем предпочтений , как это возможно. Во многих проблемных областях задача может быть выполнена с помощью различных последовательностей действий (также известных как планы). Эти планы могут различаться по качеству: может быть много способов решить проблему, но обычно предпочтительнее, например, рентабельный, быстрый и безопасный.
Планировщики, основанные на предпочтениях, принимают эти предпочтения во внимание при составлении плана решения данной проблемы. Примеры программного обеспечения для планирования на основе предпочтений включают PPLAN [1] и HTNPlan-P [2] ( планирование HTN на основе предпочтений ).
Обзор
Предпочтения можно рассматривать как мягкие ограничения плана. Качество плана повышается, когда удовлетворяется больше предпочтений, но может оказаться невозможным удовлетворить все предпочтения в одном плане. Это отличается от жестких ограничений, которые должны соблюдаться во всех планах, создаваемых программным обеспечением для планирования. Эти жесткие ограничения являются частью знаний предметной области, в то время как мягкие ограничения (или предпочтения) отдельно задаются пользователем. Это позволяет повторно использовать одни и те же знания предметной области для разных пользователей, у которых могут быть разные предпочтения.
Использование предпочтений может также увеличить длину плана, чтобы удовлетворить больше предпочтений. Например, планируя поездку из дома в школу, пользователь может предпочесть купить чашку кофе по пути. Теперь программа для планирования могла спланировать сначала посещение Starbucks, а затем продолжение учебы. [3] Это увеличивает длину плана, но предпочтения пользователя удовлетворяются.
Планирование языка определения домена
Язык определения домена планирования (начиная с версии 3.0 [4] ) поддерживает спецификацию предпочтений с помощью preference
операторов. Например, заявление
(preference (always (clean room1)))
указывает на то, что пользователь предпочитает, room1
чтобы на каждом этапе плана было чисто. Другими словами, планировщик не должен планировать действие, которое приведет room1
к загрязнению. Как показывает этот пример, предпочтение оценивается в отношении всех состояний плана (если семантически требуется).
В дополнение к этому также поддерживаются always
другие конструкции, основанные на линейной темпоральной логике , такие как sometime
(хотя бы один раз во время плана), sometime-after
(планируется после определенного состояния) и at-most-once
(предпочтение сохраняется не более чем в одной последовательности состояний в плане. ).
Качество плана
Помимо определения того, удовлетворено ли предпочтение, нам также необходимо вычислить качество плана на основе того, сколько предпочтений выполнено. Для этой цели PDDL 3.0 включает выражение с именем, is-violated
которое равно «количеству различных предпочтений с данным именем, которые не удовлетворены в плане». [4] Для плана значение теперь может быть вычислено с помощью метрической функции, которая определяется с помощью :metric
:
(:metric minimize (+ (* 5 (is-violated pref1)) (* 7 (is-violated pref2))))
Этот пример метрической функции указывает, что вычисленное значение плана должно быть минимизировано (т. Е. План со значением v1 и план со значением v2, таким, что v1 < v2 , первый план является строго предпочтительным). Стоимость плана вычисляется заданной функцией, которая выражается в польской нотации . В этом случае нарушение второго предпочтения, pref2
, было дано большее наказание , чем первое предпочтение, pref1
.
Проблема удовлетворения ограничений
В области проблем удовлетворения ограничений существуют гибкие варианты, которые работают с мягкими ограничениями аналогично предпочтениям при планировании на основе предпочтений.
Рекомендации
- ^ PPLAN , Бьенвену и др.
- ^ HTN Планирование с предпочтениями , Сохраби и др.
- ^ Планирование с предпочтениями с использованием логического программирования , Сон и Понтелли
- ^ a b Детерминированное планирование в пятом международном конкурсе планирования: PDDL3 и экспериментальная оценка планировщиков , Gerevini et al.