On mobile agent self-location using topological properties of environment.pdf В качестве топологической модели операционной среды рассматриваются конеч-ные неориентированные графы. Вершины этих графов заранее помечены, и мобиль-ный агент (МА) не меняет эти метки. Рассматривается задача определения МА своегоположения в среде. Эта задача относится к проблематике взаимодействия управляю-щей и управляемой систем, являющейся классической для теоретической кибернети-ки [1, 2]. В настоящее время эта проблема актуальна в связи с задачами навигацииавтономных мобильных роботов [3].Конечным графом с помеченными вершинами (помеченным графом) назовем чет-верку G = (V, E, M, где V, E, M - конечные множества вершин, ребер и меток со-ответственно; ^ : G ^ M - сюръективная функция разметки. Помеченный неорграфназовем сильно детерминированным (СД-графом), если в замкнутой окрестности лю-бой его вершины все вершины помечены различно. Языком Lg вершины g назовеммножество всех слов, порожденных этой вершиной, т. е. последовательностей метоквершин, лежащих на всевозможных путях с началом в вершине g. Будем говорить,что вершины g, h Е V е-неотличимы, если Lg = Lh. Лингвистическим идентифика-тором (ЛИ) вершины g Е V назовем конечное множество слов Wg С M +, таких, чтодля любой вершины h Е V равенство Wg П Lg = Wg П Lh выполняется тогда и толькотогда, когда g = h. Через Sg обозначим подграф графа G, порожденный всеми вер-шинами, достижимыми из вершины g Е V. Будем говорить, что вершины g, h Е Vа-неотличимы, если Sg = Sh. Пусть Gg и Hh являются инициально-связными поме-ченными графами с выделенными вершинами g и h соответственно. Обозначим черезGg П Hh наибольший связный подграф Gg С Gg, содержащий выделенную вершину g иизоморфно вложимый в Hh с отображением вершины g в вершину h. Топологическимидентификатором (ТИ) вершины g Е V назовем помеченный граф Dg, такой, что длялюбой вершины h Е V изоморфизм Dg П Sg = Dg П Sh существует тогда и только тогда,когда g = h. Показано, что а С е, причем обратное включение не выполняется. Пред-ложены полиномиальные методы построения ЛИ и ТИ вершин помеченных графов.Показано, что гомоморфный образ растущего помеченного дерева, соответствующегоЛИ вершины g Е V, является ТИ этой вершины. Показано, что обратное утверждениев общем случае неверно.Экспериментом с графом G относительно априорной информации I, цели C исредств S назовем процесс, состоящий из трех этапов: 1) построение некоторого те-ста P на основе I и C; 2) получение мобильным агентом экспериментальных данных Wна основе P и S; 3) вывод заключений о свойствах графа на основе W и I. Априорнаяинформация - это класс графов, которому принадлежит G. В качестве S выступаютвозможности МА перемещаться по ребрам графа от вершины к вершине, оставлятьмаркер в текущей вершине, а также обнаруживать и подбирать маркер в случае егонахождения в текущей вершине. Эксперимент назовем диагностическим (ДЭ), еслиаприори полностью известен граф G, МА установлен в произвольную начальную вер-шину этого графа, и целью эксперимента является определение этой вершины, т. е.различение этой вершины от всех других вершин.В работах [4, 5] авторами были предложены методы построения и реализации ДЭс помеченными графами, основывающиеся на проверке е-эквивалентности вершин припомощи их ЛИ. В них в качестве теста P берётся множество слов, являющееся объ-единением ЛИ всех вершин графа.В данной работе в качестве теста P используется помеченный граф, называемыйдалее диагностическим тестовым графом (ДТГ) и определяемый по следующим пра-вилам: 1) отождествим все одинаково помеченные инициальные вершины ТИ Dg всехg Е V; 2) детерминизируем остовные деревья всех графов Dg, то есть многократ-но и исчерпывающе применим следующую операцию: если в множество преемниковнекоторой вершины попадают вершины с одинаковыми метками, то такие вершиныотождествляются с заменой возникающих кратных дуг одной дугой.Первый этап диагностического эксперимента состоит в построении ДТГ P. На вто-ром этапе получение экспериментальных данных заключается в том, что МА, стартуяиз неизвестной ему вершины h графа G, проверяет наличие/отсутствие в G путей,совпадающих по разметке с путями обхода в ширину графа P из его инициальнойвершины. В зависимости от исхода каждой из этих проверок сокращается множествогипотетически возможных начальных вершин. По окончании работы алгоритма оста-ется ровно одна такая вершина.Показано, что для СД-графов временная сложность данного алгоритма проведениядиагностического эксперимента полиномиальна от числа вершин исследуемого графа.

Скачать электронную версию публикации