1

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

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

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

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

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

А.К. Платонов, Е.Ю.Зуева, А.А. Кирильченко, С.М.Соколов

ЛОГИЧЕСКИЙ ПОДХОД К ПРОЕКТИРОВАНИЮ АЛГОРИТМОВ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ МОБИЛЬНЫХ СИСТЕМ. ОСНОВНЫЕ ПОНЯТИЯ

Москва, 2006 г.

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

The main concepts of algorithms design for mobile systems information support are considered. The special attention is paid to the algorithms justification, the investigation of comparative efficiency of algorithms and adequate interpretation of sensory information. The paper is addressed to any reader interesting in this field; it also may be used for education purpose.

СОДЕРЖАНИЕ

Введение

1. Основные концепции логического подхода

2. Террайн

3. Ядра и классы видимости

4. Обоснование алгоритмов выбора пути

5. Структурные характеристики среды

6. Несравнимость и адаптация алгоритмов выбора пути в условиях неопределенности

Заключение

Приложение 1. Некоторые постулаты логического подхода

Приложение 2. Историческая справка об отношении толерантности

Литература

Список сокращений

ВВЕДЕНИЕ

алгоритм информационный мобильный сенсорный

Под мобильной системой (МС) ниже будет пониматься либо единичный мобильный робот (МР), либо МР и сенсорная распределенная система (СРС, распределенное в пространстве стационарное сенсорное устройство), либо группа МР, либо группа МР и СРС. В последних трех случаях речь идет о распределенной мобильной системе (РМС).

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

Можно выделить восемь основных направлений исследований в этой области Первое направление (его прототип - знаменитый робот "Shakey") определило линию развития методов принятия решений на основе автоматических средств формального логического вывода. Именно здесь были приложены наибольшие усилия для создания технологических и языковых средств искусственного интеллекта в робототехнике.

Второе направление развития мобильных роботов за рубежом берет свое начало от работ Брукса [4] - автора концепции "муравьиного интеллекта". На этом направлении развивается идея разработки небольших по размерам, дешевых и легко перепрограммируемых МР для решения данной функциональной задачи. Следует особо подчеркнуть, что в настоящее время направление организации совместной работы группы роботов ("Multy-robot system") активно развивается в NASA (проект легких марсоходов с манипуляторами типа Rocki-3[1]), в DARPA (перспективный проект мобильного минного поля [2]) и в ряде других систем, в частности двойного применения ("роботы - охранники").

Эти первые два направления требуют меньших затрат (они реализуются обычно в университетских центрах) и имеют целью разработку принципиально новых концепций систем управления МР.

Два следующих направления отражают разработки прототипов роботов для конкретных областей применения (что сопряжено со значительными затратами). Третье направление состоит в развитии способов управления движением машин с шагающим движителем ("Legged vehicle"), к которым, в частности, принадлежат разработки летающе-шагающих роботов в Японии и в США [1]. Четвертое направление составляют некоторые реализации роботов с традиционным типом движителей, в частности, для инспекции АЭС.

Управление МР военного применения развиваются в следующих направлениях: пятое, автономное управление движением в естественной среде- линия DARPA и шестое, супервизорное управление - линия JPO .

В соперничестве этих двух направлений зарождается концепция их объединения. Это седьмое, "смешанное управление". В этой области ведутся активные разработки военных МР в Европе [1,2] и роботов для действий в агрессивных средах в Японии [1].

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

Реализация этой идеи предполагает:

1. наличие сети подземных сейсмических датчиков для получения по колебаниям почвы предупреждения о приближении противника и распознавания типа техники (танки, джипы, артиллерия);

2. разработку системы взаимодействующих мобильных мин, способных выпрыгивать «из-под земли» и двигаться зигзагами;

3. множество небольших дистанционно-пилотируемых летательных аппаратов-камикадзе;

4. множество небольших мобильных устройств с сенсорной системой и радиусом действия в пределах 100 м, вооруженных реактивными снарядами.

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

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

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

1. системой выбора пути (на основе осмотра дальнего плана).

2. навигационной системой (которая для каждого момента движения отвечает на два вопроса «где?» и «куда?»),

3. информационным обеспечением движения по выбранному пути.

Эти три составляющие будут называться в данной работе системой информационного обеспечения распределенной мобильной системы (СИО РМС).

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

1. Как возникает несравнимость алгоритмов в условиях неопределенности? (точное определение этого понятия будет дано ниже)

2. Как может быть реализована адаптация к неизвестным заранее особенностям местности во время движения МР?

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

4. Что можно сказать о неустойчивости алгоритмов в некоторых ситуациях, когда малые вариации целевой позиции или параметров препятствий и т.п. приводят к несравнимым (например, негомотопным) путям?

5. Что может быть принято в качестве характеристик сложности среды и как эти характеристики сложности связаны с эффективностью алгоритмов выбора пути в условиях неопределенности?

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

Данная работа является обобщением и изложением с единых позиций нескольких проделанных ранее работ авторов. Она включает четыре направления исследований: обоснование алгоритмов, исследование их сравнительной эффективности в условиях неопределенности, проблему адекватной интерпретации сенсорной информации, нетрадиционные способы повышения надежности систем информационного обеспечения. Все эти проблемы плохо поддаются формализации традиционными методами и требуют новых подходов. Необходим гибкий механизм принятия решений, способный достигать цели несовершенными средствами, в мало известных и меняющихся внешних условиях. По аналогии с логикой человеческого мышления назовем такой подход логическим. Пока системы, основанные на логическом подходе такого рода, еще не созданы. Классическая дедуктивная логика не способна справиться с такой задачей. Как важный шаг в нужном направлении отметим логический подход известного отечественного логика Н.Н.Непейводы [5]. Сформулированные им методические принципы приведены в приложении 1.

1. ОСНОВНЫЕ КОНЦЕПЦИИ ЛОГИЧЕСКОГО ПОДХОДА

Рассмотрим более подробно четыре составляющие концепции логического подхода к разработке СИО:

· (1). Обоснование алгоритмов и доказательство их корректности и/или сходимости. Если предлагается алгоритм выбора пути в условиях неопределенности к целевой конфигурации РМС, то должна быть рассмотрена его сходимость и обоснованы условия применимости с данной информационной системой (ИС) сенсоров (дальномеры, телекамеры и т.п.). Если МР производит осмотр вдоль выбранного пути с целью обнаружения преодолимых препятствий (выступов, ям), то необходимо показать, что выполняются так называемые условия согласования информационно-двигательных активностей (или параметров) МР, гарантирующие обнаружение препятствий с заданными характеристиками. Здесь возникают вопросы об уровне строгости доказательства, который при некоторых условиях может препятствовать его содержательности. Подробно эти вопросы рассмотрены в [6].

· (2). Адекватность интерпретации сенсорных данных, поставляемых ИС. Решение этой проблемы позволяет организовать движение так, чтобы МР или элементы РМС не «заблудились», замечали все опасности, принимали объект А за объект А, а не за объект В и т.п. Пусть имеется два робота, P и Q, A(R,x) - описание объекта А или видимой части среды роботом R с позиции х. Тогда возможны следующие «иллюзии»:

A(P,x)=B(Q,y);

A(P,x)=B(Q,x);

A(P,x)=A(P,y).

Система так называемой интерпретирующей навигации должна быть способной разрешать подобные коллизии в рамках графа информационной эквивалентности [7].

· (3). Исследование сравнительной эффективности алгоритмов в зависимости от структурных параметров сложности среды. Здесь следует отметить одно важное обстоятельство. Обычно оценивают асимптотическую сложность алгоритма как O(P(N)), где P(N) - полиномиальная или какая-либо другая формула в зависимости от основного структурного параметра сложности задачи N. Рассмотрим, однако, пример, когда сложность алгоритма А оценивается как квадратичный полином, а сложность алгоритма В линейно зависит от параметра сложности задачи. Очевидно, что в этом случае асимптотическая сложность алгоритма А выше, чем асимптотическая сложность алгоритма В. Однако графики квадратичной и линейной зависимости наглядно демонстрируют, что может существовать конечный диапазон N, в котором алгоритм А будет эффективнее алгоритма В. В данной работе развивается альтернативный подход к оценке сложности алгоритмов, который, во-первых, позволяет с помощью кванторных приставок сравнивать классы алгоритмов, а во-вторых, составлять так называемый атлас несравнимости, в соответствии с которым любые два «разумных» алгоритма несравнимы в условиях неопределенности на множестве возможных задач [8,9].

· (4). Повышение надежности или сохранение работоспособности - «живучести» СИО. Для этих целей обычно используется «метод плавной деградации», при котором система должна оставаться эффективной при нескольких сбоях. Рассмотрим такой пример. Пусть МР оснащен лазерной ИС с дальностью действия несколько десятков метров и ультразвуковой ИС с радиусом действия несколько дециметров. В этом случае при отказе лазерной дальномерной ИС происходит отказ от алгоритмов, основанных на методе подцелей [10], и переход на алгоритмы контурного обхода или метода потенциалов ближнего действия [11-13]. Подобное переключение должно быть предусмотрено в алгоритмах выбора пути, например, с использованием экспертной схемы [14] как обобщенной схемы алгоритма.

2. ТЕРРАЙН

В простейшей модели движение РМС задается в террайне - ограниченной прямоугольной рамкой области с препятствиями, непрозрачными для измерителя и непреодолимыми для МР. Для простоты препятствия представляют собой многоугольники с углами в вершинах в 90 и 270, стороны которых параллельны граничной рамке и длина каждого отрезка принимает целочисленное значение (в соответствии с шагами по осям этой координатной системы). Подобные модели активно разрабатывались и анализировались в ИПМ [15] и других исследовательских организациях. Более сложная модель формируется в виде совокупности элементарных террайнов и классов ситуаций в них. Далее в работе рассматривается только террайн.

Отрезок [a,b] называется касательным, если: 1) он максимален для данного террайна, т.е. в направлении из a в b b является максимально удалённой видимой из a точкой (и наоборот, в направлении из b в a a является самой удаленной видимой из b точкой); 2) на интервале (a,b) есть как граничные точки, так и внутренние точки террайна.

Отрезок [c,d] называется выходным, если: 1) [c,d] строго входит в некоторый касательный отрезок; 2) c и d являются граничными точками террайна; 3) интервал (c,d) состоит только из внутренних точек террайна. Если выходной отрезок [c,d] строго входит в касательный отрезок, [a,b] а точка x расположена на этом касательном отрезке и не принадлежит указанному выходному отрезку, [c,d] называется наблюдаемым в точке x выходным отрезком.

Вершины препятствий, расположенные на интервале касательного отрезка, называются замыкающими вершинами.

Ориентация замыкающей вершины определяется тем, по какую сторону от касательного отрезка расположены содержащие замыкающую вершину граничные отрезки препятствий. Если ориентации двух замыкающих вершины, расположенных на одном касательном отрезке, различны, то на касательном отрезке имеет место ситуация типа «двойной замок». Сказанное иллюстрирует рис.1.

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

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

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

Отношение видимости является отношением толерантности, т.е. оно рефлексивно, симметрично, но в общем случае не транзитивно. Историческая справка об отношении толерантности приведена в Приложении 1.

В общем случае террайн

Ter = < V , , , ~, [...]>,

где

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

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

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

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

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

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

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

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

Справедливо

Утверждение 2.1 [15]:

(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.

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

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

3. ЯДРА И КЛАССЫ ВИДИМОСТИ

Рис. 3. Атлас классов: (a,b) - связные классы, (c,d,e) - несвязные.

Ядра и классы видимости являются основными структурными образованиями на террайне [15,16].

Ядром видимости называется максимальная область, для каждой точки которой видимая окрестность одна и та же.

Утверждение 3.1.

Если в любой точке террайна наблюдаются два выходных отрезка, которые входят в разные касательные отрезки, т.е. неколлинеарны, то в таком террайне отсутствуют нетривиальные (т.е. состоящие более чем из одной точки) ядра видимости.

Утверждение следует из теоремы, доказанной в [16], о представлении ядер видимости. Атлас возможных типов ядер видимости представлен на рис.2. Здесь изображены:

(2a): "Веер" ядер у вершины p. Каждое ядро - полуинтервал, одно из граничных точек террайна (второго типа), остальные из внутренних точек террайна (первого типа), с граничной точкой террайна- концом полуинтервала.

(2b): Ядро первого типа - интервал.

(2c): Усеченное ядро первого типа - отрезок - с граничной точкой террайна - одним из концов отрезка.

(2d): Усеченное ядро первого типа - отрезок, состоящее из внутренних точек террайна.

(2e): Невырожденное ядро второго типа, состоящее из одного или нескольких интервалов (случай несвязного ядра) граничных точек террайна.

(2f): Усеченное ядро второго типа, представляющее собой отрезок, входящий в состав граничного отрезка террайна.

(2g): Разбиение ядра второго типа из-за ситуации типа "двойной замок".

(2h): Ситуация типа "цепь": между компонентами несвязного ядра второго типа находятся ядра первого типа.

Классом видимости называется максимальная область, все точки которой видимы одна из другой. Это понятие, также как и понятие класса толерантности в общем случае [17, 18], является аналогом понятия клики на конечном графе.

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

Справедливы следующие теоремы.

Теорема 3.1. (О связных классах видимости)

Связный класс видимости является выпуклым многоугольником, или (в вырожденном случае) касательным отрезком, на котором наблюдается ситуация типа двойной замок. Если такой класс является выпуклым многоугольником, то каждая его сторона либо (а) входит в состав некоторого граничного отрезка препятствия, либо (б) на этой стороне расположены хотя бы одна замыкающая вершина, а если таких замыкающих вершин несколько, то ориентация их всех одинакова; при этом хотя бы одна сторона многоугольника удовлетворяет условию (б).

Теорема 3.2. (О несвязных классах видимости)

Несвязный класс видимости состоит из конечного числа l?3 связных непересекающихся компонент M₁,...,M_l, каждая из которых может быть либо точкой, либо отрезком, либо выпуклым многоугольником. При этом существует n?l(l-1)/2 связных классов видимости K₁,...,K_n таких, что каждая компонента M_i является пересечением m_i этих связных классов, где 2?m_i?l-1.

Рис. 3. Атлас классов: (a,b) - связные классы, (c,d,e) - несвязные.

Доказательство теорем приведено в [16]. Рис. 3,4 иллюстрируют вышесказанное. На рис.4 приведены примеры характеристик несвязного класса.

Рис. 4. (f, g, h) - иллюстрация характеристик несвязного класса:

l-число связных компонент,

n-число "образующих" классов,

- число "одиночных" компонент,

m_i - число компонент в i-ом "пучке"

Если понятие ядра видимости является более "экзотическим" (ядро видимости, как несложно заметить, имеет меру нуль, поскольку располагается на некотором касательном отрезке), то понятие класса видимости имеет более богатый спектр приложений. Покрытие террайна конечным числом классов или предклассов видимости используется для представления среды в виде графа районов [16], которые и могут выявляться на основе такого покрытия. Эти же покрытия применяются для навигационных вычислений. Наличие несвязных классов видимости свидетельствует о существовании специфической конфигурации для групп роботов, получившей в работах [16, 19] название "райского сада". Любую задачу выбора пути можно решить с точностью до класса видимости.

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

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

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

Под задачей о достижении целевой точки для одного МР понимается упорядоченная тройка 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; оно представляет собой открытую границу множества положений всех подцелей, пройденных элементами РМС к моменту n.

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

1. Организация Капитаном согласованного общего осмотра на текущих позициях и формирование текущей открытой границы dV(x₁(t_n),..,x_k(t_n))=U_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. Реализация шага элементом.

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

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

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

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

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

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

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

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

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

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

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

Рис.5 Лабиринтоподобный террайн

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

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

Теорема 4.1:

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

Следствие:

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

Теорема 4.2:

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

Следствие:

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

Подробно организация информационного обхода для РМС с малым радиусом действия информационной системы рассмотрена в [21].

5. СТРУКТУРНЫЕ ХАРАКТЕРИСТИКИ СРЕДЫ

Как уже было сказано выше, основной структурной моделью среды является магистральный граф. Террайн тоже может рассматриваться как граф с континуумом ребер и вершин.

Поэтому характеристики сложности террайна могут рассматриваться как характеристики сложности графа.

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

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

Число элементов в независимом навигационном множестве называется навигационным числом.

Нетрудно видеть, что для нетривиального террайна существуют минимальное и максимальное навигационные числа. Навигационное множество является аналогом доминирующего множества на графе, а навигационное число - аналогом числа доминирования (рис. 6).

Навигационные базисы (независимые навигационные множества)

_min=2 _max=4

Рис.6. Навигационные множества

Рассмотрим свойства магистрального графа. Порядок группы автоморфизмов этого графа является мерой его симметрии. Вместе с тем, сама группа автоморфизмов дает описание симметрии для ситуаций типа «ирония судьбы» [7]. Каждая подстановка, задающая элемент группы автоморфизма, дает описание такой ситуации ( рис. 7).

Рис 7. Пример группы автоморфизмов магистрального графа

Группа автоморфизмов порядка 8 как мера «симметрии» магистрального графа в террайне относительно ситуации типа «ирония судьбы» (повторение локального относительного описания в несвязных районах по этому описанию)

Пусть задано некоторое остовное дерево магистрального графа. Как известно, добавление к остовному дереву любого из оставшихся ребер образует фундаментальный цикл. Множество фундаментальных циклов, разумеется, зависит от выбора остовного дерева (которых может быть несколько). Однако число фундаментальных циклов постоянно, и любой цикл, не входящий в множество фундаментальных циклов для выбранного остовного дерева, может быть выражен через фундаментальные циклы с помощью операции симметричной разности a-bb-a . В реальных условиях выбор остовного дерева может быть предопределен практическими соображениями. Таким образом может быть получено базовое множество циклов данного магистрального графа и выражение произвольного цикла в рамках данного базового множества.

Цикл, как известно, - это потенциальная возможность зациклиться для алгоритма выбора пути (алгоритм без памяти, скорее всего, так и сделает) рис.8

Рис 8. Пример множества фундаментальных циклов для магистрального графа (пути в графе описываются ребрами).

Если остовное дерево есть , то множество фундаментальных циклов состоит из элементов:

Третий цикл выражается так:

Если остовное дерево есть , то множество фундаментальных циклов состоит из элементов:

Третий цикл выражается так:

Наконец, для конкретной задачи можно применить известную математическую технику [22], чтобы построить множество возможных путей. Для этого необходимо определить некоторый эталонный алгоритм выбора пути (рис.9).

Рис 9. Определение множества путей из точки в точку на основе символьных уравнений.

Задача . Индекс у наименования точки показывает значение соответствующей координаты точки: или .

Эталонный алгоритм: выбирает подцель справа (R) или слева (L) от направления на целевую точку G или же движение прямо в целевую точку (F).

Система уравнений, описывающее множество возможных путей ( - пустая цепочка символов).

Решение (множество возможных путей):

Имея оценки диаметра и навигационного числа для террайна, можно построить оценку для размерности магистрального множества[15]

6. НЕСРАВНИМОСТЬ И АДАПТАЦИЯ АЛГОРИТМОВ ВЫБОРА ПУТИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

Рассмотрим задачу достижения целевой точки g из начальной точки b на плоскости с конечным числом препятствий.

Классификация алгоритмов выбора пути в этом случае может быть проведена следующим образом. Прежде всего, мы можем различать алгоритмы с точки зрения параметров информационной системы МР. Выделим два крайних класса: V-алгоритмы и C-алгоритмы. В случае V-алгоритмов для МР доступна информация о любой точке в видимой окрестности текущего положения МР, и он может двигаться до любой точки видимой окрестности (т.е. предполагается, что МР располагает идеальными информационной и двигательной системами). В случае C-алгоритмов радиус действия информационной системы МР равен "нулю" и МР может осуществлять только две операции: двигаться в направлении к целевой точке (если это возможно) и обходить препятствие по его границе.

Предположим, что следующая подцель для V-алгоритма после сканирования МР местности и принятия решения о движении может быть только вершиной препятствия; а точка "схода" для C-алгоритма (т.е. точка, где МР меняет способ движения с обхода препятствия на движение к точке цели) также является вершиной препятствия.

Возможные точки "схода" и "захода" на препятствие для конкретного C-алгоритма мы можем рассматривать как возможные подцели движения, так же как и вершины препятствий для V-алгоритмов. Таким образом, путь, продуцируемый V- или С-алгоритмом, представляет собой ломаную. Большинство из известных и неизвестных V- и C-алгоритмов (в соответствии с приведенными выше предположениями) может быть представлено в виде следующей схемы из четырех пунктов:

1. Сканирование среды и выбор возможных подцелей для V-алгоритма (для C-алгоритма - переход от одного способа передвижения к другому в точках "схода" и "захода"). Всем новым подцелям присвоить признак «открыта».

2. Выбор вершины на пройденном пути, которая отмечена признаком "открыта" для следующей попытки движения в неизвестный район местности через некоторую (фиксированную ранее) подцель;

3. Если эта вершина не текущая, то осуществить в нее возврат.

4.Осуществление движения в неизвестный район местности; если эта попытка окончилась неудачно, то пометить эту вершину пути (или подцель) признаком "закрыта" и переход к шагу 2, иначе переход к шагу 1. Остановка, если целевая точка достигнута.

Каждый алгоритм можно характеризовать некоторой структурной формулой, которая определяет класс алгоритма. В простейшем случае имеется две формулы: V и C. V-алгоритм может быть охарактеризован также оценочной функцией для подцелей f. Функция f может быть составлена на основе оценки расстояний с помощью функций, аналогичных g и h функциям для поиска пути минимальной длины на графе [23]. Предположим, что - расстояние от подцели до целевой точки, - расстояние от текущей (не начальной - в отличие от поиска по априорно известному графу!) позиции МР до подцели. Тогда можно рассматривать такие функции f как f=, f=+, f= (+) и т.п. В структурной формуле V- алгоритма оценочная функция является вторым элементом. Тогда "естественный" V-алгоритм может быть представлен формулой V(+). В случае C-алгоритма мы можем фиксировать направление движения по границе препятствия при его обходе после первой точки "захода". Положив =+ (против часовой стрелки) и = (по часовой стрелке), получим формулы C+,C-,C (в последнем случае фиксировано, но его знак не имеет значения).

Еще одно предположение относительно C-алгоритмов заключается в следующем. После того, как МР осуществил контакт с первым встречным препятствием на точке "захода" и начал его обход по контуру, он покидает его с первой возможной точки схода, которая обязательно является вершиной препятствия.

Пусть существует базовое множество известных алгоритмов выбора пути А и множество возможных задач М. Каждая задача из М характеризуется картой препятствий, а также стартовой и целевой точками. Множество М теперь мы можем характеризовать целочисленной величиной N, которая равна максимальной длине стороны минимальной рамки, в которую может быть помещен каждый элемент из М. Число N мы будем называть "уровнем разнообразия террайна". Мы предполагаем, что каждый алгоритм из А является допустимым, т.е., для каждой задачи для любого фиксированного N он продуцирует путь от начальной до целевой точки (в предположении, что такой путь существует).

В этих предположениях продемонстрируем эффект несравнимости алгоритмов в условиях неопределенности. Эффект возникает, когда базовое множество алгоритмов А и местность достаточно разнообразны. Тогда можно показать, что не существует оптимального алгоритма для любого множества (А,М), т.е., невозможно найти алгоритм a, который продуцирует более короткий (или равный) путь, чем любой алгоритм из А на любой задаче из М. Этот факт приводит нас к необходимости хранить и использовать все несравнимые (на множестве М) алгоритмы из А (или вообще считать, что А состоит из несравнимых на М алгоритмов). Сформулируем соответствующую теорему[8].

Теорема 6.1. Если в состав базового множества алгоритмов А входят два алгоритма со структурными формулами V(+) и C, и М состоит из всех возможных элементов с уровнем разнообразия местности большим, чем 5, то не существует оптимального алгоритма для пары (А,М).

Символ, название ситуации	Типичная конфигурация	Комментарий	Эффект
(g) “H” "H+" "H-” Весы		ЧД - преобразование перемещает невидимую из S "дверь" BD -"стрелку весов” - в разные стороны относительно начальной линии цели, «закрывая» один из опорных путей достижения цели, которые инициируются двумя видимыми подцелями х2 и х7; равенства оценки + для подцелей не наблюдается.	В случае "Н+" ("дверь" BD занимает положение [у2,х4], обход справа) V(+) доминирует над любым С. В случае "Н-" (BD = [х7,у4]) С доминирует над любым "нормальным" V - алгоритмом. Отсюда следует отсутствие строго оптимального алгоритма, доминирующего и в "Н+" и в "Н-" над обоими типами алгоритмов.
	“H+”, “H-” (V,C-)=? S=(5,1) *=(6,3)

Рис. 10 Атлас особых ситуаций. «Весы»

Доказательство очевидно из рис.10, который представляет ситуацию "весы". М состоит из двух задач, для каждой задачи Ter состоит из одного препятствия, которое определяется двумя горизонтальными и одним вертикальным отрезками. Горизонтальные отрезки имеют постоянную длину, а вертикальный отрезок - "стрелка весов" может передвигаться и "закрывать" путь к целевой точке с одной из сторон (справа или слева). Очевидно, что для одной из задач более короткий путь продуцируется алгоритмом V(+h), а для другого- C+-алгоритмом. Однако видимая окрестность в начальной позиции одинакова для обоих случаев, и отсюда следует отсутствие алгоритма а, который оптимален для (А,М).

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

ЗАКЛЮЧЕНИЕ

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

теория террайнов как метрических толерантных пространств;

понятие класса и ядра видимости;

теоремы о сходимости алгоритмов выбора пути к целевой конфигурации;

теоремы о сходимости алгоритмов решения задачи информационного обхода;

несравнимость по эффективности алгоритмов выбора пути в условиях неопределенности на множестве возможных задач

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

ПРИЛОЖЕНИЕ 1. НЕКОТОРЫЕ ПОСТУЛАТЫ ЛОГИЧЕСКОГО ПОДХОДА Н.Н. НЕПЕЙВОДЫ

Приводимый ниже текст является цитатой из работы [5] и приводится для ознакомления с идеями известного логика. Не следует искать прямых аналогий этим принципам в данной работе, их влияние скорее нужно считать опосредованным и косвенным. Однако результаты данной работы могут служить иллюстративным примером цитируемых положений автора.

Начало цитаты

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

Сначала будут сформулированы базисные принципы, а потом некоторые производные от них.

Принцип 1 (принцип четырех вопросов). Прежде чем начать действовать, необходимо задать себе четыре главных вопроса:

зачем все делается, что мы имеем, чем мы можем воспользоваться, чтобы достичь цели, как обеспечить согласованность средств и цели?

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

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

Принцип 4 (принцип превращения недостатков в достоинства). Недостатки формализма являются потенциальными достоинствами, если их правильно использовать.

Принцип 5 (принцип реализма). Все время необходимо принимать во внимание средства, ресурсы, потребные для реализации планов.

Принцип 6 (принцип. антиуниверсализма). Универсальные методы -- это такие специализированные методы, создатели которых не дали себе труда подумать, для каких конкретных задач они годятся.

Принцип 1 является центральным в логической структуре нашего подхода. Часто принципиальные ошибки объясняются тем, что один из этих четырех вопросов не был задан. Обыкновенно стремятся как можно быстрее поставить вопрос «как?», совершенно не разобравшись, зачем все это нужно. Такая торопливость приводит к принципиально неправильной постановке задачи, например вместо задачи повышения надежности программ ставится задача доказательства правильности программ, а ведь даже формальное доказательство правильности совершенно не гарантирует работоспособности программы в реальной обстановке.

Не знать, что уже имеется, что же дано,-- также один из типичных грехов. И уж совсем часто для достижения цели используются такие средства, которые либо начисто уничтожают ожидавшийся позитивный эффект достигнутой цели, либо отягощают его во много раз худшими Отдаленными последствиями. Азбучной является и ошибка -- начинать действовать, не разобравшись, как же надо действовать.

Из принципа четырех вопросов следует.

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

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

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

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

Знаменитая теорема Геделя показывает, что стремление достичь полной формализации несколько наивно даже в столь упорядоченной области человеческих знаний, как математика. А когда мы сталкиваемся с практическими задачами, мы попадаем в стихию откровенно неформалпзуемых понятий, каждая попытка точного определения, формализации которых заведомо искажает их смысл. (Что такое, например, удобная в пользовании система?) И тем не менее работать с такими понятиями необходимо, и жизнь заставляет работать с ними точно. А раз никакой отдельный формализм не может охватить всей глубины даже самых элементарных человеческих понятий, так почему же не описывать такие понятия системой заведомо несовместимых, противоречащих друг другу формализаций (см. теорию неформализуемых понятий). Но тогда каждая из этих формализаций заведомо является неправильной, и ориентироваться в этом «темном лесу» помогут лишь чувство юмора и здравый смысл, которые неотделимы друг от друга. Именно они позволяют уловить момент, когда нельзя больше пользоваться некоторой формализацией и пора переходить к другой.