Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 167
Текст из файла (страница 167)
До сих пор еще очень мало сделано в области совместного использования алгоритма Глава 12. Планирование и осуществление действий в реальном мире 6! 1 минимакса с такими методами, как планирование РОР и НТХ, которые выходят за рамки модели поиска в пространстве состояний, применяемой в главе 6. Мы вернемся к вопросу конкуренции в разделе 17.6, где рассматривается теория игр. 12.8. РЕЗЮМЕ В данной главе описаны некоторые сложности, связанные с планированием и осуществлением действий в реальном мире.
Основные идеи, изложенные в этой главе, перечислены ниже. ° Во многих действиях потребляются ресурсы, такие как деньги, топливо или сырье. Эти ресурсы удобно в целом рассматривать как числовые величины, а не пытаться рассуждать, скажем, о каждой отдельной монете или купюре во всем мире. Действия способны вырабатывать и потреблять ресурсы, поэтому обычно дешевле и эффективнее проверять частичные планы на предмет удовлетворения в них ресурсных ограничений, прежде чем предпринимать попытки их дальнейшего уточнения. ° Время — это один из наиболее важных ресурсов.
За его расходованием можно следить, применяя специализированные алгоритмы составления расписаний или объединяя составление расписаний с планированием. ° Планирование с помощью иерархической сети задач (Н1егагс!з!са1 Таз!г Мега'ог~— НТХ) позволяет агенту получить совет от проектировщика проблемной области в форме правил декомпозиции. Такой подход обеспечивает создание очень больших планов, требуемых для многих реальных приложений. ° В стандартных алгоритмах планирования предполагается наличие полной и правильной информации, а также детерминированной, полностью наблюдаемой среды.
Это предположение является недействительным во многих проблемных областях. ° С проблемой неполной информации в планировании можно справиться, используя действия по применению датчиков для получения необходимой информации. Условные планы позволяют агенту получать с помощью датчиков информацию о мире во время выполнения плана для определения того, по какой ветви плана он должен следовать дальше. В некоторых случаях может использоваться планирование без использования датчиков или согласованное планирование для формирования плана, который во время своего выполнения не требует применения результатов восприятия. И планы без использования датчиков, и условные планы могут быть сформированы по методу поиска в пространстве доверительных состояний. ° Неправильная информация приводит к тому, что предусловия действий и планов остаются невыполненными.
Контроль выполнения позволяет обнаруживать нарушения предусловий, создавая предпосылки успешного осуществления плана. ° В переплаиирующем агенте используется контроль выполнения и по мере необходимости осуществляются восстановительные действия для возврата к первоначальному плану. 612 Часть 1М. Планирование ° Непрерывно планирующий агент создает новые цели в процессе своей деятельности и реагирует на изменения ситуации в реальном времени. ° Мультиагеитиое планирование необходимо, если в среде имеются другие агенты, с которыми приходится кооперировать, конкурировать или координировать свои действия.
В многотельном планировании формируются совместные планы с использованием эффективной декомпозиции описаний совместных действий, но это планирование должно дополняться определенной формой координации, если два кооперативных агента должны согласовать друг с другом, какой из совместных планов следует выполнить. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Планирование с непрерывным учетом времени было впервые реализовано в программе Реизег [154!].
Проблема систематического представления времени в планах была решена Дином и др. ]358) в системе РогЬЬь Программы )х)оп!)п+ [1496) и 8)ре [1593], [1594] обладают способностью формировать рассуждения о распределении ограниченных ресурсов по различным этапам плана. Программа О-Р!ап [93] (планировщик НТХ) поддерживает равномерное, общее представление для ограничений, распространяющихся на время и ресурсы. Кроме приложения для Н)гасЬ1, упомянутого в этой главе, программа О-Р)ап применялась для планирования поставок программного обеспечения в компании Рпсе ЪЧагегйоцзе и для планирования сборки заднего моста автомобиля в компании 3а8цаг Сага.
Кроме того, был разработан целый ряд гибридных систем планирования и составления расписании: система !з)з [489], [490) использовалась при составлении производственных расписаний компании %езг)п8Ьоцзе, система Сап [392] осуществляла планирование машинной обработки и конструирования механических деталей, система РогЬ)п применялась для управления фабрикой, а система Ь)оп11п+ служила средством планирования поставок для военно-морского флота. После первоначального стремительного наплыва теоретических работ в области временного планирования в конце 1980-х годов наступило затишье, и лишь недавно интерес к этой теме возобновился в связи с тем, что появились новые алгоритмы и возросли обрабатывающие мощности, что привело к появлению возможности создавать новые практические приложения.
В двух разработанных недавно планировшиках, бара [401] и Т4 [627], используется прямой поиск в пространстве состояний в сочетании со сложными эвристическими функциями для учета действий, характеризующихся различными продолжительностями и требующих разных ресурсов. Альтернативой этого подхода является применение очень выразительных языков действий, но поиск в подобных системах должен осуществляться под управлением составленных людьми эвристик, характерных для данной проблемной области, как это сделано в системах АВРЕХА) [511], Н8Т8 [744! и 1хТеТ [549]. Разработки в области составления расписаний для аэрокосмических проектов имеют долгую историю.
Программа Т-8с)зев [412] использовалась для составления расписаний, представляющих собой последовательности принципиально важных команд для спутника !1озаг-!!. Программы Орг)шцт-А!Ч [1] и Р!ап-ЕК81 [509], основанные на программе О-Р!ап, применялись в Европейском космическом агентст- Глава 12. Планирование и осуществление действий в реальном мире 613 ве, соответственно, для сборки космических аппаратов и планирования наблюдений. Программа Брйге [741] использовалась для планирования наблюдений с помошью космического телескопа Хаббл в )МАБА, а система Брасе БЬцц1е Огоцпб Ргосезз!п8 Бс!зег)цйпй Бумегп [355[ осуществляла составление производственного расписания с охватом вплоть до 16 000 рабочих смен.
Программа Кешоге Айеп! [1108] стала первой автономной программой планирования и составления расписаний, применяемой для управления космическим аппаратом, которая работала на борту космического аппарата Реер Брасе Опе в 1999 году. В (1527] приведен обзор литературы по применению средств составления производственных расписаний в области исследования операций; теоретические результаты приведены в (993]. Применяемые в программе Бгг!рз средства для изучения 'ж макроопераций [" микрооператоров", состоящих из последовательности примитивных этапов) могут рассматриваться как первый механизм иерархического планирования (465].
Иерархия использовалась также в системе ) атха!у [1410]. В системе АЬмпрх (1336] была реализована идея 'з. иерархии абстракции, на основе которой бьшо разрешено игнорировать предусловия действий низкого уровня при планировании на более высоких уровнях, чтобы можно было проше выявить общую структуру рабочего плана. В тезисах докторской диссертации Остина Тэйта ]1494] и в работе Эрла Сакердоти (1338] были разработаны основные идеи планирования НТЬ) в его современной форме. Многие практически применяемые планировшики, включая О-Р!ап и Б!ре, представляют собой планировшики НТЬ).
В [1628] обсуждаются свойства действий, благодаря которым планирование НТЬ) становится эффективным. В (443], ]444] представлен планировщик с полной иерархической декомпозицией, а также приведен ряд результатов анализа сложности для чистых планировшиков НТ1М. Другие авторы (25], [72], [766], [!635] предложили гибридный подход, принятый в данной главе, согласно которому декомпозиции просто представляют собой егде одну форму уточнения, которая может использоваться в планировании с частичным упорядочением.
Начиная с исследований по использованию микрооператоров в языке Бгг!рз, одной из целей иерархического планирования было повторное использование ранее накопленного опыта планирования в форме обобшенных планов. В некоторых системах, включая Боаг [881) и Ргоб!8у [221], в качестве средства обобщения ранее вычисленных планов применялся метод обучения иа основе объяснений (ехр1апабопЬазед 1еагп!пй), описанный более подробно в главе 19.
Альтернативный подход состоит в том, что ранее вычисленные планы должны сохраняться в их первоначальной форме, а затем использоваться повторно для решения новых подобных проблем по аналогии с первоначальной проблемой. Именно этот подход принят в области, получившей название 'гзх планирование иа основе прецедентов [сазе-Ьазес) р!апп!пй) [23], (220], ]609]. В [765] приведено обоснование того мнения, что планирование на основе прецедентов должно рассматриваться как форма планирования на основе уточнения и что этот метод может служить средством формального описания для планирования с частичным упорядочением на основе прецедентов, На самых ранних этапах осушествления робототехнических проектов, в которых использовались методы планирования, включая БЬайеу [465] и Ргедду [1045], была обнаружена проблема непредсказуемости и частичной наблюдаемости реальных вариантов среды.
Эта проблема стала привлекать больше внимания после публикации статьи Макдермотта Р!алтл8 алп'Асг!л8 [!021], оказавшей значительное влияние на ход дальнейших исследований. 614 Часть!У. Планирование В ранних планировщиках, в которых отсутствовали условные выражения и циклы, не была явно реализована концепция условного планирования, но несмотря на это, некоторые из таких планировщиков в ответ на неопределенность среды иногда прибегали к стилю, предусматривающему принудительный переход в заданное состояние. В программе ]Чоа1и разработанной Сакердоти, такой принудительный переход использовался в предлагаемом программой решении задачи с "ключами и ягциками".
Это — известная задача в области планирования, в которой планировщик имеет мало информации о начальном состоянии. Мэйсон [996] доказал, что вробототехническом планировании часто можно и нужно отказываться от сбора информации с помощью датчиков, и описал план без использования датчиков, позволяющий передвинуть инструмент в заданную позицию на столе с помощью последовательности раскачивающих действий, независимой от начальной позиции. Мы опишем эту идею в контексте робототехники [рис. 25.16). Голдмен и Болли [572] ввели термин согласованное планирование [сопГоппап! р!апп|п8) применительно к планировщикам без использования дазчиков, которые позволяют справиться с неопределенностью, принудительно переводя мир в известные состояния, и отметили, что планы без использования датчиков часто эффективнее, даже если агент имеет датчики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
