Результаты одних из первых, исследований основных принципов решения задач и планирования с использованием анализа целей и средств в искусственном интеллекте описаны в [113]. Эти принципы были реализованы в известной программе GPS (General Problem Solver — общий решатель задач); результаты исследования поведения этой программы подробно описаны в [46]. Важную роль в развитии искусственного интеллекта сыграла также программа планирования STRIPS [49], [50], которую можно рассматривать как одну из реализаций GPS. В программе STRIPS применен способ представления пространства планирования (с помощью отношений adds, deletes и can), который используется также и в этой главе. Двумя другими способами представления данных для планирования на основе логики (не рассматриваемыми в данной главе) являются исчисление ситуаций [80] и исчисление событий [82], [143]. Механизмы программы STRIPS и различные относящиеся к ней идеи и усовершенствования описаны в [116], где представлены также изящные формулировки алгоритмов планирования на основе логики, предложенные Грином (Green) и Ковальски (Kowalski). Одним из первых планировщиков на языке Prolog, представляющих значительный интерес, является программа WARPLAN [164]. Эту программу можно рассматривать как еще одну реализацию программы STRIPS, усовершенствованную в определенном отношении. Описание программы WARPLAN можно найти и в других источниках, например в [33], В [163] приведены результаты исследования феноменов взаимодействия конъюнктивных целей, а в их числе рассматривается также принцип регрессии целей. Задача регрессии целей связана с определением слабейших предпосылок, используемых при доказательстве правильности программы. Сложности, которые могут возникнуть перед планировщиком с защитой целей во время решения задачи, приведенной на рис. 17.1, известны в литературе как аномалия Зюссмана (Sussman) (см., например, [163]}. Одни из первых результатов разработки процедуры планирования с частичным упорядочением описаны в [134] и [157]. В [29] рассматриваются попытки предоставить единообразную теоретическую инфраструктуру для описания и исследования различных механизмов планирования с частичным упорядочением. В [166] приведен обзор результатов в области планирования с частичным упорядочением. С точки зрения теории желательно гарантировать полноту решений планировщика, но этого можно добиться лишь за счет значительного увеличения комбинаторной сложности. Поэтому намного более перспективный подход с точки зрения практики предложен в [30], где исследуются различные способы применения в планировщике знаний о конкретной проблемной области для уменьшения комбинаторной сложности. В [6] приведен отредактированный сборник классических работ по планированию. Большой объем сведений по планированию приведен в таких книгах по искусственному интеллекту общего характера, как [126] и [133]. Очень ценные статьи по планированию иногда появляются в журнале Artificial Intelligence (см., например, специальный выпуск по планированию и составлению расписаний [4]).
Глава 17. Планирование
