Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 154
Текст из файла (страница 154)
Но применительно к некоторым проблемным областям было бы желательно также указывать, когда должны начинаться и оканчиваться действия. Например, в проблемной области транспортировки грузов может потребоваться знать, когда именно прибывает самолет, перевозящий некоторый груз, а не просто пользоваться информацией о том, что он прибудет, когда закончится полет. Время является существенно важным фактором для крупного семейства приложений, называемых задачами ок планирования производства. Для выполнения таких задач требуется осу)цествление ряда работ, каждая из которых состоит из последовательности действий, а каждое действие имеет определенную продолжительность и может потребовать определенных ресурсов.
Проблема состоит в разработке расписания, которое минимизирует общее время, требуемое для выполнения всех работ, при соблюдении ограничений на ресурсы. Пример задачи планирования производства приведен в листинге 12.1. Это— в высшей степени упро(ценная задача сборки автомобиля.
В ней представлены две работы: сборка автомобилей С„и С,. Каждая работа состоит из трех действий: установка двигателя, установка колес и проверка результатов. Двигатель должен устанавливаться в первую очередь (поскольку в автомобиле этой модели с установленными передними колесами затрудняется доступ к двигательному отсеку), а проверка, безусловно, должна проводиться в последнюю очередь. Листинг 12.1. Задача планирования производства, связанная со сборкой двух автомобилей. Обозначение писасяоо(с() показывает, что для выполнения некоторого действия требуется сг минут, а обозначение епд1пе(е„ с„ ВО) показывает, что и, — зто двигатель, который устанавливается в шасси с„и для его установки требуется 60 минут 1пзг(СЬааауа(Сз) л Си*наба(Сз) л Епд1пе(Еы Сы 30) л Епд1пе(Ез, Сз ° бо) л В))зее1а((тг, Сг, 30) л Ызее1а( % Сз 15)) Соа1(попе(Сз) л ()опе(Сз) ) АСС1оп(лдддпдзпе(е, с) Ргесопд: Епдупе(е, с, ги л С)зааа1а(с) л Епдзпетп(с), ЕГгесе: Епдзпе1п(с) л оигаг1оп(г()) Асгуоп(АсЫГ))зее1а(м, с), Ргесопг(: Епдупе1п(с) л )Г)зее1а(м, с, с)) л С)зааа1а(с), Еггесг: И)зее1аоп(с) л Еига Сбоп (гй ) Асг1оп(гпарасе(с), Ргесопг(: Епдбпе7п(с) л )Г)зее1асп(с) л Спааа1а(с), Еггесе; Еппе(с) л Еигаг1оп(10)) Задача, приведенная в листинге 12.1, может быть решена с помощью любого нз планировшиков, которые уже описывались в настоящей книге.
На рис. 12.1 показано решение, которое было бы получено с помощью планировщика РОР с частичным упорядочением (если игнорируются некоторые числовые данные). Теперь для преобразования этой задачи в задачу составления расписания, а не в задачу планирования, необходимо определить, когда должно начаться и закончиться каждое действие, с учетом продолжительности действия, а также их упор)шочения.
Обозначение писа сз оп ( с)) в спецификации результата действия (где переменная с) должна быть привязана к некоторому числу) показывает, что для выполнения действия требуется с) минут. Глава 12. Планирование и осуществление действий в реальном мире 567 ти следует выполнять без задержки между ними. С другой стороны, действия, лежащие вне критического пути, имеют определенный запас времени — временное окно, в течение которого они могут быть выполнены. Это окно задается в терминах самого раннего возможного времени начали, еБ, и самого позднего возможного времени начала, ЪБ.
Разность ЬБ — еБ называется ох резервом времени для действия. Как показано на рис. 12.1, для выполнения всего плана потребуется 85 минут, каждое лействие в критическом пути имеет резерв времени О (такое условие имеет место во всех расписаниях), а каждое действие в работе по сборке Е, имеет десятиминутное окно, в пределах которого оно может быть начато. Значения времени ББ и ВБ для всех действий, вместе взятые, составляют 'а. расписание, представляющее собой решение данной задачи.
Ниже приведены формулы, которые служат определением значений еБ и ВБ, а также лежат в основе алгоритма динамического программирования, применяемого для их вычисления. ЕЯ(БСаге) = О ЕЯ(В) = п~ахв вЕЯ(А) + Юигасхоп(А) ЪБ(ЕЗпхап) = ЕБ(кхпхап) ЬБ(А) = тгп, вЬБ(В) — Вигаехоп(А) Идея этого алгоритма состоит в том, что вначале следует присвоить терму еБ(Бсагс) значение О.
Затем, как только будет выявлено действие В, такое, что все действия, непосредственно предшествующие В, имеют присвоенные значения ЕБ, терму еБ(В) присваивается максимальное из самых ранних значений времени завершения этих непосредственно предшествующих действий, где самое раннее время завершения действия опрелеляется как самое раннее время начала плюс его продолжительность. Этот процесс повторяется до тех пор, пока каждому действию не присваивается значение ЕБ. Значения ЬБ вычисляются аналогичным образом, в ходе передвижения в обратном направлении от действия езпзой, Проработку деталей этого алгоритма оставляем читателю в качестве упражнения. Сложность алгоритма критического пути составляет всего лишь 0(Мз), где А)— количество действий; .Ь вЂ” максимальный коэффициент ветвления на входе или выходе любого действия.
(Чтобы убедиться в этом, достаточно отметить, что вычисления значений ьБ и еБ осуществляются по одному разу для каждого действия, а в каждом вычислении происходит итерация, самое большее, по Ь других действий.) Поэтому, если дано частичное упорядочение действий, задача поиска расписания с минимальной продолжительностью решается очень просто. Составление расписаний с ресурсными ограничениями Реальные задачи составления расписаний усложняются из-за наличия ограничений на Ъ.
ресурсы. Например, для установки в автомобиль двигателя требуется лебедка для двигателя. Если есть только одна лебедка, то нельзя одновременно устанавливать двигатель Е, в автомобиль С, и двигатель Е, в автомобиль С,, поэтому расписание, показанное на рис. 12.1, будет неосуществимым. В данном примере лебедка для двигателя представляет собой пример 'в. повторно применяемого ресурса — ресурса, который "занят" во время действия, но снова становится доступным после завершения этого действия. Следует отметить, что повторно применяемые ре- 569 Глава 12.
Планирование и осуществление действий в реальном мире Нееоипсе: Епдтпедоуеее(1) ) Асетоп(деда(пее1е(е, с), Впесопс): Епдупетп(с) е я(пее1е(е, с, сн л Слееехе(с), ВГГесе: (Едее1есп(с) п Рипагтоп(й), Кееосесе: Яйеезяеаетопе(1)) Асетоп(гпересс(с), Вгесопс): Епдхпетп(с) е )Глеезесп(с), ЕГГесе: Ропе(с) е Рпгаехоп(10), Яееоигсе: Гпзресеопе(1)) Представление ресурсов в виде числовых количественных значений, таких как тпярессопе (2 ), а не именованных сущностей, таких как тперессоп ( 1,) и 1пэрессоп(т,), может служить примером очень продуктивного метода, называемого Ж агрегированием. Основная идея агрегирования состоит в том, что отдельные объекты должны группироваться в количественные величины, если все объекты неразличимы применительно к рассматриваемому назначению. В данной задаче сборки не имеет значения, какой именно контролер проверит автомобиль, поэтому нет необходимости проводить между ними различие.
(Та же идея может применяться при решении задачи с миссионерами и каннибалами, приведенной в упр. 3.9.) Агрегирование представляет собой важный способ уменьшения сложности задач. Рассмотрим, что произойдет, если будет предложено расписание, в котором имеется 1О одновременных действий по проверке хпяресс, но в наличии есть только 9 контролеров.
Если контролеры представлены с помощью количественных величин, неудача будет обнаружена немедленно и алгоритм выполнит возврат, чтобы попытаться составить другое расписание. А если бы контролеры были представлены как отдельные лица, то в алгоритме пришлось бы выполнять возвраты для опробования всех 10.' способов назначения контролеров для выполнения действий тпересс, притом что положительный результат так и не был бы получен. Несмотря на их преимушества, ресурсные ограничения приводят к усложнению задач планирования, поскольку в них вводятся дополнительные зависимости между действиями. К тому же составление расписания без ограничений с использованием метода критического пути является несложным, а задача поиска расписания с ресурсными ограничениями, характеризующегося самым ранним возможным временем завершения, является МР-трудной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
