Распознавание неориентированных графов коллективом агентов

Описание

Стёпкин А.В.Данная работа посвящена исследованию проблемы распознавания графов с помощью трех агентов. Два агента-исследователя (АИ) передвигаются по связному неориентированному графу без петель и кратных ребер G=(V,E), считывают и изменяют метки на элементах графа, передают информацию о своих действиях агенту-экспериментатору (АЭ), который и выполняет восстановление графа.

В литературе широко рассматриваются задачи, связанные с распознаванием среды [1]. Данная работа посвящена исследованию проблемы распознавания графов с помощью трех агентов. Два агента-исследователя (АИ) передвигаются по связному неориентированному графу без петель и кратных ребер G=(V,E), считывают и изменяют метки на элементах графа, передают информацию о своих действиях агенту-экспериментатору (АЭ), который и выполняет восстановление графа.

В работе предложен алгоритм построения маршрутов АИ по графу, позволяющих АЭ точно восстановить граф среды. У каждого из АИ есть две краски: у агента A это r и b, у агента B – y и b. Полученный алгоритм использует результаты и обозначения из [2].

Рассматриваемый алгоритм основан на стратегии поиска в глубину: агенты идут «в глубину», пока это возможно, возвращаются назад, ищут другой путь с еще не посещенными вершинами и не пройденными ребрами. В случае обнаружения смежной вершины, окрашенной в «чужой» цвет, агент метит все перешейки из текущей вершины в чужую область и сообщает второму АИ через АЭ о необходимости распознавания помеченных перешейков. Пока второй АИ распознает перешейки, первый АИ не может метить новые перешейки. В случае отсутствия других возможных вариантов перемещения, кроме как пометить новый перешеек, первый АИ останавливается до того момента, пока второй АИ не распознает все помеченные перешейки. При обходе графа создается неявная нумерация пройденных вершин: при первом посещении вершины агентом A ей фактически ставится в соответствие номер, равный значению переменной Сч _ А(Сч _ B для агента B). Отметим, что Сч _ А и Сч _ B принимают соответственно нечетные и четные значения. На основе нумерации и происходит восстановление графа G .

Рассмотрим режимы работы агентов.С нерассмотренными режимами можно ознакомиться в [2].

1. Если в процессе обхода графа в вершине v был обнаружен перешеек, то при условии, что все ранее помеченные данным АИ перешейки были распознаны, агент переключается в режим пометки перешейков. В этом режиме АИ окрашивает ближние инциденторы всех перешейков, инцидентных вершине v, в черный цвет. Агент A имеет приоритет над агентом B, поэтому в ситуации, когда оба агента одновременно обнаружат один и тот же перешеек, он будет помечен агентом A. На каждом шаге АИ обмениваются данными с АЭ. По завершении этого режима АЭ содержит информацию о количестве помеченных перешейков.

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

2.1 Помечено один перешеек. АИ окрашивает ближний инцидентор помеченного перешейка в черный цвет. Далее движется вперед по своему пути, пока не вернется в конец пути «своего» цвета.

3.2 Помечено не менее двух перешейков. АИ окрашивает ближний инцидентор помеченного перешейка в «свой» цвет. Далее АИ движется назад по своему пути, пока не будет найден следующий помеченный перешеек. При обнаружении такого перешейка возможно два случая:

3.2.1 Следующий помеченный перешеек не последний. АИ окрашивает ближний инцидентор в черный цвет. На следующем шаге АИ снова возвращается назад по своему пути до следующего помеченного перешейка.

3.2.2 Следующий помеченный перешеек последний. АИ окрашивает ближний инцидентор в «свой» цвет. На следующем шаге АИ переходит по последнему перешейку в чужую область, окрашивая ближний инцидентор в черный цвет. На следующем шаге АИ переходит по первому распознанному перешейку в свою область, окрашивая дальний инцидентор в черный цвет. Далее АИ движется вперед по своему пути, пока не вернется в конец пути «своего» цвета.

Восстановление графа производит АЭ на основе сообщений, которые он получает от АИ. Алгоритм можно рассмотреть в [2], заменив пары ВПЕРЕД_ABB(), НАЗАД_АВВ() и ВПЕРЕД_AB(), НАЗАД_АВ() процедурами: РАСП_АВ(): EH:=EH U {(N _ B,r(t-i))}; K:=K-1; UDP_ B:=(((K=Z)or(K=1))and(Z≠1)); и МЕТИМ_АВ():F=F+1;E:=1; соответственно, а также учитывая новую процедуру ВОЗВРАТ_B(): EH:=EH\{(y(p-1),(y(p))}; VH:=VH\{Сч _ B}; Сч _ B:=Сч _ B-2; p:=p-1; y(p):=Сч _ B; L:=1; K:=K+1.

Теорема 1. Выполняя алгоритм распознавания, агенты распознают любой граф G с точностью до изоморфизма.

Теорема 2. Временная и емкостная сложности алгоритма равны O(n²),где n – число вершин графа, при этом алгоритм использует 3 краски.

СПИСОК ЛИТЕРАТУРЫ

1. Albers S. Exploring unknown environments. / S. Albers, M.R. Henzinger.–SIAM Journal on Computing, 2000.– 29(4):1164 – 1188 c.

2. Стёпкин А. В. Алгоритм распознавания конечных графов тремя агентами // Theoretical and applied aspects of cybernetics. Proceedings of the International Scientific Conference of Students and Young Scientists (Kyiv, February 21-25 2011). - Р. 185-188.