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

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Штучний інтелект
Дата:	2011
Автори:	Грунский, И.С., Сапунов, С.В.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Теми:	Системы и методы искусственного интеллекта
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/58838
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Диагностика местоположения мобильного робота на основе топологической информации о среде / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2011. — № 2. — С. 15-25. — Бібліогр.: 11 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860007843904618496
author	Грунский, И.С. Сапунов, С.В.
author_facet	Грунский, И.С. Сапунов, С.В.
citation_txt	Диагностика местоположения мобильного робота на основе топологической информации о среде / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2011. — № 2. — С. 15-25. — Бібліогр.: 11 назв. — рос.
collection	DSpace DC
container_title	Штучний інтелект
description	Рассматривается задача определения автономным мобильным роботом (МР) своего положения в среде, моделируемой графом с помеченными вершинами. МР считывает метки текущей вершины и ее окрестности. Он может перемещаться по ребрам графа от вершины к вершине, оставлять маркер в текущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. В работе предложены полиномиальные методы построения и реализации экспериментов по распознаванию начального положения МР, т.е. начальной вершины графа. Эти методы основаны на проверке изоморфизма подграфов, порожденных предполагаемыми начальными вершинами. Розглянуто задачу визначення автономним мобільним роботом (МР) свого місцезнаходження у середовищі, що моделюється за допомогою графа з позначеним вершинами. МР зчитує позначки поточної вершини та її околу. Він може пересуватися ребрами графа від вершини до вершини, залишати маркер у поточній вершині, а також знаходити і підбирати маркер у разі його знаходження у поточній вершині. У роботі запропоновано поліноміальні методи побудови і реалізації експериментів з визначення початкового місцезнаходження МР, тобто початкової вершини графа. Ці методи ґрунтуються на перевірці ізоморфізму підграфів, які породжено уявними початковими вершинами. The problem of self-localization of a mobile agent (MA) in an environment modeled by a graph with labeled vertices is considered. This problem is actual in connection with problems of navigation of autonomous mobile robots. MA reads labels of the current vertex and its neighborhood. It can move along the edges of the graph from vertex to vertex. In addition MA can drop the pebble at the vertex or pick up the pebble that it has previously dropped at the vertex. We propose construction and realization methods for experiments on the recognition of MA initial position on graph. These methods are based on checking the isomorphism of subgraphs generated by hypothetical initial vertices.
first_indexed	2025-12-07T16:40:04Z
format	Article
fulltext	«Штучний інтелект» 2’2011 15 1Г УДК 519.7 И.С. Грунский, С.В. Сапунов Государственный университет информатики и искусственного интеллекта, г. Донецк, Украина Институт прикладной математики и механики НАН Украины, г. Донецк, Украина grunsky@iamm.ac.donetsk.ua, sapunov_sv@iamm.ac.donetsk.ua Диагностика местоположения мобильного робота на основе топологической информации о среде Рассматривается задача определения автономным мобильным роботом (МР) своего положения в среде, моделируемой графом с помеченными вершинами. МР считывает метки текущей вершины и ее окрестности. Он может перемещаться по ребрам графа от вершины к вершине, оставлять маркер в текущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. В работе предложены полиномиальные методы построения и реализации экспериментов по распознаванию начального положения МР, т.е. начальной вершины графа. Эти методы основаны на проверке изоморфизма подграфов, порожденных предполагаемыми начальными вершинами. Введение Интерес к взвешенным (помеченным) графам (т.е. графам с помеченными эле- ментами – вершинами, дугами, инциденторами и т.д.) вызван развитием теории фор- мальных языков и конечных автоматов [1], [2]. Результаты исследований таких графов широко используются в прикладных областях. В частности помеченные графы оказа- лись удобным средством для исследования топологических операционных сред мобиль- ных агентов (роботов, поисковых программ и т.д.) [3]. При планировании навигации мобильных агентов (МА) возникают три взаимосвязанные фундаментальные задачи: задача построения модели неизвестной среды (exploration), задача определения положе- ния робота в известной среде (robot selflocation) и задача проверки соответствия неизвест- ной среды и ее модели (карты) (map validation) [4]. В теории автоматов имеются соответ- ствующие аналоги для этих задач [5]. В ряду этих задач центральное положение занимает задача самолокализации, т.к. от ее решения зависит решение двух других. Формулируется она следующим образом: МА, обладая картой (помеченным графом) среды, должен уста- новить соответствие между вершиной на карте и неизвестной ему априори областью среды, в которой он первоначально находился. В данной работе в качестве топологической модели операционной среды рассмат- риваются конечные неориентированные графы. Вершины этих графов заранее помечены и МА не меняет эти метки. Такая модель возникает, например, при качественной нави- гации МА (qualitative navigation) [6]. Ранее автором был предложен ряд алгоритмов и методов решения задачи само- локализации, опирающихся на использование конечных множеств слов в алфавите меток, которые отличат одну вершину графа от всех других его вершин (т.н. идентификаторов вершин) [8,] [9]. Грунский И.С., Сапунов С.В. «Искусственный интеллект» 2’2011 16 1Г В данной работе авторами предлагается помимо лингвистической информации ис- пользовать также топологическую информацию о графе. Продуктивность такого подхода демонстрирует следующий пример. Рассмотрим граф G , состоящий из двух компонент G и G  (рис. 1). В [8] пока- зано, что МА, установленному, например, в вершину 1 графа G для того, чтобы отличить начальную вершину от всех других вершин, достаточно пройти путь, помеченный после- довательностью меток .adabcadabcadabcad С другой стороны, легко видеть, что только для вершины 1 путь, помеченный последовательностью меток abca , образует цикл. Поэтому для отделения этой вершины от всех других вершин достаточно проверить наличие такого цикла. Рисунок 1 Целью данной работы является изложение метода проведения диагностических экспериментов с графами путем анализа их подграфов. Постановка задачи Рассматривается задача определения МА своего местоположения в среде. Среда моделируется конечным графом, вершинам которого приписаны метки из некоторого конечного алфавита. МА устанавливается в произвольную вершину известного ему графа среды. Находясь в вершине, МА считывает ее метку и метки смежных с ней вершин. МА может перемещаться по ребрам графа от вершины к вершине, оставлять маркер в те- кущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. Задача МА заключается в определении начальной вершины, т.е. отли- чении этой вершины от всех других вершин. Основные определения Конечным графом с помеченными вершинами (помеченным графом) назовем чет- верку  ,,, MEVG  , где V – конечное множество вершин, nV  , VVE  – ко- нечное множество ребер, M – конечное множество (алфавит) меток вершин, mM  , MV : – сюръективная функция разметки. Последовательность меток вершин      kgggw  21 , соответствующую пути kggg 21 в графе G , назовем словом длины   kwd  , порожденным вершиной Vg 1 . Инверсией слова kk xxxxw 121   будем называть слово 121 xxxxw kk rev  . Обозначим через M множество всех не- пустых слов в алфавите M . Для всякого  MW высотой W назовем наибольшую из длин входящих в него слов, его кратностью – величину W , его объемом – сумму длин Диагностика местоположения мобильного робота… «Штучний інтелект» 2’2011 17 1Г всех входящих в него слов. Введем частичную операцию VMV 2:   соотно- шением: для любой вершины Vg  и любого слова Mw через wg  обозначим множество всех вершин ,h V таких, что из g в h существует путь, помеченный словом w . Для слов Mwu, введем их композицию ,u w равную wu  , если xuu  , wxw  , Mx , и не определено в противном случае. Для слов Mwu, через wu или wu  будем обозначать их конкатенацию. Языком gL вершины Vg  назовем множество всех слов, порожденных этой вершиной. Будем говорить, что вершины Vhg ,  -неотличимы, если hg LL  . Простой неориентированный помеченный граф G назовем сильно детермини- рованным графом или СД-графом, если для любой вершины Vg  и любых смежных с ней вершин s и t из ts  следует, что    ts   . Из этого определения следует, что для любой вершины g СД-графа G и любого слова Mw выполняется 1wg , где 1wg , если gLw , и 0wg в противном случае. В дальнейшем, если не оговорено противное, рассматриваются только СД-графы. Под детерминизацией помеченного графа будем понимать многократное при- менение следующей операции: если в множестве преемников некоторой вершины оказываются одинаково помеченные вершины, то такие вершины отождествляются с заменой возникающих кратных дуг одной дугой. Пусть  gMEVGg ,,,,  и  hMEVGh ,,,,  – инициально-связные поме- ченные графы. Гомоморфизмом графа gG в граф hG называется такое отображение VVf : , для которого: 1)   hgf  ; 2)     tft   для всех Vt ; 3) для любой дуги   Ette  21, существует дуга      Etftfe  21 , . Если такое отображение существует, то будем говорить, что граф gG гомоморфно вкладывается в граф hG . Если VVf  :1 является гомоморфизмом графа hG в граф gG , то f называют изоморфизмом графов gG и hG , а графы gG и hG – изоморфными, что записывают в виде hg GG  . Неотличимость вершин Пусть  ,,, MEVG  – помеченный граф. Подграфом графа G назовем граф  SSS MEVS ,,, такой, что: 1) VVS  ; 2)  SSS VVEE  ; 3) S является сужением  на множество SV . Мы будем использовать обозначение GS  для обозначения того, что S является подграфом G . Подграф S графа G называется подграфом, порожден- ным множеством вершин VVS  , если  SSS VVEE  . Через gS обозначим подграф графа G , порожденный всеми вершинами, достижимыми из вершины Vg  . Таким об- разом, gS является инициально-связным помеченным графом с выделенной вершиной g . Инъективная функция VVf : называется изоморфным вложением графа hG в граф gG , если существует подграф gg GS  , такой, что f является изоморфизмом графа hG в граф gS . Будем говорить, что вершины Vhg ,  -неотличимы и писать   hg, , если hg SS  . Грунский И.С., Сапунов С.В. «Искусственный интеллект» 2’2011 18 1Г Из определения языка вершины помеченного графа следует, что hg SS  влечет hg LL  . Иными словами, из   hg, следует   hg, , что означает   . Пример на рис. 2 показывает, что обратное включение не выполняется. Рисунок 2 Действительно, в связном СД-графе на этом рисунке 83 LL  (метод проверки равенства языков смотри в [7]), но 83 SS  . Таким образом,  порождает более грубое разбиение множества V , чем  . Очевидно, что равенство   выполняется для при- веденных графов. Действительно, по определению приведенного графа G для любых вершин Vhg , выполняется hg LL  . Пусть слово hg LLw \ . Тогда существует путь из вершины g , помеченный словом w , и не существует пути из вершины h с меткой w . Следовательно, hg SS  . Представление графов Представляющей парой (ПП) инициально-связного помеченного графа gG на- зовем пару     gg GCGT , , где  gGT – корневое остовное дерево графа gG с кор- нем в вершине g , а  gGC – множество всех инициальных подграфов графа gG , каждый из которых образован двумя унарными корневыми поддеревьями дерева  gGT и хордой, соединяющей их листья. Ясно, что в случае, когда граф gG яв- ляется деревом,  gg GTG  и   gGC . Прямой суммой помеченных графов G и H назовем помеченный граф HG  , полученный объединением множеств вершин и ребер этих графов (с предварительным переобозначением вершин так, чтобы исходные графы не имели общих вершин). Пусть gG и hH являются инициально-связными помеченными графами и    hg HG   . Соединением gG и hH назовем инициально-связный помеченный граф hg HG  , по- лученный из графов gG и hH отождествлением их начальных вершин и последующей детерминизацией. Теорема 1. Для любой ПП     gg GCGT , инициально-связного помеченного графа gG существует изоморфизм     gGCCg GCGT g   . Доказательство. Если граф gG является деревом, то справедливость теоремы очевидна. Пусть gG не является деревом. Покажем, что граф      gGCCg CGT изоморфен графу gG . Вершины графа      gGCCg CGT будем обозначать строч- Диагностика местоположения мобильного робота… «Штучний інтелект» 2’2011 19 1Г ными буквами it , а через 0t обозначим его инициальную вершину. Из определения графа      gGCCg CGT следует, что существует взаимно однозначное отображение  графа      gGCCg CGT на граф gG , такое, что   gt 0 и для любого пути kttt 10 по ветви дерева  gGT последовательность вершин      kttt  10 являет- ся путем по графу gG , причем метки этих путей совпадают. Пусть  ji tt , – ребро графа      gGCCg CGT . Если  ji tt , принадлежит  gGT , то     ji tt  , является ребром графа gG . Если  ji tt , является хордой  gGT , то, по определению множества  gGC , ребро  ji tt , принадлежит одному из графов  gGCC . Тогда     ji tt  , является ребром графа gG . Следовательно,     gGCCg GCGT g   . Пусть  ji gg , – ребро графа gG . Если  ji gg , принадлежит  gGT , то     ji gg 11 ,   является реб- ром графа      gGCCg CGT . Если  ji gg , является хордой  gGT , то, по опре- делению множества  gGC , ребро  ji gg , принадлежит одному из графов  gGCC . Тогда     ji gg 11 ,   является ребром графа      gGCCg CGT . Следовательно,      gGCCgg CGTG . Таким образом,     gGCCg GCGT g   . Что и требовалось доказать. Из определения СД-графа следует, что всякому пути из вершины такого графа соответствует единственное слово из языка этой вершины, являющееся меткой этого пути. Поэтому всякую ПП     gg GCGT , графа gG можно представить в виде пары множеств     gg GG C,T , где  gGT – множество всех слов, являющихся метками простых путей из корня дерева  gGT во все его вершины,  gGC – множество всех неупорядоченных пар слов  wu, таких, что  gGwu T,  , wu  , и gwug rev  . Рассмотрим метод перехода от ПП к помеченному графу. Каждому слову  gGw T поставим в соответствие унарное корневое дерево  wT так, чтобы w было меткой пути из корня этого дерева в его лист. Множеству  gGT поставим в соответствие корневое дерево, являющееся результатом соединения всех деревьев  wT . Каждой паре    gGvu C,  поставим в соответствие корневое дерево  vuT , , являющееся резуль- татом соединения унарных корневых деревьев  uT и  vT . Множеству  gGC поста- вим в соответствие корневое дерево, являющееся результатом соединения всех деревьев  vuT , . Построим соединение деревьев, соответствующих  gGT и  gGC . Инициаль- ную вершину полученного графа обозначим через 0t . Для каждой пары слов  ,u v   C gG построим ребро  vtut  00 , . Очевидно, что полученный граф изоморфен графу gG . Таким образом, пару     gg GG C,T можно использовать для представления графа gG наряду с парой     gg GCGT , . Поэтому пару     gg GG C,T будем также называть представляющей парой графа gG . Грунский И.С., Сапунов С.В. «Искусственный интеллект» 2’2011 20 1Г Зададим частичный порядок  на множестве меток M и связанный с ним лексикографический порядок  на множестве M . ПП     gg GG C,T графа gG назовем выделенной (ВПП), если множество  gGT состоит из меток кратчайших по длине и наименьших по метке путей из g во все вершины gG . Очевидно, что крат- ность и высота  gGT не превосходят n . Кратность  gGC равна числу хорд остова  gGT , т.е. не превосходит 12  nn [11]. Высота  gGC равна  nO . Легко видеть, что ВПП графа gG может быть построена путем обхода графа в ширину со слож- ностью  2nO . Топологический идентификатор Пусть gG и hH являются инициально-связными помеченными графами с вы- деленными вершинами g и h соответственно. Обозначим через hg HG  операцию нахождения наибольшего связного подграфа gg GG  , содержащего выделенную вершину ,g такого, что gG изоморфно вложим в ,hH причем вершина g отобра- жается в вершину h . Топологическим идентификатором (ТИ) вершины Vg назовем помеченный граф gD такой, что для любой вершины Vh изоморфизм hggg SDSD  существует тогда и только тогда, когда   hg, . Рассмотрим примеры топологических идентификаторов вершин помеченных графов. Очевидно следующее утверждение. Утверждение 1. Граф gS является ТИ вершины g приведенного графа G . Следующее утверждение демонстрирует связь между позитивными лингвисти- ческими идентификаторами (ЛИ) вершин графа [9] и их ТИ. Утверждение 2. Пусть gW – позитивный ЛИ вершины g графа G . Гомо- морфный образ корневого дерева    gWw wT в графе gS является ТИ g . Доказательство. Действительно, т.к. gg LW  , то существует гомоморфизм корневого дерева    gWw wT в граф ,gS сохраняющий метки вершин. По опреде- лению gW , для любой вершины  gVh \ существует слово hg LWw \ . Тогда су- ществует унарное корневое поддерево  wT дерева    gWw wT и его гомоморф- ный образ gS  в графе ,gS такой, что hg SS  . Что и требовалось доказать. Рассмотрим метод построения ПП     gg DD C,T ТИ gD вершины g графа G . Пусть для каждой вершины Vh построена ВПП     hh SS C,T . Для каждой вершины Vh каждой паре    hSvu C,  поставим в соответствие меньшее (по  ) из слов revvu и revuv . Полученное множество слов обозначим  hSC ~ . Далее, для вершины g и всех вершин  gVh \ отыщем меньшее (по  ) среди кратчайших слов  T gw S   T hS и    hg SSw C ~ C ~  , если они существуют. Диагностика местоположения мобильного робота… «Штучний інтелект» 2’2011 21 1Г Основная идея метода диагностики положения МА из следующего подраздела состоит в исследовании подграфов, порожденных вершинами, удаленными от исходной на расстояние не превосходящее k , где k пробегает значения от 1 до n . Поэтому принимать решение о помещении слова в ВПП ТИ будем исходя из следующих соображений: если     2wdwd  , то w помещаем в  gDT , иначе w  помещаем в  gDC ~ . Алгоритм 1. Построение ТИ вершины графа. Вход. ВПП     hh SS C,T всех вершин Vh . Выход. ПП ТИ вершины Vg . Метод. 1. Положить VQ  ,   gDT ,   gDC ~ . 2. Выбрать вершину Qg . 3. Положить  gQQ \ ,       gDD gg  TT . 4. Удалить из Q все вершины h , для которых    gh   . 5. Если Q , то пара     gg DD C ~ ,T уже построена. Пополним множество  gDT объединением собственных начальных отрезков всех входящих в него слов. Каждое слово  gDw C ~  заменить соответствующей ему парой слов  vu, и обозна- чить полученное множество пар через  gDC . Конец работы. 6. Выбрать вершину Qh . Положить  hQQ \ . 7. Найти кратчайшие по длине и наименьшие по  слова    hg SSw TT  и    hg SSw C ~ C ~  . 8. Если     2wdwd  , то      wDD gg  TT . Перейти к п. 5. 9.      wDD gg  C ~ C ~ . Перейти к п. 5. Анализ алгоритма начнем со следующей теоремы. Теорема 2. Граф gD , построенный по алгоритму 2, является ТИ вершины g графа G . Доказательство. Из процедуры построения графа gD следует, что в ПП     gg DD C,T для любой вершины  gVh \ существует слово    hg SSw TT  или пара слов      hg SSvu CC,  . Пусть, для определенности,    gSvu C,  . Из процедуры построения  gDC следует, что hvuh rev  . Обозначим через  vuS , гомоморфный образ унарного корневого дерева  revvuT в графе gS . Ясно, что     hg SvuSSvuS  ,, . Пусть  gSw T . Если hLw , то     hg SwTSwT  . Предположим, что hLw . Так как w является кратчайшим по длине и наименьшим по  словом из    hg SS TT  , то всякий его собственный начальный отрезок    hg SSw TT  . Из процедуры построения ПП графа gD следует, что  hSw T . Тогда существует слово  T ,hu S такое, что whuh  и, следовательно, huwh rev   . Так как  hSu T , то либо     1 wdud , либо    wdud  и wu  . Грунский И.С., Сапунов С.В. «Искусственный интеллект» 2’2011 22 1Г Тогда     g rev h rev SuwSSuwS   . Так как     wduwd rev 2 , то  gDw T , что невозможно. Следовательно, если    hg SSw TT  , то hLw . Аналогично доказывается случай, когда  hSw T или    hSvu C,  . Что и тре- бовалось доказать. Оценку временной сложности Алгоритма 1 устанавливает следующее утверждение. Теорема 3. Алгоритм 1 строит ТИ вершины g графа G за время  2nO . Доказательство. Очевидно, что наибольших затрат времени требует 7-я строка алгоритма. Опишем подробно метод отыскания кратчайших слов. Множества  g       T Tg hS h S   и        hg ShSg CC  упорядочим по длине второй ком- поненты. В результате получим их разбиение на подмножества, состоящие из пар, у которых длина второй компоненты одинакова. Эти подмножества упорядочим лексико- графически. Сложность такого упорядочивания имеет порядок  2nO [10]. В упорядочен- ных таким образом множествах        hg ShSg TT  и        hg ShSg CC  про- анализируем последовательность первых компонент. Вторая компонента той пары, на которой нарушается чередование g и h , является искомым кратчайшим словом для соответствующего множества. Для такого анализа достаточно  2nO шагов. Таким обра- зом, сложность алгоритма 1 имеет порядок  2nO . Что и требовалось доказать. Диагностический эксперимент Экспериментом с графом G относительно априорной информации I, цели C и средств S назовем процесс, состоящий из трех этапов: 1) построение теста P на основе I и C; 2) получение МА экспериментальных данных W на основе P и S; 3) вывод заключений о свойствах графа на основе W и I. Априорная информация – это класс графов, к которому принадлежит G . В качестве S выступают возможности МА перемещаться по графу, воспринимать локальную информацию о вершинах и ставить в них дополнительные стираемые/нестираемые метки. Эксперимент назовем диагностическим (ДЭ), если априори полностью известен граф G и МА установлен в произвольную начальную вершину этого графа, а целью является определение этой вершины, т.е. отличие этой вершины от всех других вершин. Из определения эксперимента следует, что он осуществляется посредством прохождения МА некото- рого связанного с тестом P множества путей по графу G из начальной вершины. Очевидно, что если граф G не приведен, то, в общем случае, невозможно однозначно определить начальную вершину и, следовательно, невозможен ДЭ с ним. Рассмотрим метод построения диагностического теста для графа G с исполь- зованием ТИ всех его вершин. Для каждой метки Mx построим граф   ,,,, 0qMEVDx такой, что        xg gx DD    TT и        xg gx DD    CC . Обозна- чим через D граф, являющийся прямой суммой всех графов xD . Очевидно, что для любых Vhg , выполняется hg SDSD  . Действительно, из    DDg TT  и    DDg CC  следует, что DDg  . Тогда по определению ТИ hggg SDSD  , а следовательно, hg SDSD  . Таким образом, справедливо следующее утверждение. Диагностика местоположения мобильного робота… «Штучний інтелект» 2’2011 23 1Г Теорема 4. Граф D является диагностическим тестом для графа G для любого множества ТИ   VggD  . Эта теорема дает метод построения диагностических тестов для СД-графов. Стратегия получения экспериментальных данных заключается в том, что МА, стартуя из неизвестной ему вершины h графа ,G проверяет наличие/отсутствие в G путей, помеченных словами из ПП графа xD , где  hx  . В зависимости от исхода каждой из таких проверок количество претендентов на роль начальной вершины может быть только уменьшено. В основу алгоритма положен метод обхода графа в ширину [10]. С вершиной 0q свяжем множество вершин xVQx  , где Mx (т.е. всех вершин с меткой x ). Для каждого слова  xDw T с вершиной wqq  0 свяжем два множества     gx SwQgqQ T\|  и     gx SwQgqQ T\| ~  . Пусть  qq , – произвольная хорда остова  xDT . Обозначим через w и w  слова из  xDT , в т.ч. qwq 0 и qwq 0 . С каждой хордой  qq , свяжем три множества: 1)  qqQ , состоит из всех вершин ,xg Q в т.ч.   gwwg rev  ; 2)  qqQ , ~ состоит из всех вершин ,xg Q в т.ч.    qwg  и     gwqwg rev   ; 3)  qqQ ,ˆ состоит из всех вершин ,xg Q в т.ч. wg и    qwg  . Для упрощения записи алгоритма введем частичную функцию VV : соотношениями:   hq 0 и для любого  xDw T положим   whwq 0 . Для наглядности мы будем считать, что в процессе работы алгоритма вершины графа xD могут быть белыми, серыми и черными. Алгоритм 2. Диагностический эксперимент. Вход. СД-граф G , граф D , МА установлен в неизвестную ему вершину Vh . Выход. Множество xQ . Метод. 1. Считать метку  h . Пусть   xh  . Положить F . 2. Выбрать из графа  Vg gD компоненту xD . 3. Для всех Vq  положить  qcolor БЕЛЫЙ. Пометить все хорды остова  xDT как неисследованные. 4. Положить   0color q СЕРЫЙ и  0qFF  . 5. Если 1xQ , то вершина h уже определена. Алгоритм прекращает работу. 6. Положить  Ft head и  tFF \ . Перейти в вершину  t . 7. Если   t , то положить  tQQQ xx \ , удалить из xD вершину t и все инцидентные ей ребра и перейти к п. 5. 8. Положить  tcolor ЧЕРНЫЙ и  tQQQ xx ~ \ . 9. Если 1xQ , то перейти к п. 5. 10. Для всех tQs если   scolor БЕЛЫЙ, то положить   scolor СЕРЫЙ и  sFF  . 11. Если вершине t инцидентна неисследованная хорда  st, и   scolor ЧЕРНЫЙ, то перейти к п. 12, иначе перейти к п. 5. 12. Если        stt  , то положить    stQstQQQ xx , ~ \,\ , удалить из xD ребро  st, и если 1xQ , то перейти к п. 5, иначе перейти к п. 11. Грунский И.С., Сапунов С.В. «Искусственный интеллект» 2’2011 24 1Г 13. Перейти в вершину      stt   , оставить в ней маркер и вернуться в вершину  t . 14. Перейти в вершину  s по образам ЧЕРНЫХ вершин графа xD . 15. Если маркер обнаружен, то положить    stQstQQQ xx ,ˆ\, ~ \ , пометить  st, как исследованную хорду, подобрать маркер, вернуться в вершину  t и если 1xQ , то перейти к п.5, иначе перейти к п.11. 16. Положить    stQstQQQ xx , ~ \,\ , удалить из xD ребро  st, , перейти в вершину      stt   , подобрать маркер, вернуться в вершину  t и если 1xQ , то перейти к п. 5, иначе перейти к п. 11. Анализ алгоритма 3 начнем со следующей теоремы. Теорема 5. По окончании работы алгоритма 3 множество xQ всегда содержит единственную вершину. Доказательство. Предположим, что на некоторой итерации алгоритма 1xQ и F , т.е. условие окончания алгоритма не выполнено, но его дальнейшее продолже- ние невозможно. Пусть  hgQx , , где hg  . Из определения графа xD , что для лю- бой вершины  hVg \ выполняется xhxg DSDS  . Следовательно, имеет место, по крайней мере, одно из утверждений: 1) существует вершина q графа xh DS  или его ребро  , ,q q  в т.ч.  qQh и  qQg ~  или  qqQh  , и    qqQqqQg  ,€, ~ ; 2) существует вершина q графа xg DS  или его ребро  , ,q q  в т.ч.  qQg и  qQh ~  или  qqQg  , и    qqQqqQh  ,€, ~ . Пусть выполняется утверждение 1. По условию F . Следовательно, вершины q , q и q  уже были удалены из F . Тогда вершина g должна уже быть удалена из xQ . Полученное противоречие доказывает теорему. В наихудшем случае выполнение Алгоритма 2 будет сведено к обходу в ширину графа hS . Следовательно, временная сложность Алгоритма 3 равна  2nO . Заключение В работе решена задача различения вершин топологической модели (помеченного неорграфа) операционной среды мобильного агента. С этой целью введены топологи- ческие идентификаторы вершин, на их основе построены диагностические экспери- менты и разработаны стратегии их реализации на модели. Найдены оценки сложности соответствующих алгоритмов. В дальнейшем предполагается распространить понятие топологических идентификаторов на более широкие классы графов и разработать на их основе эффективные эксперименты с этими графами. Литература 1. James A. Anderson. Automata Theory with Modern Applications / James A. Anderson. – Cambridge University Press, 2006. – 255 p. 2. Droste M. Handbook of Weighted Automata / Droste M., Kuich W., Vogler H. – Springer, New York, 2009. – 608 p. Диагностика местоположения мобильного робота… «Штучний інтелект» 2’2011 25 1Г 3. Dudek G. Computational Principles of Mobile Robotics / G. Dudek, M. Jenkin. – Cambridge University Press, Cambridge, 2000. – 280 p. 4. Dudek G. Map Validation and Robot Self-Location in a Graph-Like World / G. Dudek, M. Jenkin, E. Milios, D. Wilkes // Robotics and Autonomous Systems. – 1997. – Vol. 22, № 2. – P. 159-178. 5. Грунский И.С. Анализ поведения конечных автоматов / Грунский И.С. – Луганск : Изд-во Луганск. гос. пед. ун-та, 2003. – 318 с. 6. Lewitt T. Qualitative navigation for mobile robot / T. Lewitt, D.T. Lawton // Artificial Intelligence. – 1990. – Vol. 40. – P. 306-360. 7. Сапунов С.В. Неотличимость вершин помеченных графов / С.В. Сапунов // Труды ИПММ. – 2008. – Т. 16. – С. 179-189. 8. Сапунов С.В. Определение положения робота в топологической среде / С.В. Сапунов // Искусственный интеллект. – 2008. – № 4. – С. 558-565. 9. Грунский И.С. Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды ИПММ. – 2010. – Т. 20. – С. 86-97. 10. Кормен Т. Алгоритмы: построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р. – М. : МЦНМО, 2001. – 960 с. 11. Харари Ф. Теория графов / Харари Ф. – М. : Мир, 1973. – 303 с. Literatura 1. James A. Anderson. Cambridge University Press, 2006. 255 p. 2. Droste M. Springer, New York. 2009. 608 p. 3. Dudek G. Cambridge University Press, Cambridge. 2000. 280 p. 4. Dudek G. Robotics and Autonomous Systems. Vol. 22, № 2. 1997. P. 159-178. 5. Grunsky I.S. Lugansk : Lugansk University Press. 2003. 318 p. 6. Lewitt T. Artificial Intelligence. Vol. 40. 1990. P. 306-360. 7. Sapunov S.V. Studies of IPMM. Vol. 16. 2008. P. 179-189. 8. Sapunov S.V. Artificial Intelligence. Vol. 4. 2008. P. 558-565. 9. Grunsky I.S. Stidies of IPMM. Vol. 20. 2008 P. P. 86-97. 10. Kormen T. Moscow : MCNMO. 2001. 960 p. 11. Harary F.Moscow : Mir. 1973. 303p. І.С. Грунський, С.В. Сапунов Діагностування місцезнаходження мобільного робота на підставі топологічної інформації щодо середовища Розглянуто задачу визначення автономним мобільним роботом (МР) свого місцезнаходження у середовищі, що моделюється за допомогою графа з позначеним вершинами. МР зчитує позначки поточної вершини та її околу. Він може пересуватися ребрами графа від вершини до вершини, залишати маркер у поточній вершині, а також знаходити і підбирати маркер у разі його знаходження у поточній вершині. У роботі запропоновано поліноміальні методи побудови і реалізації експериментів з визначення початкового місцезнаходження МР, тобто початкової вершини графа. Ці методи ґрунтуються на перевірці ізоморфізму підграфів, які породжено уявними початковими вершинами. I.S. Grunsky, S.V. Sapunov Location Diagnostics of the Mobile Robots on the Basis of the Topological Information on the Environment The problem of self-localization of a mobile agent (MA) in an environment modeled by a graph with labeled vertices is considered. This problem is actual in connection with problems of navigation of autonomous mobile robots. MA reads labels of the current vertex and its neighborhood. It can move along the edges of the graph from vertex to vertex. In addition MA can drop the pebble at the vertex or pick up the pebble that it has previously dropped at the vertex. We propose construction and realization methods for experiments on the recognition of MA initial position on graph. These methods are based on checking the isomorphism of subgraphs generated by hypothetical initial vertices. Статья поступила в редакцию 19.04.2011.
id	nasplib_isofts_kiev_ua-123456789-58838
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-12-07T16:40:04Z
publishDate	2011
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Грунский, И.С. Сапунов, С.В. 2014-03-31T12:15:44Z 2014-03-31T12:15:44Z 2011 Диагностика местоположения мобильного робота на основе топологической информации о среде / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2011. — № 2. — С. 15-25. — Бібліогр.: 11 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58838 519.7 Рассматривается задача определения автономным мобильным роботом (МР) своего положения в среде, моделируемой графом с помеченными вершинами. МР считывает метки текущей вершины и ее окрестности. Он может перемещаться по ребрам графа от вершины к вершине, оставлять маркер в текущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. В работе предложены полиномиальные методы построения и реализации экспериментов по распознаванию начального положения МР, т.е. начальной вершины графа. Эти методы основаны на проверке изоморфизма подграфов, порожденных предполагаемыми начальными вершинами. Розглянуто задачу визначення автономним мобільним роботом (МР) свого місцезнаходження у середовищі, що моделюється за допомогою графа з позначеним вершинами. МР зчитує позначки поточної вершини та її околу. Він може пересуватися ребрами графа від вершини до вершини, залишати маркер у поточній вершині, а також знаходити і підбирати маркер у разі його знаходження у поточній вершині. У роботі запропоновано поліноміальні методи побудови і реалізації експериментів з визначення початкового місцезнаходження МР, тобто початкової вершини графа. Ці методи ґрунтуються на перевірці ізоморфізму підграфів, які породжено уявними початковими вершинами. The problem of self-localization of a mobile agent (MA) in an environment modeled by a graph with labeled vertices is considered. This problem is actual in connection with problems of navigation of autonomous mobile robots. MA reads labels of the current vertex and its neighborhood. It can move along the edges of the graph from vertex to vertex. In addition MA can drop the pebble at the vertex or pick up the pebble that it has previously dropped at the vertex. We propose construction and realization methods for experiments on the recognition of MA initial position on graph. These methods are based on checking the isomorphism of subgraphs generated by hypothetical initial vertices. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Системы и методы искусственного интеллекта Диагностика местоположения мобильного робота на основе топологической информации о среде Діагностування місцезнаходження мобільного робота на підставі топологічної інформації щодо середовища Location Diagnostics of the Mobile Robots on the Basis of the Topological Information on the Environment Article published earlier
spellingShingle	Диагностика местоположения мобильного робота на основе топологической информации о среде Грунский, И.С. Сапунов, С.В. Системы и методы искусственного интеллекта
title	Диагностика местоположения мобильного робота на основе топологической информации о среде
title_alt	Діагностування місцезнаходження мобільного робота на підставі топологічної інформації щодо середовища Location Diagnostics of the Mobile Robots on the Basis of the Topological Information on the Environment
title_full	Диагностика местоположения мобильного робота на основе топологической информации о среде
title_fullStr	Диагностика местоположения мобильного робота на основе топологической информации о среде
title_full_unstemmed	Диагностика местоположения мобильного робота на основе топологической информации о среде
title_short	Диагностика местоположения мобильного робота на основе топологической информации о среде
title_sort	диагностика местоположения мобильного робота на основе топологической информации о среде
topic	Системы и методы искусственного интеллекта
topic_facet	Системы и методы искусственного интеллекта
url	https://nasplib.isofts.kiev.ua/handle/123456789/58838
work_keys_str_mv	AT grunskiiis diagnostikamestopoloženiâmobilʹnogorobotanaosnovetopologičeskoiinformaciiosrede AT sapunovsv diagnostikamestopoloženiâmobilʹnogorobotanaosnovetopologičeskoiinformaciiosrede AT grunskiiis díagnostuvannâmísceznahodžennâmobílʹnogorobotanapídstavítopologíčnoíínformacííŝodoseredoviŝa AT sapunovsv díagnostuvannâmísceznahodžennâmobílʹnogorobotanapídstavítopologíčnoíínformacííŝodoseredoviŝa AT grunskiiis locationdiagnosticsofthemobilerobotsonthebasisofthetopologicalinformationontheenvironment AT sapunovsv locationdiagnosticsofthemobilerobotsonthebasisofthetopologicalinformationontheenvironment

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

Репозитарії

Схожі ресурси