Главная arrow книги arrow Копия Глава 11. Основы планирования arrow Библиографические и исторические заметки
Библиографические и исторические заметки

Направление планирования в области искусственного интеллекта сформировалось на основе исследований в части поиска в пространстве состояний, доказательства теорем и теории управления, а также на основании практических потребностей робототехники, составления расписаний и других проблемных областей. Первой важной системой планирования стала система Strips [466], которая наглядно иллюстрирует продуктивность взаимодействия этих научных направлений. Система Strips была разработана как планирующий компонент программного обеспечения для проекта создания робота Shakey в институте SRI. Модель ее общей структуры управления была создана на основе программы GPS (General Problem Solver — общий решатель задач) [1129] — системы поиска в пространстве состояний, в которой используется анализ целей и средств (means—ends analysis). В системе Strips применялась одна из версий системы доказательства теорем QA3 [592] в качестве процедуры определения истинности предусловий для действий. Точные определения для языка Strips и анализ этого языка представлены Лифшицем [928]. Байлендер [213] показал, что простые задачи планирования Strips являются PSPACE-полными. В [467] приведена историческая ретроспектива проекта Strips и дан краткий обзор того, как этот проект связан с более современными разработками в области планирования.

Способ представления действий, использовавшийся в системе Strips, оказал гораздо более значительное влияние на дальнейшие разработки, чем ее алгоритмический подход. С тех пор почти во всех системах планирования применяется тот или иной вариант языка Strips. К сожалению, из-за огромного разнообразия вариантов задача их сравнения стала чрезмерно трудной. Со временем возникло лучшее понимание ограничений и компромиссов между формальными подходами. В языке ADL (Action Description Language— язык описания действий) [1195] ослаблены некоторые ограничения языка Strips и создана возможность представлять более реалистичные задачи. В [1119] рассматриваются схемы, применимые для компиляции определений ADL в определения Strips. Для использования в качестве стандартизированного синтаксиса, допускающего синтаксический анализ с помощью компьютера, который предназначен для представления определений на языках Strips, ADL и других языках, был предложен язык PDDL (Problem Domain Description Language — язык описания проблемной области) [548]. PDDL использовался в качестве стандартного языка для соревнований по планированию на конференции AIPS, начиная с 1998 года.