ТЕХНОЛОГИИ “ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ“ И “ВИРТУАЛЬНАЯ РЕАЛЬНОСТЬ” В СИСТЕМАХ АВТОНОМНОЙ НАВИГАЦИИ
Канд. физ.-мат. наук В.О.Афанасьев, канд. техн. наук В.И.Алешин,
доктор техн. наук В.Н.Почукаев
Центр управления полетами и моделирования
г. Королев Московской области.

Доктор физ.-мат.наук А.Н.Томилин
Институт системного программирования РАН
г. Москва.



В работе изложен концептуальный подход к построению системы управления движением объектов в условиях высокого риска и высокой цены риска (космических аппаратов и орбитальных станций), которая должна содержать компоненты, использующие возможности Искусственного Интеллекта и Виртуальной реальности.
В алгоритмах управления предлагается использовать априорную информацию о внешней поверхности объектов и окружающей среды в виде виртуальных трехмерных моделей. Такой подход в принципе дает возможность осуществлять в реальном времени реконструкцию взаимного положения всех точек моделей поверхностей на основе слежения за опорными точками, связанными с системами координат управляемых объектов, и более точно контролировать и управлять движением объектов. Предлагаемый подход позволяет создавать принципиально новые алгоритмы и системы управления, применимые в бортовых системах автономной навигации космических аппаратов, функционирующих на расстояниях, соизмеримых с их габаритами.
Данная работа проводится при непосредственной финансовой поддержке Российского фонда фундаментальных исследований (грант № 99-01-00202).

Математическое обеспечение существующих систем автономной навигации, как правило, строится на основе моделей движения объектов, в которых сами объекты описываются как материальные точки. Размеры и форма управляемых объектов не учитываются, если достаточно велики расстояния между объектами и величины их перемещений за характерное время. Однако если управляемые объекты находятся друг от друга на расстояниях, соизмеримых с их габаритами, размеры и форма объектов могут оказаться решающими.
Современные и перспективные долговременные орбитальные станции, такие как “Мир” и МКС имеют сложную пространственную конфигурацию, для которой характерно расположение крупногабаритных, протяженных фрагментов вдоль нескольких пространственных осей. Такие конструкции можно назвать сильно разветвленными, сравнивая их с космическими аппаратами, которые в этом контексте можно считать “компактными”. Движение и управление движением вблизи центра масс сильно разветвленных КА сопряжено с большим риском и высокой ценой риска столкновений фрагментов конструкций КА. Во избежание таких столкновений фактически требуется одновременное слежение за взаимным расположением и параметрами движения большого числа точек, относимых к конструкциям КА.
Оценка роста сложности задачи слежения за поведением двух объектов по отношению к задаче для центров масс дает величину n2 (n – число точек, выделенных для одного объекта) и, на первый взгляд, такой подход заведомо бесперспективен для значений n, полезных для практики. Однако возможности появившихся в последние годы информационных технологий позволяют использовать принципиально новые подходы как к постановке, так и к решению задачи одновременного слежения за большим числом точек, число которых для каждого объекта на сегодняшний день может составлять 107 – 108 (если использовать новые возможности). В первую очередь, речь идет о возможностях технологии “Виртуальная реальность”, и, в частности, о таких задачах, как “Перехват движений (Motion Capture) и “Анализ Столкновений” (Collision Detection, Interference Detection), на основе которых авторами предлагается подход к построению системы управления движением объектов сложной пространственной формы в условиях опасности столкновений.
Предпосылками предлагаемого подхода к постановке задачи управления являются три следующих концептуальных положения.
1. Для описания моделей объектов управления используется вся доступная априорная информация о пространственной форме внешней поверхности КА. Такая информация может быть представлена массивом координат узлов трехмерной сетки (может быть очень большой размерности), аппроксимирующей поверхности объектов с заданной точностью.
2. Для слежения за поведением объектов управления используется небольшое число опорных точек. Из общих соображений следует, что для определения положения и ориентации жестких объектов, минимальное число таких точек – три. Введение четвертой опорной точки уже позволяет оценивать статистические параметры погрешности слежения, в частности, могут быть решены задачи идентификации координат и параметров движения по схеме Гаусса-Маркова, фильтра Каллмана и т.д.
3. Для оценки взаимного положения поверхностей объектов, анализа развития ситуации, принятия решений и т.п. используется трехмерное виртуальное пространство, в котором движение управляемых реальных объектов отображается путем моделирования движения их трехмерных сеточных моделей. При этом оперативно анализируется взаимное расположение узлов поверхностей объектов.
Следует подробнее пояснить положения 2 и 3 и их взаимосвязь. В частности, важно, что опорные точки трехмерной модели поверхности объекта, за которыми осуществляется слежение, не обязательно должны принадлежать самой поверхности объекта (желательно даже, чтобы они отстояли от поверхности как можно дальше). Существенно лишь то, что эти точки детерминировано связаны с поверхностью, и по их координатам могут быть однозначно восстановлены координаты всех точек поверхности. Таким образом, слежение за объектом управления и оценка состояния объекта управления осуществляются принципиально в разных пространствах. Эти два пространства можно считать сопряженными относительно функционала, задающего связи между опорными точками и точками поверхности.
Виртуальное 3D-пространство, в котором производится оценка состояния управляемой системы (взаимного положения объектов управления), в данном случае можно трактовать как носитель обратной связи. Таким образом, традиционные винеровские понятие и модель обратной связи расширяются, и просматриваются новые подходы к решению задач управления.
Например, несколько необычным способом может быть поставлена и решена задача прицеливания (при стыковке, посадке и т.п.). В обычной постановке задачи для минимизации координатной невязки между исполнительным органом и мишенью необходимо непосредственное наблюдение мишени (обратная связь осуществляется внутри того же пространства, где производятся наблюдения). Если по каким-то причинам условия наблюдения не позволяют определить координаты (проекции координат) мишени, задача прицеливания, сопровождения цели и т.д. может стать невыполнимой. В предлагаемой постановке без ущерба для выполнения основной задачи мишень может быть вообще вне поля видимости (скрыта фрагментами конструкции, препятствиями и т.п.), так как наблюдение ведется не за мишенью непосредственно, а за опорными точками (они могут находиться на большом удалении от мишени). Далее в виртуальном пространстве могут быть с высокой точностью восстановлены координаты мишени (по функционалу связи с опорными точками) и, соответственно, минимизирована невязка между координатами мишени и исполнительного органа.
Основные компоненты системы
Попытаемся в общих чертах обрисовать облик прототипа системы управления, не вникая в подробности технической реализации, и остановившись лишь на основных функциях такой системы. Это можно сделать, опираясь на указанные выше концептуальные положения.
Система должна включать в себя следующие основные функциональные подсистемы:
- подсистема трехмерных моделей поверхностей управляемых объектов (в простейшем случае – это набор массивов трехмерных координат узлов сеток, аппроксимирующих поверхности объектов);
- подсистема слежения за детерминированными опорными точками, жестко связанными с системой координат контролируемого объекта (сенсорная система);
- подсистема анализа состояния, развития ситуации.
Опишем некоторые особенности реализации перечисленных подсистем, отметив попутно, что в таком сочетании эти подсистемы часто рассматривают в контексте системы Искусственного Интеллекта (ИИ). Причем в данной постановке, похоже, наконец, проясняется, каким образом может быть устроена “внутренняя модель внешнего мира”, являвшаяся предметом дискуссий в области ИИ в 60-70-х годах прошлого века.

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

Подсистема слежения за опорными точками.
Существует множество различных подходов к созданию и способов реализации систем технического зрения, которые позволяют извлекать необходимую информацию из проекций изображений трехмерной среды. Вместе с тем, точки зрения предлагаемого подхода, большинство этих систем обладают избыточностью, поскольку значительный (если не основной) объем релевантной информации о наблюдаемой сцене уже содержится в моделях поверхностей наблюдаемых объектов. Объем данных, которые в действительности должна регистрировать следящая система, могут быть радикально понижены, а алгоритмы обработки этих данных сильно упрощены, поскольку необходимо лишь реконструировать пространственные координаты очень ограниченного набора точек (можно считать их маяками или мишенями). В качестве прототипа такой системы можно рассматривать систему перехвата движений, которая используется в технологии “Виртуальная Реальность” для анимации виртуальных актеров.
Заметим, что система слежения за опорными точками может быть пространственно распределенной. В этом заключается ее принципиальное отличие от зрительной системы в традиционном понимании (это относится, в том числе, и к системам технического зрения). Для “обычных” зрительных систем характерны компактная компоновка проекционной (или фасеточной) системы и обработка двумерного изображения проекции сцены, включающая фильтрацию, выделение характерных фрагментов, контуров и т.п. (решаются задачи распознавания образов). В предлагаемой системе вообще отсутствует концепция изображения в традиционном понимании, поскольку в этом нет необходимости. Для реконструкции трехмерной сцены, в которой участвуют объекты, с достаточной точностью представляемые массивами трехмерных координат точек своих поверхностей, достаточно восстановить пространственные параметры связанных систем координат этих объектов. В свою очередь, для восстановления параметров системы координат необходимо знание координат трех некомпланарных точек, или координат вершин симплекса (если ставится задача оценивания, как отмечалось выше).
Для восстановления пространственных координат опорных точек могут использоваться методы обработки двумерных изображений проекций этих точек. Заметим только, что для этой цели нет необходимости привлечения концепции распознавания образов. Более того, алгоритмы восстановления могут быть элементарными, если опорные точки удается сделать автодетерминированными [1] (например, для их кодирования можно применить цвет и т.п.).
Следует отметить, что при реконструкции трехмерной сцены по опорным точкам, связанным с объектами (в особенности при оценке точности такой реконструкции), в принципе, могут возникнуть проблемы, обусловленные свойствами функционала связи опорных точек и узлов сетки. Здесь, возможно, потребуются дополнительные исследования, но сразу же можно заметить следующее. В силу конечности отображаемых множеств и “хороших” свойств норм рассматриваемых пространств (размеры объектов ограничены, число опорных точек и узлов сетки также ограничены), эти проблемы будут связаны, в основном, со свойствами информационных матриц. Для их решения существуют достаточно мощные средства теории планирования эксперимента [2].

Подсистема анализа и принятия решений.
Основная задача, которую должна решать эта подсистема – оперативный анализ взаимного расположения узлов сеток, аппроксимирующих поверхности объектов. Данная задача является одной из компонент систем виртуальной реальности, а соответствующие направления исследований, как уже отмечалось выше, известны под названиями “Collision Detection” и “Interference Detection” (в кратком переводе - “Анализ Столкновений”). Характерными значениями порядков сеточных описаний поверхностей в задачах анализа столкновений на сегодняшний день являются 107 - 108 .Это типовая трехмерная сцена средней сложности, обрабатываемая трехмерным геометрическим ускорителем “бюджетного класса” в реальном времени.
В системах ВР моделируемые объекты (точнее, поверхности объектов) чаще всего существуют независимо от своих реальных прототипов. Задача актуализации виртуальных моделей в “обычных” системах ВР не ставится (авторам не известны публикации или сообщения на эту тему). Обычно системы ВР используются для отображения процессов моделирования. Даже с появлением и развитием интерфейса слежения за движениями (Motion Capture) данные о движении реальных объектов и их составных частей используются, как правило, в режиме “off-line” – записываются в базу данных, откуда извлекаются позднее для анимации виртуальных актеров. Тем не менее, инструментарий, разработанный за последние годы для решения задачи анализа столкновений, заслуживает внимания, поскольку созданные методы, алгоритмы и подходы рассчитаны на применение в достаточно жестких временных рамках – результат должен быть получен в течение сотых долей секунды (внутри паузы обратного хода луча развертки).
Проблема анализа столкновений изучается уже достаточно длительное время (не менее 5-7 лет), и к настоящему моменту сложился достаточно широкий круг алгоритмов для решения данной задачи. В основном все существующие подходы основаны на попарном анализе взаимного расположения всех объектов сцены (рассматриваются все пары участвующих объектов, то есть задача решается “в лоб”). Для сокращения числа анализируемых пар узлов сеток используются разнообразные методы сужения множеств таких пар путем отсева подмножеств пар, которые заведомо можно не рассматривать.
Методы отсева базируются на упрощенном анализе взаимного расположения фрагментов сетки, заключенных внутри многогранников с небольшим числом вершин. Фактически рассматриваются пары не фрагментов сеток (которые могут содержать достаточно большое число узлов), а пары ограничивающих эти фрагменты многогранников с очень малым числом узлов (например, параллелепипедов). Борьба за быстродействие идет, в частности, в направлении выбора способа разбиения объема, внутри которого содержится модель поверхности объекта. Такое разбиение можно выполнить не только статически (заранее), но и динамически, рекурсивно (по мере получения результатов расположения объемлющих ограничивающих объемов).
Среди наиболее известных методов разбиения объемов следует упомянуть такие, как бинарные деревья, актантные деревья, деревья из ограничивающих объемов различной формы: сферические, полигональные, с выравниванием граней вдоль координатных осей или вдоль осей объектов и т.д. Одним из перспективных для предлагаемой постановки задачи является метод деревьев из ориентированных ограничивающих объемов (ОВВ [3]), позволяющий с высокой скоростью анализировать объекты сложной формы на близких расстояниях (соизмеримых с их габаритами).

В заключение коснемся некоторых аспектов реализации предложенной концепции системы. В первую очередь следует отметить, что еще 10 лет назад описанная постановка задачи управления не имела бы под собой реальной технической базы. На первую половину 2000-го года корпорация Intel анонсировала серийный выпуск микропроцессора Pentium-III со средней производительностью 6 Гфлопс (6 миллиардов операций с плавающей точкой в секунду). Напомним, что в середине 90-х нижней границей производительности супер-ЭВМ была величина 1 Гфлопс (Pentium III - “обычный” микропроцессор). Похожая ситуация и с объемами оперативной памяти – с начала 1999 года серийно выпускаются системные платы, рассчитанные на установку “в железе” до 1 Гбайта оперативной памяти. Бортовая вычислительная система, построенная на основе компонент с указанными параметрами, способна в реальном времени эффективно справиться с решением описанных выше задач.
Следует также упомянуть интересную задачу, возложенную на экипаж МТКК “Endeavour” в феврале 2000 года, – сканирование рельефа земной поверхности радиоинтерферометром с длиной базы около 60 метров (на длинах волн 5.6 и 3.1 см). Сканированию была подвергнута полоса земного шара между 60 градусом северной и 55 градусом южной широты, а суммарный объем полученных данных составил около 10 Терабайт. Полученное в данной экспедиции разрешение пока что не очень высоко (около 30 метров по высоте и 15-20 метров вдоль поверхности). Важно, что высокоточная 3D-модель всей земной поверхности, которая будет получена NASA в недалекой перспективе, затем может быть использована для решения любых задач, требующих детального знания рельефа в любом заданном районе земного шара.
ЛИТЕРАТУРА
1. В.А.Князь, А.В.Сибиряков. Бесконтактное построение 3D-моделей реальных объектов методами короткобазисной фотограмметрии на основе использования кодированных меток.– В сб.: 8-я Международная конференция по компьютерной графике и визуализации. Графикон-98. 7-11 сентября 1998 года. Москва, Россия. Труды конференции. Изд-во МГУ им. М.В.Ломоносова, 1998.
2. Математическая теория планирования эксперимента./ Под ред. С.М.Ермакова.– М.: Наука.1983.
3. S.Gottschalk, M.C.Lin and D.Manocha. OBBTree: A hierarchical structure for rapid interference detection, Department of Computer Science, UNC Chapel Hill, 1996.