О самолокализации мобильного агента с использованием топологических свойств среды
Аннотация
В качестве топологической модели операционной среды рассматриваются конечные неориентированные графы. Вершины этих графов заранее помечены, и мобильный агент (МА) не меняет эти метки. Рассматривается задача определения МА своего положения в среде. Эта задача относится к проблематике взаимодействия управляющей и управляемой систем, являющейся классической для теоретической кибернетики [1 2]. В настоящее время эта проблема актуальна в связи с задачами навигации автономных мобильных роботов [3].
Конечным графом с помеченными вершинами (помеченным графом) назовем четверку G = (V, Е, М, fi), где V, Е, – конечные множества вершин, ребер и меток соответственно;cц : G —>• М – сюръективная функция разметки. Помеченный неорграф назовем сильно детерминированным (СД-графом), если в замкнутой окрестности любой его вершины все вершины помечены различно. Языком Ьд вершины д назовем множество всех слов, порожденных этой вершиной, т. е. последовательностей меток вершин, лежащих на всевозможных путях с началом в вершине д. Будем говорить, что вершины g,h E V е-неотличимы, если Lg = L^. Лингвистическим идентификатором (ЛИ) вершины д Е V назовем конечное множество слов Wg С М+, таких, что для любой вершины h E V равенство Wg Г) Lg = Wg П Lh выполняется тогда и только тогда, когда д = h. Через Sg обозначим подграф графа G, порожденный всеми вершинами, достижимыми из вершины д Е V. Будем говорить, что вершины g,h E V с-неотличимы, если Sg = S^. Пусть Gg и Н^ являются инициально-связными помеченными графами с выделенными вершинами д и h соответственно. Обозначим через Gg П Н^ наибольший связный подграф G' С. Gg, содержащий выделенную вершину д и изоморфно вложимый в Н^ с отображением вершины д в вершину h. Топологическим идентификатором (ТИ) вершины д Е V назовем помеченный граф Dg, такой, что для любой вершины h Е V изоморфизм Dg П Sg = Dg П Sh существует тогда и только тогда, когда д = h. Показано, что о С е, причем обратное включение не выполняется. Предложены полиномиальные методы построения ЛИ и ТИ вершин помеченных графов. Показано, что гомоморфный образ растущего помеченного дерева, соответствующего ЛИ вершины д Е V, является ТИ этой вершины. Показано, что обратное утверждение в общем случае неверно.
Экспериментом с графом G относительно априорной информации, цели С и средств S назовем процесс, состоящий из трех этапов:
1) построение некоторого теста Р на основе и С;
2) получение мобильным агентом экспериментальных данных W на основе Р и S;
3) вывод заключений о свойствах графа на основе W и I. Априорная информация — это класс графов, которому принадлежит G. В качестве S выступают возможности МА перемещаться по ребрам графа от вершины к вершине, оставлять маркер в текущей вершине, а также обнаруживать и подбирать маркер в случае его нахождения в текущей вершине. Эксперимент назовем диагностическим (ДЭ), если априори полностью известен граф G, МА установлен в произвольную начальную вершину этого графа, и целью эксперимента является определение этой вершины, т. е. различение этой вершины от всех других вершин.
В работах [4, 5] авторами были предложены методы построения и реализации ДЭ с помеченными графами, основывающиеся на проверке е-эквивалентности вершин при помощи их ЛИ. В них в качестве теста Р берётся множество слов, являющееся объединением ЛИ всех вершин графа.
В данной работе в качестве теста Р используется помеченный граф, называемый далее диагностическим тестовым графом (ДТГ) и определяемый по следующим правилам: 1) отождествим все одинаково помеченные инициальные вершины ТИ Dg всех д Е V; 2) детерминизируем остовные деревья всех графов Dg, то есть многократно и исчерпывающе применим следующую операцию: если в множество преемников некоторой вершины попадают вершины с одинаковыми метками, то такие вершины отождествляются с заменой возникающих кратных дуг одной дугой.
Первый этап диагностического эксперимента состоит в построении ДТГ Р. На втором этапе получение экспериментальных данных заключается в том, что МА, стартуя из неизвестной ему вершины h графа G, проверяет наличие/отсутствие в G путей, совпадающих по разметке с путями обхода в ширину графа Р из его инициальной вершины. В зависимости от исхода каждой из этих проверок сокращается множество гипотетически возможных начальных вершин. По окончании работы алгоритма остается ровно одна такая вершина.
Показано, что для СД-графов временная сложность данного алгоритма проведения диагностического эксперимента полиномиальна от числа вершин исследуемого графа.
Литература
1. Кудрявцев В. Б., Алешин С В., Подколзин А. С Введение в теорию
автоматов. М.: Наука, 1985.
2. Капитонова Ю. В., Летичевский А. А.
Математическая теория
проектирования вычислительных систем. М.: Наука, 1988.
3. Dudek G. and Jenkin M. Computational
Principles of Mobile Robotics. Cambridge: Cambridge University Press,
2000.
4. Сапунов С. В. Определение положения робота в
топологической среде // Искусственный интеллект. 2008. Т. 4. С.
558–565.
5. Грунский И. С, Сапунов С В. Идентификация вершин
помеченных графов // Труды ИПММ НАН Украины. 2010. Т. 21. С. 86-97.