Самоорганизация коллектива мобильных измерительных агентов в задаче распределенных контактных измерений
Автор: БочкарёвА.Ю , Голембо В.А.
Источник: Национальный университет «Львовская политехника», Украина, УДК 681.3, 621.3
Автор: БочкарёвА.Ю , Голембо В.А.
Источник: Национальный университет «Львовская политехника», Украина, УДК 681.3, 621.3
Рассмотрена проблема самоорганизации коллектива автономных мобильных исследовательских станций (измерительных агентов) в задаче распределенных контактных измерений. Обоснована необходимость в использовании принципов самоорганизации для обеспечения качественного перехода на более высокий уровень автономных исследований (с точки зрения количества и качества собираемой коллективом измерительных агентов информации об объекте исследования). Рассмотрена проблема количественной оценки процесса самоорганизации. Предложен ряд моделей коллективного поведения, в которых раскрывается проблематика распределенных контактных измерений коллективом автономных исследовательских станций (алгоритмическая модель, интерполяционная модель, энтропийная модель). Приводится постановка задачи по разработке алгоритмов коллективного поведения измерительных агентов на основе принципов самоорганизации в рамках предложенных моделей. Обсуждается ряд решений этой задачи в условиях полностью децентрализованного управления и локального ограниченного информационного взаимодействия измерительных агентов.
Задача распределенных контактных измерений [1], [2] становится все более актуальной с ростом возможностей по созданию систем автономных долговременных исследований в интересах различных наук (океанология, метеорология), решения экологических проблем (экологический мониторинг, выявление и контроль загрязнений окружающей среды), а также промышленных и военных приложений. Общий сценарий распределенных контактных измерений предусматривает размещение непосредственно в пространстве объекта исследования некоторого ограниченного количества функционально автономных измерителей, способных собирать измерительную информацию и передавать ее в центр сбора и обработки (глобальный пользователь). В другом варианте сценария потребитель получаемой измерительной информации (локальный пользователь) также находится в пространстве объекта исследования и использует эту информацию, например, для синтеза прямых управляющих воздействий на объект. При этом, в зависимости от возможностей измерителей и стоящих перед ними задач, можно различать системы разного уровня, начиная от простых сенсорных сетей и заканчивая глобальными системами сбора гидрометеорологических данных.
Отдельного внимания заслуживают системы автономных долговременных исследований, в которых измерители способны перемещаться в пространстве объекта исследования. Последнее открывает широкие возможности по более глубокому изучению объекта, поскольку появляется возможность управлять размещением и (или) перемещением измерителей в пространстве исследуемого объекта. В качестве примера таких систем можно привести мобильные беспроводные сенсорные сети [3], [4] или автономные системы океанологических исследований [5], [6]. В данном случае в качестве носителя, который дает возможность перемещать измеритель в пространстве, могут, например, выступать мобильный робот, беспилотный летательный аппарат или автономный подводный аппарат. Таким образом, можно говорить о мобильной автономной исследовательской станции, в состав которой, кроме всего прочего, входят сенсорная система, система связи и навигации, система перемещения, система энергообеспечения и блок принятия решений. В дальнейшем мы будем называть такую станцию мобильным измерительным агентом, а систему одновременно функционирующих станций – коллективом мобильных измерительных агентов.
С функционированием систем автономных долговременных исследований на основе мобильных измерительных агентов связан ряд проблем [7]. Среди них можно выделить две – наиболее существенные на наш взгляд – проблемы.
Первая проблема – проблема размещения – вызвана ограничением на количество измерительных агентов, размещаемых в пространстве объекта исследования. Это ограничение является естественным отображением принципа минимизации влияния инструмента измерения на объект исследования [8] и приводит к тому, что в один момент времени можно получить ограниченное количество информации об этом объекте. Естественно предположить, что разным размещениям измерительных агентов в пространстве объекта исследования соответствуют разные по количеству содержащейся в них информации отображения этого объекта. Следовательно,возникает проблема размещения: каким образом разместить заданное количество измерительных агентов в пространстве, чтобы получить наиболее информативное в рамках естественных ограничений отображение исследуемого объекта?
Вторая проблема – проблема управления – вызвана «удаленностью»
пользователя (глобального или локального) от системы автономных долговременных исследований, что, в большинстве случаев, не дает возможности пользователю эффективно (точно и своевременно) решать проблему размещения. Спецификой работы систем автономных долговременных исследований является полное или частичное отсутствие у пользователя априорных сведений о характере исследуемых процессов, протекающих в объекте. Поэтому эффективность предлагаемых пользователем решений проблемы размещения всегда будет ограничена некоторым фиксированным значением, соответствующим уровню нехватки информации о текущих условиях решения этой проблемы. При этом полностью преодолеть эту нехватку информации (неопределенность) пользователь в силу своей «удаленности» не может. Следовательно, возникает проблема управления: каким образом передать «инициативу» по решению проблемы размещения самой системе автономных долговременных исследований?
Рассматривая указанные проблемы вместе, можно прийти к идее о прямой зависимости способа функционирования системы автономных долговременных исследований от характера тех процессов, которые протекают в объекте исследований. Другими словами, можно говорить о задаче разработки такого инструмента исследований, который бы самостоятельно (проблема управления) находил наилучший, согласно заданной системе критериев, способ исследования целевого объекта (проблема размещения). При этом в наиболее сложном варианте данной задачи процессы, протекающие в объекте исследования, подчиняются законам нелинейной динамики (то есть являются синергетическими процессами).
С учетом этого в [7] выдвинута гипотеза о том, что если синергетическим процессам, протекающим в объекте исследования, поставить в соответствие возможности самоорганизации системы автономных долговременных исследований, то такое опосредствованное подобие объекта и инструмента позволит поднять автономные исследования на новый качественный уровень (с точки зрения количества и качества собираемой информации). С точки зрения возможностей подтвердить или опровергнуть эту гипотезу, а также с учетом функциональной автономности отдельной исследовательской станции (измерительного агента) для решения поставленной задачи целесообразнее всего, на наш взгляд, использовать методы теории коллективного поведения (многоагентных систем) [9-11]. Этот выбор в первую очередь основан на том, что в рамках теории коллективного поведения исследуется вопрос о передаче «инициативы» в принятии решений автономным техническим системам (определение интеллектуального агента в [10]). Кроме этого, в данном случае можно провести прямую аналогию между процессом самоорганизации системы автономных долговременных исследований и возникновением сложных форм коллективного поведения на основе совместной реализации относительно простых поведенческих актов отдельными измерительными агентами [9], другими словами, рассматривать процесс функциональной эмерджентности [12], [13], где элементами системы (коллектива) выступают измерительные агенты.
Таким образом, общая задача сводится к разработке таких алгоритмов коллективного поведения измерительных агентов, которые позволяли бы определять «порядок», присущий исследуемым процессам, и исходя из этого организовывали бы такое коллективное поведение (способ функционирования системы), которое бы наилучшим образом соответствовало этому «порядку». То есть в данном случае предполагается, что коллектив измерительных агентов будет способен ассимилировать «порядок» среды [14] так, чтобы возникающее при этом коллективное поведение соответствовало наилучшему способу исследования этой среды. При этом к разрабатываемым алгоритмам коллективного поведения выдвигаются три основных требования: децентрализация (измерительные агенты самостоятельно принимают решения в условиях отсутствия единого центра управления), однородность (все измерительные агенты одинаковы с точки зрения алгоритмов индивидуального поведения) и локальность информационного взаимодействия (измерительные агенты принимают решения в условиях ограничений на объем и скорость обмена информацией между собой). Следует подчеркнуть, что выполнение этих требований гарантирует высокую надежность работы системы автономных исследований (в первую очередь с точки зрения ее «живучести» [15]). В данном случае система продолжает выполнять свои функции до тех пор, пока в ее составе остается хотя бы один исправный измерительный агент. При этом изменение количества измерительных агентов, как в сторону уменьшения, так и в сторону увеличения, не требует никаких специальных «внешних» процедур, корректирующих работу системы. В то же время вопрос о том, как качество работы системы зависит от количества измерительных агентов, заслуживает отдельного внимания.
Отдельного внимания заслуживает проблема получения оценок процесса самоорганизации системы автономных исследований. Известны разные подходы к определению самого понятия «самоорганизация» [12], [14], [16-18] и соответствующие им способы получения количественных оценок процесса самоорганизации.
Поскольку в данном случае мы имеем дело с набором однородных элементов (коллективом измерительных агентов), поведение которых некоторым образом взаимно обуславливается в процессе их взаимодействия, то наиболее подходящим, на наш взгляд, способом оценки процесса самоорганизации является способ, предложенный в [14]. К одному из основных преимуществ этого способа можно отнести то, что он дает возможность наравне с характером межэлементных связей учитывать изменение количества элементов. Кроме этого, данный способ использует понятие энтропии и коэффициента избыточности, предложенных К. Шенноном [19], что дает возможность напрямую соотнести процесс самоорганизации измерительных агентов с количеством собираемой ими измерительной информации об объекте исследования. Основная идея выбранного способа оценки процесса самоорганизации заключается в том, что чем больше действия измерительных агентов взаимообусловлены (то есть чем больше значения соответствующих условных вероятностей отличаются от 0.5), тем меньше текущее значение энтропии и, соответственно, тем больше значение коэффициента избыточности, который в рамках данного способа является основной количественной оценкой процесса самоорганизации [14].
Основной проблемой при разработке алгоритмов коллективного поведения является переход от общей целевой функции коллектива (многоагентной системы) к индивидуальным целевым функциям отдельных составляющих его агентов [9], [10], [20]. Универсальных обобщенных методов решения этой проблемы на данный момент не существует [20]. Поэтому в каждом отдельном случае приходится решать эту проблему исходя из специфики той задачи, которая ставится перед коллективом (многоагентной системой).>
В случае распределенных контактных измерений имеют место несколько важных аспектов соответствующей задачи, каждый из которых заслуживает отдельного рассмотрения. С этой целью нами разработан ряд моделей коллективного поведения измерительных агентов [21], в рамках которых предлагаются решения общей задачи разработки системы автономных исследований. Предложенные решения основаны на теории коллективного поведения обучающихся автоматов [9], [15], методах теории игр в применении к проблемам коллективного поведения [9], [22] и методах обучения с подкреплением (reinforcement learning) [11], [23].
В рамках алгоритмической модели коллективного поведения измерительных агентов исследуется проблема децентрализации управления процессом измерения.
Название модели отражает взаимосвязь с алгоритмической теорией измерения [24], [25], в которой обобщенный алгоритм измерения представляется как процесс уравновешивания измеряемой величины с помощью набора «весовых гирь» (модель взвешивания на рычажных весах) и ставится вопрос о синтезе оптимального алгоритма измерения. В случае децентрализованного управления процессом измерения возможность централизовано манипулировать «весовыми гирями» разных весов отсутствует. Другими словами, ситуацию можно представить так, что измеряемую величину уравновешивает коллектив «весовых гирь», каждая из которых может самостоятельно выбирать свой вес в некоторых заданных пределах. При этом после каждого взвешивания «весовым гирям» сообщается результат (например, «больше», «меньше» или «равно»), на основании которого они должны выбрать свой вес для следующего взвешивания. В алгоритмической модели эта ситуация отображена следующим образом [26]. Рассматривается некоторая ограниченная плоскость (например, плоский диск) с одной точкой опоры, которая совмещена с центром тяжести этой плоскости. На ней случайным образом размещаются мобильные измерительные агенты, каждый из которых имеет единичный вес. В результате этого размещения плоскость наклонится (ее центр тяжести сместится). Перед коллективом измерительных агентов ставится задача найти такое взаимное размещение на плоскости, которое бы вернуло ее в горизонтальное положение (то есть найти «уравновешивающее» размещение, которое совместило бы новый центр тяжести с точкой опоры). В данном случае роль неопределенности вместо неизвестного «веса» измеряемой величины играют неизвестные координаты (положение) точки опоры. При этом в базовом варианте алгоритмической модели всем измерительным агентам сообщается значение текущего угла наклона плоскости (или разность моментов). Задача считается выполненной, когда угол наклона становится равным нулю. Основным критерием качества решения задачи выбрана скорость уравновешивания с учетом величины первоначального угла наклона.
Основная проблема, с которой сталкивается каждый из решающих эту задачу агентов, – это интерпретация отклика на свои действия [11]. Поскольку угол наклона плоскости меняется в результате действий всех агентов коллектива, отдельный агент, не обладающий полной информацией о действиях всех других агентов, не может сделать однозначного вывода об успешности своих действий в предыдущих тактах уравновешивания (например, действия агента могут быть «правильными», но за счет «неправильности» действий большинства других агентов ситуация ухудшится и он получит негативный отклик на свои действия). Неопределенность этого рода является прямым следствием децентрализации управления, и она тем больше, чем жестче ограничения на информационное взаимодействие измерительных агентов (то есть чем меньше у агентов возможностей сообщать друг другу о своих действиях). Таким образом, можно предположить, что наилучшим алгоритмом коллективного уравновешивания является тот алгоритм, который наилучшим образом ликвидирует эту неопределенность. Исходя из этого предположения нами разработан ряд алгоритмов коллективного поведения измерительных агентов, решающих задачу уравновешивания [26]. Алгоритмы основаны на идеях обучения с подкреплением [11], [23] и демонстрируют возможность успешной организации совместных коллективных действий в условиях неопределенности, вызванной децентрализацией управления. В ходе проведенных вычислительных экспериментов установлены зависимости показателей эффективности разработанных алгоритмов от основных параметров модели. К основным выводам можно отнести то, что с ростом информационной связности агентов скорость уравновешивания растет, а с ростом количества агентов в коллективе скорость уравновешивания падает.
В рамках интерполяционной модели коллективного поведения измерительных агентов исследуются пути непосредственного решения проблемы размещения, а также способы ее совместного решения с проблемой управления [27]. В базовом варианте модели рассматривается ограниченная область пространства, в которой реализована некоторая функция от времени и координат (далее - функция среды, которая может представлять собой, например, температурное поле). В этой области размещается заданное число мобильных измерительных агентов, каждый из которых может измерять значение функции в той точке области, где он находится, и передавать его вместе со своими координатами в центр сбора и обработки.
В результате таких действий всех измерительных агентов в центре строится изображение функции среды с помощью какого-либо метода интерполяции (отсюда и название модели). В данном случае измерительные агенты выступают в роли узлов интерполяции, которые могут самостоятельно перемещаться в области задания функции среды. Вследствие ограниченного числа агентов изображение всегда будет отличаться от функции среды, и это отличие можно оценить с точки зрения внешнего наблюдателя, используя выбранный критерий расхождения (например, наибольшего отклонения, среднеквадратичный или интегральный [28]). Естественно предположить, что для каждого конкретного случая (для каждой функции среды) существуют такие размещения узлов интерполяции, которые доставляют глобальный минимум выбранного критерия расхождения. Таким образом, в рамках данной модели можно исследовать способы нахождения коллективом измерительных агентов таких размещений (статика) или способы организации сходимости перемещений измерительных агентов к таким размещениям (динамика).
В рамках теории приближения функций вопрос о существовании и нахождениинаилучших размещений узлов (базисов) интерполяции в основном исследован только лишь для функций одного аргумента [29], [30]. Уже для функции двух аргументов в этом вопросе много неясностей [29]. В то же время в данном случае в качестве полезных для решения поставленной задачи эвристик могут найти применение некоторые методы вычислительной геометрии и методы поиска экстремумов функции (по аналогии со способами активного сканирования [1]).
На данный момент нами разработан ряд алгоритмов коллективного поведения измерительных агентов, решающих задачу поиска наилучшего базиса [27]. Среди них можно выделить три группы. В первую группу входят относительно простые «релаксационные» алгоритмы коллективного поведения, которые отличаются минимальными требованиями к уровню информационной связности измерительных агентов (например, алгоритм «размещения по Темникову», в котором использована идея квантового критерия отсчетов для адаптивной дискретизации с некратными интервалами [28]). Во вторую группу входят алгоритмы коллективного поведения, разработанные на основе S-преобразования базисов (алгоритм Валле - Пуссена) и R-преобразования базисов (R-алгоритм) [30] для случая чебышевской интерполяции (критерий наибольшего отклонения) функции одного аргумента. В третью группу входят относительно сложные алгоритмы коллективного поведения, в которых использован ряд эвристик, согласно которым, кроме всего прочего, допускается функциональная специализация измерительных агентов (формирование взаимодополняющих групп стратегий). При этом в алгоритмах второй и третьей групп в разной степени реализована изложенная выше идея самоорганизации инструмента исследования. В ходе проведенных вычислительных экспериментов установлены зависимости показателей эффективности разработанных алгоритмов от основных параметров модели. К основным выводам можно отнести то, что с ростом сложности алгоритмов, как правило, растет эффективность решения поставленной перед коллективом задачи. Особо следует отметить достаточно успешные действия коллектива (алгоритмы второй и третьей группы) по исследованию синергетических процессов (использовалась простая модель нелинейной динамики [31]).
В рамках энтропийной модели коллективного поведения измерительных агентов непосредственно исследуется взаимосвязь процесса самоорганизации коллектива и количества собираемой им информации [21]. В базовом варианте модели рассматривается набор полностью или частично независимых источников событий из некоторого ограниченного алфавита, которые охвачены произвольным графом соединений. В первом приближении считается, что все источники стационарны. В узлах этого графа (в каждом из которых находится соответствующий источник) размещается ограниченное число мобильных измерительных агентов (предполагается, что число агентов намного меньше числа источников (узлов графа соединений) и каждый агент может свободно перемещаться по графу). При этом каждый агент может определять событие в том источнике, где он находится, и вместе с идентификатором источника сообщать о нем центру сбора и обработки. В результате таких действий всех агентов в центре накапливается статистическая информация в виде вероятностей реализации разных событий в источниках. Соответственно для статистического портрета каждого источника в центре может быть рассчитано значение его энтропии [19] (с учетом того, что в начальный момент времени согласно принципу недостаточного обоснования Лапласа для всех статистических портретов устанавливается максимальное значение энтропии). Таким образом, перед коллективом измерительных агентов ставится задача построить статистический портрет всего набора источников событий. Как основной критерий качества рассматривается скорость решения поставленной задачи.
Согласно логике энтропийной модели, агенту не выгодно находиться в источнике, настоящая энтропия которого максимальна, так как этот факт уже отображен в центре и новой информации в данном случае агент не привносит.
Соответственно, чем ближе настоящая энтропия источника к максимальной, тем меньше времени должен проводить в нем агент. Проблема заключается в том, что настоящие энтропии источников не известны агентам заранее. Нами разработано несколько алгоритмов коллективного поведения измерительных агентов, которые решают задачу построения статистического портрета. Алгоритмы основаны на идее вероятностного автомата [15] и на идеях обучения с подкреплением [11], [23]. В ходе проведения вычислительных экспериментов установлены зависимости между количественной оценкой процесса самоорганизации и количеством собираемой коллективом информации.
1. Цапенко М.П. Измерительные информационные системы: Структуры и алгоритмы, системотехническое проектирование. – М.: Энергоатомиздат, 1985.
2. Бочкарьов О.Ю., Голембо В.А. Система розподілених контактних вимірювань на основі автономних мобільних інтелектуальних агентів // Вісник НУ «Львівська політехніка» «Комп’ютерні системи та мережі». – 2001. – № 437. – С. 14-20.
3. Cortes J., Martinez S., Karatas T., Bullo F. Coverage control for mobile sensing networks: variations on a theme // Proc. of the Mediterranean Conf. on Control and Automation. – Lisbon (Portugal). – 2002.
4. Andrew Howard, Maja J. Mataric, Gaurav S. Sukhatme, Mobile Sensor Network Deployment using otential Fields: A Distributed, Scalable Solution to the Area Coverage Problem // Proc. of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS'02). – Fukuoka (Japan). – 2002.
5. Turner R.M., Turner E.H. Organization and reorganization of autonomous oceanographic sampling networks // Proc. of the IEEE International Conf. on Robotics and Automation. – Leuven (Belgium). – May 1998. – Р. 2060-7.
6. Autonomous oceanographic sampling networks / Curtin T.B., Bellingham J.G., Catipovic J., Webb D. // Oceanography. – 1993. – Vol. 6, № 3. – P. 86-94.
7. Бочкарьов О.Ю., Голембо В.А., Мельник А.О. Нові принципи побудови вимірювально-обчислювальних мереж на основі інтелектуальних агентів // Вісник НУ «Львівська політехніка» «Комп’ютерні системи та мережі». – 2003. – № 492. – С. 100-107.
8. Орнатский П.П. Теоретические основы информационно-измерительной техники. – К.: Вища школа, 1983.
9. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. – М.: Главная редакция физико-математической литературы изд-ва «Наука», 1969.
10. Woolridge М. An Introduction to MultiAgent Systems, John Wiley & Sons. – 2002.
11. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, by Gerhard Weiss (Editor). – MIT Press, 2000.
12. Эшби У.Р. Введение в кибернетику. –М.: Прогресс, 1959./p>
13. Горбатов В.А. Теория частично упорядоченных систем. – М.: Советское радио, 1976.
14. Фёрстер Г.О самоорганизующихся системах и их окружении // Самоорганизующиеся системы. – М.: Мир, 1964. – С. 113-139.
15. Варшавский В.И. Коллективное поведение автоматов. – М.: Наука, 1973.
16. Turing A.M. The chemical basis of morphogenesis // Philosophical Transacions of the Royal Society. - Series B 237. – 1952. – Vol. 37.
17. Gregoriy J. Chaitin. Algorithmic Information Theory. – Cambridge University Press, 1987.
18. Дружинин В.В., Конторов Д.С. Системотехника. – М.: Радио и связь, 1985.
19. Шеннон К. Работы по теории информации и кибернетике. – М.: Изд-во иностранной литературы, 1963.
20. David H. Wolpert, Kagan Tumer. Introduction to collective intelligence. – NASA Ames Research
Center, CA, USA. – 2000.
21.Бочкарьов О.Ю., Голембо В.А. Моделі колективної поведінки вимірювальних агентів // Вісник НУ «Львівська політехніка» «Комп’ютерні системи та мережі». – 2002. – № 463. – С. 19-27.
22. Опойцев В.И. Равновесие и устойчивость в моделях коллективного поведения. – М.: Наука, 1974.
23. Richard S. Sutton, Andrew G. Barto, Reinforcement Learning: An Introduction. – Cambridge: MIT Press, 1998.
24. Стахов .П. Введение в алгоритмическую теорию измерения. – М.: Советское радио, 1977.
25. Стахов А.П. Алгоритмическая теория измерения. – М.: Знание, 1979.
26. Бочкарьов О.Ю. Вирішення задачі механічного врівноваження колективом мобільних агентів //Вісник НУ «Львівська політехніка» «Комп’ютерні системи та мережі». – 2002. – № 463. – С. 14-18.
27. Бочкарьов О.Ю., Голембо В.А. Інтерполяційна модель колективної поведінки мобільних агентів вимірювально-обчислювальної мережі // Вісник НУ «Львівська політехніка» «Комп’ютерні системи та мережі». – 2003. – № 492. – С. 21-27.
28. Темников Ф.Е., Афонин В.А., Дмитриев В.И. Теоретические основы информационной техники. – М.: Энергия, 1971.
29. Бабенко К.И. Основы численного анализа. – М.: Наука, 1986.
30. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. – М.: Наука, 1972.
31. Maynard Smith J. Evolution and theory of games. – Cambridge, 1982.