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

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

Full description

Saved in:

Bibliographic Details
Date:	2008
Main Author:	Сапунов, С.В.
Format:	Article
Language:	Russian
Published:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Subjects:	Управление и информационное обеспечение мехатронных и робототехнических систем
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/7561
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Определение положения мобильного робота в топологической среде / С.В. Сапунов // Штучний інтелект. — 2008. — № 4. — С. 558-565. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859478206003806208
author	Сапунов, С.В.
author_facet	Сапунов, С.В.
citation_txt	Определение положения мобильного робота в топологической среде / С.В. Сапунов // Штучний інтелект. — 2008. — № 4. — С. 558-565. — Бібліогр.: 9 назв. — рос.
collection	DSpace DC
description	Рассматривается задача определения автономным мобильным роботом своего положения в среде, моделируемой графом с помеченными вершинами. Решение заключается в построении диагностического эксперимента – специального вида множества слов в алфавите меток вершин и способа его реализации на графе. Розглядається задача визначення автономним мобільним роботом свого місця знаходження у середовищі, яке моделюється за допомогою графа з позначеними вершинами. Розв’язок лежить у побудові діагностичного експерименту – спеціального виду множини слів у алфавіті відміток та способу його реалізації на графі. 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.
first_indexed	2025-11-24T11:53:35Z
format	Article
fulltext	«Искусственный интеллект» 4’2008 558 6С УДК 519.7 С.В. Сапунов Институт прикладной математики и механики НАН Украины, г. Донецк, Украина sapunov_sv@iamm.ac.donetsk.ua Определение положения мобильного робота в топологической среде Рассматривается задача определения автономным мобильным роботом своего положения в среде, моделируемой графом с помеченными вершинами. Решение заключается в построении диагностического эксперимента – специального вида множества слов в алфавите меток вершин и способа его реализации на графе. Задачи организации двигательного поведения или навигации автономных мобиль- ных роботов являются одними из основных задач искусственного интеллекта [1]. Целенаправленное автономное передвижение робота в его операционной среде невоз- можно без формирования достаточно полной ее модели (карты среды). К моделированию таких сред определилось два подхода: метрический, использующий геометрические свойства среды, и топологический, использующий описания связей между различными областями среды [2]. Топологические модели представляют собой ориентированные или неориентированные графы с размеченными различными способами вершинами и/или дугами [3]. Фундаментальной проблемой навигации является самостоятельное определение (диагностика) роботом своих координат (robot self location). Задача диаг- ностики положения робота формулируется следующим образом: робот, обладая картой среды (помеченным графом), должен установить соответствие между вершиной на карте и неизвестной ему априори областью среды, в которой он был первоначально уста- новлен [3]. В данной работе в качестве топологической модели операционной среды рассмат- риваются конечные ориентированные графы с помеченными вершинами. Теоретическая важность и актуальность работы определяются тем, что анализ графов проводится методами, аналогичными методам теории автоматов. Эти методы эффективно рас- пространяются на графовые системы, неявляющиеся конечными автоматами, но являющиеся в некотором смысле автоматоподобными системами. Целью данной статьи является изложение метода проведения диагностических экспериментов с графами путем анализа и различения языков в алфавите меток, свя- занных с вершинами графа. Постановка задачи Рассматривается задача отличения блуждающим по помеченному графу роботом одной вершины этого графа от всех других его вершин. Блуждание состоит в пере- мещениях робота по ребрам графа от вершины к вершине. При этом, находясь в вершине графа, робот считывает ее метку и метки смежных с ней вершин. Таким образом он может определить наличие или отсутствие некоторой метки в упомянутых вершинах. Робот установлен в произвольную вершину известного ему графа. Задача заключается в определении этой вершины, то есть отличении этой вершины от всех других вершин. Определение положения мобильного робота в топологической среде «Штучний інтелект» 4’2008 559 6С Основные определения Конечным ориентированным графом с помеченными вершинами (помеченным орграфом) назовем четверку   ,,,G MGEG , где G – конечное множество вер- шин, nG  ,   GGGE  – конечное множество ребер, M – конечное множество меток, mM  , MG : – сюръективная функция разметки. Последовательность меток вершин    kggw  1 , соответствующую некоторому пути kgg 1 в графе G , назовем словом длины k , порожденным вершиной 1g . Обозначим через M множество всех непустых слов в алфавите M. Языком gL вершины g назовем множество всех слов, порожденных этой вершиной. Введем частичную операцию GMG 2:   соотно- шением: для любой вершины Gg и любого слова Mw через wg  обозначим множество всех вершин Gh , таких, что существует путь из g в h помеченный словом w . Для слов Mwu, введем их композицию wu  , равную wu  , если xuu  , wxw  , Mx , и не определено в противном случае. Помеченный орграф G назо- вем детерминированным орграфом или D-орграфом, если для любой вершины Gg и любых вершин  gts, из ts  следует, что    ts   (здесь g – множество всех вершин, являющихся концами дуг, исходящих из g ). В противном случае G назовем ND-орграфом. Простой D-орграф G, для которого выполняются следующие ограни- чения: 1) для любых вершин Ghg , если    GEhg , , то    GEgh , ; 2) для любой вершины Gg и любых вершин  gOts , из ts  следует, что    ts   (здесь    gO gg   ), назовем сильно детерминированным или SD-графом. Будем говорить, что вершины Ghg , неотличимы, и писать   hg, , если hg LL  . Отношение  рефлексивно, симметрично и транзитивно, т.е. является эквивалентностью. Идентификатором вершины Gg назовем конечное множество слов  MWg , такое, что для любой вершины Gh равенство hggg LWLW  выполняется тогда и только тогда, когда hg  . Всякий идентификатор gW можно представить как объе- динение   gg WW двух множеств ggg LWW  и ggg LWW  . Идентификатор gW назовем позитивным, если  gW , и негативным, если  gW . Детально иденти- фикаторы рассматриваются в [4]. Каждому графу   G,,,G MGEG поставим в соответствие граф пар     D,,,D MDEDG  , построенный следующим образом. Сначала определим множест- во 1D по правилу:   1, DQS  точно тогда, когда GQS 2,  , QS и   1G QS . При этом полагаем, что    QSQS  GD ,  . Затем множество 1D пополним m экземп- лярами пар  , , при этом их метки попарно различны. Полученное семейство пар образует «множество» вершин D графа пар. Из вершины  QS , с меткой x исходит дуга в вершину  QS , с меткой y точно тогда, когда xySS  и xyQQ  . Деталь- но граф пар и его настройки рассматриваются в [5]. Сапунов С.В. «Искусственный интеллект» 4’2008 560 6С Эксперименты с помеченными графами Экспериментом с графом G относительно априорной информации I и цели C с использованием средств S назовем процесс, состоящий из трех этапов. Этап 1: пост- роение теста  MP на основе априорной информации I и с учетом цели C . Этап 2: получение порождаемых тестом P с использованием средств S экспериментальных данных W . Этап 3: вывод заключений о свойствах графа G на основе эксперимен- тальных данных W и априорной информации I . Определяющими при проведении эксперимента являются следующие факторы: свойства исследуемого графа; способ получения экспериментальных данных; цель эксперимента; априорная информация об исследуемом графе; способ вывода заклю- чений. Априорная информация об исследуемом графе – это класс графов, к которому принадлежит исследуемый. Этот класс может задаваться явно (перечислением графов), способом порождения его элементов из некоторого графа-эталона, набором свойств и параметров. Основное отличие экспериментов с графами от экспериментов с автоматами сос- тоит в методах и средствах S получения экспериментальных данных. Под средствами экспериментирования с графом мы будем подразумевать мобильных агентов (МА), блуждающих по графу и воспринимающих некоторую локальную информацию об окрестностях его вершин. В зависимости от априорной информации о графе, МА могут быть добавлены дополнительные возможности по распознаванию графа, такие как камни [6] или маркеры [7]. Эксперимент назовем диагностическим, если априори полностью известен граф G и МА установлен в произвольную начальную вершину этого графа, а целью экспе- римента является определение этой вершины, то есть отличение начальной вершины от всех других вершин. Допуская вольность речи, множество W также будем называть экспериментом с графом G . В этом смысле можно сказать, что эксперимент W по- рождается тестом P. Тесты, порождающие эксперименты, будем также называть диагностическими. Будем рассматривать следующие меры сложности экспериментов. Высотой теста P назовем величину  w Pw dmax  , кратностью P – величину P , объемом P – величину   Pw wd . Будем также рассматривать сложность построения теста и сложность проведения эксперимента. Под сложностью проведения эксперимента будем понимать его опера- ционные кратность и высоту. Операционной кратностью эксперимента назовем величину, равную, в зависимости от способа проведения эксперимента, либо количеству экземп- ляров МА, использованных при получении порожденных тестом P эксперименталь- ных данных W, либо количеству установок МА экспериментатором в начальную вершину исследуемого графа. Если используется только один экземпляр МА (одна установка), то эксперимент назовем простым. Операционной высотой эксперимента назовем наибольшую из длин путей, которые проходит каждый экземпляр МА по исследуемому графу в ходе эксперимента (в работах Г. Дудека [3] аналогичный параметр назван механической сложностью). Диагностические эксперименты Из определения диагностического эксперимента следует, что он осуществля- ется посредством прохождения МА некоторого связанного с тестом P множества путей по графу G из вершины g . Будем полагать, что, находясь в любой вершине Определение положения мобильного робота в топологической среде «Штучний інтелект» 4’2008 561 6С Gg  , МА воспринимает множество слов   h k LMhOb  , где  MM k явля- ется множеством всех слов длины не больше k в алфавите меток M, и вычисляет множество слов    hObMLMhOb k h k   . При 1k полагаем, что МА восприни- мает только метку текущей вершины. Таким образом, проходя путь lgg 1 в графе G , МА воспринимает множество слов           l i iil gObggggOb 1 11     и вычис- ляет множество слов           l i iil gObggggOb 1 11     . В дальнейшем, если не оговорено противное, будем считать, что 2k . Пусть Mw . Обозначим через  wg множество всех путей из вершины g , которые помечены словом w . По произвольному множеству  MP и Gg  постро- им пару   ggg WWW ~,~~ , где       Pw gg wObW    ~ и       Pw gg wObW    ~ , а  P является замыканием множества P по всем непустым начальным отрезкам слов из P . Экспери- ментом W с графом G , порожденным тестом P , назовем семейство   GggW  ~ . Экспе- римент W назовем диагностическим точно тогда, когда для любых вершин Ghg , из hg  вытекает hg WW ~~  , то есть   hg WW ~~ или   hg WW ~~ . В этом случае тест P также назовем диагностическим. Очевидно, что если граф G не приведен, то диаг- ностический эксперимент с ним невозможен. Действительно, если   hg, , то вер- шины Ghg , по определению неотличимы никаким словом из M . Если граф G приведен, то существует k такое, что k h k g LL  для всех hg  , Ghg , . Тогда  Gg k gLP   является диагностическим тестом для G , поскольку порожденный P эксперимент W является диагностическим экспериментом с графом G , так как hg LWLW  , то есть hg WW ~~  для всех hg  . Поэтому в дальнейшем, если не оговорено против- ное, будем считать, что все рассматриваемые графы приведены. Следующая теорема описывает класс диагностических тестов, определяемых иден- тификаторами вершин графа G . Рассмотрим множество слов  Gg gWP   , где gW является некоторым идентификатором вершины Gg . Очевидно, что для любых различных вершин Ghg , выполняется hg LPLP  . Действительно, так как PWg  , то по определению идентификатора hggg LWLW  , а следовательно, hg LPLP  . Таким образом, справедливо следующее утверждение. Теорема 1. Множество слов  Gg gWP   является диагностическим тестом для графа G при любом семействе идентификаторов   GggW  . Эта теорема дает метод построения диагностических тестов для помеченных гра- фов различных типов. Опишем подробно каждый этап диагностического эксперимента. Для построения теста P воспользуемся настроенным графом пар   FIT DDG ,,D [5], у которого множество ID состоит из всех вершин   1, DQg  , где Gg ,   Qg  и 1Q , а множество FD состоит из всех вершин   1, DQS  , где Сапунов С.В. «Искусственный интеллект» 4’2008 562 6С S или Q . Ясно, что  2nODI  , 1DDT  и  n T OD 22 . Для каждой вер- шины    IDQg , найдем кратчайшее слово w , такое, что    FDwQg , . Ясно, что множество P таких слов, выбранных по одному для каждой вершины из ID , явля- ется объединением идентификаторов всех вершин графа G и по теореме 1 является диагностическим тестом для этого графа. Очевидно, что кратность теста P равна  2nO , его высота не превосходит n22 [8], а его объем равен  nnO 22 2 . Для построения теста P достаточно (при использовании известных алгоритмов обхода графа [8])  nnO 42 2 шагов. Для построенного теста P с каждой вершиной Gg свяжем его разбиение  g на два класса gg LPP  и gg LPP  . Ясно, что для построения семейства    Ggg  достаточно  nnO 43 2 шагов. Далее МА помещается в произвольную неизвестную ему вершину h графа G . Целью второго этапа эксперимента является построение раз- биения  h путем перемещения МА по графу G . Полагаем вначале, что  hP и  hP . МА считывает метку  h и строит разбиение теста P на классы   whwwP  \| и PPP  . Если P , то искомое разбиение  h найдено и  hP , а PPh  . В противном случае, пока P , МА произвольно выбирает слово Pw  и последовательно для каждого начального отрезка iw слова w , где i пробегает все значения от 1 до  wd , проверяет наличие пути в графе G с меткой iw , исходящего из h . Если такой путь существует, то МА вычисляет  iwhOb  и все слова Pv  , для которых некоторое слово из множества  ii whObw  является начальным отрезком слова v , помещает в P  и удаляет из P . Если при этом началь- ный отрезок 1iw слова w находится в  ii whObw  , то слово w удаляется из P, помещается в P  и его исследование оканчивается. Если  wi d , то w помещается в  hP , удаляется из P и его исследование оканчивается. Поскольку при каждой ите- рации цикла из P удаляется по крайней мере одно слово, то этот алгоритм всегда завершается и при P получаем разбиение  h теста P на два класса  hP и PPh  . В наихудшем случае алгоритм построения  h требует проверки всех слов из P . Сле- довательно, сложность такого построения равна объему P , то есть равна  nnO 22 2 . Далее, на третьем этапе эксперимента, построенное экспериментально разбиение  h сравнивается со всеми разбиениями из семейства    Ggg  . Если для некоторого  g выполняется    hg   , то hg  и эксперимент окончен. Из правил построения семейства    Ggg  и разбиения  h следует, что последнее равенство всегда дости- гается. Рассмотрим свойства этого алгоритма. Поскольку, в общем случае, тест P кратный, то при выполнении второго этапа эксперимента предполагается, что или МА перед началом анализа слова Pw  переносится экспериментатором в началь- ную вершину h , или в h помещается новый экземпляр МА. Таким образом, для теста P кратности k и данной стратегии проведения диагностического эксперимента операционная кратность диагностического эксперимента не превосходит k , а опера- ционная высота диагностического эксперимента равна высоте теста P. Определение положения мобильного робота в топологической среде «Штучний інтелект» 4’2008 563 6С Покажем, что для частных случаев помеченных графов построение диагностичес- кого теста может быть упрощено. Пусть G является D-орграфом. Тогда  2nODD IT  [8]. Для построения теста P достаточно  6nO шагов. Очевидно, что кратность этого теста равна  2nO , а его высота не превосходит 1mn [7]. Объем теста P равен  3nO . Покажем, что для SD-графов существуют и другие стратегии проведения диаг- ностического эксперимента, отличные от описанной выше. Рассмотрим стратегию, в которой при такой проверке возврат в начальную вершину не требуется. Прежде, чем приступить к изложению этой стратегии, проведем дополнительные построения. Пусть G является приведенным максимальным SD-графом. Для каждой вер- шины Gg построим следующим способом позитивный идентификатор. Восполь- зуемся настроенным графом пар  FIT DD ,,D , у которого множество ID состоит из всех вершин    1, DQg  , где 1Q и  gQ  , множество FD состоит из всех вершин    1, Dh  , где Gh . Ясно, что IF DD  , 1 mnDI , nDF  и nnDT  2 . С целью упрощения этого графа удалим все дуги, исходящие из его финальных вершин. Для каждой вершины    IDQg , найдем кратчайшее слово w , такое, что    FDwQg , . Множество таких слов, выбранных по одному для каждой начальной вершины, обозначим через gW . Если  hQ  , где Gh , то слово w является крат- чайшим словом из множества hg LL  . Если Q , то  gw  и для любой вершины Gh , где    gh   , слово w является кратчайшим словом из множества hg LL  . Следовательно, gW является позитивным идентификатором вершины g , причем любое слово gWw не содержит подслов вида revuu  . Очевидно, что кратность gW не пре- восходит 1mn . Если граф G не связен, то по теореме [4] высота gW не превосхо- дит 12 n . Если граф G связен, то по теореме [4] высота gW не превосходит n3 . Для построения идентификатора gW достаточно (при использовании известных алгоритмов обхода графа [8])  4nO шагов. По теореме 1 множество  Gg gWP   , где gW – идентификатор вершины g , построенный приведенным выше способом, является диагностическим тестом для графа G . Ясно, что кратность такого теста не пре- восходит 2n . Если граф G не связен, то высота теста P не превосходит 12 n , а его объем равен  4nO . Если граф G связен, то высота этого теста не превосходит n3 , а его объем равен  3nO . Для построения теста P достаточно  5nO шагов. С тестом P свяжем помеченный лес  PF корневых деревьев и детерминизи- руем все деревья этого леса [4]. Обозначим через xP множество всех слов из P , начинающихся с метки Mx . Ясно, что xP является объединением позитивных иден- тификаторов всех вершин Gg , таких, что   xg  . Тогда корневое дерево  xPT является компонентой леса  PF . Для всех Mx с деревом  xPT свяжем множество вершин xGGx  . Обозначим корень дерева  xPT через xt . Для каждого слова xPw вершину wt x  дерева  xPT назовем выделенной. С каждой выделенной вершиной wtt x  свяжем множество    gLwgtG  \| . Множество всех выделенных вершин Сапунов С.В. «Искусственный интеллект» 4’2008 564 6С дерева  xPT обозначим через xT . Далее МА помещается в произвольную неиз- вестную ему вершину h графа G . Процесс получения экспериментальных данных заключается в проверке наличия в графе G путей, помеченных словами, которые являются метками путей из корня дерева   hPT  во все выделенные вершины этого дерева. МА считывает метку  h . Если   1hG , то вершина h определена и алгоритм оканчивает работу. В противном случае, пока   1hG , МА выполняет следующий итеративный алгоритм. Обозначим через  it вершину дерева   hPT , являющуюся начальной вершиной i-й итерации. При этом положим, что    htt 1 . Обозначим через iv слово, соответствующее пути по дереву   hPT из вершины  1it в вершину  it . При этом положим, что  hv 1 . На i-й итерации МА произвольно выбирает и удаляет из  hT некоторую выделенную вершину s . Пусть слово u соответствует кратчайшему пути по дереву   hPT из вершины  it в вершину s . МА последова- тельно для каждого начального отрезка ju слова u , где j пробегает все значения от 1 до  ud , проверяет, существует ли путь по графу G с меткой ju из вершины  ii vvhh 1 . Если такой путь не существует, то МА вычисляет для всех вершин  hTt  множество      sGtGtG  и полагает      sGGG hh   ,     1 1    j ii utt и 11   ji uv . На этом исследование слова u оканчивается. Если  uj d , то МА вычисляет для всех вершин  hTt  множество      sGtGtG  и полагает    sGG h  ,   st i 1 и uvi 1 . Далее МА удаляет из множества  hT все выделенные вершины, связан- ные с пустым множеством. Покажем, что по окончании работы алгоритма множество  hG всегда содержит единственную вершину. Предположим, что после некоторой итерации алгоритма   1hG и xT , то есть условие окончания алгоритма не достигнуто, но дальней- шее его выполнение невозможно. Пусть     GhG h  , где Gh  . Из построения теста  hP следует, что для любой вершины Gg  существует слово  hPv  , такое, что gh LLv  . Тогда вершина   vts h   является выделенной вершиной дерева   hPT ,  sGh и  sGg . Так как   hT , то вершина s была удалена из  hT в ходе некоторой итерации алгоритма. Рассмотрим, как могло произойти такое удаление. Если вершина s была удалена из  hT по причине того, что   sG , то на этой же итерации вершина h была удалена из  hG , что невозможно. Следовательно, на этой итерации МА побывал в вершине s и по этой причине эта вершина была удалена из  hT . Тогда на этой же итерации вершина g была удалена из  hG , так как  sGg . Из проведенных рассуждений следует, что при   hT выполняется    hG h  . Таким образом, данная стратегия объединяет два этапа диагностического экс- перимента – этап получения экспериментальных данных и этап вывода заключений. В наихудшем случае на каждой итерации алгоритма из  hG удаляется одна верши- на. Так как число вершин графа G с меткой равной  h не превосходит 1mn , Определение положения мобильного робота в топологической среде «Штучний інтелект» 4’2008 565 6С то алгоритм оканчивает свою работу не более чем за mn итераций. Так как граф G и дерево   hPT неориентированные, то получение экспериментальных данных в ходе диагностического эксперимента можно осуществить с использованием одного экземпляра МА, то есть диагностический эксперимент, при рассмотренной стратегии проведения, является простым вне зависимости от кратности диагностического теста. В теории экспериментов с конечными автоматами кратность эксперимента и кратность теста совпадают. В наихудшем случае МА проверяет mn  выделенных вершин дерева   hPT . Ясно, что расстояние от корня  ht этого дерева до любой из выделенных вершин не превосходит высоту теста P . Тогда, если граф G не связен, то операционная высота эксперимента равна  3nO , а если граф G связен, то опера- ционная высота эксперимента равна  2nO . Это коренным образом отличается от ре- зультатов теории экспериментов с автоматами, где И.К. Рысцовым [9] показано, что высота кратчайшего простого диагностического эксперимента равна       63 n O . Заключение Таким образом, в работе решена задача различения вершин топологической мо- дели операционной среды автономного мобильного робота (помеченного графа-карты). Решение заключается в построении и проведении диагностического эксперимента с графом, основанного на построении идентификаторов всех вершин исследуемого графа. Показано, что для детерминированных графов предложенный метод полиномиален. Литература 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.
id	nasplib_isofts_kiev_ua-123456789-7561
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-11-24T11:53:35Z
publishDate	2008
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Сапунов, С.В. 2010-04-02T11:36:17Z 2010-04-02T11:36:17Z 2008 Определение положения мобильного робота в топологической среде / С.В. Сапунов // Штучний інтелект. — 2008. — № 4. — С. 558-565. — Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7561 519.7 Рассматривается задача определения автономным мобильным роботом своего положения в среде, моделируемой графом с помеченными вершинами. Решение заключается в построении диагностического эксперимента – специального вида множества слов в алфавите меток вершин и способа его реализации на графе. Розглядається задача визначення автономним мобільним роботом свого місця знаходження у середовищі, яке моделюється за допомогою графа з позначеними вершинами. Розв’язок лежить у побудові діагностичного експерименту – спеціального виду множини слів у алфавіті відміток та способу його реалізації на графі. 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. ru Інститут проблем штучного інтелекту МОН України та НАН України Управление и информационное обеспечение мехатронных и робототехнических систем Определение положения мобильного робота в топологической среде Визначення місця знаходження мобільного робота в топологічному середовищі Mobile Robot Self Location on Topological Environment Article published earlier
spellingShingle	Определение положения мобильного робота в топологической среде Сапунов, С.В. Управление и информационное обеспечение мехатронных и робототехнических систем
title	Определение положения мобильного робота в топологической среде
title_alt	Визначення місця знаходження мобільного робота в топологічному середовищі Mobile Robot Self Location on Topological Environment
title_full	Определение положения мобильного робота в топологической среде
title_fullStr	Определение положения мобильного робота в топологической среде
title_full_unstemmed	Определение положения мобильного робота в топологической среде
title_short	Определение положения мобильного робота в топологической среде
title_sort	определение положения мобильного робота в топологической среде
topic	Управление и информационное обеспечение мехатронных и робототехнических систем
topic_facet	Управление и информационное обеспечение мехатронных и робототехнических систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/7561
work_keys_str_mv	AT sapunovsv opredeleniepoloženiâmobilʹnogorobotavtopologičeskoisrede AT sapunovsv viznačennâmíscâznahodžennâmobílʹnogorobotavtopologíčnomuseredoviŝí AT sapunovsv mobilerobotselflocationontopologicalenvironment

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

Institution

Similar Items