Искусственный интеллект. Современный подход

ПЛАНИРОВАНИЕ И ОСУЩЕСТВЛЕНИЕ ДЕЙСТВИЙ В РЕАЛЬНОМ МИРЕ

В этой главе показано, что более выразительные представления и более интерактивные архитектуры агентов обеспечивают возможность создания планировщиков, применимых в реальном мире.

В предыдущей главе описывались наиболее важные понятия, представления и алгоритмы для планирования. Планировщики, применяемые в реальном мире для решения таких задач, как планирование наблюдений с помощью космического телескопа Хаббл, управление заводами и фабриками, а также осуществление поставок для военных кампаний, являются более сложными; они превосходят свои более простые аналоги и с точки зрения языка представления, и с точки зрения того способа, который применяется в планировщике для взаимодействия с его средой. Такие различия описаны в настоящей главе. В разделе 12.1 рассматриваются задачи планирования и составления расписаний с учетом временнь/х и ресурсных ограничений, а в разделе 12.2 описывается планирование с помощью предопределенных субпланов. В разделах 12.3-12.6 рассматривается ряд архитектур агентов, предназначенных для осуществления действий в неопределенных вариантах среды. В разделе 12.7 показано, как должны составляться планы, когда среда содержит и других агентов.
ВРЕМЯ, РАСПИСАНИЯ И РЕСУРСЫ
В представлении на языке Strips говорится о том, какие действия должны быть выполнены, но это представление основано на ситуационном исчислении, поэтому с его помощью нельзя показать, сколько времени потребуется на проведение того или иного действия, или даже обозначить время, когда должно произойти это дейст-тлг, помимо указаний на то, что оно должно быть осуществлено до или после другого действия. Но применительно к некоторым проблемным областям было бы желательно также указывать, когда должны начинаться и оканчиваться действия. Например, в проблемной области транспортировки грузов может потребоваться знать, когда именно прибывает самолет, перевозящий некоторый груз, а не просто пользоваться информацией о том, что он прибудет, когда закончится полет.
Время является существенно важным фактором для крупного семейства приложений, называемых задачами планирования производства. Для выполнения таких задач требуется осуществление ряда работ, каждая из которых состоит из последовательности действий, а каждое действие имеет определенную продолжительность и может потребовать определенных ресурсов. Проблема состоит в разработке расписания, которое минимизирует общее время, требуемое для выполнения всех работ, при соблюдении ограничений на ресурсы.
Пример задачи планирования производства приведен в листинге 12.1. Это— в высшей степени упрощенная задача сборки автомобиля. В ней представлены две работы: сборка автомобилей С1 и С2. Каждая работа состоит из трех действий: установка двигателя, установка колес и проверка результатов. Двигатель должен устанавливаться в первую очередь (поскольку в автомобиле этой модели с установленными передними колесами затрудняется доступ к двигательному отсеку), а проверка, безусловно, должна проводиться в последнюю очередь.
Листинг 12.1. Задача планирования производства, связанная со сборкой двух автомобилей. Обозначение Duration{d) показывает, что для выполнения некоторого действия требуется d минут, а обозначение Engine(Elt clt 60) показывает, что Е1 — это двигатель, который устанавливается в шасси Ci, и для его установки требуется 60 минут
Init {Chassis (d) л Chassis (С2)
л Engine {Elt Clt 30) л Engine {E2l С2, 60)
л Wheels(Wlt Clt 30) л Wheels(W2t С2, 15)) Goal (Done (Ci) л Done (С2) )
Action{AddEngine(e, c)
Precond: Engine(e, c, d) л Chassis(c) л —lEngineln (c) ,
Effect: Engineln{c) л Duration(d)) Action{AddWheels(w, c) ,
Precond: Engineln(c) л Wheels{w, c, d) л Chassis(с),
Effect: WheelsOn(c) л Durationid)) Action{Inspect(c), Precond: Engineln(c) л WheelsOn(c) л Chassis(c),
Effect: Done(c) л Duration(10))
Задача, приведенная в листинге 12.1, может быть решена с помощью любого из планировщиков, которые уже описывались в настоящей книге. На рис. 12.1 показано решение, которое было бы получено с помощью планировщика POP с частичным упорядочением (если игнорируются некоторые числовые данные). Теперь для преобразования этой задачи в задачу составления расписания, а не в задачу планирования, необходимо определить, когда должно начаться и закончиться каждое действие, с учетом продолжительности действия, а также их упорядочения. Обозначение Duration (d) в спецификации результата действия (где переменная d должна быть привязана к некоторому числу) показывает, что для выполнения действия требуется d минут.

Определив частичное упорядочение действий с учетом их продолжительности, как показано на рис. 12.1, можно применить метод критического пути (Critical Path Method — СРМ) для выяснения допустимых значений времени начала и окончания каждого действия. Путем через план с частичным упорядочением называется линейно упорядоченная последовательность действий, начинающаяся в состоянии Start и оканчивающаяся в состоянии Finish (например, в плане с частичным упорядочением, показанном на рис. 12.1, есть два пути).
Критическим называется путь, имеющий максимальную суммарную продолжительность; этот путь называется "критическим", поскольку от него зависит продолжительность выполнения всего плана, — сокращение продолжительности других путей не приведет к сокращению времени выполнения всего плана в целом, но задержка начала любого действия в критическом пути замедлит осуществление всего плана. На этом рисунке критический путь показан жирными линиями. Для осуществления всего плана за минимальное суммарное время действия в критическом пути следует выполнять без задержки между ними. С другой стороны, действия, лежащие вне критического пути, имеют определенный запас времени — временное окно, в течение которого они могут быть выполнены. Это окно задается в терминах самого раннего возможного времени начали, ES, и самого позднего возможного времени начала, LS. Разность LS - ES называется резервом времени для действия. Как показано на рис. 12.1, для выполнения всего плана потребуется 85 минут, каждое действие в критическом пути имеет резерв времени 0 (такое условие имеет место во всех расписаниях), а каждое действие в работе по сборке сх имеет десятиминутное окно, в пределах которого оно может быть начато. Значения времени ES и LS для всех действий, вместе взятые, составляют расписание, представляющее собой решение данной задачи.
Ниже приведены формулы, которые служат определением значений ES и LS, а также лежат в основе алгоритма динамического программирования, применяемого для их вычисления.
ES(Start) = О
ES{B) = may:A LS{Finish) = ES{Finish)
LS(A) = minA Идея этого алгоритма состоит в том, что вначале следует присвоить терму ES{ Start) значение 0. Затем, как только будет выявлено действие В, такое, что все действия, непосредственно предшествующие в, имеют присвоенные значения ES, терму ES{B) присваивается максимальное из самых ранних значений времени завершения этих непосредственно предшествующих действий, где самое раннее время завершения действия определяется как самое раннее время начала плюс его продолжительность. Этот процесс повторяется до тех пор, пока каждому действию не присваивается значение ES. Значения LS вычисляются аналогичным образом, в ходе передвижения в обратном направлении от действия Finish. Проработку деталей этого алгоритма оставляем читателю в качестве упражнения.
Сложность алгоритма критического пути составляет всего лишь 0{Nb), где N — количество действий; Ь— максимальный коэффициент ветвления на входе или выходе любого действия. (Чтобы убедиться в этом, достаточно отметить, что вычисления значений LS и ES осуществляются по одному разу для каждого действия, а в каждом вычислении происходит итерация, самое большее, по Ь других действий.) Поэтому, если дано частичное упорядочение действий, задача поиска расписания с минимальной продолжительностью решается очень просто.