Проблемы управления распределенными мобильными системами

Размещено на http://www.allbest.ru/

Российская Академия Наук

ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ

им. М.В. Келдыша

ПРОБЛЕМЫ УПРАВЛЕНИЯ РАСПРЕДЕЛЕННЫМИ МОБИЛЬНЫМИ СИСТЕМАМИ

А.К. Бакиров, А.А. Кирильченко

Москва, 2000 г.



Аннотация

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



Abstract

The paper deals with problems of grouped mobile robots behavior. A review of basic methods of distributed mobile robot system control is given. The problems of goal point achievement, information bypass and information blocking are described.



Введение

В проектах мобильных роботов (МР) в настоящее время весьма перспективной является концепция распределенной мобильной системы (РМС). Эти системы ориентированы на развитие группового действия при решении различных задач в условиях неопределенности. Перспективы развития РМС и их основные проекты подробно рассмотрены в [1,14,15].

Следует отметить определенную взаимосвязь между проектами РМС и многоагентными системами (МАС) в искусственном интеллекте, а также проектами типа «искусственная жизнь». Специфику двух последних направлений отражают схема 1 и таблицы 1-2. Они составлены на основе содержания обзоров [2-6]. Разряды объема возможных и перспективных РМС иллюстрирует таблица 3.

Среда, в рамках которой действует РМС, состоящая из отдельных элементов - МР, представляет собой толерантное метрическое пространство (основным отношением толерантности является отношение видимости). Такая структура ниже называется террайном. Двигательное поведение МР и РМС на террайне определяется алгоритмом функционирования, состоящем из набора информационно двигательных действий (ИДД) и диалогов МР между собой и диспетчером.

Управление движением одного МР является трехуровневым: реагирование в зоне безопасности, осмотр дальнего плана с выделением возможных подцелей движения на данном шаге, построение глобальной модели местности в виде графа пройденных подцелей. Следующие уровни управления действуют в рамках РМС. Сюда относятся: уровень группы МР и уровень миссии.

Моделирование движения РМС рассматривалось для следующих задач: (1) достижение целевой точки, (2) информационного обхода ограниченного участка террайна (в результате которого получается информация об этом участке в целом), (3) информационного блокирования (при этом движение РМС должно быть организованно так, чтобы РМС гарантированно обнаруживала любой движущийся предмет на ограниченном участке террайна).

Управление движением РМС в общем случае строится следующим образом. Пусть V(M) - видимая окрестность множества M, а dA - открытая граница множества A, т.е. те участки границы множества A, через которые МР может покинуть A. Пусть X_i(t_k) - положение i-го МР в момент времени t_k. Тогда такт работы системы управления (СУ) РМС при решении задач (1) и (2) заключается в выборе подцелей движения для элементов РМС из множества

dV(X₁(t₁),X₁(t₂),..,X₁(t_n),..,X_m(t₁),X_m(t₂),..,X_m(t_n)).

В задаче (3) существенную роль играет организация информационного взаимодействия между роботами, в частности, при формировании группы роботов для решения некоторой подзадачи. При этом начальная синхронизация МР группы требует до 10 шагов «информационных переговоров» между МР.

СУ как МР, так и РМС реализуется на основе частного вида магазинного автомата (МА). При этом входом является код ответа ИДД, на основе которого модифицируется стек МА. В таблице приведен список основных ИДД СУ МР:

Осмотр дальнего плана

Выделение подцелей

Поиск альтернативных путей

Выбор оптимальной подцели из множества новых подцелей

Выбор оптимальной подцели из множества необследованных подцелей графа подцелей

Реализация движения непосредственно в выбранную подцель с корректировкой положения подцели

Реализация движения по графу подцелей в заданную подцель с корректировкой положения подцели

Упрощение графа подцелей

Остановка

Обновление стека

Выдача сообщения диспетчеру



Парадокс критерия эффективности РМС

Прежде чем начать обсуждение способов управления РМС, следует отметить, что для оценки эффективности работы РМС можно использовать различные критерии. При этом, в зависимости от критерия возможен различный характер поведения этой эффективности в зависимости от числа элементов РМС. Сказанное иллюстрирует таблица 4, где приведены различные критерии эффективности для задачи контурного обхода РМС некоторой области.

Исследования показывают, что в общем случае эффективность (рассматриваемая как время выполнения задачи) изменяется следующим образом. При небольшом количестве элементов группы, время выполнения задачи уменьшается с ростом их числа. Далее, оно слабо колеблется у некоторой постоянной величины. А затем, оно увеличивается (роботы начинают мешать друг другу).

Основные способы управления РМС

Исследования системы управления (СУ) РМС показывают, что можно выделить следующие пять основных способов управления РМС:

Один ведущий. При этом ведомыми реализуется режим «движение за лидером» или «конвой». Следует особо отметить, что ведущий элемент группы не обязательно является постоянным.

Центральное управление последовательное (ЦУПос). В этом случае центр управления связан с каждым элементом группы непосредственно, и шагом работы СУ является движение одного элемента группы. Очередность выбора элементов для шага может быть различной.

Центральное управление параллельное (ЦУПар). В этом случае центр управления также связан непосредственно с каждым элементом группы, и шагом является одновременное движение всех элементов группы. Каждый элемент при этом реализует собственную подцель движения. Новый шаг начинается лишь тогда, когда каждый элемент группы реализовал свою подцель движения на предыдущем шаге.

Распределенное автономное управление (РАУ). Этот тип управления соответствует линии «муравьиного интеллекта» П. Брукса. В этом случае производится априорная настройка процедур решения у каждого элемента группы. Обмена информации между элементами группы нет. [13]

Распределенное управление с обменом информацией (РУСОИ). При этом производится обмен информацией между элементами всей группы или отдельных ее подмножеств. Управление организуется без иерархического подчинения (гетерархия), и информация касается в основном характеристик среды. При этом обмен информацией может осуществляться, если элементы группы достаточно близко находятся друг от друга, либо находятся в пределах видимости друг друга, а также возможно планирование мест встречи для обмена информацией.

Следует особо подчеркнуть, что в реальной системе управления могут комбинироваться различные из указанных способов управления. Например, режим ЦУПар + РУСОИ позволяет при общем централизованном управлении организовывать группы элементов, решающих конкретную подзадачу.

Основные характеристики данных способов управления для задач достижения целевой точки и информационного обхода сведены в таблицу 5.

Задачи достижения целевой точки и информационного обхода

Движение РМС задается в террайне - ограниченной области с препятствиями непрозрачными для измерителя и непреодолимыми для МР. Для простоты препятствия представляют собой многоугольники с углами в вершинах в 90 и 270. Подобные модели активно исследовались в ИПМ [6-8] и других исследовательских организациях [9].

Основные понятия теории террайнов иллюстрирует рис.1. Пусть V - заключенная в рамку область допустимых положений МР (который представляется точкой). Две точки x,y видимы одна из другой (что записывается как x~y), если отрезок [x,y] не пересекает препятствий (но может их касаться).

В общем случае террайн Ter = < V, , , ~, [...]>, где

V - носитель террайна,

(x,y) - исходная евклидова метрика,

(x,y) - вторая основная непрерывная метрика, удовлетворяющая отношению (x,y) (x,y) (обычно выбирается длина геодезической, т.е. кратчайшего пути, не пересекающего препятствий),

“~” - основное отношение толерантности (отношение видимости), которое может быть определено по схеме (x~y) <=>((x,y)=(x,y)),

[...] - индуцированные на основе указанных выше метрик и толерантности другие метрики и толерантности.

Всегда предполагается, что число препятствий в террайне и число вершин препятствий конечны.

Отрезок [a,b] называется касательным, если

(1) он максимален для данного террайна, т.е. в направлении b из a b является максимально удаленной видимой из a точкой.

(2) На интервале (a,b) есть как граничные точки, так и точки из Int V.

Отрезок [c,d] называется гейтом, если

(1) [c,d] строго входит в некоторый касательный отрезок;

(2) c и d являются граничными точками террайна;

(3) интервал (c,d) состоит только из внутренних точек террайна - Int V.

Если гейт [c,d] строго входит в касательный отрезок [a,b], а точка x расположена на этом касательном отрезке и не принадлежит указанному гейту, то [c,d] называется наблюдаемым в точке x гейтом. Нетрудно видеть, что хотя бы одна из конечных точек гейта является вершиной препятствия.

Вершины препятствий, расположенные на интервале касательного отрезка, называются класпами. Если p - некоторый класп, то его ориентация определяется тем, по какую сторону от касательного отрезка расположены содержащие p граничные отрезки препятствия. Если p1 и p2 - два класпа, расположенные на одном касательном отрезке и их ориентации различны, то на касательном отрезке имеет место ситуация типа "двойной класп" - см. рис.1.

Наряду с традиционным понятием границы множества M в террайнах большую роль играет свободная граница множества M - dM. Она определяется как подмножество таких точек x "обычной границы", что в сколь угодно малой окрестности x найдутся точки y из носителя террайна V, которые не входят в замыкание M.

Отличие от "обычной границы" в том, что там все y, не входящие в замыкание M, могут принадлежать препятствию. dV(x) - множество, через которое МР может покинуть V(x) - видимую окрестность x (т.е. множество всех точек, видимых из x). Видимая окрестность множества V(M) понимается как объединение видимых окрестностей всех точек множества.

Справедливо

Утверждение 1 [7]:

(1) V(M)=V(dM)

(2) dV(x) состоит из всех гейтов, наблюдаемых в точке x.

(3) dV(M) в общем случае состоит из гейтов или участков гейтов, наблюдаемых из точек множества M.

Конечное множество A называется навигационным, если V(A)=V.

Конечное множество M называется магистральным, если

(1) M является навигационным множеством;

(2) если x, y - элементы M, то существует путь из x в y, все вершины которого суть элементы M.

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

Пусть МР обладает возможностью фиксировать точки некоторого магистрального множества M и осуществлять к ним передвижение, а также опознавать целевую точку. Тогда задача выбора пути между произвольными точками террайна x и y сводится к задаче построения такого пути по магистральному графу, вершинами которого являются элементы M и, возможно, точки x и y. Ребра графа при этом определяются на основе отношения видимости. При этом известные алгоритмы выбора маршрута по известному графу модифицируется с учетом того, что МР в каждый момент времени может находиться в единственной вершине (или двигаться по ребру) итеративно строящегося в процессе решения задачи путевого графа, являющегося подграфом магистрального [7].

Под задачей о достижении целевой точки для одного МР понимается упорядоченная тройка m=(Ter,b,g), где Ter - некоторый террайн, b - точка начала движения, g - целевая точка. При этом b,gV, т.е. являются допустимыми точками террайна. Террайн при этом предполагается линейно связным.

Задача называется тривиальной, если [b,g ]V, т.е. начальная и целевая точки видимы. В дальнейшем будут рассматриваться только нетривиальные задачи.

Террайн Ter предполагается линейно связным, т.е. для любой задачи m=(Ter,b,g) на нем существует путь из b в g. Более того - существует путь, представимый ломаной.

Путь ph, есть последовательность точек террайна (ломаная) ph={s₀,s₁,…,s_n} такая, что [s_i,s_i+1 ]V, i=0,..n-1 (при этом точки не обязаны быть различными). Последовательность ph называется решением задачи m, если s₀=b, s_n=g.

Точки s_i, i>0 называются подцелями. а n есть информационная длина пути (число звеньев ломаной).

Под задачей информационного обхода понимается сбор информации обо всем носителе террайна V, который является ограниченной областью. Если для задачи m задана недостижимая целевая точка g, то естественно за достаточный промежуток времени МР решит задачу информационного обхода.

При формулировке задачи для РМС вместо b определяется B - множество, характеризующее расположение МР РМС в начальный момент времени.

Управление движением РМС в общем случае строится следующим образом. Пусть x_i(t_k) - положение i-го МР в момент времени t_k. Тогда такт работы системы управления (СУ) РМС при решении рассматриваемых задач заключается в выборе подцелей движения для элементов РМС из множества dV(x₁(t₁),x₁(t₂),..,x₁(t_n),..,x_m(t₁),x_m(t₂),..,x_m(t_n)). Это множество будем обозначать через W_n оно представляет собой открытую границу множества положений всех подцелей, пройденных элементами РМС.

Ниже приводится схема шага ЦУПос для решения задач достижения целевой точки и информационного обхода. (Капитаном называется центр управления РМС).

1) Организация Капитаном согласованного общего осмотра на текущих позициях и формирование текущей открытой границы dV(x₁(t_n),..,x_k(t_n))=W_n⁰

2) Формирование полной открытой границы dV(x₁(t₁),..,x₁(t_n),...,x_k(t₁),..,x_k(t_n))=W_n

3) Выделение на W_n множества гейтов {_i}

4) Выбор элемента системы для шага из условия , здесь G - целевая точка, ch - оценочная функция расстояния от гейта до целевой точки.

5) Реализация шага элементом.

Процесс активации группового шага информационного обхода в режиме ЦУПар следующий. (Предполагается террайн типа изображенного на рис. 2: помещение с «коридорами», «комнатами» и «дверьми»).

1) Выбор Капитаном Ведущего группы и передача ему задания на шаг.

2) Расстановка Ведущим приоритетов в группе.

3) Выполнение группой маневра "продвижение через дверь".

4) Построение группы псевдоядром видимости (т.е. видимые окрестности положений элементов группы отличаются незначительно).

5) Проведение элементами группы осмотра дальнего плана (ДП).

6) Проведение Ведущим согласованной интерпретации объектов ДП и активация у каждого из элементов группы процесса информационного слежения.

7) Сообщение от Ведущего к Капитану.

8) Выбор Капитаном подцелей движения на шаге.

9) Построение Ведущим плана реализации подцелей на шаге.

10) Запуск шага.

Следует отметить то обстоятельство, что в режиме ЦУПар достижение текущих подцелей реализуется одновременно всеми элементами РМС. При этом осуществляется синхронизация по окончанию шага: шаг считается завершенным, когда все МР достигли своих подцелей.

Корректность определения алгоритмов достижения целевой точки и информационного обхода обосновывается следующей теоремой.

Теорема 1:

Пусть для алгоритма, реализующего ЦУПос, на шаге выбирается подцель из W_n. Тогда данный алгоритм сходится за конечное число шагов для любой задачи достижения целевой точки на данном террайне.

Доказательство проводится методом «от противного».

1) Пусть для данной задачи алгоритм не сходится к целевой точке за конечное число шагов. Тогда алгоритм строит некоторый потенциально бесконечный путь.

2) В силу схемы процедуры выбора очередной подцели, указанной выше, и утверждения 1.(3) в этом случае можно выбрать сколь угодно длинную последовательность гейтов _i такую, что подцели пути принадлежат этим гейтам.

3) Поскольку вершин препятствий конечное число, то отсюда следует, что можно выбрать сколь угодно длинную подпоследовательность гейтов, для которых ближайшая к точке наблюдения (пройденной подцели) вершина p одна и та же.

4) Пусть на некоторый конечный момент времени на вершине p построено n гейтов. Перенумеруем наблюдаемые на p гейты. Пусть ₁ - первый из них, полученный в процессе работы алгоритма, а ₂ - ближайший из n-1 оставшихся по углу между гейтами с вершиной p. Пусть подцель s₁₁, а подцель s₂₂.

5) Если s₁=p, то s₁ видима из s₂ (s₁~s₂). Тогда существует вершина q(s₁,s₂), т.к. подцель s₂ принадлежит открытой границе видимой окрестности пройденных подцелей. В противном случае s₂ будет видима из p с некоторой своей окрестностью и не сможет принадлежать открытой видимой границе пройденных подцелей. Таким образом, ближайшей к точке наблюдения вершиной гейта ₂ будет q, а не p, что противоречит нашему предположению.

6) Аналогично рассматриваются случаи s₂=p

7) Пусть (s₁p)&(s₂p). В случае s₁~s₂ аналогичным образом показывается, что существует вершина q(s₁,s₂). Если s₁ не видима из s₂ (s₁/~s₂), то в соответствии с леммой о треугольнике [10] существует вершина препятствия q принадлежащая внутренности треугольника ps₁s₂. Таким образом, всегда найдется вершина препятствия, расположенная во внутренности угла, образованного выделенной парой гейтов.

8) Повторяя проведенные рассуждения для любой другой пары подцелей, находящихся на соседних по углу гейтах, получаем, что число вершин препятствий в террайне не ограниченно. Полученное противоречие доказывает теорему.

Следствие:

Алгоритм ЦУПос решения задачи информационного обхода сходится за конечное число шагов.

Теорема 2:

Пусть для алгоритма, реализующего ЦУПар, на шаге выбирается подцели из W_n. Тогда данный алгоритм сходится за конечное число шагов для любой задачи достижения целевой точки на данном террайне.

Основная схема доказательства остается той же самой.

Следствие:

Алгоритм ЦУПар решения задачи информационного обхода сходится за конечное число шагов.

Задача информационного блокирования

Задача информационного блокирования заключается в том, что РМС осуществляет информационный обход некоторой ограниченной среды так, чтобы ни один объект (в том числе, динамический) не остался незамеченным. Эта задача является аналогом задачи Парсонса на конечном графе (блокирование подвижного объекта - «беглеца» - подвижными объектами - «полицейскими») [12]. Пример решения задачи информационного блокирования иллюстрирует рис. 2. [11].

При управлении РМС в этом случае могут использоваться 2 подхода: а) геометрический и б) топологический. В случае (а) движение организуется на основе выбора подцелей из открытой границы множества пройденных подцелей, как это указывалось ранее. В случае (б) СУ РМС оперирует понятиями «коридор», «дверь», «комната» («район»), отдельный «объект в комнате».

При организации движения используются следующие локальные правила:

1) Обход района может начаться, если вход в район (дверь) фиксирован (наблюдается) каким-либо неподвижным МР.

2) При исследовании района все неизвестные двери должны фиксироваться.

3) Если МР фиксирует дверь, то он обладает наименьшим приоритетом по вовлечению в поисковые группы.

4) В коридоре допускается поисковое движение одного МР, в комнату должны входить не менее двух МР (один фиксирует вход).

Конечное положение МР должно, по возможности, обеспечивать выполнение условия V(V(M))=V, где M - множество МР РМС. Индексная таблица событий при обследовании РМС данного района приведена в таблице 6.

Результаты имитационного моделирования

Исследования показывают, что в общем случае эффективность (рассматриваемая как время выполнения задачи) изменяется следующим образом. При небольшом количестве элементов группы время выполнения задачи уменьшается с ростом их числа. Далее, оно слабо колеблется у некоторой постоянной величины. А затем, оно увеличивается (роботы начинают мешать друг другу).

Указанные особенности подтверждены имитационным моделированием задачи достижения каждым элементом РМС своей подцели. На рис. 3 приведены зависимости общего относительного результирующего перемещения элементов РМС в зависимости от числа элементов РМС. На рис. 4 приведены кадры движения РМС при решении этой задачи: рис. 4а - стартовая позиция (для каждого элемента показана его связь с подцелью назначения), рис. 4б и 4в показывает взаимодействие элементов РМС в процессе движения. Реализация движения в режиме РАУ основывалась на реагировании МР на движущиеся объекты в зоне безопасности.

Заключение

В работе получены следующие результаты:

1) Показана зависимость эффективности действия РМС от выбранного критерия эффективности.

2) Проанализированы основные способы управления РМС.

3) Для задачи достижения целевой точки и информационного обхода сформулированы теоремы о сходимости алгоритма управления РМС к целевой конфигурации за конечное число шагов для конечной статичной среды.

4) Предложен алгоритм решения задачи информационного блокирования РМС подвижного объекта. Сходимость данного алгоритма к цели функционирования авторы предполагают доказать в следующих работах.

5) Исследовано влияния числа элементов РМС на пройденный суммарный путь элементов РМС для задачи достижения каждым элементом назначенной подцели.

На основе полученных результатов можно сделать следующие выводы:

1) Для управления РМС в определенных задачах может быть эффективным комбинирование различных способов управления. Например: Центральное Управление Последовательное с Распределенным Групповым Управлением при решении задачи информационного блокирования.

2) В общем случае эффективность (рассматриваемая как время выполнения задачи) изменяется следующим образом: при небольшом количестве элементов группы время выполнения задачи уменьшается с ростом их числа. Далее, оно слабо колеблется у некоторой постоянной величины. А затем, оно увеличивается (роботы начинают мешать друг другу). Таким образом следует ожидать наличия оптимального диапазона числа элементов РМС для решения данной задачи.

3) Доказательство сходимости алгоритмов центрального управления РМС для случая ограниченной статичной среды при решении задач достижения целевой точки и информационного обхода проводится методом от противного в принятой формализации (выбор подцели осуществляется в открытой границе множества всех пройденных элементами РМС подцелей).

мобильный робот алгоритм архитектура



Литература

Кирильченко А.А., Платонов А.К., Гашков И.А., Трубицин О.Н. Перспективы развития распределенных мобильных робототехнических систем // Препринт Ин. прикл. матем. им. М.В. Келдыша РАН, 1998, N 23, 30 с.

В.Б. Тарасов/ Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатики и искусственном интеллекте // Новости искусственного интеллекта - Москва - 1998 - N 2, с. 5-63

В.И. Городецкий, М.С. Грушинский, А.В. Хабалов. Многоагентные системы (обзор) // Новости искусственного интеллекта - Москва - 1998 - N 2 с. 64-116

Под редакцией Э. Кьюсиака. Системы распределенного искусственного интеллекта // Искусственный интеллект: Применение в интегрированных производственных системах - М.: Машиностроение, 1991

Бобровский С. Искусственное выживание // PC Week/RE, №38, 29.09.1998

Кирильченко А.А., Карпов И.И., Платонов А.К. Метод подцелей в задаче выбора трассы мобильного робота в условиях неопределенности // Препринт Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1983, N 16, 28 с.

Кирильченко А.А. Обоснование алгоритмов выбора пути в условиях неопределенности. // Препринт Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1991, N 108, 25 с.

Кирильченко А.А. Об исследовании эффективности алгоритмов выбора пути в условиях неопределенности. 2. Атлас особых ситуаций и атлас "неустойчивого доминирования" // Препринт Ин. прикл. матем. им. М.В. Келдыша РАН, 1997, N 44.

Сирота И.М. Прокладка маршрута автономного робота в незнакомой среде. // Проблемы создания гиб. автоматизир. производств, 1987.

Кирильченко А.А. Ядра и классы видимости в задачах информационного обеспечения мобильных роботов // Препринт Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1988, № 181, 28 с.

Белоусов А.И., Кирильченко А.А. Управление группой мобильных роботов в задаче информационного блокирования подвижного объекта. // V. Межд. Научно-тех. конф. «Современные методы и средства океанологических исследований», М.: ИО РАН, 1999, с. 154-155.

Megiddo N., Hakini S.L. e.a. The complexity of searching a graph // “J. Assoc. Comput. Mach”, 1988, v.35, № 1, pp 18-44

Rover on a chip // “Aerospace America” 1989, Dec., pp 22-26

Петров А.А., Активное формирование моделей проблемной среды очувственными роботами. // М.: ИППИ РАН, 1997, 229 с.

Vainio M., Appelqvist P., Halme A., Mobile robot society for distributed operations in closed aquatic environment // Robotica, 2000, v.18, pp. 235-250.



Приложение

Схема 1. Архитектуры многоагентных систем (МАС)

Архитектура	Взаимодействия агентов	Одноуровневая	Полностью децентрализована. Информация носит существенно распределенный характер и лишь частично доступна каждому из участников. Каждому агенту назначается определенная роль, причем эти роли могут динамически меняться. Пример приложения: динамические задачи составления расписаний при выполнении некоторой деятельности в условиях ограниченных ресурсов.
		Иерархическая	Предполагается использование хотя бы одного агента "метауровня", осуществляющего координацию распределенного решения задач агентами. Агент-координатор может быть привязан к конкретному серверу, и тогда он называется АМР (Agent Meeting Place - место встречи агентов). АМР - это по сути дела агент, играющий роль брокера между агентами, запрашивающими некоторые требующиеся им ресурсы, и агентами, которые эти ресурсы могут предоставить.
	Агента	Основанная на знаниях	Содержит символьную модель мира в явной форме, где принятие решений о действиях, которые должны быть предприняты агентом, осуществляется на основе рассуждений логического и псевдологического типа. Чисто логическая основа дополняется специальными вариантами модальных логик, образуя BDI (Belief-Desire-Intention) архитектуру.
		Основанная на планировании (реактивная)	Планирование понимается, как конструирование последовательности действий, которая, будучи исполненной, приводила бы в результате к достижению желаемой цели.	Реакция агента на внешние события генерируется конечным автоматом.
				Система STRIPS. Имея описание мира и желаемой цели, требуется найти последовательность действий, которая в итоге приведет к достижению цели с удовлетворением постусловий. Система оказалась неэффективной.



Таблица 1. Основные школы в построении МАС

Школа	Основные идеи
Школа организационного моделирования и проектирования (нисходящий подход)	Опирается на современные подходы общей теории систем и организаций, включая функционально-структурный и эволюционно-органический подходы, а также использует социо-психологические методы. Нисходящий подход основывается на концепции, в русле которой индивидуальные свойства и поведение агентов в МАС определяются на основе типа социальной организации и множества соответствующих взаимодействий между агентами. Общую идею можно выразить в виде следующей цепочки: "выбор социальных критериев для характеризации сообщества МАС - определение типа искусственного сообщества - синтез структуры МАС - выбор типов агентов - проектирование архитектуры агента".
Школа организационного моделирования и проектирования (восходящий подход)	Аналогичная цепочка для восходящего проектирования включает следующие этапы: Формулирование назначения (цели разработки) МАС Определение типа и основных свойств среды МАС Определение основных и вспомогательных функций агентов в МАС Уточнение состава агентов и распределение функций между агентами, выбор архитектур агентов Выделение базовых взаимосвязей (отношений) между агентами в МАС Определение возможных действий (операций) агентов Построение базовой архитектуры МАС, анализ ее возможных состояний Анализ реальных текущих или предполагаемых изменений внешней среды (условий функционирования) или внутренних противоречий МАС Определение соответствующих изменений функций агентов и формулирование стратегии эволюции МАС Построение общей архитектуры МАС, инвариантной к рассмотренной области изменений среды.
Логическая школа моделирования	Моделируются убеждения, намерения, желания и склонности агентов на основе неклассических логик. Главной идеей данного подхода является представление характеристик агента в виде логической теории. При этом можно выделить два основных направления работ: а) Расширение классической и многосортной логик с помощью предикатов высокого порядка. б) Обобщение модальных логик, допускающее модальности типа "возможно" и "необходимо", "известно" и "неизвестно", "желает" и "не желает" и т.д.
Лингвистическая школа моделирования	Моделируются речевые акты, используемые при построении протоколов коммуникации и описании взаимодействия агентов на основе потоков работ (workflows). Процесс координации в МАС понимается как моделирование сети взаимных обязательств между агентами, направленных на удовлетворение агента-клиента. Базовый контур в модели потоков работ связывает агента-заказчика с агентом-исполнителем в рамках цикла, состоящего из четырех этапов или потоков: "подготовка - переговоры - выполнение - приемка"



Таблица 2. Системы искусственной жизни

Название	Разработчики	Особенности
Swarm	Крис Ленгтон	Позволяет задавать произвольные наборы свойств проектируемого виртуального пространства - число измерений, форму, способы передвижения агентов и их методы влияния на характеристики мира. Для достижения общей цели агентам позволено объединяться в группы, организовывать действия этих групп. Исследовалось поведение больших коллективов виртуальных существ в пространствах со сложной или динамически изменяемой геометрией.
MANTA (Modeling an ANTnest Activity	Алексис Дрогаул	Это колония реактивных агентов (реагирующих на внешнюю среду и не способных "думать", обучаться и общаться с другими агентами). Каждый агент определяется заданной формой поведения, имеет графическое представление на экране, свое место в пространстве, может расти в зависимости от времени и (в некоторых случаях) от количества пищи. С помощью этой системы Дрогаул моделировал развитие колоний самых разных насекомых.
LEE	Филипп Шенцер, Рик Белью	Виртуальный мир представляет собой двухмерное замкнутое пространство, где случайным образом распределены элементарные физические объекты трех типов (атомы). Съедаемые существом атомы реагируют друг с другом, и в результате выделяется или поглощается энергия (мера жизнеспособности существа). В каждой ячейке пространства может одновременно располагаться несколько существ и разных атомов пищи. Существа могут перемещаться, питаться, умирать и размножаться. Каждое существо снабжено нейронной сетью, связывающей сенсоры и моторную систему. Сеть анализирует и запоминает результаты взаимодействия атомов.
Tierra	Том Рей	Моделирует эволюцию компьютерных программ. В типичном эксперименте виртуальная память "заражается" единственной программой, способной самовоспроизводиться - копировать себя в другие области памяти. Двоичный код программы может подвергаться случайным мутациям, становясь в некоторых случаях невыполнимым. Тогда считается, что программа генерирует ошибку, т.е. «больна». Когда память переполняется, Tierra проверяет, сколько ошибок генерирует каждая программа, и удаляет самые «больные». Выживают в основном программы, менее требовательные к ресурсам (памяти и количеству тактов) и способные быстро размножаться.



Таблица 3. Разряды объема распределенных мобильных систем (РМС)

Разряд	Число мобильных единиц	Примеры
0	2-3	1. Система "робот-матка - робот-дитя" 2. Транспортировка мобильными манипуляторами крупногабаритного груза
1	3-10	1. Транспортные системы малых и средних гибких производственных систем (ГПС) 2. Соревнования МР-хоккеистов, МР-футболистов 3. Система подводного патрулирования (США)
2	10-30	1. Транспортные системы больших ГПС 2. Дистанционно-управляемые мишенные поля (США)
3	30-100	Проекты: "Роботы против стихийных бедствий", "Роботы против лесных пожаров" (Япония)
4	Сотни-Тысяча	1. Проект мобильного минного поля (США) 2. Исследование среды на основе концепции "муравьиного интеллекта" (США)
5	Тысячи	Танковое сражение под Прохоровкой - 1200
		Курская битва - 6144
		Число самолетов, ежесекундно находящихся в полете над США - 7000 (проект системы "Свободный полет")
6	Порядка и более 10000	Число танков, задействованных в ходе конфликта в Персидском заливе в 1991 г. - 10,5 тысяч

Таблица 4. "Парадокс критерия" для оценки эффективности РМС на примере задачи контурного обхода (время выхода на начальную позицию не учитывается).

Тип оценки эффективности	Формула	Характер функции критерия
Время обхода	где - длина контура, - число МР, - скорость МР	Монотонное уменьшение с ростом n.
Мультипликативная схема "время на стоимость эксплуатации"	где - стоимость эксплуатации одного МР во время операции обхода	Постоянная
Аддитивная весовая схема		Есть оптимальное решение
Аддитивная схема с учетом затрат на обмен сообщениями	где - период обмена сообщениями типа "каждый с каждым", - цена обмена единичным сообщением	Есть оптимальное решение

Таблица 5. Управление РМС при решении задач достижения целевого положения и информационного обхода в условиях неопределенности.

Тип стратегии	Комментарий
Один ведущий	Реализация ведомыми режима «движение за лидером» или «конвой»
ЦУПос: ЦУ - последовательное; шаг - движение одного элемента группы; Центр связан с каждым элементом группы непосредственно.	Подцель p dV (xkt, k =1,...,n; t = 0,...,T) pht(xk)=(xk0, xk1,...xkt) - путь k-ого элемента к моменту t; V(М) - видимая окрестность множества M; dM - открытая граница множества M; Два этапа реализации подцели: Выбор p0 из условия || p - g|| min (g - целевая точка) Выбор k из условия || p0 - xkt || min
ЦУПар: ЦУ - параллельное. Шаг - движение всех элементов группы синхронно (с ожиданием) или асинхронно	|| p - x k || min; вариант задачи о назначениях. Возможна ситуация «бесполезного» хода для некоторого k: V(x kt ) \ V(j k ph t(xj)) =
РАУ - распределенное автономное управление (каждый за себя: линия «муравьиного интеллекта»)	Априорная настройка процедур решения у каждого элемента группы. Обмена информации между элементами группы нет.
РУСОИ: распределенное управление с обменом информацией между элементами группы без подчинения (гетерархия)	Варианты: в пределах ; в пределах видимости; в пределах R-видимости. Возможно планирование мест встречи для обмена информацией.



Рис. 1 Основные понятия теории террайнов.

V есть область в граничной рамке, исключая внутренние точки препятствий П₁ и П₂. Точки x и y, а также x и z видимы одна из другой, а точки z и y - нет. [a₁, b₁] и [a₂, b₂] являются касательными отрезками; [p₁, b₁] - гейт, наблюдаемый в точке x, этот гейт входит в dV(x); p₁, i =1, 2, 3, 4 - класпы на указанных касательных отрезках. На [a₂,b₂] наблюдается ситуация "двойной класп" и этот касательный отрезок является классом видимости.

Рис. 2 Обследование ограниченной области группой из 7 MP



В начальный момент группа MP {A,B,C,D,K} находится у нижнего левого входа, группа {E,F} - у верхнего правого.

Районы области помечены R 'L' (L - номер района), положение MP: Z 'N', где N - номер события. ( означает, что MP остановился).

Таблица 6. Индексная временная таблица событий.

N события	t(усл. ед)	Комментарий
1	4	A,B начинают обходить с двух сторон П1; К фиксирует три входа
2	8	Встреча (A,B) после обхода
3	12	Встреча (C,D,E,F), B обходит R2; C,E заходят в R5
4	16	Встреча (B,D). B начинает обход R3. D фиксирует входы
5	24	B,E дают сигнал о тупике, A начинает движение в R7
6	28	B заканчивает обход R3, E фиксирует вход, C идет в R1
7	32	A фиксирует перекресток и ждет, C фиксирует вход
8	40	Встреча (A,B), A начинает обход R9, B ждет
9	52	A заканчивает обход R9, B начинает обход R10
10	64	Конец исследования области

Размещено на Allbest.ru

...