4430
правок
Мобильные агенты и исследования с их помощью: различия между версиями
Материал из WEGA
Мобильные агенты и исследования с их помощью (посмотреть исходный код)
Версия от 22:36, 27 октября 2023
, 27 октября 2023→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показаны 33 промежуточные версии этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Можно ли эффективно исследовать сеть при помощи мобильных агентов? Это слишком общий вопрос; чтобы адекватно ответить на него, необходимо точнее понимать, что представляют собой мобильные агенты, какие разновидности сетевого окружения они должны изучать и какие меры сложности было бы интересно анализировать. | Можно ли эффективно исследовать сеть при помощи мобильных агентов? Это слишком общий вопрос; чтобы адекватно ответить на него, необходимо точнее понимать, что представляют собой мобильные агенты, какие разновидности сетевого окружения они должны изучать и какие меры сложности нам было бы интересно анализировать. | ||
'''Мобильные агенты''' | '''Мобильные агенты''' | ||
Мобильные агенты представляют собой автономные | Мобильные агенты представляют собой автономные «разумные» программные модули, способные перемещаться по сети. Они моделируются посредством автоматов с ограниченным объемом памяти и ограниченными вычислительными возможностями и обычно запускаются другими модулями (которым они отправляют свои находки) с целью сбора информации. Действия, выполняемые мобильными агентами, могут быть дискретными или непрерывными, а переходы из одного состояния в другое могут быть детерминированными или недетерминированными, что позволяет использовать различные натуральные меры сложности в зависимости от рассматриваемых предположений. | ||
'''Модель сети''' | '''Модель сети''' | ||
Модель сети унаследована непосредственно из теории распределенных вычислений. Она представляет собой связный граф, вершинами которого являются вычислительные узлы, а ребра соответствуют линиям связи. Модель может быть статической или динамической, а ее ресурсы | Модель сети унаследована непосредственно из теории распределенных вычислений. Она представляет собой связный граф, вершинами которого являются вычислительные узлы, а ребра соответствуют линиям связи. Модель может быть статической или динамической, а ее ресурсы могут иметь различные уровни доступности. В зависимости от рассматриваемой модели вершины и связи сети могут иметь различные метки. Особенно полезной на практике абстракцией является анонимная сеть, в которой вершины не имеют идентификаторов, в силу чего агент не может различить две вершины иначе как по их степеням. Исходящие из вершины ребра обычно полагаются различимыми, однако не стоит смешивать две совершенно разных ситуации – глобально согласованную систему меток ребер и локально независимые пометки. | ||
| Строка 23: | Строка 23: | ||
'''Основные задачи''' | '''Основные задачи''' | ||
Пусть даны модели агентов и самой сети. Задача исследования графа заключается в разработке алгоритма для агента, | Пусть даны модели агентов и самой сети. Задача исследования графа заключается в разработке алгоритма для агента, позволяющего ему посещать все вершины и/или ребра сети. С ней тесно связана еще одна задача, в которой объект, подлежащий исследованию, представлен в виде области на плоскости, имеющей препятствия, а исследование будет заключаться в посещении всех беспрепятственно доступных фрагментов области в зоне видимости. Еще одна задача заключается в нахождении рандеву – событий, в ходе которых два или более агентов должны встретиться в одной вершине сети. | ||
== Основные результаты == | |||
Клод Шеннон [17] первым предложил алгоритм на базе конечных автоматов для исследования произвольного лабиринта (размером 5 x 5 квадратов) методом проб и ошибок. Задачи об исследованиях с помощью мобильных агентов широко изучались в научной литературе; полезное историческое введение можно найти в работе Фрейньо и др. [11]. | |||
'''Исследование в графах общего вида''' | |||
Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Графовая формулировка задачи может уточняться двумя разными способами. В работе Денга и Пападимитриу [8] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [15] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [1], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [15] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [11] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью d мобильному агенту необходимо <math>\Omega (D \; log \; d)</math> бит памяти даже в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [4] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, в противном случае необходимо и достаточно <math>\Theta(log \; log \; n)</math> камней. | |||
'''Исследование на деревьях''' | |||
В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс ''исследования с остановкой'' завершается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. При ''исследовании с возвращением значения'' мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется ''бессрочное исследование'', мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [9], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, <math>N \ge n \;</math> – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева. | |||
Таблица 1. | |||
{| class="wikitable" style="text-align:center" | |||
! Исследование !! Знание !! Нижние границы !! Верхние границы | |||
|- | |||
| Бессрочное | |||
| <math>\empty</math> | |||
| Нет | |||
| <math>O(log \; d)</math> | |||
|- | |||
| Без остановки | |||
| <math>n \le N</math> | |||
| <math>\Omega (log \; log \; log \; n)</math> | |||
| <math>O(log \; N)</math> | |||
|- | |||
| С возвращением значения | |||
| <math>\empty</math> | |||
| <math>\Omega (log \; n)</math> | |||
| <math>O (log^2 \; n)</math> | |||
|} | |||
'''Исследование в геометрической формулировке''' | |||
Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде многоугольников и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [3], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию. | |||
'''Рандеву''' | |||
Задача поиска рандеву отличается от задачи исследования в том, что она рассматривает два поисковых инструмента, расположенных в разных вершинах графа, которые стремятся минимизировать время, необходимое для их встречи (рандеву) в одной вершине. В любое заданное время мобильные агенты занимают вершину графа и могут оставаться в ней либо перемещаться от вершины к вершине. Нашей задачей является минимизация времени, необходимого для рандеву. Естественным расширением задачи является исследование мобильных систем с несколькими агентами. Говоря в более общем контексте, пусть даны конкретная модель агентов и модель сети; мы говорим, что множество агентов, произвольным образом распределенных по вершинам сети, встречаются (организуют рандеву), если при выполнении своих программ по прошествии некоторого конечного времени все они занимают одну и ту же вершину сети в одно и то же время. Нас особо интересует высокосимметричный случай с анонимными агентами в анонимной сети, а простейшим вариантом является случай с двумя агентами, стремящимися организовать рандеву в кольцевой сети. В частности, в модели, изучавшейся Савчуком [16], агенты не могут различать вершины, вычисление выполняется посредством синхронных шагов, а ребра при каждой вершине имеют согласованную ориентацию. В таблице 2 приведены соотношения времени и памяти, известные для шести алгоритмов (см. Кранакис и др. [13], а также Флоччини и др. [10]) в случае, когда k мобильных агентов используют неразличимые камни (по одному на каждого мобильного агента) для обозначения своей позиции в кольце, состоящем из n вершин. | |||
Таблица 2. | |||
{| class="wikitable" style="text-align:center" | |||
! Память !! Время !! Память !! Время | |||
|- | |||
| 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>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>O(D|L_{min}|^2) \;</math>, если D известно, и <math>O((D + |L_{max}|)^3) \;</math>, если D неизвестно, где <math>|L_{min}| \;</math> и <math>|L_{max}| \;</math> – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью <math>O(n|L_{min}|) \;</math>, если размер n кольца известен, и <math>O(n|L_{max}|) \;</math> – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью <math>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) | |||
