1
Российская Академия Наук
ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ
им. М.В. Келдыша
А.К. Платонов, Е.Ю.Зуева, А.А. Кирильченко, С.М.Соколов
ЛОГИЧЕСКИЙ ПОДХОД К ПРОЕКТИРОВАНИЮ АЛГОРИТМОВ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ МОБИЛЬНЫХ СИСТЕМ. ОСНОВНЫЕ ПОНЯТИЯ
Москва, 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] как обобщенной схемы алгоритма.