Автор: Шатохина Н.К., Кузнецов Ю.А.
Источник: Математичне та програмне забезпечення інтелектуальних систем (МПЗІС-2013) / Матерiали XI мiжнародної науково-практичної конференцiї. – Днепропетровск, ДНУ ім. О. Гончара – 2013. – С. 141–142.
Шатохина Н.К., Кузнецов Ю.А. О задаче выхода агента на границу графа мозаичной структуры с дырами. В данной работе представлен алгоритм выхода на границу графа агента, который поставлен в случайную вершину графа мозаичной структуры с дырами.
В предложенной работе рассматривается тематика, связанная автоматным анализом геометрических сред, графов, изображений. Этой тематике посвящено большое количество работ, например [1], [2].
Одной из задач этой тематики является нахождения выхода из графа -лабиринта автоматом - агентом (далее агентом).
В данной работе рассматривается лабиринт специального вида, представленный плоским неориентированным графом мозаичной структуры, состоящей из правильных треугольников. Работа является продолжением исследований, описанных в [3]. В качестве усложнения модели объекта используется неориентированный плоский граф мозаичной структуры с дырами. Моделью дыры проанализирован случай отсутствия одного из ребер любой из внутренних вершин.
Рассмотрены следующие свойства агента. Располагаясь в вершине он может воспользоваться ее локальной информацией – степенью вершины, может выполнять повороты по и против часовой стрелки, перемещаться в следующей вершине по ребрам и определять направление своего перемещения.
Алгоритм выхода агента на вершину графа обращается у двум стан-дартным алгоритмам А1, А2. Алгоритм А1 позволяет определить, расположена ли вершина на контуре дырки. Алгоритм А2 позволяет выбрать ребро дальнейшего следования.
Алгоритм перемещения агента состоит из ряда следующих шагов.
1. Агент помещается случайным образом в произвольную вершину графа.
2. Агент определяет степень вершины.
3. Если степень ее меньше пяти, это граничная вершина и агент оста-навливается.
4. Если степень равна шести, то это внутренняя вершина, и агент пе-ремещается по диаметрально противоположному ребру относительно первого встречного ребра до следующей вершины. Дальнейший анализ производится, начиная с пункта 2.
5. Если степень равна пяти (это либо граничная вершина, либо внут-ренняя, у которой отсутствует инцидентное ребро, т. е. рядом с которой находится дыра), то выполняется алгоритм А1.
6. Если А1 возвращает, что вершина является граничной, то агент останавливается.
7. Если А1 возвращает, что вершина является внутренней, то выполняется алгоритм А2.
8. Агент переходит по найденому ребру. Следующая вершина анализируется, начиная с пункта 2.
Показано, что суммарная временная сложность этого алгоритма оценивается как О(7n/8).
1. Levitt T., Lawton D.N. Qualitative navigation for mobile robots// Artificial Intelli-gence, 1990, v.40, p. 305-360.
2. В.Б. Кудрявцев, Ш. Ушчумлич, Г. Килибарда. О поведении автоматов в лабиринтах // Дискретная математика.-1992.-Т.4, вып.3.- С.3-28.
3. Шатохина Н.К., Шатохин П.А. Распознавание графа мозаичной структуры коллективом агентов. // Наукові праці Донецького національного технічного універсітету. Серія: Проблеми моделювання та проектування (МАП2011), випуск 9(179). Донецьк, ДонНТУ, 2011. С. 111-121.