Мобильные агенты и исследования с их помощью
Ключевые слова и синонимы
Распределенные алгоритмы; исследование графов; мобильный агент; навигация; рандеву; маршрутизация; соотношение времени и памяти
Постановка задачи
Можно ли эффективно исследовать сеть при помощи мобильных агентов? Это слишком общий вопрос; чтобы адекватно ответить на него, необходимо точнее понимать, что представляют собой мобильные агенты, какие разновидности сетевого окружения они должны изучать и какие меры сложности нам было бы интересно анализировать.
Мобильные агенты
Мобильные агенты представляют собой автономные «разумные» программные модули, способные перемещаться по сети. Они моделируются посредством автоматов с ограниченным объемом памяти и ограниченными вычислительными возможностями и обычно запускаются другими модулями (которым они отправляют свои находки) с целью сбора информации. Действия, выполняемые мобильными агентами, могут быть дискретными или непрерывными, а переходы из одного состояния в другое могут быть детерминированными или недетерминированными, что позволяет использовать различные натуральные меры сложности в зависимости от рассматриваемых предположений.
Модель сети
Модель сети унаследована непосредственно из теории распределенных вычислений. Она представляет собой связный граф, вершинами которого являются вычислительные узлы, а ребра соответствуют линиям связи. Модель может быть статической или динамической, а ее ресурсы могут иметь различные уровни доступности. В зависимости от рассматриваемой модели вершины и связи сети могут иметь различные метки. Особенно полезной на практике абстракцией является анонимная сеть, в которой вершины не имеют идентификаторов, в силу чего агент не может различить две вершины иначе как по их степеням. Исходящие из вершины ребра обычно полагаются различимыми, однако не стоит смешивать две совершенно разных ситуации – глобально согласованную систему меток ребер и локально независимые пометки.
Меры эффективности, подлежащие исследованию
Одной из наиболее часто используемых мер эффективности является время, необходимое для выполнения исследовательской задачи, измеряемое либо в количестве обходов ребер, либо в количестве вершин, посещенных мобильным агентом. Соотношение между временем, необходимым для исследования, и объемом памяти, используемой мобильным агентом, является основным параметром, используемым для оценки алгоритмов. Некоторые экспериментаторы не налагают ограничений на объем памяти и ищут алгоритмы, минимизирующие время исследования. Другие ищут минимальный объем памяти, позволяющий исследовать конкретный тип сети (например, дерево) заданного (известного или неизвестного) размера, независимо от затраченного на исследование времени. И, наконец, многие исследователи рассматривают различные соотношения времени и памяти.
Основные задачи
Пусть даны модели агентов и самой сети. Задача исследования графа заключается в разработке алгоритма для агента, позволяющего ему посещать все вершины и/или ребра сети. С ней тесно связана еще одна задача, в которой объект, подлежащий исследованию, представлен в виде области на плоскости, имеющей препятствия, а исследование будет заключаться в посещении всех беспрепятственно доступных фрагментов области в зоне видимости. Еще одна задача заключается в нахождении рандеву – событий, в ходе которых два или более агентов должны встретиться в одной вершине сети.
Основные результаты
Клод Шеннон [17] первым предложил алгоритм на базе конечных автоматов для исследования произвольного лабиринта (размером 5 x 5 квадратов) методом проб и ошибок. Задачи об исследованиях с помощью мобильных агентов широко изучались в научной литературе; полезное историческое введение можно найти в работе Фрейньо и др. [11].
Исследование в графах общего вида
Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Графовая формулировка задачи может уточняться двумя разными способами. В работе Денга и Пападимитриу [8] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [15] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [1], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [15] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [11] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью d мобильному агенту необходимо [math]\displaystyle{ \Omega (D \; log \; d) }[/math] бит памяти даже в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [4] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, в противном случае необходимо и достаточно [math]\displaystyle{ \Theta(log \; log \; n) }[/math] камней.
Исследование на деревьях
В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс исследования с остановкой завершается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. При исследовании с возвращением значения мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется бессрочное исследование, мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [9], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, [math]\displaystyle{ N \ge n \; }[/math] – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева.
Таблица 1.
| Исследование | Знание | Нижние границы | Верхние границы |
|---|---|---|---|
| Бессрочное | [math]\displaystyle{ \empty }[/math] | Нет | [math]\displaystyle{ O(log \; d) }[/math] |
| Без остановки | [math]\displaystyle{ n \le N }[/math] | [math]\displaystyle{ \Omega (log \; log \; log \; n) }[/math] | [math]\displaystyle{ O(log \; N) }[/math] |
| С возвращением значения | [math]\displaystyle{ \empty }[/math] | [math]\displaystyle{ \Omega (log \; n) }[/math] | [math]\displaystyle{ O (log^2 \; n) }[/math] |
Исследование в геометрической формулировке
Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде многоугольников и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [3], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию.
Рандеву
Задача поиска рандеву отличается от задачи исследования в том, что она рассматривает два поисковых инструмента, расположенных в разных вершинах графа, которые стремятся минимизировать время, необходимое для их встречи (рандеву) в одной вершине. В любое заданное время мобильные агенты занимают вершину графа и могут оставаться в ней либо перемещаться от вершины к вершине. Нашей задачей является минимизация времени, необходимого для рандеву. Естественным расширением задачи является исследование мобильных систем с несколькими агентами. Говоря в более общем контексте, пусть даны конкретная модель агентов и модель сети; мы говорим, что множество агентов, произвольным образом распределенных по вершинам сети, встречаются (организуют рандеву), если при выполнении своих программ по прошествии некоторого конечного времени все они занимают одну и ту же вершину сети в одно и то же время. Нас особо интересует высокосимметричный случай с анонимными агентами в анонимной сети, а простейшим вариантом является случай с двумя агентами, стремящимися организовать рандеву в кольцевой сети. В частности, в модели, изучавшейся Савчуком [16], агенты не могут различать вершины, вычисление выполняется посредством синхронных шагов, а ребра при каждой вершине имеют согласованную ориентацию. В таблице 2 приведены соотношения времени и памяти, известные для шести алгоритмов (см. Кранакис и др. [13], а также Флоччини и др. [10]) в случае, когда k мобильных агентов используют неразличимые камни (по одному на каждого мобильного агента) для обозначения своей позиции в кольце, состоящем из n вершин.
Таблица 2.
| Память | Время | Память | Время |
|---|---|---|---|
| O(k log n) | O(n) | O(log n) | O(n) |
| O(log n) | O(kn) | O(log k) | O(n) |
| O(k log log n) | [math]\displaystyle{ O \bigg( \frac{n \; log \; n}{log \; log \; n} \bigg) }[/math] | O(log k) | O(n log k) |
Кранакис и др. [14] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты могут иметь большее число неразличимых маркеров. Было показано, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе при наличии константного объема памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. Имея заданное начальное положение агентов в графе, Де Марко и др. [6] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет [math]\displaystyle{ O(D|L_{min}|^2) \; }[/math], если D известно, и [math]\displaystyle{ O((D + |L_{max}|)^3) \; }[/math], если D неизвестно, где [math]\displaystyle{ |L_{min}| \; }[/math] и [math]\displaystyle{ |L_{max}| \; }[/math] – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью [math]\displaystyle{ O(n|L_{min}|) \; }[/math], если размер n кольца известен, и [math]\displaystyle{ O(n|L_{max}|) \; }[/math] – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью [math]\displaystyle{ O(D|L_{min}|) \; }[/math] для случая, когда топология графа и начальные положения известны агентам.
Применение
Интерес к использованию мобильных агентов был вызван двумя родственными задачами. Во-первых, они использовались для упрощения сложных аспектов распределенных вычислений, во-вторых – помогали обойти ограничения пользовательских интерфейсов. Сегодня они находят широкое применение в таких различных областях, как распределенное решение задач и планирование (например, разделение и координация заданий), обслуживание сетей (например, использование в качестве демонов в сетевых системах для выполнения таких задач, как мониторинг и наблюдение), электронная коммерция и поиск информации (например, добыча данных и роботы-сборщики, выполняющие поиск продуктов и услуг из нескольких источников), исследования при помощи роботов (например, вездеходы и другие мобильные платформы, способные исследовать потенциально опасные среды и даже выполнять работы в открытом космосе), распределенное принятие рациональных решений (например, ведение протоколов аукционов или заключение сделок). Много полезной информации по данной теме можно найти в нескольких статьях тома под редакцией Вайса [18].
Открытые вопросы
Среди направлений будущих исследований можно упомянуть изучение соотношений времени и памяти для моделей игр на поиск (см. Альперн и Галь [2]). Системы с несколькими агентами особенно полезны для поиска и исследования на базе контента; дальнейшие изыскания в этой области обещают быть плодотворными. Мобильные агенты с ограниченной памятью образуют перспективную модель для применения в системах датчиков. В геометрической формулировке навигация и маршрутизация в трехмерной среде с использованием только локальной информации представляют собой область с большим количеством нерешенных вопросов.
См. также
Литература
1. Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29,1164-1188 (2000)
2. Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Norwell (2003)
3. Bar-Eli, E., Berman, P., Fiat, A., Yan, R.: On-line navigation in a room. J. Algorithms 17, 319-341 (1994)
4. Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: Proc. 30th Ann. Symp. on Theory of Computing, pp. 269-278. Dallas, 23-26 May 1998
5. Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM J. Comput. 26,110-137 (1997)
6. De Marco, G., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous Deterministic Rendezvous in Graphs. Theoret. Comput. Sci.355, 315-326 (2006)
7. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment I: the rectilinear case. J. ACM 45, 215-245 (1998)
8. Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32, 265-297 (1999)
9. Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51, 38-63 (2004)
10. Flocchini, P., Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Multiple Mobile Agent Rendezvous in the Ring. In: Proc. LATIN 2004. LNCS, vol. 2976, pp. 599-608. Bueons Aires, 5-8 April 2004
11. Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345, 331-344(2005)
12. Kranakis, E., Singh, H., Urrutia, J.: Compass Routing in Geometric Graphs. In: Proceedings of 11th Canadian Conference on Computational Geometry, CCCG-99, pp. 51-54, Vancouver, 15-18 August 1999
13. Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile Agent Rendezvous Search Problem in the Ring. In: Proc. International Conference on Distributed Computing Systems (ICDCS), pp. 592-599. Providence, Rhode Island 19-22 May 2003
14. Kranakis, E., Krizanc, D., Markou, E.: Mobile Agent Rendezvous in a Synchronous Torus. In: Proceedings of LATIN 2006, 7th Latin American Symposium. Valdivia, March 20-24 2006. Correa, J., Hevia, A., Kiwi, M. SVLNCS 3887,653-664 (2006)
15. Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281-295 (1999)
16. Sawchuk, C.: Mobile Agent Rendezvous in the Ring. Ph. D. thesis, Carleton University, Ottawa, Canada (2004)
17. Shannon, C.: Presentation of a Maze Solving Machine, in Cybernetics, Circular, Causal and Feedback Machines in Biological and Social Systems. In: von Feerster, H., Mead, M., Teuber, H.L. (eds.) Trans. 8th Conf, New York, March 15-16, 1951. pp. 169-181. Josiah Mary Jr. Foundation, New York (1952)
18. Weiss, G. (ed.): Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. MIT Press, Cambridge, MA (1999)