Дополнительные источники информации. Результаты одних из первых, исследований основных принципов решения задач и планирования с использованием анализа целей и средств в искусственном интеллекте

Результаты одних из первых, исследований основных принципов решения задач и планирования с использованием анализа целей и средств в искусственном интеллекте описаны в [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. Планирование