Прикладная дискретная математика. Приложение

УДК 519.7

И. С. Грунский

С.В. Сапунов

О самолокализации мобильного агента с использованием топологических свойств среды

Аннотация

В качестве топологической модели операционной среды рассматриваются конечные неориентированные графы. Вершины этих графов заранее помечены, и мобиль­ный агент (МА) не меняет эти метки. Рассматривается задача определения МА своего положения в среде. Эта задача относится к проблематике взаимодействия управляющей и управляемой систем, являющейся классической для теоретической кибернетики [1,2]. В настоящее время эта проблема актуальна в связи с задачами навигации автономных мобильных роботов [3].

Конечным графом с помеченными вершинами (помеченным графом) назовем чет­верку G = (V, Е, М, f_i), где V, Е, М – конечные множества вершин, ребер и меток со­ответственно; μ: G→М – сюръективная функция разметки. Помеченный неорграф назовем сильно детерминированным (СД-графом), если в замкнутой окрестности лю­бой его вершины все вершины помечены различно. Языком Lg вершины g назовем множество всех слов, порожденных этой вершиной, т. е. последовательностей меток вершин, лежащих на всевозможных путях с началом в вершине g. Будем говорить, что вершины g,h ∈ V ξ–неотличимы, если Lg = Lh. Лингвистическим идентифика­тором (ЛИ) вершины g ∈ V назовем конечное множество слов Wg ⊆ М⁺, таких, что для любой вершины h ∈ V равенство W_g ∩ L_g = W_g ∩ L_h выполняется тогда и только тогда, когда g = h. Через S_g обозначим подграф графа G, порожденный всеми вер­шинами, достижимыми из вершины g ∈ V. Будем говорить, что вершины g,h ∈ V σ–неотличимы, если S_g ≅ S_h. Пусть G_g и Н_h являются инициально-связными поме­ченными графами с выделенными вершинами д и h соответственно. Обозначим через G_g ∩ Н_h наибольший связный подграф G' С. G_g, содержащий выделенную вершину д и изоморфно вложимый в Н^ с отображением вершины д в вершину h. Топологическим идентификатором (ТИ) вершины g ∈ V назовем помеченный граф Dg, такой, что для любой вершины h ∈ V изоморфизм D_g ∩ S_g ≅ D_g ∩ S_h существует тогда и только тогда, когда g = h. Показано, что σ ⊆ ξ, причем обратное включение не выполняется. Предложены полиномиальные методы построения ЛИ и ТИ вершин помеченных графов. Показано, что гомоморфный образ растущего помеченного дерева, соответствующего ЛИ вершины g ∈ V, является ТИ этой вершины. Показано, что обратное утверждение в общем случае неверно.

Экспериментом с графом G относительно априорной информации I, цели С и средств S назовем процесс, состоящий из трех этапов: 

1) построение некоторого теста Р на основе I и С;

2) получение мобильным агентом экспериментальных данных W на основе Р и S;

3) вывод заключений о свойствах графа на основе W и I. Априорная информация – это класс графов, которому принадлежит G. В качестве S выступают возможности МА перемещаться по ребрам графа от вершины к вершине, оставлять маркер в текущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. Эксперимент назовем диагностическим (ДЭ), если априори полностью известен граф G, МА установлен в произвольную начальную вершину этого графа, и целью эксперимента является определение этой вершины, т. е. различение этой вершины от всех других вершин.

В работах [4, 5] авторами были предложены методы построения и реализации ДЭ с помеченными графами, основывающиеся на проверке ξ–эквивалентности вершин при помощи их ЛИ. В них в качестве теста Р берётся множество слов, являющееся объединением ЛИ всех вершин графа.

В данной работе в качестве теста Р используется помеченный граф, называемый далее диагностическим тестовым графом (ДТГ) и определяемый по следующим правилам: 1) отождествим все одинаково помеченные инициальные вершины ТИ D_g всех g ∈ V; 2) детерминизируем остовные деревья всех графов D_g, то есть многократ­но и исчерпывающе применим следующую операцию: если в множество преемников некоторой вершины попадают вершины с одинаковыми метками, то такие вершины отождествляются с заменой возникающих кратных дуг одной дугой.

Первый этап диагностического эксперимента состоит в построении ДТГ Р. На втором этапе получение экспериментальных данных заключается в том, что МА, стартуя из неизвестной ему вершины h графа G, проверяет наличие/отсутствие в G путей, совпадающих по разметке с путями обхода в ширину графа Р из его инициальной вершины. В зависимости от исхода каждой из этих проверок сокращается множество гипотетически возможных начальных вершин. По окончании работы алгоритма остается ровно одна такая вершина.

Показано, что для СД–графов временная сложность данного алгоритма проведения диагностического эксперимента полиномиальна от числа вершин исследуемого графа.

Литература

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

2. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычисли­тельных систем / Ю.В. Капитонова, А.А Летичевский – М.: Наука, 1988.

3. Dudek G. Computational Principles of Mobile Robotics / G. Dudek, M. Jenkin – Cambridge: Cambridge University Press, 2000.

4. Сапунов С.В. Определение положения робота в топологической среде / С.В. Сапунов // Искусственный интеллект. 2008. – т.4. – С. 558–565.

5. Грунский И.С Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды ИПММ НАН Украины. 2010. – т.21. – С. 86–97.

                                                                                                                                                   Надійшла до редакції 2011 р.