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

( The Problems of Distributed Mobile Robot System Control
Preprint, Inst. Appl. Math., the Russian Academy of Science)

СОДЕРЖАНИЕ

1.  ВВЕДЕНИЕ.. 2

2.  ПАРАДОКС КРИТЕРИЯ ЭФФЕКТИВНОСТИ РМС.. 4

3.  ОСНОВНЫЕ СПОСОБЫ УПРАВЛЕНИЯ РМС.. 4

4.  ЗАДАЧИ ДОСТИЖЕНИЯ ЦЕЛЕВОЙ ТОЧКИ И ИНФОРМАЦИОННОГО ОБХОДА   5

5.  ЗАДАЧА ИНФОРМАЦИОННОГО БЛОКИРОВАНИЯ.. 10

6.  РЕЗУЛЬТАТЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.. 10

7.  ЗАКЛЮЧЕНИЕ.. 11

8.  ЛИТЕРАТУРА.. 12

ТАБЛИЦЫ И РИСУНКИ

1.    ВВЕДЕНИЕ

В проектах мобильных роботов (МР) в настоящее время весьма перспективной является концепция распределенной мобильной системы (РМС). Эти системы ориентированы на развитие группового действия при решении различных задач в условиях неопределенности. Перспективы развития РМС и их основные проекты подробно рассмотрены в [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 шагов «информационных переговоров» между МР.

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

2.    ПАРАДОКС КРИТЕРИЯ ЭФФЕКТИВНОСТИ РМС

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

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

3.    ОСНОВНЫЕ СПОСОБЫ УПРАВЛЕНИЯ РМС

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

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

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

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

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

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

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

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

4.    ЗАДАЧИ ДОСТИЖЕНИЯ ЦЕЛЕВОЙ ТОЧКИ И ИНФОРМАЦИОННОГО ОБХОДА

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

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

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

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

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

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

“~” - основное отношение толерантности (отношение видимости), которое может быть определено по схеме (x~y) <=>(a(x,y)=r(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,gÎV, т.е. являются допустимыми точками террайна. Террайн при этом предполагается линейно связным.

Задача называется тривиальной, если [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 множества гейтов {g_i}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 1:

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

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

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

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

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

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

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

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

Следствие:

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

5.    ЗАДАЧА ИНФОРМАЦИОННОГО БЛОКИРОВАНИЯ

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

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

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

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

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

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

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

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

Индексная таблица событий при обследовании РМС данного района приведена в таблице 6.

6.    РЕЗУЛЬТАТЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

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

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

7.    ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

БЛАГОДАРНОСТИ

Авторы выражают глубокую признательность А.К. Платонову и С.Б. Ткачеву за полезные обсуждения, Г.К. Боровину за полезные редакторские замечания и А.И. Белоусову за любезно предоставленные иллюстративные материалы.

8.    ЛИТЕРАТУРА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.    ПРИЛОЖЕНИЕ

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

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

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

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

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

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

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

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