БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Планирование с непрерывным учетом времени было впервые реализовано в программе Deviser [1541]. Проблема систематического представления времени в планах была решена Дином и др. [358] в системе Forbin. Программы Nonlin+ [1496] и Sipe [1593], [1594] обладают способностью формировать рассуждения о распределении ограниченных ресурсов по различным этапам плана. Программа 0-Р1ап [93] (планировщик HTN) поддерживает равномерное, общее представление для ограничений, распространяющихся на время и ресурсы. Кроме приложения для Hitachi, упомянутого в этой главе, программа 0-Р1ап применялась для планирования поставок программного обеспечения в компании Price Waterhouse и для планирования сборки заднего моста автомобиля в компании Jaguar Cars. Кроме того, был разработан целый ряд гибридных систем планирования и составления расписаний: система Isis [489], [490] использовалась при составлении производственных расписаний компании Westinghouse, система Gari [392] осуществляла планирование машинной обработки и конструирования механических деталей, система Forbin применялась для управления фабрикой, а система Nonlin+ служила средством планирования поставок для военно-морского флота.
После первоначального стремительного наплыва теоретических работ в области временного планирования в конце 1980-х годов наступило затишье, и лишь недавно интерес к этой теме возобновился в связи с тем, что появились новые алгоритмы и возросли обрабатывающие мощности, что привело к появлению возможности создавать новые практические приложения. В двух разработанных недавно планировщиках, Sapa [401] и Т4 [627], используется прямой поиск в пространстве состояний в сочетании со сложными эвристическими функциями для учета действий, характеризующихся различными продолжительностями и требующих разных ресурсов. Альтернативой этого подхода является применение очень выразительных языков действий, но поиск в подобных системах должен осуществляться под управлением составленных людьми эвристик, характерных для данной проблемной области, как это сделано в системах ASPEN [511], HSTS [744] и IxTeT [549].
Разработки в области составления расписаний для аэрокосмических проектов имеют долгую историю. Программа T-Sched [412] использовалась для составления расписаний, представляющих собой последовательности принципиально важных команд для спутника Uosat-II. Программы Optimum-AIV [1] и Plan-ERSl [509], основанные на программе О-Plan, применялись в Европейском космическом агентстве, соответственно, для сборки космических аппаратов и планирования наблюдений. Программа Spike [741] использовалась для планирования наблюдений с помощью космического телескопа Хаббл в NASA, а система Space Shuttle Ground Processing Scheduling System [355] осуществляла составление производственного расписания с охватом вплоть до 16 ООО рабочих смен. Программа Remote Agent [1108] стала первой автономной программой планирования и составления расписаний, применяемой для управления космическим аппаратом, которая работала на борту космического аппарата Deep Space One в 1999 году. В [1527] приведен обзор литературы по применению средств составления производственных расписаний в области исследования операций; теоретические результаты приведены в [993].
Применяемые в программе Strips средства для изучения макроопераций ("микрооператоров", состоящих из последовательности примитивных этапов) могут рассматриваться как первый механизм иерархического планирования [465]. Иерархия использовалась также в системе Lawaly [1410]. В системе Abstrips [1336] была реализована идея иерархии абстракции, на основе которой было разрешено игнорировать предусловия действий низкого уровня при планировании на более высоких уровнях, чтобы можно было проще выявить общую структуру рабочего плана. В тезисах докторской диссертации Остина Тэйта [1494] и в работе Эрла Сакердоти [1338] были разработаны основные идеи планирования HTN в его современной форме. Многие практически применяемые планировщики, включая О-Plan и Sipe, представляют собой планировщики HTN. В [1628] обсуждаются свойства действий, благодаря которым планирование HTN становится эффективным. В [443], [444] представлен планировщик с полной иерархической декомпозицией, а также приведен ряд результатов анализа сложности для чистых планировщиков HTN. Другие авторы [25], [72], [766], [1635] предложили гибридный подход, принятый в данной главе, согласно которому декомпозиции просто представляют собой еще одну форму уточнения, которая может использоваться в планировании с частичным упорядочением.
Начиная с исследований по использованию микрооператоров в языке Strips, одной из целей иерархического планирования было повторное использование ранее накопленного опыта планирования в форме обобщенных планов. В некоторых системах, включая Soar [881] и Prodigy [221], в качестве средства обобщения ранее вычисленных планов применялся метод обучения на основе объяснений (explanation-based learning), описанный более подробно в главе 19. Альтернативный подход состоит в том, что ранее вычисленные планы должны сохраняться в их первоначальной форме, а затем использоваться повторно для решения новых подобных проблем по аналогии с первоначальной проблемой. Именно этот подход принят в области, получившей название планирование на основе прецедентов (case-based planning) [23], [220], [609]. В [765] приведено обоснование того мнения, что планирование на основе прецедентов должно рассматриваться как форма планирования на основе уточнения и что этот метод может служить средством формального описания для планирования с частичным упорядочением на основе прецедентов.
На самых ранних этапах осуществления робототехнических проектов, в которых использовались методы планирования, включая Shakey [465] и Freddy [1045], была обнаружена проблема непредсказуемости и частичной наблюдаемости реальных вариантов среды. Эта проблема стала привлекать больше внимания после публикации статьи Макдермотта Planning and Acting [1021], оказавшей значительное влияние на ход дальнейших исследований.
В ранних планировщиках, в которых отсутствовали условные выражения и циклы, не была явно реализована концепция условного планирования, но несмотря на это, некоторые из таких планировщиков в ответ на неопределенность среды иногда прибегали к стилю, предусматривающему принудительный переход в заданное состояние. В программе Noah, разработанной Сакердоти, такой принудительный переход использовался в предлагаемом программой решении задачи с "ключами и ящиками". Это — известная задача в области планирования, в которой планировщик имеет мало информации о начальном состоянии. Мэйсон [996] доказал, что в робототехническом планировании часто можно и нужно отказываться от сбора информации с помощью датчиков, и описал план без использования датчиков, позволяющий передвинуть инструмент в заданную позицию на столе с помощью последовательности раскачивающих действий, независимой от начальной позиции. Мы опишем эту идею в контексте робототехники (рис. 25.16).
Голдмен и Бодди [572] ввели термин согласованное планирование (conformant planning) применительно к планировщикам без использования датчиков, которые позволяют справиться с неопределенностью, принудительно переводя мир в известные состояния, и отметили, что планы без использования датчиков часто эффективнее, даже если агент имеет датчики. Первым достаточно эффективным согласованным планировщиком была программа Conformant Graphplan, или CGP, Смита и Уэлда [1437]. Феррарис и Гуинки-лья [464], а также Ринтанен [1289] независимо разработали согласованные планировщики на основе алгоритма SATplan. В [148] описан согласованный планировщик, основанный на эвристическом поиске в пространстве доверительных состояний, который представляет собой результат дальнейшего развития идей, впервые реализованных в 1960-х годах в частично наблюдаемых марковских процессах принятия решения, или POMDP (Partially Observable Markov Decision Processes) (см. главу 17). В настоящее время в самых быстрых согласованных планировщиках, осуществляющих поиск в пространстве доверительных состояний, таких как HSCP [118], для представления доверительных состояний используются двоичные диаграммы решений (Binary Decision Diagram — BDD) [200]; такие планировщики характеризуются быстродействием, примерно на пять порядков превышающим быстродействие алгоритма CGP.
Планировщик Warplan-C [1555] представляет собой один из вариантов планировщика Warplan, который принадлежит к числу первых планировщиков, основанных на использовании условных действий (conditional action). В [1153] описаны основные проблемы, касающиеся условного планирования.
Подход к организации условного планирования, описанный в данной главе, основан на эффективных алгоритмах поиска для циклических графов AND—OR, разработанных Хименесом и Торрасом [737], а также Хансеном и Зильберштейном [613]. В [119] описан подход на основе BDD, позволяющий составлять условные планы с циклами. В программе C-Buridan [413] осуществляется условное планирование для действий с вероятностными результатами; это — та же проблема, попытки решения которой предпринимались с помощью процессов POMDP (см. главу 17).
Существует тесная связь между условным планированием и автоматизированным синтезом программ; большое количество ссылок по этой теме приведено в главе 9. Но работы в этих двух научных областях осуществлялись отдельно из-за невероятной разницы в стоимостях между выполнением машинных команд и осуществлением действий с помощью транспортных средств или манипуляторов роботов. В [934] предпринята явная попытка добиться взаимного обогащения идеями между этими двумя областями.
Теперь в ретроспективе можно непредвзято наблюдать за тем, как появление основных классических алгоритмов планирования привело к созданию расширенных версий этих алгоритмов для проблемных областей, связанных с учетом неопределенности. Разработка методов на основе поиска привела к созданию методов поиска в пространстве доверительных состояний [148]; опыт в области использования алгоритма SATplan привел к созданию стохастического алгоритма SATplan [970] и к разработке средств планирования с применением булевых логических выражений с кванторами [1289]; работы в области планирования с частичным упорядочением привели к созданию программ UWL [446], CNLP [1206] и Cassandra [1241]. Опыт эксплуатации алгоритма Graphplan привел к появлению программы Sensory Graphplan, или SGP [1569], но задача разработки полностью вероятностного алгоритма Graphplan еще не совсем решена.
Одной из самых первых значительных работ по контролю выполнения было создание программы Planex [465], которая применялась в сочетании с планировщиком Strips для управления роботом Shakey. В программе Planex использовались треугольные таблицы (по сути — это эффективный механизм хранения для предусловий плана в каждом пункте плана), что обеспечивает возобновление работы после частичного неудачного завершения при выполнении плана без полного перепланирования. Модель выполнения, применяемая в роботе Shakey, рассматривается более подробно в главе 25. В планировщике Nasi [1021] проблема планирования рассматривается просто как спецификация выполнения сложного действия, что позволяет полностью унифицировать этапы выполнения и планирования В этом планировщике для формирования рассуждений о таких сложных действиях используются средства доказательства теорем.
Одним из первых планировщиков, в котором осуществлен систематический подход к решению задач перепланирования, была программа Sipe (System for Interactive Planning and Execution monitoring) [1593], [1594]. Эта программа использовалась в демонстрационных проектах в нескольких проблемных областях, включая планирование операций на взлетной палубе авианосца и составление производственного расписания для одного из пивзаводов в Австралии. Еще в одном исследовании программа Sipe применялась для планирования строительства многоэтажных зданий, что представляет собой одну из наиболее сложных проблемных областей, в которых когда-либо применялись программы-планировщики.
Система Ipem (Integrated Planning, Execution, and Monitoring) [25] оказалась первой системой, в которой было применено сочетание планирования с частичным упорядочением и выполнения для создания непрерывно планирующего агента. В алгоритме Continuous-POP-Agent, приведенном в этой книге, объединены идеи, взятые из системы Ipem, планировщика Puccini [570] и системы Cypress [1595].
В середине 1980-х годов некоторые специалисты считали, что планирование с частичным упорядочением и связанные с ним методы никогда не позволят добиться достаточно высокого быстродействия для формирования эффективного поведения агента в реальном мире [7]. Вместо этого были предложены системы реактивного планирования; в своей основной форме эти системы представляли собой рефлексных агентов, возможно, с учетом внутреннего состояния, которые могут быть реализованы с помощью любого из самых различных представлений для правил "условие—действие". В архитектуре обобщения Брукса [189] (см. главы 7 и 25) использовались многоуровневые конечные автоматы для управления движениями и обхода препятствий шагающими и колесными роботами. Система Pengi [7] обладала способностью играть в (полностью наблюдаемую) видеоигру с использованием логических схем в сочетании с "визуальным" представлением текущих целей и внутреннего состояния агента.
В качестве метода поиска по таблице для реактивного планирования были разработаны "универсальные планы" Шопперса [1366], но, как оказалось, они представляли собой повторное открытие идеи правил, которые уже давно использовались в марковских процессах принятия решений. Универсальный план (или правило) содержит отображение из любого состояния в действие, которое должно быть выполнено в этом состоянии. Гинсберг [557] предпринял яростную эмоциональную атаку на идею универсальных планов и, в частности, показал неразрешимость результатов для некоторых формулировок задачи реактивного планирования. Шопперс [1367] ответил на эту статью не менее эмоционально.
Как часто случается, сложившееся противоречие удалось разрешить с помощью гибридного подхода. Использование тщательно разработанных иерархий, планировщиков HTN, таких как PRS [542] и RAP [471], а также непрерывно планирующих агентов позволяет добиться сокращения времени отклика, свойственного реактивным подходам, и осуществления сложного долгосрочного планирующего поведения во многих проблемных областях.
Популярность мультиагентного планирования особенно возросла в последние годы, но само это направление имеет долгую историю. В [833] предложена формализация мультиагентного планирования в логике первого порядка, а описание в стиле Strips дано в [1195]. Понятие совместного намерения, которое приобретает особую важность, если агенты должны выполнить совместный план, впервые было сформулировано в исследованиях по актам общения [276], [277]. Приведенное в данной главе описание многотельного планирования с частичным упорядочением основано на [157].
В этой главе была лишь слегка затронута тема согласования в мультиагентном планировании. В [424] обсуждается вопрос о том, как может осуществляться совместное использование задач агентами с помощью согласования действий между ними. В [858] описана система для ведения Diplomacy, настольной игры, в которой допускается согласование действий, формирование и разрушение коалиций, а также нарушение взятых на себя обязательств. В [1468] показано, что агенты могут взаимодействовать как члены одной команды в конкурентной, динамической, частично наблюдаемой среде робототехнического футбола. В [1564] приведен обзор мультиа-гентных систем, который занимает целую книгу.
Модель орнитоида, приведенная на с. 609, разработана Рейнольдсом [1284], который получил премию Оскар Американской академии киноискусства за успешное применение этой модели во время съемок полчищ летучих мышей и стай пингвинов в кинофильме "Batman Returns" (Бэтмен возвращается).