Институт прикладной математики и механики НАН Украины, г. Донецк, Украина

«Искусственный интеллект» 4’2008

С.В. Сапунов

    Определение положения мобильного робота в топологической среде

Аннотация

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

УДК 519.7

        Задачи организации двигательного поведения или навигации автономных мобильных роботов являются одними из основных задач искусственного интеллекта [1]. Целенаправленное автономное передвижение робота в его операционной среде невозможно без формирования достаточно полной ее модели (карты среды). К моделированию таких сред определилось два подхода: метрический, использующий геометрические свойства среды, и топологический, использующий описания связей между различными областями среды [2]. Топологические модели представляют собой ориентированные или неориентированные графы с размеченными различными способами вершинами и/или дугами [3]. Фундаментальной проблемой навигации является самостоятельное определение (диагностика) роботом своих координат (robot self location). Задача диагностики положения робота формулируется следующим образом: робот, обладая картой среды (помеченным графом), должен установить соответствие между вершиной на карте и неизвестной ему априори областью среды, в которой он был первоначально установлен [3].
        В данной работе в качестве топологической модели операционной среды рассматриваются конечные ориентированные графы с помеченными вершинами. Теоретическая важность и актуальность работы определяются тем, что анализ графов проводится методами, аналогичными методам теории автоматов. Эти методы эффективно распространяются на графовые системы, неявляющиеся конечными автоматами, но являющиеся в некотором смысле автоматоподобными системами.

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

Постановка задачи

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

Основные определения

Конечным ориентированным графом с помеченными вершинами (помеченным орграфом) назовем четверку G = (G,E(g),M, /и), где G - конечное множество вер­шин, \G\ = п, E(G)с: G x G - конечное множество ребер, М- конечное множество меток, М= т, ц:С^-М – сюръективная функция разметки. Последовательность меток вершин w = (и (g1)... и, gk ), соответствующую некоторому пути g1...gk в графе G, назовем словом длины к, порожденным вершиной g1. Обозначим через М+ множество всех непустых слов в алфавите М. Языком Lg вершины g назовем множество всех слов,порожденных этой вершиной. Введем частичную операцию * : GxM+ —» 2° соотно­шением: для любой вершины gsG и любого слова wgM+ через g*w обозначим множество всех вершин h g G, таких, что существует путь из g в h помеченный словом w . Для слов u,w gM+ введем их композицию u°w, равную tiw', если и =и'х, w = xwr, хеМ, и не определено в противном случае. Помеченный орграф G назо­вем детерминированным орграфом или D-орграфом, если для любой вершины g gG и любых вершин s,t sTg из s Ф t следует, что u(s)^ ,u(t) (здесь Tg - множество всех вершин, являющихся концами дуг, исходящих из g). В противном случае G назовем ND-орграфом. Простой D-орграф G, для которого выполняются следующие ограни­чения: 1) для любых вершин g,hsG если (g,h)e E(G), то (г,g)e E(G); 2) для любой вершины gsG и любых вершин s,tGOtg из s^t следует, что u(s)^ u(t) (здесь Oig= Tg ^{g}), назовем сильно детерминированным или SD-графом. Будем говорить, что вершины g,hsG неотличимы, и писать (g,h)e а, если Lg = Lh. Отношение а рефлексивно, симметрично и транзитивно, т.е. является эквивалентностью. Идентификатором вершины gsG назовем конечное множество слов Wg cM+, такое, что для любой вершины h e G равенство Wg c\ Lg =Wg c\ Lh выполняется тогда и только тогда, когда g = h. Всякий идентификатор Wg можно представить как объе­динение Wg ^j Wg двух множеств Wg =Wgc\Lg и W~=Wg-Lg. Идентификатор Wg назовем позитивным, если W~= 0, и негативным, если Wg = 0 . Детально иденти­фикаторы рассматриваются в [4]. Каждому   графу   G = (G,E(G),M,/ug)   поставим   в   соответствие   граф   пар D(g) = [D, E(p),M, /uD ), построенный следующим образом. Сначала определим множест­во D по правилу: (S,Q) g D точно тогда, когда S,Q g 2g , S ^Q ^ 0 и \/uG(S ^Q) = 1. При этом полагаем, что uD (S, Q) = fiG(S<jQ). Затем множество Д пополним т экземп­лярами пар (0,0), при этом их метки попарно различны. Полученное семейство пар образует «множество» вершин D графа пар. Из вершины (S,Q) с меткой х исходит дуга в вершину (S',Q) с меткой у точно тогда, когда S' = S *ху и Q' = Q*xy . Деталь­но граф пар и его настройки рассматриваются в [5].

Эксперименты с помеченными графами

        Экспериментом с графом G относительно априорной информации I и цели C с использованием средств S назовем процесс, состоящий из трех этапов. Этап 1: пост-см на основе априорной информации I и с учетом цели C . Этап 2: получение порождаемых тестом Р с использованием средств S экспериментальных данных W. Этап 3: вывод заключений о свойствах графа G на основе эксперимен­тальных данных W и априорной информации I.

        Определяющими при проведении эксперимента являются следующие факторы: свойства исследуемого графа; способ получения экспериментальных данных; цель эксперимента; априорная информация об исследуемом графе; способ вывода заклю­чений. Априорная информация об исследуемом графе – это класс графов, к которому принадлежит исследуемый. Этот класс может задаваться явно (перечислением графов), способом порождения его элементов из некоторого графа-эталона, набором свойств и параметров. Основное отличие экспериментов с графами от экспериментов с автоматами сос­тоит в методах и средствах S получения экспериментальных данных. Под средствами экспериментирования с графом мы будем подразумевать мобильных агентов (МА), блуждающих по графу и воспринимающих некоторую локальную информацию об окрестностях его вершин. В зависимости от априорной информации о графе, МА могут быть добавлены дополнительные возможности по распознаванию графа, такие как камни [6] или маркеры [7].

        Эксперимент назовем диагностическим, если априори полностью известен граф G и МА установлен в произвольную начальную вершину этого графа, а целью экспе­римента является определение этой вершины, то есть отличение начальной вершины от всех других вершин. Допуская вольность речи, множество W также будем называть экспериментом с графом G. В этом смысле можно сказать, что эксперимент W по­рождается тестом Р. Тесты, порождающие эксперименты, будем также называть диагностическими. Будем рассматривать следующие меры сложности экспериментов. Высотой теста Р назовем величину max d(w) , кратностью Р – величину \Р\, объемом Р – величину d{w). wgP Будем также рассматривать сложность построения теста и сложность проведения эксперимента. Под сложностью проведения эксперимента будем понимать его опера­ционные кратность и высоту. Операционной кратностью эксперимента назовем величину, равную, в зависимости от способа проведения эксперимента, либо количеству экземп­ляров МА, использованных при получении порожденных тестом Р эксперименталь­ных данных W, либо количеству установок МА экспериментатором в начальную вершину исследуемого графа. Если используется только один экземпляр МА (одна установка), то эксперимент назовем простым. Операционной высотой эксперимента назовем наибольшую из длин путей, которые проходит каждый экземпляр МА по исследуемому графу в ходе эксперимента (в работах Г. Дудека [3] аналогичный параметр назван механической сложностью).

Диагностические эксперименты

        Из определения диагностического эксперимента следует, что он осуществля­ется посредством прохождения МА некоторого связанного с тестом Р множества путей по графу G из вершины g. Будем полагать, что, находясь в любой вершине  g^G, МА воспринимает множество слов Ob+(h) = Mk ^Lh, где Мк сМ+ явля­ется множеством всех слов длины не больше к в алфавите меток М, и вычисляет множество слов Ob (h) = Мк -Lh= Mk - Ob+ (h). При к = 1 полагаем, что МА восприни­мает только метку текущей вершины. Таким образом, проходя путь g1...gl в графе G, МА воспринимает множество слов Ob+ (g1... gn) = ^J \^i{g1)... /uyg,)° Ob+ (gj ) и вычислить z=1 ляет множество слов Ob~{g1 ...gl) = 1. В дальнейшем, если не оговорено противное, будем считать, что к = 2 . Пусть w еМ+. Обозначим через S (w) множество всех путей из вершины g, которые помечены словом w . По произвольному множеству Р сМ+ и g e G постро­им пару Wg = (Wg ,Wg), где Wg = N^ Vgv^ и Wg = U^ D14, а И является lang="EN-US">we[p] we[p] замыканием множества P по всем непустым начальным отрезкам слов из Р . Экспери­ментом W с графом G, порожденным тестом Р, назовем семейство Wg . Экспе­римент W назовем диагностическим точно тогда, когда для любых вершин g,hsG из gФh вытекает Wg^Wh, то есть Wg ФW^ или Wg ФWh . В этом случае тест Р к g gGG также назовем диагностическим. Очевидно, что если граф G не приведен, то диаг­ностический эксперимент с ним невозможен. Действительно, если ( g, h) e а , то вер­шины g,hsG по определению неотличимы никаким словом из М+. Если граф G приведен, то существует к такое, что Lkg Ф Lkh для всех g^ h, g,h^G . Тогда Р =L является диагностическим тестом для G, поскольку порожденный Р эксперимент W является диагностическим экспериментом с графом G, так как W c\Lg ^W  ^Lh, то есть Wg ФWh для всех g^h. Поэтому в дальнейшем, если не оговорено против­ное, будем считать, что все рассматриваемые графы приведены. Следующая теорема описывает класс диагностических тестов, определяемых иден­тификаторами вершин графа G. Рассмотрим множество слов Р = И     Wg , где Wg является некоторым идентификатором вершины g e G. Очевидно, что для любых различных вершин g, hsG выполняется Р^Lg ФРc\Lh. Действительно, так как Wg с: Р, то по определению идентификатора Wg c\ Lg Ф Wg c\ Lh, а следовательно, Р   ^Lg Ф Р c\Lh. Таким образом, справедливо следующее утверждение. Теорема 1. Множество слов Р = I I Wa является диагностическим тестом для графа G при любом семействе идентификаторов W *& *g^g Эта теорема дает метод построения диагностических тестов для помеченных гра­фов различных типов. Опишем подробно каждый этап диагностического эксперимента. Для построения теста Р воспользуемся настроенным графом пар (Dj,(G),Z)/,Z)f) [5], у которого множество Dj состоит из всех вершин (g,Q)G, где g^G, \g^Q и |<2|<1, а множество Df состоит из всех вершин (S',Q')gD1 , где  S' = 0 или Q' = 0 . Ясно, что I Dj I = 0\п2, £)гсД и I Z>r| = 0(22"). Для каждой вер­шины  найдем кратчайшее слово w, такое, что gDf . Ясно, что множество Р таких слов, выбранных по одному для каждой вершины из Dt, явля­ется объединением идентификаторов всех вершин графа G и по теореме 1 является диагностическим тестом для этого графа. Очевидно, что кратность теста Р равна 0\п2, его высота не превосходит 22п [8], а его объем равен 0\п222п. Для построения теста Р достаточно (при использовании известных алгоритмов обхода графа [8]) 0\п224п шагов. Для построенного теста Р с каждой вершиной g gG свяжем его разбиение 7i\g на два класса Р^ = Р  и Р~ = Р – Ln. Ясно, что для построения семейства g  n  V \0/7gECj достаточно 0\п324п шагов. Далее МА помещается в произвольную неизвестную ему вершину h графа G. Целью второго этапа эксперимента является построение раз­биения n\h) путем перемещения МА по графу G . Полагаем вначале, что Р^ = 0 и Ph = 0. МА считывает метку (луп) и строит разбиение теста Р на классы Р' =( {w | w = /луп) °w) и Р" = Р – Р'. Если Р' = 0, то искомое разбиение (пуп) найдено и Р^ = 0, а Ph = Р. В противном случае, пока Р' Ф 0 , МА произвольно выбирает слово w g Р' и последовательно для каждого начального отрезка wi слова w, где / пробегает все значения от 1 до d(w), проверяет наличие пути в графе G с меткой wt, исходящего из h. Если такой путь существует, то МА вычисляет Ob(h*wi) и все слова v g P', для которых некоторое слово из множества wt ° Ob (h * wt) является начальным отрезком слова v, помещает вР'и удаляет из Р'. Если при этом началь­ный отрезок wi+1 слова w находится в wt oOb(h*wi), то слово w удаляется из Р', помещается в Р" и его исследование оканчивается. Если  d(i4'), то w помещается в Р^ , удаляется из Р' и его исследование оканчивается. Поскольку при каждой ите­рации цикла из Р' удаляется по крайней мере одно слово, то этот алгоритм всегда завершается и при Р' = 0 получаем разбиение n\h теста Р на два класса Р^ и Ph = Р". В наихудшем случае алгоритм построения n\h требует проверки всех слов из Р. Сле­довательно, сложность такого построения равна объему Р, то есть равна (0\п222п). Далее, на третьем этапе эксперимента, построенное экспериментально разбиение п (h) сравнивается со всеми разбиениями из семейства. Если для некоторого i\g выполняется n{g) = h(п), то g = h и эксперимент окончен. Из правил построения семейства D и разбиения п\п) следует, что последнее равенство всегда достигается. Рассмотрим свойства этого алгоритма. Поскольку, в общем случае, тест Р кратный, то при выполнении второго этапа эксперимента предполагается, что или МА перед началом анализа слова  или в h помещается новый экземпляр МА. Таким образом, для теста Р кратности к и данной стратегии проведения диагностического эксперимента операционная кратность диагностического эксперимента не превосходит к, а опера­ционная высота диагностического эксперимента равна высоте теста Р. Покажем, что для частных случаев помеченных графов построение диагностичес­кого теста может быть упрощено. Пусть G является D-орграфом. Тогда DT I = Dj I = 0(п2) [8]. Для построения теста Р достаточно 0\п6 шагов. Очевидно, что кратность этого теста равна Оуп2, а его высота не превосходит п-т + 1 [7]. Объем теста Р равен 0\п3. Покажем, что для SD-графов существуют и другие стратегии проведения диаг­ностического эксперимента, отличные от описанной выше. Рассмотрим стратегию, в которой при такой проверке возврат в начальную вершину не требуется. Прежде, чем приступить к изложению этой стратегии, проведем дополнительные построения. Пусть G является приведенным максимальным SD-графом. Для каждой вер­шины ggG построим следующим способом позитивный идентификатор. Восполь­зуемся настроенным графом пар Dj, у которого множество Dj состоит из всех вершин (\g\(d) е D), где Q < 1 и Q  {g}, множество Dp состоит из всех вершин G. Ясно, что Dp < " lang="EN-US"><z D, IД1 < п-т +1, п2 +п. С целью упрощения этого графа удалим все дуги, исходящие из его финальных вершин. Для каждой вершины (\g\ Q) e Д найдем кратчайшее слово w, такое, что DF. Множество таких слов, выбранных по одному для каждой начальной вершины, обозначим через Wg. Если Q = h, где hsG, w является крат­чайшим словом из множества Lg – Lh. Если Q = 0, то w = u(g) и для любой вершины h g G слово w является кратчайшим словом из множества Lg – Lh. Следовательно, Wg является позитивным идентификатором вершины g, причем любое слово w sWg не содержит подслов вида и °urev. Очевидно, что кратность Wg не пре­восходит п– т + 1. Если граф G не связен, то по теореме [4] высота Wg не превосхо­дит п2 +1. Если граф G связен, то по теореме [4] высота Wg не превосходит 3п. Для построения идентификатора Wg достаточно (при использовании известных алгоритмов обхода графа [8]) . По теореме 1 множество Р = МWg , где Wg - идентификатор вершины g, построенный приведенным выше способом, является диагностическим тестом для графа G. Ясно, что кратность такого теста не превосходит п2. Если граф G не связен, то высота теста Р не превосходит п2 +1, а его объем равен Если граф G связен, то высота этого теста не превосходит 3п, а его объем равен 0\п3. Для построения теста Р достаточно 0\п5 шагов. С тестом Р свяжем помеченный лес F(P) корневых деревьев и детерминизируем все деревья этого леса [4]. Обозначим через Рх множество всех слов из Р, начинающихся с метки х е М. Ясно, что Рх является объединением позитивных иден­тификаторов всех вершин g^G, таких, что u(g) = x. Тогда корневое дерево T(РХ) является компонентой леса F(P). Для всех х еМ с деревом T(РХ) свяжем множество вершин Gx = G* х . Обозначим корень дерева T(РХ) через tx. Для каждого слова w e Рх вершину tx*w дерева T(РХ) назовем выделенной. С каждой выделенной вершиной t = tx * w свяжем множество Gt = g | w e Lg j. Множество всех выделенных вершин  дерева T(РХ) обозначим через Тх. Далее МА помещается в произвольную неиз­вестную ему вершину h графа G. Процесс получения экспериментальных данных заключается в проверке наличия в графе G путей, помеченных словами, которые являются метками путей из корня дерева T\P^h во все выделенные вершины этого дерева. МА считывает метку лук. Если (G^h) = 1, то вершина h определена и алгоритм оканчивает работу. В противном случае, пока G^A >1, МА выполняет следующий итеративный алгоритм. Обозначим через г' вершину дерева T\PM<h, являющуюся начальной вершиной i-й итерации. При этом положим, что г' = t^h. Обозначим через v. слово, соответствующее пути по дереву T\PM(h) из вершины г> в вершину г1'. Далее МА удаляет из множества Т все выделенные вершины, связан­ные с пустым множеством. Покажем, что по окончании работы алгоритма множество GMth всегда содержит единственную вершину. Предположим, что после некоторой итерации алгоритма GM(h)> 1 и Гх = F, то есть условие окончания алгоритма не достигнуто, но дальней­шее его выполнение невозможно. Пусть GMth = h^>G', где h<£G'. Из построения теста P^h следует, что для любой вершины g e G' существует слово v e PM<h, такое, что vGLh– Lg. Следовательно, на этой итерации МА побывал в вершине s и по этой причине эта вершина была удалена. Тогда на этой же итерации вершина g была удалена из GMth, так как g £ G(s). Из проведенных рассуждений следует, что при T^h= 0 выполняется GMth = h. Таким образом, данная стратегия объединяет два этапа диагностического экс­перимента – этап получения экспериментальных данных и этап вывода заключений. В наихудшем случае на каждой итерации алгоритма из GMth удаляется одна верши­на. Так как число вершин графа G с меткой равной луп не превосходит n–m + 1,  то алгоритм оканчивает свою работу не более чем за n-m итераций. Так как граф G и дерево T\PM<h неориентированные, то получение экспериментальных данных в ходе диагностического эксперимента можно осуществить с использованием одного экземпляра МА, то есть диагностический эксперимент, при рассмотренной стратегии проведения, является простым вне зависимости от кратности диагностического теста. В теории экспериментов с конечными автоматами кратность эксперимента и кратность теста совпадают. В наихудшем случае МА проверяет n-m выделенных вершин дерева. Ясно, что расстояние от корня t^h этого дерева до любой из выделенных вершин не превосходит высоту теста P. 

Заключение

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

Литература

1. Borenstein J., Everett B., Feng L. Navigation Mobile Robots: System and Techniques. – A.K. Peters, Ltd., Wellesley (MA), 1996. –  № 223 p.

2. Thrun S. Robotic mapping: A survey // Exploring Artificial Intelligence in the New Millenium.  – Morgan Kaufmann, 2002.  – P. № 1–35.

3. Dudek J., Jenkin M., Milios E., Wilkes D. Map validation and Robot Self-Location in a Graph-Like World // Robotics and Autonomous Systems, 1997.  – V. 22(2).  – P. 159 –178.

4. Сапунов С.В. Идентификаторы вершин помеченных графов // Труды ИПММ НАН Украины.  – 2008.  – Т. 17 (в печати).

5. Сапунов СВ. О методе построения отношения неотличимости помеченных графов // Труды ИПММ НАН Украины.  – 2008. – Т. 16 (в печати).

6. Кудрявцев В.Б., Алешин СВ., Подколзин АС Введение в теорию автоматов.  – М.: Наука, 1985.  – 320 с.

7. Грунский И.С Анализ поведения конечных автоматов. – Луганск: Изд-во Луганского гос. пед. ун-та, 2003.  – 318 с.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.  – М.: МЦНМО, 2001.  – 960 с.

9. Рысцов И.К. Исследование сложности решения некоторых задач теории конечных автоматов: Автореф. дис. канд. физ.-мат. наук: 01.01.09 / Ин-т. кибернетики АН УССР.  – К, 1980.  – 16 с.

СВ. Сапунов

Визначення мкця знаходження мобшьного робота в тополопчному середовипц

Розглядається задача визначення автономним мобільним роботом свого місця знаходження у середовищі, яке моделюється за допомогою графа з позначеними вершинами. Розв’язок лежить у побудові дагностичного експерименту - спеціального виду множини слів у алфавт відміток та способу його реалізації на графі.

S. V. Sapunov

Mobile Robot Self Location on Topological Environment

The mobile robot self location problem is considered when robot environment is modeled by a graph with labeled vertices. The solution lies in constructing a distinguishing experiment, i.e. a special set of words over the alphabet of labels, and its implementation on the graph.

                                                                                                                                         

                                                                                                                                              Статья поступила в редакцию 23.07.2008.