Зачем нам PDDL, когда у нас уже есть логика первого порядка?
Это может быть совершенно наивный вопрос, но мне интересно знать конкретные причины. Почему PDDL был разработан в первую очередь? Почему мы не можем рассуждать, используя First Order Logic?
2 ответа
Эффективность в решении
Использование более специфического языка для выражения вашей проблемы позволяет применять более конкретные алгоритмы для их решения.
С теоретической точки зрения FOL неразрешима, в то время как большинство разновидностей PDDL все еще разрешимы, потому что PDDL может только выражать проблемы планирования. И, например, классическое планирование с параметризованными действиями "только", как EXPSPACE-complete.
Конечно, EXPSPACE-полная проблема, выраженная в более общем / выразительном FOL, все еще разрешима в EXPSPACE, если вы знаете об этом. Но насколько сложно придумать общий FOL-решатель, который гарантирует решение всех задач в EXPSPACE, используя только экспоненциальное пространство?
Эффективность в моделировании
С практической стороны, выражение проблемы планирования с использованием языка, предназначенного для моделирования задач планирования, гораздо удобнее, чем записывать его в FOL.
Разве вы не предпочли бы писать C++ вместо Assembler? Даже если все, что вы можете написать на C++, можно выразить в Ассемблере.
Другой момент, явно не упомянутый ziggystar, - помимо того факта, что использование PDDL более удобно, чем FOL, - что проблемы планирования лежат в основе совершенно другой семантики, чем FOL.
В то время как ассемблер и C++ используются для описания компьютерных программ (причем ассемблер является более общим, чем C++, поскольку последний переводится на ассемблер), FOL служит совершенно иной цели, чем PDDL (в то время как FOL, как указал ziggystar, является более общим, чем PDDL).
FOL был разработан для выражения утверждений, предложений и отношений между объектами, например (цитируя пример ziggystar из аналогичного вопроса " Причина разработки логики первого порядка и PDDL") "Все люди могут думать". Обычно, когда мы используем FOL, нас просто интересует, справедлива ли формула (или, например, одно предложение следует из другого). Наиболее ярким примером будет следующий набор утверждений (формализованный в FOL): (1) "Все люди смертны". (2) "Сократ - это человек". При формализации этого с использованием FOL, мы можем спросить, следует ли (3) "Сократ смертен" из "(1) и (2)". Любой полный мыслитель FOL ответит на это да.
Планирование (и, следовательно, проблемы, описанные с использованием PDDL) заключается в том, чтобы задать вопрос о том, существует ли последовательность действий (то есть, экземпляры схем оператора PDDL), которые преобразуют начальное состояние (описание предшествующего миру выполнения действия) в некоторую желаемую цель. государство. Таким образом, планирование - это выполнение действий и обоснование того, существует ли такая последовательность. Это в основном не имеет ничего общего с FOL.
Поскольку FOL более выразителен, чем большинство стандартных формализмов планирования (например, "разновидности PDDL"), можно также использовать FOL для описания проблем планирования. Однако из-за полной разницы в семантике планирования и FOL нужно было бы "неправильно использовать" FOL для выражения проблем планирования - и на самом деле это сложный вопрос исследования, как можно это сделать. В случае, если вы заинтересованы: Google для "планирования как SAT".