Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 155
Текст из файла (страница 155)
Такая сложность часто наблюдается не только в теории, но и на практике. Одно из заданий, которое предложили исследователям для проверки их сил в 1963 году (найти оптимальное расписание для задачи, в которой рассматриваются только 1О машин и 10 работ по 100 действий каждая), не удавалось решить в течение 23 лет (900]. Для его решения было опробовано много подходов, включая метод ветвей и границ, алгоритм эмуляции отжига, поиск с запретами, метод удовлетворения ограничений и другие методы, описанные в части 11 этой книги.
Одной из простых, но широко применяемых эвристик является алгоритм с 'в. минимальным резервом. В нем планирование действий осуществляется в режиме жадного поиска. Во время каждой итерации в этом алгоритме рассматриваются не введенные в расписание действия, для которых в расписании заданы все их преемники, и в расписание вводится то действие, которое имеет наименьший резерв для самого раннего возможного времени начала. После этого в алгоритме обновляются значения времени е5 и ь5 для каждого затронутого действия и повторя- 570 Часть !Ч.
Планирование ется итерация. Эвристика основана на том же принципе, что и эвристика с "наиболее ограниченной переменной" в задачах удовлетворения ограничений. Этот алгоритм хорошо работает на практике, но применительно к рассматриваемой задаче сборки он привел к получению !30-минутного решения, а не 115-минутного решения, показанного на рис.
12.2. Подход, принятый в этом разделе, состоит в том, что "вначале следует оставлять план, а затем расписание". Это означает, что общая задача подразделяется на этап планирования, в котором выбираются и частично упорядочиваются действия лля достижения целей данной задачи, и на следующий за ним этап составления расписания, в котором в план вводится временная информация для обеспечения того, чтобы он соответствовал ограничениям по ресурсам и срокам. Такой подход широко применяется в организациях, занимающихся реальным планированием производства и поставок, в которых этап планирования часто выполняется экспертами-людьми.
Однако, если существуют жесткие ограничения на ресурсы, могут возникать такие ситуации, что одни допустимые планы приводят к получению гораздо более лучших графиков, чем другие. В этом случае имеет смысл интегрировать этапы планирования и составления расписаний, принимая во внимание продолжительности и совпадения действий во времени на этапе создания плана с частичным упорядочением. Для учета такой информации могут быть дополнены некоторые алгоритмы планирования, описанные в главе 11. Например, планировщики с частичным упорядочением могут обнаруживать нарушения ресурсных ограничений во многом с помощью такого же способа, который в них используется для обнаружения конфликтов с помощью причинных связей. А эвристики могут быть модифицированы для оценки общего времени завершения плана, а не просто суммарной стоимости всей лействий.
В настоящее время в этой области исследований ведется активная работа. 12.2. ПЛАНИРОВАНИЕ ИЕРАРХИЧЕСКОЙ СЕТИ ЗАДАЧ Одной из наиболее привлекательных идей в области решения сложных задач является Ъ. иерархическая декомпозиция. На основе иерархии процедур или классов объектов создается сложное программное обеспечение; из иерархии боевых подразделений складываются армии; иерархии отделов, филиалов и дочерних организаций лежат в основе правительств и корпораций. Основное преимущество иерархической структуры состоит в том, что на каждом уровне иерархии вычислительная задача, военная операция или административная функция сводится к небольшому количеству действий, выполняемых на более низком уровне, поэтому вычислительная стоимость поиска правильного способа упорядочения этих действий для решения текущей задачи очень невелика.
С другой стороны, в неиерархических методах задача сводится к очень большому количеству отдельных действий; при решении крупномасштабных задач такой подход становится полностью неприменимым. Но в наилучшем случае 1в котором высокоуровневые решения всегда сводятся к решениям, имеющим удовлетворительные низкоуровневые реализации) иерархические методы могут привести к созданию алгоритмов планирования с линейными, а не экспоненциальными затратами времени. В настоящем разделе рассматривается метод планирования, основанный на 'ж иерархических сс задач, или сетях НТ)х) 1Н1егагсЫса! Таз)г )х)е1чог)г). В приня- 571 Глава 12.
Планирование и осуществление действий в реальном мире том нами подходе объединены идеи из области планирования с частичным упорядочением (раздел! 1.3) и из области, известной под названием "планирование в иерархических сетях задач", или планирование НТХ. В планировании НТ)к( первоначальный план, который описывает задачу, рассматривается как описание на очень высоком уровне того, что должно быть сделано, например строительство дома. Планы уточняются путем применения Ъ. декомпозиций действий. В каждой декомпозиции действия одно действие высокого уровня сводится к частично упорядоченному множеству действий низкого уровня. Поэтому в декомпозициях действий воплощены знания о том, как осуществляются действия.
Например, строительство дома может быть сведено к получению разрешения, найму подрядчика, осуществлению строительства и оплате работы подрядчика (такая декомпозиция показана на рис. ! 2.3). Этот процесс продолжается до тех пор, пока в плане не остаются только сзк примитивные действия. Как правило, примитивными считаются такие действия, которые могут быть выполнены агентом автоматически. Например, для генерального подрядчика такое действие, как "оформление ландшафтной архитектуры", может оказаться примитивным, поскольку оно сводится к привлечению подрядчика по ландшафтной архитектуре, а для подрядчика по ландшафтной архитектуре могут рассматриваться как примитивные действия, подобные "посадке на этом участке рододендронов". папи даазе вы!о Нонке компонуется на Рис.
72 3. Одна из возиоясиых декомпозиций дяя действия вп! у дно зэе В "чистом" планировании НТ)к( планы разрабатываются только путем последовательной декомпозиции действий. Поэтому планирование НТХ может рассматриваться как процесс конкретизации описания некоторой деятельности, а не как процесс создания описания деятельности, начиная с пустого действия (как в случае планирования в пространстве состояний и планирования с частичным упорядочением). Как оказалось, каждое описание действия Вгпрз может быть преобразовано в декомпозицию действия (см. упр. 12.6), а планирование с частичным упорядочением может рассматриваться как частный случай чистого планирования НТ)к). Однако для некоторых задач (особенно для тех, в которых применяется так называемая "новаторская" постановка с конъюнктивными целями) подход с использованием чистого планирования НТХ становится не совсем естественным.
Поэтому авторы предпочитают применять гибридный подход, в котором декомпозиции действий используются как уточнения плана в планировании с частичным упорядочением, в до- 572 Часть 1"гг. Планирование полнение к стандартным операциям определения открытых условий и разрешения конфликтов путем введения ограничений упорядочения. (Подход, в котором планирование НТХ рассматривается как расширение планирования с частичным упорядочением, имеет дополнительное преимущество в том, что могут использоваться те же соглашения по системе именования вместо введения полностью нового набора обозначений.) Начнем с более подробного описания декомпозиций действий.
Затем рассмотрим, как можно модифицировать алгоритм планирования с частичным упорядочением лля учета декомпозиций, и, наконец, рассмотрим вопросы полноты, сложности и практической применимости алгоритмов. Представление декомпозиций действий Общие описания методов декомпозиции действий хранятся в ох библиотеке планов, из которой они извлекаются и конкретизируются для обеспечения потребностей формирования текущего плана.
Каждый метод представляет собой выражение в форме ()есотрояе(а, д) . Это выражение указывает, что может быть выполнена декомпозиция действия а на план д, представленный в виде плана с частичным упорядочением, как описано в разделе 11.3. Строительство дома — это прекрасный, конкретный пример, поэтому мы будем использовать его для иллюстрации концепций декомпозиции действия. На рис. 12.3 показана одна возможная декомпозиция действия Ви11дноияе на четыре действия низкого уровня, а в листинге ! 2.3 приведены некоторые из описаний действий для данной проблемной области, а также декомпозиция действия Ви11дноияе в том виде, в каком она могла бы присутствовать в библиотеке планов.
В этой библиотеке могут находиться также другие возможные декомпозиции. Листинг 12.3. Декомпозиции действий для задачи построения дома и подробная декомпозиция для действия Вилздяоияе. В этих декомпозициях приняты упрощенное представление о деньгах, а также оптимистическое представление строителей в отяощении перспектив оплаты АСС1оп(виулапд, Рсесопдг Мопеу, Еегесег Ьапд л -Мопеу) Асегоп(сеесоап, Рхесопдг аооде гедг'С, ЕССессг Мопеу л Моседаде) Асегоп(Виг1дНоияе, Рсесопдг Ьапд, ЕГгесег Ноияе) Асегоп(деерегтг'С, Рсесопдг Ьапд, ЕГсессг Регтге) Аседоп(Н1сеВиг1дес, Егтесег Сопегасе) АсСгоп(оопяггисС1оп, Рсесопдг РегтгС л йопегасе, Еггессг НоияеВи11С л Рестге) АсС1оп(РауВи11дес, Рсесопдг Мопсу л НоияеВиг1С, Еугесег Мопсу л Ноияе л йопегасе) Весотрояе(Виг1дноияе, Р1ап(ЯСеряг (Яг: ОеерестйС, Ягг НйгеВи11дег, ягг йопяегисейоп, ягг РауВиг1дея) Осдесьпдя г (ясасс ч яг ч яг ч яг и Ргпйял, ясаяс м яг ч яг), ьгпхяг ( Ясасс †"лгигвг, Ясах с-" †'-"лгЯ4, м с Ьг л гфггг Яг ЧРгпгя)г Я4 ~Р~пгяд) ) Глава 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
