Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации

Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации

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

Full description

Saved in:
Bibliographic Details
Published in:Штучний інтелект
Date:2012
Main Authors: Грунский, И.С., Сапунов, С.В.
Format: Article
Language:Russian
Published: Інститут проблем штучного інтелекту МОН України та НАН України 2012
Subjects:
Интеллектуальные робототехнические системы
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/57751
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:Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2012. — № 4. — С. 420-428. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-57751
record_format dspace
spelling Грунский, И.С.
Сапунов, С.В.
2014-03-14T13:31:39Z
2014-03-14T13:31:39Z
2012
Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2012. — № 4. — С. 420-428. — Бібліогр.: 12 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/57751
519.7
Рассматривается задача построения автономным мобильным роботом топологической модели своей операционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. В работе предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из робота-супервизора и робота-исследователя.
Розглянуто задачу побудови автономним мобільним агентом топологічної моделі свого операційного середовища. Модель середовища є зв’язним неорієнтованим графом з позначеними вершинами. В статті запропоновано поліноміальний алгоритм відновлення і розмітки графа середовища для колективу з робота-супервізора і робота-дослідника.
The problem of robotic exploration of graph-like operating environment is considered. The environment is defined as simple connected undirected vertex labeled graph. In the article, polynomial time graph reconstruction and vertex labeling algorithm for collective of robot-explorer and robot-supervisor is proposed.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Штучний інтелект
Интеллектуальные робототехнические системы
Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
Відновлення графа операційного середовища мобільного робота шляхом позначення його вершин, яке сприяє подальшій навігації
Reconstruction of the Graph of Operating Environment of Mobile Robot by Vertex Labeling Sufficient for Further Navigation
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
spellingShingle Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
Грунский, И.С.
Сапунов, С.В.
Интеллектуальные робототехнические системы
title_short Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
title_full Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
title_fullStr Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
title_full_unstemmed Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
title_sort восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации
author Грунский, И.С.
Сапунов, С.В.
author_facet Грунский, И.С.
Сапунов, С.В.
topic Интеллектуальные робототехнические системы
topic_facet Интеллектуальные робототехнические системы
publishDate 2012
language Russian
container_title Штучний інтелект
publisher Інститут проблем штучного інтелекту МОН України та НАН України
format Article
title_alt Відновлення графа операційного середовища мобільного робота шляхом позначення його вершин, яке сприяє подальшій навігації
Reconstruction of the Graph of Operating Environment of Mobile Robot by Vertex Labeling Sufficient for Further Navigation
description Рассматривается задача построения автономным мобильным роботом топологической модели своей операционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. В работе предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из робота-супервизора и робота-исследователя. Розглянуто задачу побудови автономним мобільним агентом топологічної моделі свого операційного середовища. Модель середовища є зв’язним неорієнтованим графом з позначеними вершинами. В статті запропоновано поліноміальний алгоритм відновлення і розмітки графа середовища для колективу з робота-супервізора і робота-дослідника. The problem of robotic exploration of graph-like operating environment is considered. The environment is defined as simple connected undirected vertex labeled graph. In the article, polynomial time graph reconstruction and vertex labeling algorithm for collective of robot-explorer and robot-supervisor is proposed.
issn 1561-5359
url https://nasplib.isofts.kiev.ua/handle/123456789/57751
citation_txt Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации / И.С. Грунский, С.В. Сапунов // Штучний інтелект. — 2012. — № 4. — С. 420-428. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv AT grunskiiis vosstanovleniegrafaoperacionnoisredymobilʹnogorobotaputemrazmetkiveršinprigodnoidlâdalʹneišeinavigacii
AT sapunovsv vosstanovleniegrafaoperacionnoisredymobilʹnogorobotaputemrazmetkiveršinprigodnoidlâdalʹneišeinavigacii
AT grunskiiis vídnovlennâgrafaoperacíinogoseredoviŝamobílʹnogorobotašlâhompoznačennâiogoveršinâkespriâêpodalʹšíinavígacíí
AT sapunovsv vídnovlennâgrafaoperacíinogoseredoviŝamobílʹnogorobotašlâhompoznačennâiogoveršinâkespriâêpodalʹšíinavígacíí
AT grunskiiis reconstructionofthegraphofoperatingenvironmentofmobilerobotbyvertexlabelingsufficientforfurthernavigation
AT sapunovsv reconstructionofthegraphofoperatingenvironmentofmobilerobotbyvertexlabelingsufficientforfurthernavigation
first_indexed 2025-11-25T21:05:34Z
last_indexed 2025-11-25T21:05:34Z
_version_ 1850544894005739520
fulltext «Искусственный интеллект» 4’2012 420 5Г УДК 519.7 И.С. Грунский, С.В. Сапунов Донецкий национальный технический университет Украина, 83001, г. Донецк, ул. Артема, 58 Институт прикладной математики и механики НАН Украины, г. Донецк Украина, 83114, г. Донецк, ул. Розы Люксембург, 74 Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации I.S. Grunsky, S.V. Sapunov Donetsk National Technical University Ukraine, 83001, c. Donetsk, Artema st., 58 Institute of Applied Mathematics and mechanics of NAS of Ukraine, Donetsk Ukraine, 83114, c. Donetsk, Rozy Luxemburg st., 74 Reconstruction of the Graph of Operating Environment of Mobile Robot by Vertex Labeling Sufficient for Further Navigation І.С. Грунський, С.В. Сапунов Донецький національний технічний університет Україна, 83001, м. Донецьк, вул. Артема 58 Інститут прикладної математики і механіки НАН України, м. Донецьк Україна, 83114, м. Донецьк, вул. Рози Люксембург, 74 Відновлення графа операційного середовища мобільного робота шляхом позначення його вершин, яке сприяє подальшій навігації Рассматривается задача построения автономным мобильным роботом топологической модели своей опера- ционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. В работе предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из робота-супервизора и робота-исследователя. Ключевые слова: мобильный робот, топологическая модель среды, восстановление графа. The problem of robotic exploration of graph-like operating environment is considered. The environment is defined as simple connected undirected vertex labeled graph. In the article, polynomial time graph reconstruction and vertex labeling algorithm for collective of robot-explorer and robot-supervisor is proposed. Key Words: mobile robot, topological model of environment, graph reconstruction. Розглянуто задачу побудови автономним мобільним агентом топологічної моделі свого операційного середовища. Модель середовища є зв’язним неорієнтованим графом з позначеними вершинами. В статті запропоновано поліноміальний алгоритм відновлення і розмітки графа середовища для колективу з робота-супервізора і робота-дослідника. Ключові слова: мобільний робот, топологічна модель середовища, відновлення графа. Восстановление графа операционной среды мобильного робота... «Штучний інтелект» 4’2012 421 5Г Введение Актуальными проблемами в области разработки информационного обеспечения мобильных роботов являются проблемы представления операционной среды и раз- работка методов навигации в этой среде [1]. К моделированию таких сред определилось два подхода: метрический, использующий геометрические свойства среды, и топологи- ческий, использующий описания связей между различными областями среды [2]. Топо- логические модели представляют собой ориентированные или неориентированные графы с размеченными различными способами вершинами и/или дугами. Такой подход позволяет применять для решения конкретных задач навигации широкий набор эффек- тивных алгоритмов теории графов [3]. В данной работе под навигацией понимается перемещение мобильного агента (робота, поисковой программы и т.п.) из текущей области его операционной среды в заданную ее область. Полагаем, что в решении задач навигации участвует коллектив, состоящий из агента-супервизора (АС) и транспортного агента (АТ). АС выраба- тывает описание пути из текущего местоположения АТ в область назначения и пере- дает его АТ. Используя это описание, АТ самостоятельно проходит путь в среде. При планировании навигации возникают три взаимосвязанные фундаменталь- ные задачи: задача построения модели неизвестной среды (exploration), задача опре- деления положения робота в известной среде (robot self-location) и задача проверки соответствия неизвестной среды и ее модели (карты) (map validation) [4]. Заметим, что эти задачи имеют соответствующие аналоги в теории автоматов [5]. В данной работе рассматривается построение коллективом агентов модели не- известной им среды. Коллектив состоит из агента-супервизора (АС) и агента-иссле- дователя (АИ). АИ перемещается по среде и воспринимает локальную информацию, достаточную для сопоставления областям среды элементов модели. Если восприни- маемой информации не достаточно для такого сопоставления, то АИ изменяет среду путем установки искусственных ориентиров. АИ передает информацию о среде и произведенных им ее изменениях АС, который и строить модель среды. По этой модели АС создает описания путей для АТ. В качестве модели рабочей среды мобильных агентов мы будем рассматривать конечные простые связные неориентированные графы, вершины которых могут быть помечены метками из некоторого множества меток (т.н. помеченные графы). Такая модель возникает, например, при качественной навигации мобильных роботов [6], [7]. Целью данной работы является разработка алгоритма построения коллекти- вом из АС и АИ топологической модели неизвестной ему среды в условиях, когда естественные (т.е. являющиеся частью среды) ориентиры недоступны АИ. В результате выполнения алгоритма в областях среды устанавливаются искусственные ориентиры так, что АТ может осуществлять навигацию по путям, описываемым цепочками этих ориентиров. Постановка задачи АИ установлен в произвольную вершину неизвестного ему связного простого неорграфа. Все вершины графа не помечены (или, что равносильно, помечены одной и той же меткой). АИ наблюдает 3-окрестность текущей вершины (т.е. все вершины, удаленные от текущей на расстояние не более чем в 3 вершины). Он может пере- мещаться по ребрам между смежными вершинами. АИ также может метить текущую вершину меткой (искусственным ориентиром) из некоторого множества меток. При Грунский И.С., Сапунов С.В. «Искусственный интеллект» 4’2012 422 5Г А этом он не может менять метку, которую сам установил. АИ передает АС разметку наблюдаемой им локальной окрестности и имя установленной им метки. АС передает АИ последовательность меток вершин, описывающую путь по графу. Требуется разработать алгоритм перемещений АИ по графу и разметки прой- денных вершин, который позволяет восстановить граф. Причем, полученная разметка должна позволить АТ, наблюдающему 2-окрестность текущей вершины, осуществ- лять навигацию по графу. К настоящему времени известно довольно много методов восстановления гра- фов [8]. Однако эти методы, как правило, предполагают разметку всех вершин графа одной и той же меткой, что неприемлемо для последующей навигации. Тривиаль- ным методом решения поставленной задачи является восстановление графа с размет- кой каждой его вершины уникальной меткой. В работе предложен алгоритм, в котором на основе анализа структуры графа уменьшается число различных меток. Основные определения Неопределяемые понятия общеизвестны и их можно найти в [9]. Помеченным графом назовем конечный простой связный неориентированный граф с помеченными вершинами  ,,, MEVG  , где V – множество вершин, nV  , E – множество ребер (т.е. неупорядоченных пар вершин), M – множество меток, MV : – сюръективная функция разметки вершин. Путем в графе G назовем последовательность вершин kggp 1 такую, что   Egg ii 1, , 1,,1  ki  . Число Nk назовем длиной пути p . Кратчайший путь из вершины g в вершину h называется расстоянием между этими вершинами. Меткой  p пути p назовем слово    kggw  1 в алфавите меток M . Будем говорить, что слово w опреде- ляется вершиной 1g . Длину слова w будем обозначать через  wd . Начальный отрезок или префикс длины l слова w будем обозначать через  wlpre . Конечный отрезок или суффикс длины l слова w будем обозначать через  wlsuf . Инверсией слова w     kgg  1 назовем слово    1 1 ggw k   . Множество gL всех слов Mw , определяемых вершиной Vg , будем называть языком этой вершины. Граф G будем называть приведенным, если для любых вершин Vhg , из hg  следует hg LL  . Определим на M частичную операцию  композиции слов. Пусть Mba , , Mvw, , тогда wavavwa  и bvwa  не определено, если ba  . Введем операцию VMV 2:   соотношением: для любой вершины Vg и любого слова Mw через wg  обозначим множество всех вершин Vh таких, что существует путь p , соединяющий вершины g и h , и   wp  . Ясно, что если слово gLw , то 0wg и 0wg в противном случае. Под k-окрестностью )2( g вершины Vg будем понимать множество всех вер- шин, находящихся от g на расстоянии не превосходящем Nk . Число k назовем размером окрестности )2( g .Таким образом, имеем: }{)1( gg  , }),(|{)1()2( Ehghgg  ,      EshEhghsgg  ,,|)2()3( и т.д. Восстановление графа операционной среды мобильного робота... «Штучний інтелект» 4’2012 423 5Г АИ, находясь в вершине Vg , наблюдает метки всех вершин из  k g для неко- торого Nk . Основываясь на анализе «увиденного», агент принимает решение о перемещении в одну из смежных вершин. Будем считать, что для перемещения из вершины g в смежную ей вершину h АИ должен наблюдать h и отличать ее от всех вершин из  k g . Тогда для перемещений по графу АИ должен отличать вершины из 2-окрестности текущей вершины от других наблюдаемых им вершин. АИ может либо произвольно блуждать по графу, либо следовать по заданному пути из текущей вершины. АИ имеет следующие возможности по временному или постоянному из- менению разметки вершин. Он может пометить непомеченную вершину меткой из множества M . Он также может устанавливать и подбирать в текущей вершине пере- носные маркеры (т.н. камни). В качестве меры сложности агента будем рассматривать размер наблюдаемой им окрестности текущей вершины. Через Ak обозначим агента, который наблюдает k-окрестность текущей вершины. Заметим, что А2 является простейшим агентом, так как агент А1 не может осуществлять целенаправленное перемещение. Детерминированная разметка вершин Обоснуем выбор специальной разметки вершин графа, позволяющей агенту А2 осуществлять навигацию. Функцию разметки MV : будем называть детерминированной или Д-раз- меткой, если для любой вершины Vg и любых вершин  2, gts  из ts  следует    ts   . Помеченный граф G с детерминированной функцией разметки будем называть детерминированным или Д-графом. Рассмотрим свойства Д-графов. Лемма 1. Помеченный граф G является Д-графом тогда и только тогда, когда для любой вершины Vg и любого слова Mw выполняется      случае. противном в 0, , если ,1 gLw wg (1) Доказательство. Действительно, для всех слов длины 1 и 2 равенство (1) очевидно, а любое слово длины больше 2 единственным образом записывается в виде композиции своих двухбуквенных подслов. С другой стороны, из того, что для любой вершины Vg и любого слова Mw выполняется 1wg следует, что в  2 g нет одинаково помеченных вершин. Лемма доказана. Таким образом, Д-граф определяется или через локальные свойства его вер- шин, или через нелокальное свойство множества всех путей, определяемых каждой из вершин. Лемма 2. Для любых различных вершин Vhg , и любого слова hg LLw  расстояние между вершинами wg  и wh  не меньше 4. Доказательство. Пусть kxxw 1 , где Mxi  , ki 1 . Предположим, что расстояние между вершинами wgs  или wht  меньше 4. Пусть это расстояние равно 1, т.е. txxhxxgs kk   11 Тогда в окрестности  2 s окажутся две различ- ные вершины с одной и той же меткой 1kx , что невозможно по определению Д-графа. Грунский И.С., Сапунов С.В. «Искусственный интеллект» 4’2012 424 5Г А Следовательно, 1111   kk xxhxxg  . По индукции hg  , что невозможно. Пусть расстояние между вершинами s и t равно 2, то есть   Ets , . Тогда в окрестности  2 s находится вершина t с меткой    sy   , что невозможно по определению Д- графа. Пусть расстояние между вершинами s и t равно 3, то есть существует вершина Vq такая, что путь sqt является кратчайшим путем из s в t . Тогда  2, qts  и    ts   , что невозможно по определению Д-графа. Лемма доказана. Одной из центральных проблем, возникающих при навигации МА, является проблема самостоятельного определения агентом своего положения в среде (задача самолокализации агента) [2], [4]. В [10], [11] предложено решение задачи само- локализации для приведенных Д-графов. Следующее утверждение показывает, что на вершинах любого конечного связного простого неорграфа может быть построена такая Д-разметка, что полученный в результате Д-граф является приведенным, т.е. для него разрешима задача самолокализации. Лемма 3. Если в Д-графе G существует вершина с уникальной меткой, то G является приведенным графом. Доказательство. Будем говорить, что вершины Vhg , неотличимы, если hg LL  . Ясно, что отношение неотличимости является эквивалентностью на множе- стве V . Пусть BB , – некоторые классы неотличимости вершин и Bg . Пусть Bwg  . Покажем, что BB  . Если Bh , то из неотличимости g и h следует, что Bwh  . По определению Д-графа wgwh  при gh  . Поэтому BB  . Обозначим wgg  и whh  . Из очевидного неравенства 11   wgwh сле- дует BB  . Таким образом, если некоторый класс неотличимости одноэлементен, то и все классы неотличимости одноэлементны. Следовательно, Д-граф G является приведенным. Лемма доказана. Таким образом, если пометить произвольную вершину произвольного Д-графа уникальной меткой, то получим приведенный Д-граф. Теорема 1. Агент Ak может осуществлять навигацию на Д-графе с 3n тогда и только тогда, когда 2k . Доказательство. Покажем, что агент A2, находящийся в вершине g Д-графа G , получив от АС слово gLw , может переместиться из нее в вершину wgh  . Пусть   2wd . Тогда, по определению Д-графа, в  2 g находится единственная вершина с меткой  w1suf и этой вершиной является вершина h . A2 «видит», что эта вершина смежная вершине g и может переместиться в нее. Пусть   2wd . Тогда слово w единственным образом записывается в виде композиции lwww  21 двухбуквен- ных подслов iw ,   2iwd , li 1 . Из вершины g агент A2 переходит в вершину  2 gwg  . Из вершины iwg  он переходит в вершину  2 1 iwgiwg   , 11  li . Наконец, из вершины 1 lwg агент переходит в вершину  2 1 lwglwg , которая и является вершиной h . Заметим, что агент А1 не может пройти путь 21xx так как, на- ходясь в вершине с меткой 1x , агент не «знает» по какому ребру перейти в вершину с меткой 2x . Теорема доказана. Восстановление графа операционной среды мобильного робота... «Штучний інтелект» 4’2012 425 5Г Таким образом, Д-разметка графа является достаточным условием для того, чтобы простейший агент мог осуществлять навигацию. Рассмотрим проблему построения Д-разметки на графе. Если G является аци- клическим графом, т.е. деревом, то агент А2 может построить на нем Д-разметку, если агент «запоминает» метки пройденных путей. Покажем, что существует граф, который не может быть Д-размечен агентом А2. Рассмотрим пример на рис. 1. Рисунок 1 Пусть агент А2 уже выполнил Д-разметку трех вершин графа. Перейдя в непо- меченную вершину, он наблюдает вершину с меткой 3 и вершину без метки. Пред- положим, что А2 «запомнил» все установленные им метки. Тогда он не может ис- пользовать метки 2 и 3. Так как априори граф не известен А2, то, исходя из дос- тупной ему информации, агент пометит текущую вершину меткой 1 и, тем самым, нарушит детерминированность разметки. Заметим, что агент А3, находясь в той же вершине, «увидел» бы, что метку 1 нельзя использовать для ее разметки. Из леммы 2 следует, что вершины, удаленные друг от друга на расстояние не более чем 3 вер- шины, не должны иметь одинаковые метки. Таким образом, справедливо следующее утверждение. Теорема 2. Для Д-разметки произвольного графа агентом Ak достаточно, чтобы k превосходило 2. Д-разметка вершин графа коллективом агентов Из теоремы 2 следует, что для построения Д-разметки достаточно использовать агента А3. Построение минимальной Д-разметки на основе только лишь локальной информации о вершинах (т.е без знания всего графа) представляется невозможным в общем случае. Поэтому будем рассматривать «жадный» алгоритм решения этой за- дачи с помощью А3. В основу предлагаемого в работе метода восстановления графа положен метод обхода графа в ширину [12]. При этом для каждой вершины Vg в качестве имени используется метка пути в нее из начальной вершины по дереву обхода (этим объясняется выбор в пользу метода обхода в ширину: так как путь в любую вершину из начальной по дереву обхода имеет кратчайшую длину среди всех таких путей, то и длина имени этой вершины также кратчайшая). Зададим линейный порядок на множестве M . Без потери общности можно предположить, что NM  и, что перед началом работы алгоритма все вершины исследуемого графа помечены меткой 0. Грунский И.С., Сапунов С.В. «Искусственный интеллект» 4’2012 426 5Г А Для каждой вершины Vg хранятся ее имя )(gname , ее метка  g , множе- ство  gAl смежных с ней вершин и множество  gLl меток этих вершин. Для хра- нения множества имен вершин, окрестности которых еще не обработаны, использу- ется список T типа FIFO. Для хранения имен всех вершин используется множество W. Первоначально АИ устанавливается в неизвестную ему вершину s исследуемого графа G . АИ считывает метки вершин из )3( s , корректирует множество доступных для Д-разметки меток, метит s наименьшей из них и передает АС метку )(s . Если требу- ется получить приведенный граф, то метка )(s больше не используется. АС вычисляет имя )(sname (для начальной вершины )()( ssname  ) и добавляет его в T и W. Пусть на i-ой итерации АИ находится в некоторой уже помеченной им вершине Vg . Для всех вершин с меткой 0 из )2( g АИ выбирает любую из них, например t , и перемещается в нее. АИ считывает метки вершин из )3( t , корректирует множество доступных для Д-разметки меток, метит t наименьшей из них и передает АС метку )(t . АС добавляет )(t в )(gLl , вычисляет имя )(tname как конкатенацию )()( tgname  и добавляет его в T, W и )(gAl . Далее, АС добавляет )(gname и )(g в )(tAl и )(tLl соответственно. После этого АИ возвращается в вершину g . Окончив разметку )2( g , коллектив агентов приступает к проверке ребер, попе- речных дереву обхода. АИ считывает метки всех вершин из )2( g и передает АС мно- жество )( )2( g . Если  )(\)( )2( gLlg , то АС передает АИ произвольную метку из )(\)( )2( gLlg , например метку )(q вершины q . АИ переходит в q и оставляет в ней камень. АС находит в W имена всех вершин, которые имеют длину больше или равную длине )(gname и оканчиваются на )(q . Затем АС поочередно передает АИ метки путей в эти вершины по дереву обхода. АИ перемещается по этим путям до тех пор, пока не обнаруживает камень. АИ подбирает камень и переходит в вершину g . АС добавляет )(qname , )(q , )(gname , )(g в )(gAl , )(gLl , )(qAl , )(qLl соот- ветственно. Описанные выше действия выполняются до тех пор, пока в )(gLl не окажутся все вершины из 2-окрестности вершины g . Далее АС пытается извлечь имя вершины из списка T. Если он пуст, то все вершины графа G уже помечены и алгоритм оканчивает работу. В противном случае, АС извлекает из T имя очередной вершины, например h . По именам вершин g и h АС вычисляет метку пути из g в h по дереву обхода и передает ее АИ. АИ переме- щается по этому пути в вершину h и приступает к обработке ее 2-окрестности. С целью анализа предложенного метода, докажем следующее утверждение. Теорема 3. Коллектив из АС и АИ восстанавливает произвольный связный неорграф G путем Д-разметки его вершин за время )( 3nO . Доказательство. Покажем, что, по окончании работы алгоритма, у каждой вершины Vg в множестве  gAl содержатся все смежные g вершины графа G . Действительно, вершины из )2( g , смежные g в дереве обхода, попадают в  gAl при разметке ее окрестности, а вершины, соединенные с g поперечными дереву обхода ребрами, попадают в  gAl при обработке поперечных ребер. Таким образом, по окончании работы алгоритма полностью восстанавливаются списки смежности для всех вершин графа G . Восстановление графа операционной среды мобильного робота... «Штучний інтелект» 4’2012 427 5Г Каждая вершина графа G один раз помещается в очередь T и один раз извлекается из нее. Таким образом, для выполнения алгоритма достаточно )(nO итераций. Для раз- метки окрестности )2( g текущей вершины g достаточно )(nO шагов. Для отыскания по- перечных ребер, соединяющих вершину g с другими вершинами дерева обхода, достато- чно )( 2nO шагов: не более )(nO шагов на отыскание поперечных ребер и не более )(nO шагов на поиск по дереву обхода вершины помеченной камнем. Таким образом, вре- менная сложность Д-разметки графа коллективом из АС и АИ ограничена )( 3nO . Теорема доказана. Выводы В работе решена задача восстановления связного неорграфа мобильным агентом путем детерминированной разметки его вершин. Разработан алгоритм восстановления графа агентом, наблюдающим 3-окрестности посещаемых им вершин. Доказана коррек- тность алгоритма и найдена оценка его временной сложности. В дальнейшем пред- полагается исследовать влияние размера наблюдаемой агентом окрестности и объема используемой им памяти на способность агента решить задачу восстановления графа. Литература 1. Borenstein J. Navigation Mobile Robots: System and Techniques / Borenstein J., Everett B., Feng L. – A.K. Peters Ltd., Wellesley (MA), 1996. – 223 p. 2. Dudek G. Computational Principles of Mobile Robotics / Dudek G., Jenkin M. – Cambridge University Press, 2000. – 280 p. 3. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / Касья- нов В.Н., Евстигнеев В.А. – СПб.: БХВ-Петребург, 2003. – 1104 c. 4. Dudek G. Map validation and Robot Self-Location in a Graph-Like World / Dudek G., Jenkin M., Milios E., Wilkes D. // Robotics and Autonomous Systems. – 1997. – Vol. 22, № 2. – P.159-178. 5. Kohavi Z. Switching and finite automata theory / Kohavi Z., Jha N. – Cambridge University Press, 2010. – 617 p. 6. Levitt T. Qualitative navigation for mobile robot / T. Levitt, D.T. Lawton // Artificial Intelligence. – 1990. – Vol. 40. – P. 306-360. 7. Кирильченко А.А. Теоретические аспекты интерпретирующей навигации мобильного робота / Кирильченко А.А., Платонов А.К., Соколов С.М. // Препринт Института прикладной математики им. М.В. Келдыша РАН. – 2002. – № 5. 8. Голубев Д.В. Об обходе графов автоматами с одной нестираемой краской. // Интеллектуальные системы. – 1999. – Т. 4. – Вып. 1-2. – С. 243-272. 9. Хопкрофт Д.Э. Введение в теорию автоматов, языков и вычислений / Хопкрофт Д.Э., Мотвани Р., Ульман Д.Д. – М. : Изд. дом «Вильямс», 2002. – 528 с. 10. Грунский И.С. Идентификация вершин помеченных графов / Грунский И.С., Сапунов С.В. // Труды ИПММ НАНУ. – 2010. – Т. 21. – С. 86-97. 11. Грунский И.С. Диагностика местоположения мобильного робота на основе топологической информации о среде / Грунский И.С., Сапунов С.В. // Искусственный интеллект. – 2011. – № 2. – С. 15-25. 12. Кормен Т. Алгоритмы: построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р. – М. : МЦНМО, 2001. – 960 с. Literatura 1. Borenstein J. Navigation Mobile Robots: System and Techniques. A.K. Peters Ltd., Wellesley (MA), 1996. 223 p. 2. Dudek G. Computational Principles of Mobile Robotics. Cambridge University Press, 2000. 280 p. Грунский И.С., Сапунов С.В. «Искусственный интеллект» 4’2012 428 5Г А 3. Kasyanov V.N. Grafy v programmirovanii: obrabotka, vizualizacija i primenenie. SPb, BHV-Peterburg. 2003. 1104 p. 4. Dudek G. Robotics and Autonomous Systems. 1997. Vol. 22, № 2. P.159-178. 5. Kohavi Z. Switching and finite automata theory Cambridge University Press, 2010. 617 p. 6. Levitt T. Artificial Intelligence. 1990. Vol. 40. P. 306-360. 7. Kirilchenko A.A. Preprint Instituta prikladnoj matematiki im, M.V. Keldysha. RAN. 2002. № 5. 8. Golubev D.V. Intellektualnye sistemy. 1999. T. 4. Vyp. 1-2. S. 243-272. 9. Hopcroft J.E. Vvedenie v teoriju avtomatov, jazykov i vychislenij. Moscow: Izdatelskij dom “Viliams”. 2002.528 s. 10. Grunsky I.S. Transactions of IAMM NASU. 2010. Vol. 21. S.86-97. 11. Grunsky I.S. Iskusstvennyj intellect. 2011. №.2. S. 15-25. 12. Kormen T. Algoritmy: postroenie i analiz. Moscow: MCNMO. 2001. 960 p.. RESUME I.S. Grunsky, S.V. Sapunov Reconstruction of the Graph of Operating Environment of Mobile Robot by Vertex Labeling Sufficient for Further Navigation The problem of robotic exploration of graph-like operating environment is consi- dered. The problem is: an unknown environment modeled as finite simple connected undirected vertex labeled graph is given, formulate an exploration strategy for the robot, so that, after carrying out the actions specified by the strategy, the robot will have formed a representation of its environment sufficient for solving navigation tasks i.e. a map. The authors call vertex labeled graph deterministic if all vertices in neighborhood of each vertex have distinct labels. The sufficiency of deterministic graphs for solving navigation tasks is demonstrated. The authors propose polynomial time exploration algorithm for collective of robot- explorer and robot-supervisor. Robot-explorer traverses the graph, observes the local neighborhoods of the vertices and changes the environment by setting labels at the vertices in deterministic manner. Robot-explorer sends information about vertex labeling to robot- supervisor. Robot-supervisor forms a map of the environment based on this information. To solve the problem of determining when the robot-explorer has returned to a previously visited vertex during map building, the authors use portable marker as a part of exploration strategy. Статья поступила в редакцию 15.06.2012. .

Similar Items