Ускоренная перемотка вперед и pddl: является ли вычисленное решение лучшим?

Question

Как я могу быть уверен, что план, рассчитанный планировщиком ускоренного продвижения вперед, является лучшим из всех возможных планов?!

Существует ли автоматический инструмент для решения этой проблемы?!

большое спасибо!

Answer 1

Если я не помню его неправильно, FF не является оптимальным планировщиком, поэтому вы не можете быть уверены, что сгенерированный план является оптимальным. С другой стороны, FF быстро генерирует "достаточно хорошие" решения в отличие от оптимальных планировщиков (cpt4, bjolp, ECC...), которые обеспечивают оптимальные планы, но гораздо медленнее, чем удовлетворительные планировщики.

Вы можете найти список этих планировщиков здесь: IPC2011 Planners

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

Answer 2

Как уже отмечал Демпло, FF не гарантирует нахождения оптимальных решений. Причину этого важно знать, если вы действительно хотите найти оптимальные решения:

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

Чтобы "исправить" оба, нужно использовать алгоритм A* в сочетании с допустимой эвристикой.

Я рекомендую установить известную систему быстрого нисходящего планирования (www.fast-downward.org/), так как она поддерживает большое количество различных алгоритмов и эвристик. В качестве алгоритма, как сказано, следует выбирать A*, а в качестве эвристического - любое допустимое. При таком сочетании любой найденный план является оптимальным решением данной проблемы.

Просто замечание (в основном для экспертов по поиску / планированию): A* гарантированно найдет оптимальные решения, только если оно реализует поиск по дереву, а не поиск по графику (то есть, если дубликаты многократно расширяются). Если он реализует поиск в графе, для эвристики недостаточно быть допустимым, он также должен быть монотонным (также называемым непротиворечивым). Однако, согласно http://www.fast-downward.org/Doc/SearchEngine, он реализует поиск по дереву (я думаю). Также есть последовательная эвристика, тоже.