Зачем нам нужен PDDL, когда у нас уже есть логика первого порядка?

Question

Это может быть совершенно наивный вопрос, но мне интересно знать конкретные причины. Почему PDDL был разработан в первую очередь? Почему мы не можем рассуждать, используя First Order Logic?

Answer 1

Эффективность в решении

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

С теоретической точки зрения FOL неразрешима, в то время как большинство разновидностей PDDL все еще разрешимы, потому что PDDL может только выражать проблемы планирования. И, например, классическое планирование с параметризованными действиями "только", как EXPSPACE-complete.

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

Эффективность в моделировании

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

Разве вы не предпочли бы писать C ++ вместо Assembler? Даже если все, что вы можете написать на C ++, можно выразить в Ассемблере.

Answer 2

Еще один момент, явно не упомянутый ziggystar , - в дополнение к тому факту, что использование PDDL удобнее, чем FOL, - что проблемы планирования лежат в основе совершенно другой семантики, чем FOL.

В то время как ассемблер и C ++ используются для описания компьютерных программ (причем ассемблер является более общим, чем C ++, поскольку последний переводится на ассемблер), FOL служит совершенно иным целям, чем PDDL (в то время как FOL - ziggystar * 1006). * указал, является более общим, чем PDDL).

FOL был разработан для выражения утверждений, предложений и отношений между объектами, например (например, ziggystar из аналогичного вопроса Причина разработки логики первого порядка и PDDL ) «Все люди могут думать». Обычно при использовании FOL нас просто интересует, выполняется ли формула (или, например, следует ли одно предложение из другого). Наиболее ярким примером может служить следующий набор предложений (формализованный в FOL): (1) «Все люди смертны». (2) «Сократ - это человек». При формализации этого с использованием FOL мы можем спросить, следует ли (3) «Сократ смертелен» из «(1) и (2)». Любой полный рассудок FOL ответит на это да.

Планирование (и, следовательно, описанные проблемы, основанные на PDDL) заключается в том, чтобы задать вопрос, существует ли последовательность действий (т. Е. Созданные схемы оператора PDDL), которые преобразуют исходное состояние (описание мирового предшествующего выполнения действия) в какое-то желаемое целевое состояние. Таким образом, планирование - это выполнение действий и обоснование того, существует ли такая последовательность. Это в основном не имеет ничего общего с FOL.

Поскольку FOL более выразителен, чем большинство стандартных формализмов планирования (например, «разновидности PDDL»), можно также использовать FOL для описания проблем планирования. Однако из-за полной разницы в семантике планирования и FOL нужно было бы «неправильно» использовать FOL для выражения проблем планирования - и на самом деле это сложный вопрос исследования, как можно это сделать. В случае, если вы заинтересованы: Google для "планирования как SAT".