Планирование действий в искусственном интеллекте
1. Введение Решение большого числа как теоретических, так и чисто практических или даже бытовых задач не может быть выполнено за один или несколько очевидных шагов. Причиной этого может быть, например, большое количество разнообразных условий и ограничений, неполная информация о предметной области, множество используемых параметров.
Одним из наиболее распространенных способов решения таких сложных задач является построение плана – упорядоченного набора несложных действий, позволяющего достичь поставленную цель. Поэтому вопросы, связанные с теорией планирования как составляющей теории решения задач, занимают одно из ведущих мест в области исследования интеллектуальных систем.
В данной работе проводится общее описание задачи, классификация существующих методов и формулируются основные перспективные направления научных и практических работ.
2. Задача планирования
Общее описание
Наиболее распространенное неформальное описание задачи планирования заключается в следующем: активный элемент (агент) действует в некотором окружении (среде) и пытается достичь поставленной цели.
В каждый момент времени среда находится в некотором состоянии, при этом агент может выполнять действия, изменяющие состояние среды.
Задача планирования состоит в нахождении последовательности действий, которые позволяют агенту перевести систему из некоторого исходного состояния в заданное целевое состояние.
В общем случае целевое множество может состоять из нескольких состояний, достижение любого из них означает достижение цели. Возможна также ситуация, когда ни одно из этих эти состояний недостижимо, например, в силу того или иного поведения среды.
Формально задача планирования описывается следующим образом [Safra95]:
дана система агент-среда M=(Q,A,ГM), где
Требуется найти план – упорядоченное множество действий P={a1,..,an}, такое что суперпозиция функций перехода ГM(ГM(…ГM(ГM(q0, a1) a2)…, an-1), an) принадлежащего G при q0 принадлежащего I.
При заданной системе агент-среда M=(Q,A,ГM) для задачи планирования {I,G} удовлетворительная процедура построения плана GeneratePlan должна обладать следующими свойствами [Hanks95]:
1. Корректность: для любой задачи с заданными M, I, G если GeneratePlan успешно генерирует план P, то выполнение шагов в P в любой ситуации, удовлетворяющей I, всегда дает состояние из множества G.
2. Полнота: GeneratePlan находит план-решение, если он существует
3. Системность: GeneratePlan никогда не рассматривает один и тот же план (полностью или частично) более одного раза.
Таким образом, в задаче имеются две основные составляющие – среда и агент, которые более подробно обсуждаются в следующих секциях.
Моделирование среды
Существуют два основных подхода к представлению среды – представление в пространстве состояний и представление в пространстве задач [Поспелов90].
В первом подходе строится граф среды, в котором вершины соответствуют состояниям, а дуги – действиям, позволяющим перейти из одного состояния в другое.
При использовании второго подхода формируется иерархия подзадач, исходная сложная проблема декомпозируется на несколько более простых, что в ряде случаев существенно облегчает решение.
Представление в пространстве состояний можно рассматривать как частный случай представления в пространстве задач, когда одна из подзадач является элементарной – переход в соседнее состояние.
В общем случае среда, в которой действует агент, обладает собственным поведением, которое может быть известно полностью или частично. Более того, в процессе выполнения плана агент обычно имеет дело не с реальными состояниями среды, а с наблюдаемыми, предполагаемыми на основе имеющейся у него информации.
Для построения плана и управления его выполнением необходимо построить формальное описание (модель) реальной среды. Поскольку в реальной ситуации обычно невозможно или крайне трудно построить абсолютно полную и корректную модель, приходиться строить некоторую упрощенную модель среды, на основе которой агент генерирует и верифицирует план.
Основные способы, используемые для описания среды, базируются на методах представления знаний: продукционных моделях, логических выражениях, семантических сетях, фреймовых структурах.
В работах по теории планирования среда действий агента классифицируется по следующим признакам [Kambhampati95]:
Таким образом, вырисовывается одна из основных подзадач задачи планирования - построение модели среды, адекватной реальной системе и в то же время удобной для решения исходной задачи.
Интеллектуальные агенты
Второй фундаментальной составляющей в задаче планирования является понятие агента – того объекта, который действует в среде с намерением достичь цель.
Специальная управляющая подсистема (планировщик) генерирует план для агента и может управлять его выполнением. В реальной системе агент и планировщик могут быть реализованы раздельно и взаимодействовать посредством некоторого коммуникационного протокола.
Более универсальной концепцией является понятие интеллектуального агента, совмещающего в себе управляющий и исполняющий элементы. Существуют различные определения агента, два из которых приведены здесь [Wooldridge95]:
Примером интеллектуального агента является софтбот (программный робот) – система, взаимодействующая с компьютерной средой (например, операционной системой) посредством выполнения команд и интерпретации результатов команд и других сообщений среды.
В простейшем случае агент действует в одиночку, между тем очень интересна и в то же время сложна задача распределенного искусственного интеллекта, когда в системе действуют несколько агентов, некоторым образом взаимодействующих между собой.
Исследования в области интеллектуальных агентов ведутся в нескольких направлениях:
3. Исторический экскурс
Проблема планирования действий является одной из основных в области искусственного интеллекта, поэтому неудивительно, что исследования в этом направлении ведутся достаточно давно.
Ниже кратко характеризуются основные системы, определившие путь развития всего направления.
4. Классификация систем планирования
Анализ работ по тематике планирования позволяет выделить классы используемых подходов, различающихся:
По способу взаимодействия со средой
Наряду с приведенной классификацией принято также выделять следующие подходы [Doyle97]:
Условное и универсальное планирование
Условный план включает в себя действия, предпринимаемые в случае выполнения некоторого условия. Соответственно, агент должен обладать сенсорами для проверки выполнения условия и даже может планировать действия, направленные на проверку условий.
Универсальное планирование заключается в создании агентом универсального плана – такого, в котором определены действия агента для всех состояний при любом возможном поведении среды. Очевидно, что такое решение имеет смысл, например, для недетерминированных сред, и требует значительных вычислительных ресурсов как для генерации плана, так и для его последующего использования.
Оппортунистическое планирование
Классическая модель планирования подразумевает иерархическую декомпозицию исходной задачи на подзадачи до максимально достижимого уровня, после чего строятся простые планы достижения подцелей. Затем из этих частных планов строится полный план достижения исходной цели. Альтернативным подходом является оппортунистическое планирование [Hayes-Roth79], идея которого базируется на наблюдениях за процессом планирования человеческого индивидуума: после формулирования основной задачи сразу начинаются манипулирования простыми действиями, из которых составляются частные планы.
Потом происходит увязка этих частных планов в основной план. Фундаментальный аспект состоит в попытке взглянуть на исходную задачу с разных точек зрения, на практике это реализуется в создании "виртуальных специалистов" – интеллектуальных агентов, которые начинают действовать по выполнению какого-то условия и, в свою очередь, могут провоцировать действия других специалистов.
Адаптивное планирование
Основная идея данного подхода заключается в построении искомого плана посредством модификации некоторого исходного плана, который обычно берется из библиотеки решений по принципу максимальной близости к данной ситуации в некотором смысле. Основными задачами при использовании адаптивного планирования являются:
При условии существования библиотечного решения адаптация плана, как правило, является более выгодной процедурой, чем генерация, более того, задачу генерации плана можно рассматривать как адаптацию нулевого плана.
Реактивное планирование
В значительном числе случаев невозможно, затруднительно или нерационально генерировать полный план до начала действий агента. Обычно это обусловлено сложностью среды, неполнотой информации и ограниченной наблюдаемостью. При реактивном планировании агент не генерирует весь план заранее как в случае классического планирования. После выполнения одного или нескольких действий агент запускает процедуру перегенерации плана относительно своего текущего состояния. Другое распространенное название данного подхода - чередование планирования и выполнения. Одним из частных случаев является чередование планирования и обучения – в этом случае действия агента между генерациями плана направлены на сбор новой информации и совершенствование модели среды.
5. Описание задачи и представление знаний
Описание знаний о среде – формализация представления среды в системе планирования с учетом выявленных свойств, отношений и возможной неопределенности является одной из основных и наиболее сложных задач не только в области планирования, но и в области любых искусственных интеллектуальных систем.
Особенность современных систем планирования заключается в активном двустороннем взаимодействии с подсистемой управления знаниями, то есть не только использование уже имеющихся знаний, но и пополнение базы новыми знаниями, полученными в результате обучения, как принудительного, так и самостоятельного.
Исследования в области управления знаниями в настоящее время переживают активный рост, стимулируемый как нерешенными теоретическими задачами, так и практическими проблемами в области прикладных информационных технологий, в частности, задачами обработки больших объемов распределенной гетерогенной информации с целью извлечения знаний.
Основными способами описания знаний [Осуга89], используемыми в задачах планирования, являются:
Продукционные правила
Исторически первым подходом к описанию предметной области является использование продукционных правил: формализмов вида ЕСЛИ-ТО. Они достаточно просты и естественны и, как следствие, легко понимаемы. Однако при этом не реализуется целостность представляемых знаний, кроме того при решении неоднородных задач продукционные модели оказываются низкоэффективными.
Логика предикатов
Логика предикатов является мощным средством описания знаний, обладает высоким уровнем модульности и, кроме того, позволяет обеспечить целостность знаний. Недостатками данного подхода являются чрезмерный уровень формализации представления знаний, трудность из прочтения, не слишком высокая производительность обработки.
Семантические сети
Характерной особенностью семантической сети является наглядность представления знаний системы. Однако, присутствующий в описании элемент произвольности влечет возможность возникновения противоречий в знаниях, полученных путем вывода. Управление непротиворечивостью при увеличении объема знаний резко усложняет их представление, что ограничивает круг решаемых проблем сравнительно небольшими задачами.
Фреймовое представление
Определяемая форма представления знаний как фреймов предполагает значительную степень свободы и не только описывает знания, но и алгоритмы вывода. Данный подход позволяет частично снять ограничения последовательного процесса обработки, однако усложняет приобретение знаний и уменьшает возможность динамической адаптации к изменениям среды. Для проблем большого масштаба описание и управление знаниями во фреймовой системе становится более сложным, чем в системах на основе продукционных правил, логики предикатов и семантических сетей.
Специальные языки планирования
Наиболее перспективным подходом является использование специальных языков планирования, которые обычно базируются на некотором обобщенном теоретическом фундаменте и являются с одной стороны достаточно абстрактными в смысле проблемно-независимости, но в тоже время оптимально ограниченными для их эффективного использования в системах планирования. Классический пример такого языка – язык системы STRIPS (1971г.), построенный на базе логики первого порядка с некоторыми упрощениями и успешно используемый в системах планирования до настоящего времени.
6. Перспективные направления исследований
Сложившееся в настоящее время положение в области исследований по тематике планирования действий характеризуется следующими особенностями:
В данной ситуации основными направлениями исследований становятся:
Планирование в условиях неопределенности
Характерной чертой реальной системы является присутствие неопределенности, вызванное неполнотой используемой информации, невозможностью учета всех особенностей среды, ограниченностью человеческого знания, вероятностной природой отдельных элементов. Следствием этого является необходимость создания как новых методов планирования для недетерминированных сред, так и специальных методик описания и обработки знаний и построения моделей среды.
Информационное планирование
Современные системы обработки информации, включающие, как правило, географически распределенные информационные источники различной архитектуры, зачастую не справляются с растущими потребностями пользователей. Специфика заключается в том, что обработка сложного запроса в такой системе не может быть эффективно выполнена без предварительного тщательного планирования предстоящей деятельности.
Особое значение это приобретает в сети Internet, поскольку доступ к огромному количеству полезной и открытой информации затруднен из-за большого числа источников, неструктурированности данных, постоянно проводимых изменений и ограниченных скоростей передачи данных.
Планирование с ограничением ресурсов
Другой важной особенностью реальной системы является ограничение по ресурсам. Как правило, основными ресурсами являются временные и стоимостные, однако в конкретной задаче могут возникать и свои специфические ограничения.
Планирование во времени
Особое место занимают задачи, связанные с представлением планирования во времени. В этом случае к основному вопросу планирования (что делать?) добавляется другой (когда делать?). Обычно задачи такого плана относятся к теории составления расписаний.
Оптимальное планирование
В ряде случаев недостаточно только нахождение плана, позволяющего достичь заданную цель. Необходимо также произвести оптимизацию этого плана по некоторым заданным критериям – минимизация времени, расхода ресурсов, максимизация утилизации вторичных целей. Особо необходимо выделить задачи, суть которых заключается не только в построении оптимального плана как способа достижения цели, но и в оптимизации самой цели.
Динамическое и адаптивное планирование
Задачи планирования действий в сложных изменяющихся средах требуют особенной гибкости от интеллектуального агента. В таких системах невозможно или недостаточно только найти статический план, обычно требуется проводить динамическую адаптацию некоторого начального плана к постоянно меняющейся среде и, возможно, динамически меняющейся цели непосредственно по мере поступления новой информации.
Распределенное планирование
Особую группу составляют задачи распределенного планирования – планирование в системе с несколькими агентами, работающими над достижением одной цели. В этом случае необходимо изучать не только проблемы взаимодействия агентов со средой, но и вопросы взаимодействия агентов между собой, такие как обмен информацией и совместные действия.
7. Заключение
Основной целью проделанной работы был анализ современного состояния исследований в области планирования действий. В работе приводится общее описание задачи и классификация ее основных компонентов, таких как среда, интеллектуальный агент, система представления знаний, алгоритм планирования. Выполнена классификация используемых подходов и методов планирования и их основные характеристики. На основании изученных материалов сделаны выводы о перспективных направлениях исследований в изучаемой области, обусловленных в первую очередь необходимостью решать теоретические и практические задачи в сложных, динамических средах в условиях неполноты информации, поскольку такие системы наиболее адекватно отображают проблематику реального мира. Очевидно, что успешное решение таких задач возможно лишь при интегрированном подходе, рассматривающем задачу не только с позиций теории планирования, но и с точки зрения других подходов, таких как теория игр, теория управления, теория принятия решений.
Список литературы: