Бондаренко Антон Владимирович

 

ПОД- СЕКЦИЯ  3. Информатика.

Метод самолокализации агента в рабочей среде

 

Разработка и анализ метода автоматизированной самолокализации.

Ключевые слова: самолокализация, детерминированный граф, различие вершин, раскраска.

Розробка та аналіз методу автоматизованої самолокалізації.

Ключові слова: самолокалізація, детермінований граф, відмінність вершин, розфарбовування.

Development and analysis of method of the automated selflocalization.

Keywords: selflocalization, determined count, distinction of tops, coloration.

 

Бондаренко Антон Владимирович

        Институт информатики и искусственного интеллекта ДонНТУ 

 

Задачи, связанные с анализом различных сред с помощью блуждающих по ним агентов (мобильных роботов, автоматов, поисковых программ и т.п.)  относятся к категории традиционных задач искусственного интеллекта. Агент перемещается по среде, получая при этом некоторую локальную информацию о среде, на основе которой, исходя из некоторой априорной информации, решает поставленные перед ним задачи: например, обходит среду и делает заключения о её свойствах [1].

В настоящее время несколько подходов к проблеме анализа графов блуждающим агентом:

1) среда рассматривается как конечный инициальный автомат без выхода, что позволяет использовать методы, разработанные в рамках теории конечных автоматов;

2) среда  рассматривается как конечный неориентированный граф с помеченными концами ребер;

3) среда рассматривается как граф с помеченными вершинами [6].

Третий подход взят за основу в разработке метода самолокализации, предложенном в данной работе.

Задача самолокализации состоит в том, что агент в результате движений по среде должен определить первоначальное положение в среде. Наш подход заключается в том, что задача самолокализации решается в 4 этапа:

1) построение различающего графа , у которого  – множество вершин, каждая из которых представляет собой пару из исходного графа , для которых . При этом в множество  добавляются пары вида , такие, что в графе  существует вершина , и смежная с ней , имеющая отметку , причем вершина  не имеет смежной вершины с отметкой . Вершину такого вида назовем различающей [3];

2) нахождение в графе  кратчайших маршрутов от каждой вершины вида  до каждой различающей вершины с записью полученных маршрутов в список маршрутов ;

3) построение матрицы , столбцами которой являются вершины из множества вершин  исходного графа , строками – маршруты из полученного на предыдущем шаге списка ,  – вершина, в которую попадает агент, прошедший из вершины  по маршруту , либо ноль, если агент не сможет пройти из вершины  по маршруту  [2];

4) построение бинарного дерева принятия решения , листьями которого являются вершины из множества вершин графа , вершинами – маршруты из списка маршрутов . Возможность перехода по маршруту, определенная матрицей , определяет направление движения по дереву [4].

Построение различающего графа осуществляется в два этапа: генерация списка пар, которые требуется различить и непосредственно построение графа, основанное на идее о том, что из любой неразличенной пары вершин может существовать путь либо в другую неразличенную пару (когда у обоих вершин пары имеются смежные вершины, имеющие одинаковые отметки), либо в различающую вершину, если для пары вершин  выполняется следующее условие:  имеет смежную вершину  с отметкой , в то время как в списке смежности вершины  отсутствуют вершины с отметкой  [5].

Алгоритм построения списка маршрутов построен на волновом алгоритме и являет собой итеративный его запуск для каждой вершины из графа  в каждую различающую вершину. После чего производится группировка найденных маршрутов по начальной вершине и занесение их в сводную таблицу.

Суть алгоритма построения дерева принятия решения:

1) создаем список вершин  графа , в которых мог бы находиться агент (на первом шаге это все вершины);

2) из матрицы маршрутов выбираем маршрут, который может разделить множество  на два подмножества максимальной мощности: множество вершин, которые могут быть достигнуты агентом при прохождении по данному маршруту и множество вершин, которые не могут быть им достигнуты;

3) добавляем найденный маршрут в корень дерева;

4) пока мощность любого из созданных на шаге 2 множеств больше 1, повторяем алгоритм, начиная с пункта 1, используя в качестве множества вершин  поочередно множества, полученные на шаге 2.

5) если мощность одного из множеств, полученных на шаге 2, равна 1, добавляем его в качестве листа.

В ходе исследований была получена оценка высоты дереве . Показано что высота дерева не превышает  , где  – общее число различных меток в исходном графе, а  – максимальное число одинаковых меток.

Сложность алгоритма не превышает , причем наиболее затратным является получение списка маршрутов. Сложность волнового алгоритма известна, и равна , где  - число вершин в различающем графе, а волновой алгоритм будет выполнен  раз, следовательно в наихудшем случае сложность получения списка маршрутов будет равна , и поскольку  , то итоговая оценка сложности составит.

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

Исходя из этого, с помощью разработанной программной системы был проведен анализ 25000 графов с числом вершин от 2 до 250, раскрашенных точным методом детерминированной раскраски. На практике среднее число вершин, которое необходимо посетить агенту, с ростом числа вершин исходного графа  растет пропорционально .

 

 

 
 
Список используемых источников:
 
  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 с.