В повседневной жизни под термином планирование (planning) мы обычно понимаем процесс составления некоторой последовательности действий, которая ведет к заранее намеченной цели.
Этот термин перекликается с еще одним процессом, решающим схожую задачу. Речь идет о составлении расписаний. Иногда эти термины употребляются даже как синонимы, хотя это и неверно. Составление расписаний (scheduling) — это проблема назначения множества задач множеству рабочих ресурсов, на которые (как на задачи, так и на ресурсы) накладывается ряд ограничений. В качестве примеров ограничений можно привести предельный срок выполнения задачи (deadline), количество рабочих ресурсов, ограничения предшествования на множестве задач, приоритеты задач и т.п. Таким образом, составление расписаний — это распределение (атомарных) задач по исполнителям. Расписание определяет кто чем занимается (как правило, с привязкой ко времени). То есть здесь действия (задачи), которые нужно выполнить, заданы заранее. Нужно отыскать лишь их порядок и распределение по рабочим ресурсам [прим. 1]. В отличие от составления расписаний, планирование заключается в отыскании действий, необходимых для решения задачи, и выстроении этих действий в последовательность, приводящую к решению. То есть нужно найти не только порядок, но и сами действия, которые позволят решить задачу в целом. Фактически, планирование — это нахождение способа достижения цели при заданных возможностях. План определяет, как достичь цель при наличии определенных механизмов воздействия.
Можно привести множество примеров, когда автоматическое решение задачи планирования могло бы быть полезно. Человеку в своей практике довольно часто приходится сталкиваться с задачами планирования чего-либо. При этом, найденные человеком решения являются далеко не всегда оптимальными, а иногда и не всегда верными. Кроме того, поиск решения может потребовать просмотра большого объема информации, а значит, грозит стать скучным долговременным процессом. Было бы удобнее, если бы план составлялся вычислительной машиной. При этом перед машиной можно сразу поставить задачу оптимизации решения по некоторому критерию или даже множеству критериев. Человеку оставалось бы лишь оценить приемлемость плана для себя. В качестве еще одной области, где автоматическое решение задачи планирования могло бы найти свое применение, можно отметить системы автоматического управления. Некоторые задачи автоматического управления требуют гибкого поведения при изменении внешних факторов. То есть в некоторых областях автоматизацию управления нельзя осуществить одним лишь реактивным поведением на внешние воздействия. Иногда требуется поиск решения во вновь сложившихся условиях.
Автоматический поиск плана принято относить к задачам из области искусственного интеллекта. Поэтому сам процесс поиска плана вычислительной машиной называют интеллектуальным планированием (AI planning). Проблема исследуется уже довольно давно. Первые работы в этом направлении появились еще в 70-ые годы, и к настоящему времени найдено множество интересных решений этой задачи. Появились отдельные школы и течения в рамках общего подхода. В материалах этого сайта мы постараемся осветить наиболее значительные события и достижения в области интеллектуального планирования, свершившиеся к настоящему моменту. Мы расскажем, как подходят к планированию с позиций искусственного интеллекта, какие факторы влияют на решение задачи, какие были предложены решения и многие другие вопросы, связанные с автоматическим поиском планов. Наш рассказ мы начнем с постановки задачи интеллектуального планирования.
Задача планирования требует мобилизации человеческого интеллекта и относится к разряду творческих. Каким образом человек решает эту задачу неизвестно, и, следовательно, построить точную компьютерную модель не представляется возможным. С другой стороны, так как мы собираемся решать эту задачу при помощи вычислительной машины, нам необходимо иметь какое-то строгое, формальное описание задачи и метода ее решения. Но прежде, чем мы перейдем к формальной постановке задачи планирования, необходимо рассмотреть, как в целом с точки зрения искусственного интеллекта выглядит эта задача.
Прежде всего, отметим, что подходы, применяемые в искусственном интеллекте, не стремятся строить функциональные модели человеческого мозга или его отделов. Решения, предлагаемые теориями искусственного интеллекта, строят модели, поведение которых схоже с поведением человека. Но внутреннее (физическое, функциональное и логическое) устройство этих моделей, как правило, не является моделью нервной ткани или процессов, протекающих в нервной ткани живого существа. Т.е. искусственный интеллект хоть и занимается воспроизведением отдельных функций творческой деятельности человека, но его методы кардинально отличаются (в функциональном аспекте) от естественного, биологического протекания интеллектуальных процессов.
Формально, интеллектуальное планирование основано на аппарате математической логики, а рассуждения, необходимые для формирования плана, сводятся к логическому выводу. Таким образом, логический вывод, в данном случае, и будет являться моделью рассуждений. Вопрос, возможно ли построить какую-то другую модель, не базирующуюся на логическом выводе, пока остается открытым. Автору неизвестны работы в этом направлении.
Чтобы сформулировать саму постановку задачи планирования с точки зрения искусственного интеллекта, нам потребуется определить ряд понятий, имеющих непосредственное отношение к процессу планирования.
Как уже упоминалось, планирование - это поиск последовательности действий, ведущих к намеченной цели. Целенаправленная последовательность действий не может рассматриваться в отрыве от контекста исполнения этих действий. В зависимости от внешних условий последовательность действий может приводить или не приводить к поставленной цели. Так, например, если мы ставим себе целью попить кофе, мы можем составить такой план: засыпать кофе в электрокофеварку, залить воду, включить кофеварку, подождать 10 минут и выпить кофе. Но если в сети электропитания нет напряжения, то цель мы не достигнем. Т.е. выполнение всякого плана окружено контекстом, в котором этот план выполняется. Модель контекста, в котором выполняются действия, называется моделью мира (world model).
Модель мира может включать статическую и динамическую составляющую. К статическим элементам относят модели объектов мира и отношений между ними. Динамическим элементом является модель изменения мира по своим внутренним законам, не зависимо от воздействия со стороны субъекта, исполняющего план. Будем называть динамическую составляющую динамикой мира (world dynamics).
Действия плана и динамика мира осуществляют преобразование модели мира (как правило, только статической составляющей). Про изменение модели мира говорят, что модель мира переходит в новое состояние (state). Состояние модели мира в момент, непосредственно предшествующий моменту начала выполнения плана, называется начальным состоянием (initial state) задачи планирования. Большинство современных планировщиков при построении плана оперируют именно понятием состояние, а не модель мира. Формально, состояние может быть представлено различными способами, и мы пока не будем вдаваться в подробности.
Конструктивным элементом для процесса планирования является действие. (Под действием в данном контексте следует понимать, разумеется, модель действия.) Действие (action) определяет, какие изменения в модели мира произойдут, если действие будет выполнено. В качестве модели действия в интеллектуальном планировании используется сущность, описывающая вид деятельности, условия, когда это действие выполнимо, и эффекты, которые это действие производит. В настоящее время принято обозначать действие в виде кортежа, состоящего из трех элементов:
<Name, Precondition, Effect>.
Здесь Name — это имя действия, т.е. символьное обозначение некоторого вида деятельности. Precondition — предусловие действия — те условия, при которых возможно выполнение действия. Effect — эффект действия — описание изменений, которое действие производит. Такая модель действия сложилась исторически, и вопрос о том, является ли эта модель идеальной для решения задачи планирования, пока еще рано закрывать. Возможно, она и не учитывает каких-то важных факторов, которые принимает во внимание человек, когда решает аналогичную задачу.
Теперь мы можем сформулировать задачу планирования.
Задача планирования заключается в поиске последовательности действий, применение которой в начальном состоянии модели мира, приведет к такому состоянию, в котором достигается заранее заданная цель. |
Последовательность действий, полученная в результате решения задачи планирования, называется планом (plan). Программное средство, осуществляющее решение задачи планирования, называется планировщиком (planner). Важно отметить, что планировщик только ищет план, но не отвечает за его выполнение. Иногда процессы планирования и исполнения осуществляются одновременно. То есть сначала планировщик находит действие, которое нужно выполнить следующим, для того, чтобы, в конечном счете, достичь намеченную цель. Затем исполняющие средства это действие осуществляют. После чего планировщик вновь ищет очередное действие и т.д. Такое чередование позволяет планировщику "видеть", насколько его предположения о способе достижения цели соответствуют реальной ситуации, что бывает очень полезно, когда мы не обладаем достаточно точной моделью мира. И здесь важно видеть границу между планировщиком (который предлагает решение) и исполнителем (который это решение реализует).
Кроме приведенных здесь понятий, следует упомянуть еще одно. Это понятие регулярно встречается при описании задач планирования. Речь идет о домене планирования (planning domain). Трудно дать строгое определение этого понятия. В некотором смысле это урезанное описание предметной области, в рамках которой осуществляется планирование. Домен планирования состоит из описаний видов действий (которые допустимы в данной модели), описаний динамики и законов мира и описаний возможных видов отношений между объектами. Но описание самих объектов модели мира не входит в домен планирования. Поэтому нельзя его назвать синонимом "предметной области".
С одной стороны такое разделение дает больше гибкости. В рамках одного домена мы можем решать различные задачи с разными объектами. Кроме того, мы можем и не обладать знаниями обо всех объектах, которые потом будут вовлечены в процесс планирования. Но с другой стороны отделение самих объектов от домена влечет некоторые сложности, если мы, например, захотим воспользоваться методами машинного обучения, для настройки системы на конкретную предметную область. К этому вопросу мы еще вернемся в материалах, посвященных обучению.
В зависимости от условий, в которых происходит процесс планирования, выделяют несколько разновидностей сред планирования (planning environment). Они определяются рядом свойств исполнителя и мира, в котором он оперирует. Вот эти свойства:
То есть можно говорить, что среда планирования определяется кортежем из пяти элементов:
<World observability, World static character, Action determinancy, Action durability, Action parallelism>
, где
World observability — наблюдаемость мира (полностью или не полностью);
World static character — статичность мира (статичен или динамичен);
Action determinancy — детерминированность действий (детерминированные или нет);
Action durability — длительность действий (длительные или дискретные);
Action parallelism — параллелизм действий (допустим или нет).
Различные способы означивания этого кортежа порождают различные среды планирования. Среди них особо выделяют среду планирования, когда мир полностью наблюдаем и статичен, а действия детерминированны, дискретны и недопустимо их параллельное исполнение. Планирование в такой среде называется планированием с классическими допущениями или классическим планированием. Все остальные виды сред называются неклассическими, а планирование, соответственно, неклассическим.
Рассмотрим типичный подход к постановке задачи классического планирования. В дальнейшем, если мы ссылаемся на задачу классического планирования, то мы будем пользоваться как раз таким формализмом (если это не оговорено особенно).
В классическом планировании для описания состояния модели мира используется конечное множество означенных формул исчисления предикатов первого порядка. Означенными (ground) формулами мы называем формулы без свободных переменных. Описание состояния (в целом) представляет собой описание множества отношений между объектами. Для обозначения различных отношений между объектами используются предикаты.
Просто множество формул не может являться описанием модели мира. Есть два варианта назначения семантики этим формулам. Первый вариант предлагает трактовать все формулы состояния как истинные высказывания о мире. Все остальные высказывания о мире, которые не входят в число тех, что описаны в состоянии или выводимы из них, считаются ложными. Второй вариант сужает множество допустимых формул до литералов. Тогда положительные литералы отражают истинные высказывания о мире, а отрицательные — ложные. Мы будем пользоваться первым подходом, но сузим множество допустимых формул до множества атомарных формул (т.е. предикатов). Кроме того, мы не будем пользоваться функциональными символами исчисления предикатов, т.е. литералы не должны содержать функции. Итак.
Состояние в классическом планировании описывается при помощи конечного множества означенных атомарных формул (предикатов), несодержащих функциональные символы. Эти высказывания о мире считаются истинными. Прочие атомарные формулы, которые могут фигурировать в описании состояний (но в описании данного конкретного состояния отсутствуют), считаются ложными. |
Например, то, что грузовик truckA и груз objB находятся внутри склада depC, можно выразить следующим образом. Здесь truckA, objB и depC — это вполне конкретные сущности модели, а не абстрактные понятия. Не следует путать "понятие грузовик" и "данный конкретный грузовик с именем truckA". Пусть двуместный предикат InDepot(x, y) отражает факт нахождения некоторого объекта в складском помещении. Первый аргумент — x — указывает, какой именно объект находится в складском помещении. Второй аргумент — y — указывает, в каком именно складе находится объект. Тогда атомарные формулы InDepot(truckA, depC) и InDepot(objB, depC) будут являться формальным описанием того, что упомянутые грузовик и объект находятся внутри склада depC. Если же эти формулы входят во множество формул, описывающих некоторое состояние, то мы получим состояние модели мира, когда грузовик и объект находятся в одном и том же складском помещении depC. Т.е. они станут истинными высказываниями о состоянии модели мира.
Цель в классическом планировании задается при помощи одной формулы исчисления предикатов первого порядка. Как правило, для простоты цель задают в виде конъюнкции литералов. Тогда считается, что цель достигнута в некотором состоянии, если все положительные литералы цели присутствуют в описании этого состояния и ни один из отрицательных литералов цели не присутствует в описании состояния.
Цель в классическом планировании задается при помощи одной формулы исчисления предикатов первого порядка. |
Возвращаясь к модели мира с грузовиками, объектами и складами, мы можем, например, задать цель InDepot(objA, depC) & InDepot(objB, depF). Эта цель декларирует тот факт, что мы хотим найти такую последовательность действий, которая приведет нас из начального состояния модели мира, в такое состояние, в котором эта целевая формула будет истинной.
Состояние мира в классическом планировании изменяется только посредством оказания непосредственного воздействия на него. Как мы уже упоминали ранее, действие описывается тройкой: имя, предусловие и эффект. В классическом планировании предусловие и эффект описываются формулами исчисления предикатов первого порядка. Предусловие задается одной формулой (как правило, конъюнкцией литералов). Если эта формула истинна в некотором состоянии (т.е. выводима из множества формул, описывающих состояние), то действие выполнимо в этом состоянии. Эффект также задается одной формулой — конъюнкцией литералов. В эффекте положительные литералы — это те атомарные формулы, которые будут гарантированно истинными в состоянии, полученном в результате применения действия. Отрицательные литералы указывают те атомарные формулы, которые будут гарантированно ложными в новом состоянии. Иногда эффект задается двумя списками атомарных формул: в первом из них перечисляются атомарные формулы, которые должны быть удалены из описания состояния (если они там присутствуют), а во втором списке перечисляются атомарные формулы, которые должны быть добавлены в описание состояния (если их там еще нет).
Действие в классическом планировании состоит из трех компонент: имени, предусловия и эффекта. Имя — это символическое обозначение действия. Предусловие — это формула исчисления предикатов первого порядка, истинность которой в некотором состоянии модели мира говорит о том, что это действие можно выполнить в этом состоянии. Эффект — это конъюнкция литералов. Позитивные литералы определяют те атомарные формулы, которые будут гарантированно истинными в состоянии, полученном в результате выполнения действия. Отрицательные литералы определяют атомарные формулы, которые будут гарантированно ложными в новом состоянии. |
В качестве примера приведем описание действия "погрузка объекта на грузовик". Нижеследующее описание является лишь одним из многочисленных способов формального описания действий. В дальнейшем, когда мы познакомимся с языками описания действий, мы будем пользоваться другой нотацией, которая в настоящее время, практически, является стандартом описания задач планирования. Пока же временно максимально упростим описание действия. Итак, действие "погрузить объекта objA на грузовик truck4, если объект и грузовик находятся в складском помещении depM" можно описать следующим образом.
action LOAD-TRUCK
precondition: InDepot(truck4, depM) & InDepot(objA, depM)
effect: ¬InDepot(objA, depM) & InTruck(objA, truck4)
В начале идет имя действия — LOAD-TRUCK (выделено серым цветом). Далее описано предусловие, которое представляет собой конъюнкцию двух литералов (зеленые) и декларирует требование, что грузовик и объект должны находиться внутри склада depM. Только в этом случае мы можем выполнить это действие. Эффект также являет собой конъюнкцию двух литералов: одного положительного (синий) и одного отрицательного (красный). Отрицание будем обозначать знаком "¬". Отрицательный литерал говорит нам, что после того, как действие выполниться, объект objA больше не будет находиться на складе (он будет в грузовике). Т.е. утверждение о том, что объект на складе, должно исчезнуть из описания нового состояния. Положительный литерал декларирует, что объект objA окажется в грузовике truck4 после выполнения действия.
Часто при описании задачи планирования применяют параметризованные описания действий — схемы действий. Схема действия (action schema) — это такая абстракция действия, в которой ряд объектов модели мира, использованных в описании действия, заменяется параметрами. Рассмотрим это на том же простом примере с погрузкой.
action LOAD-TRUCK (?object,
?truck, ?location)
precondition: InDepot(?truck, ?location)
& InDepot(?object, ?location)
effect: ¬InDepot(?object, ?locaction)
& InTruck(?object, ?truck)
Здесь слова, начинающиеся со знака вопроса, являются именами параметров схемы. При описании схемы действия принято перечислять список параметров вместе с именем схемы. В остальном, структура описания схемы действия ничем не отличается от описания самого действия.
Этот пример декларирует следующее. Для того, чтобы выполнить погрузку, необходимо, чтобы грузовик и груз находились в одном и том же месте. В результате погрузки объект окажется в грузовике и перестанет находиться там, где был изначально. Таким образом, мы в описании перешли от конкретных объектов к абстрактным понятиям. Подставив вместо параметров конкретные объекты, мы получим обычное действие. Так, если мы заменим ?object на objA, ?truck на truck4 и ?location на depM, то мы получим ранее описанное действие. Целесообразность такого подхода к описания очевидна. Если мы имеем тысячи объектов в наше модели мира, и все они могут подвергаться воздействию, то описание множества возможных действий было бы достаточно громоздким.
В процессе планирования схема действия конкретизируется. То есть вместо параметров схемы подставляются объекты модели мира. Таким образом, когда дело доходит до выполнения действия, схема действия становится самим действием, т.е. не содержит параметров.
Примечание. Параметры в формулах не следует путать со связанными (квантифицированными) переменными. Если мы в качестве предусловия будем использовать не конъюнкции литералов, а более сложные формулы с кванторами, то мы должны будем в одной формуле указывать и переменные, и параметры.
Итак, формулируя задачу классического планирования, мы внесли ряд ограничений на:
Таким образом,
"определение задачи классического планирования" = "определение
задачи планирования" + "вышеуказанные ограничения".
Трофимов И.В.
апрель 2005 г
Примечания
1. Подробнее с вопросом составления расписаний, а также с вопросом соотношения планирования и составления расписаний, можно ознакомиться в работе Дэвида Смита и его коллег.
D.Smith, J.Frank, and A.Jonsson. Bridging the gap between planning and scheduling. Knowledge Engineering Review, 15(1):47–83, 2000.