Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 168
Текст из файла (страница 168)
Первым достаточно эффективным согласованным планировщиком бьша программа Соп|оппапг Огарйр!ап, или СОР, Смита и Уэлда [1437]. Феррарис и Гуинкилья [464], а также Ринтанен [1289] независимо разработали согласованные планировщики на основе алгоритма Яйтр2ап. В [148] описан согласованный планировщик, основанный на эвристическом поиске в пространстве доверительных состояний, который представляет собой резулыат дальнейшего развития идей, впервые реализованных в !960-х годах в частично наблюдаемых марковских процессах принятия решения, или РОМОР [Рап|а1|у ОЬзегтаЫе Магйоч ОесЬюп Ргосеззез) [см, главу 17). В настоящее время в самых быстрых согласованных планировщиках, осуществляющих поиск в пространстве доверительных состояний, таких как НБСР [118], для представления доверительных состояний используются двоичные диаграммы решений [В!лагу Рес|гйоп О[айгагп— ВРО) [200]; такие планировщики характеризуются быстродействием, примерно на пять порядков превышающим быстродействие алгоритма СОР.
Планировщик %агр!ап-С [1555] представляет собой один из вариантов планировщика УУагр1ап, который принадлежит к числу первых планировщиков, основанных на использовании условных действий [сонг!!![она! асйоп). В [1153] описаны основные проблемы, касающиеся условного планирования. Подход к организации условного планирования, описанный в данной главе, основан на эффективных алгоритмах поиска для циклических графов А]ЧР— ОК, разработанных Хименесом и Торрасом [737], а также Хансеном и Зильберщтейном [6!3]. В [119] описан подход на основе ВГ)О, позволяющий составлять условные планы с циклами.
В программе С-Вцг|бап [413] осуществляется условное планирование для действий с вероятностными результатами; это — та же проблема, попытки решения которой предпринимались с помощью процессов РОМРР [см. главу 17). Существует тесная связь между условным планированием и автоматизированным синтезом программ; большое количество ссылок по этой теме приведено в главе 9. Но работы в этих двух научных областях осуществлялись отдельно из-за невероятной разницы в стоимостях между выполнением мацгинных команд и осуществлением действий с помощью транспортных средств или манипуляторов роботов. В [934[ предпринята явная попытка добиться взаимного обогащения идеями между этими двумя областями. Глава 12.
Планирование и осуществление действий в реальном мире 615 Теперь в ретроспективе можно непредвзято наблюдать за тем, как появление основных классических алгоритмов планирования привело к созданию расширенных версий этих алгоритмов для проблемных областей, связанных с учетом неопределенности. Разработка методов на основе поиска привела к созданию методов поиска в пространстве доверительных состояний [148]; опыт в области использования алгоритма ядтр).ап привел к созданию стохастического алгоритма ядтрТап [970] и к разработке средств планирования с применением булевых логических выражений с кванторами [1289]; работы в области планирования с частичным упорядочением привели к созданию программ \)%Е [446», СМЕР [1206] и Саззапг)га [124!].
Опыт эксплуатации алгоритма СгарпрТап привел к появлению программы Бепзогу Огар!зр!ап, или БОР [1569], но задача разработки полностью вероятностного алгоритма СгарЬр1ап еще не совсем решена. Одной из самых первых значительных работ по контролю выполнения было создание программы Р!апех [465], которая применялась в сочетании с планировщиком Бгг!рз для управления роботом Бйа)геу. В программе Р1апех использовались треугольные таблицы (по сути — это эффективный механизм хранения для предусловий плана в каждом пункте плана), что обеспечивает возобновление работы после частичного неудачного завершения при выполнении плана без полного перепланирования. Модель выполнения, применяемая в роботе 8)за)геу, рассматривается более подробно в главе 25.
В планировгцике Хаз] [1021] проблема планирования рассматривается просто как спецификация выполнения сложного действия, что позволяет полностью унифицировать этапы выполнения и планирования В этом планировщике для формирования рассуждений о таких сложных действиях используются средства доказательства теорем. Одним из первых планировшиков, в котором осуществлен систематический подход к решению задач перепланирования, была программа Рйре (Бузгетп рог 1пгегас!1че Р)аппш8 апг) Ехесшюп гпоппопп8) [1593], [1594]. Эта программа использовалась в демонстрационных проектах в нескольких проблемных областях, включая планирование операций на взлетной палубе авианосца и составление производственного расписания для одного из пивзаводов в Австралии.
Еще в одном исследовании программа Рйре применялась для планирования строительства многоэтажных зданий, что представляет собой одну из наиболее сложных проблемных областей, в которых когда-либо применялись программы-планировщики. Система!реги (!пге8гагег) Р1апп!п8, Ехесибоп, апд Мошгопп8) [25] оказалась первой системой, в которой было применено сочетание планирования с частичным упорядочением и выполнения для создания непрерывно планирующего агента.
В алгоритме сопсйпиоиэ-РОР-Адепс, приведенном в этой книге, объединены идеи, взятые из системы 1регп, планировщика Росс)п] [570] и системы Сургезз [1595]. В середине 1980-х годов некоторые специалисты считали, что планирование с частичным упорядочением и связанные с ним методы никогда не позволят добиться достаточно высокого быстродействия для формирования эффективного поведения агента в реальном мире [7]. Вместо этого были предложены системы 'в. реактивного планирования; в своей основной форме эти системы представляли собой рефлексных агентов, возможно, с учетом внутреннего состояния, которые могут быть реализованы с помощью любого из самых различных представлений для правил "условие — действие".
В архитектуре обобщения Брукса [189] (см. главы 7 и 25) использовались многоуровневые конечные автоматы для управления движениями и Часть!У. Планирование 6!6 обхода препятствий шагающими и колесными роботами. Система Реп81 [7] обладала способностью играть в (полностью наблюдаемую) видеоигру с использованием логических схем в сочетании с визуальным" представлением текущих целей и внутреннего состояния агента. В качестве метода поиска по таблице для реактивного планирования были разработаны "универсальные планы" Шопперса [1366], но, как оказалось, они представляли собой повторное открытие идеи 'гь правил, которые уже давно использовались в марковских процессах принятия решений. Универсальный план (или правило) содержит отображение из любого состояния в действие, которое должно быть выполнено в этом состоянии.
Гинсберг [557] предпринял яростную эмоциональную атаку на идею универсальных планов и, в частности, показал неразрешимость результатов для некоторых формулировок задачи реактивного планирования. Шопперс [1367] ответил на эту статью не менее эмоционально. Как часто случается, сложившееся противоречие удалось разрешить с помощью гибридного подхода. Использование тщательно разработанных иерархий, планировшиков НТХ, таких как РКБ [542] и КАР [471), а также непрерывно планирующих агентов позволяет добиться сокрашения времени отклика, свойственного реактивным подходам, и осуществления сложного долгосрочного планирующего поведения во многих проблемных областях.
Популярность мультиагентного планирования особенно возросла в последние годы, но само это направление имеет долгую историю. В [833) прелложена формализация мультиагентного планирования в логике первого порядка, а описание в стиле Бгпрз дано в [1195]. Понятие совместного намерения, которое приобретает особую важность, если агенты должны выполнить совместный план, впервые было сформулировано в исследованиях по актам общения [276], [277]. Приведенное в данной главе описание многотельного планирования с частичным упорядочением основано на [157]. В этой главе была лишь слегка затронута тема согласования в мультиагентном планировании. В [424] обсуждается вопрос о том, как может осуществляться совместное использование задач агентами с помощью согласования действий между ними.
В [858] описана система для ведения Р1р1огпасу, настольной игры, в которой допускается согласование действий, формирование и разрушение коалиций, а также нарушение взятых на себя обязательств. В [1468] показано, что агенты могут взаимодействовать как члены одной команды в конкурентной, динамической, частично наблюдаемой среде робототехнического футбола. В [1564] приведен обзор мультиагентных систем, который занимает целую книгу. Модель орнитоида, приведенная на с. 609, разработана Рейнольдсом [1284), который получил премию Оскар Американской академии киноискусства за успешное применение этой модели во время съемок полчищ летучих мышей и стай пингвинов в кинофильме "Ваппап Кешгпз" (Бэтмен возвращается). УПРАЖНЕНИЯ 12.1.
Тщательно изучите представление времени и ресурсов, приведенное в разделе 12.1. а) Почему целесообразно сделать предикат пихасуоп(о) одним из результатов действия, а не предусмотреть в действии отдельное поле в форме Глава 12. Планирование и осуществление действий в реальном мире 617 12.2. 12.3. 12.4. 12.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
