Бондаренко А.В. МЕТОД САМОЛОКАЛИЗАЦИИ АГЕНТА В РАБОЧЕЙ СРЕДЕ
Бондаренко Антон Владимирович
Институт информатики и искусственного интеллекта ДонНТУ
МЕТОД САМОЛОКАЛИЗАЦИИ АГЕНТА В РАБОЧЕЙ СРЕДЕ
Разработка и анализ метода автоматизированной самолокализации.
Ключевые слова: самолокализация, детерминированный граф, различие вершин, раскраска.
Розробка та аналіз методу автоматизованої самолокалізації.
Ключові слова: самолокалізація, детермінований граф, відмінність вершин, розфарбовування.
Development and analysis of method of the automated selflocalization.
Keywords: selflocalization, determined count, distinction of tops, coloration.
Задачи, связанные с анализом различных сред с помощью блуждающих по ним агентов (мобильных роботов, автоматов, поисковых программ и т.п.) относятся к категории традиционных задач искусственного интеллекта. Агент перемещается по среде, получая при этом некоторую локальную информацию о среде, на основе которой, исходя из некоторой априорной информации, решает поставленные перед ним задачи: например, обходит среду и делает заключения о её свойствах [1].
В настоящее время несколько подходов к проблеме анализа графов блуждающим агентом:
1) среда рассматривается как конечный инициальный автомат без выхода, что позволяет использовать методы, разработанные в рамках теории конечных автоматов;
2) среда рассматривается как конечный неориентированный граф с помеченными концами ребер;
3) среда рассматривается как граф с помеченными вершинами [6].
Третий подход взят за основу в разработке метода самолокализации, предложенном в данной работе.
Задача самолокализации состоит в том, что агент в результате движений по среде должен определить первоначальное положение в среде. Наш подход заключается в том, что задача самолокализации решается в 4 этапа:
1) построение различающего графа 
, у которого V - множество вершин, каждая из которых представляет собой пару
из исходного графа G, для которых
. При этом в множество V добавляются пары вида 
, такие, что в графе G существует вершина 
, и смежная с ней 
, имеющая отметку m, причем вершина не имеет смежной вершины с отметкой m. Вершину такого вида назовем различающей [3];
2) нахождение в графе D кратчайших маршрутов от каждой вершины вида до каждой различающей вершины с записью полученных маршрутов в список маршрутов S;
3) построение матрицы P, столбцами которой являются вершины из множества вершин V исходного графа G, строками - маршруты из полученного на предыдущем шаге списка S, 
- вершина, в которую попадает агент, прошедший из вершины по маршруту 
, либо ноль, если агент не сможет пройти из вершины по маршруту 
[2];
4) построение бинарного дерева принятия решения R, листьями которого являются вершины из множества вершин V графа G, вершинами - маршруты из списка маршрутов S. Возможность перехода по маршруту, определенная матрицей , определяет направление движения по дереву [4].
Построение различающего графа осуществляется в два этапа: генерация списка пар, которые требуется различить и непосредственно построение графа, основанное на идее о том, что из любой неразличенной пары вершин может существовать путь либо в другую неразличенную пару (когда у обоих вершин пары имеются смежные вершины, имеющие одинаковые отметки), либо в различающую вершину, если для пары вершин выполняется следующее условие: имеет смежную вершину v с отметкой c, в то время как в списке смежности вершины отсутствуют вершины 
с отметкой с [5].
Алгоритм построения списка маршрутов построен на волновом алгоритме и являет собой итеративный его запуск для каждой вершины из графа в каждую различающую вершину. После чего производится группировка найденных маршрутов по начальной вершине и занесение их в сводную таблицу.
Суть алгоритма построения дерева принятия решения:
1) создаем список вершин L графа G, в которых мог бы находиться агент (на первом шаге это все вершины);
2) из матрицы маршрутов выбираем маршрут, который может разделить множество L на два подмножества максимальной мощности: множество вершин, которые могут быть достигнуты агентом при прохождении по данному маршруту и множество вершин, которые не могут быть им достигнуты;
3) добавляем найденный маршрут в корень дерева;
4) пока мощность любого из созданных на шаге 2 множеств больше 1, повторяем алгоритм, начиная с пункта 1, используя в качестве множества вершин поочередно множества, полученные на шаге 2.
5) если мощность одного из множеств, полученных на шаге 2, равна 1, добавляем его в качестве листа.
В ходе исследований была получена оценка высоты дереве R. Показано что высота дерева не превышает 
, где m - общее число различных меток в исходном графе, а k - максимальное число одинаковых меток.
Сложность алгоритма не превышает 
, причем наиболее затратным является получение списка маршрутов. Сложность волнового алгоритма известна, и равна 
, где k - число вершин в различающем графе, а волновой алгоритм будет выполнен kn раз, следовательно в наихудшем случае сложность получения списка маршрутов будет равна 
, и поскольку 
, то итоговая оценка сложности составит 
.
Так как при росте числа красок сложность самолокализации падает и чем меньше связность графа, тем меньшее число красок необходимо для его раскраски, то наиболее целесообразным является исследование поведения алгоритма на графах невысокой связности.
Исходя из этого, с помощью разработанной программной системы был проведен анализ 25000 графов с числом вершин от 2 до 250, раскрашенных точным методом детерминированной раскраски. На практике среднее число вершин, которое необходимо посетить агенту, с ростом числа вершин исходного графа n растет пропорционально
.
Литература:
•1. Гилл А. Введение в теорию конечных автоматов. - М.: Наука, 1966. - 272 с.
•2. Dudek G, 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.
•3. Dudek G, Jenkin M., Milios E., Wilkes D. Map validation in a graph-like world in 13th International Joint Conference on Artificial Intelligence. - 1993. - p. 1648-1653.
•4. Грунский И.С, Олейник Р.И. Об отличимости инициальных лабиринтов конечными автоматами // Интеллектуальные системы. - 1999. - Т. 4. - № 1-2.-с. 273-283.
•5. Сапунов С.В. Анализ графов с помеченными вершинами: Дисс. канд. физ-мат. наук: 01.05.01. - Донецк, 2007. - 150с.
•6. Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с.
