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

Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Графовая формулировка задачи может уточняться двумя разными способами. В работе Денга и Пападимитриу [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> камней.

| <math>\Omega (log \; log \; log \; n)</math>

'''Исследование в геометрической формулировке'''

Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде многоугольников и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [3], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию.

Задача поиска рандеву отличается от задачи исследования в том, что она рассматривает два поисковых инструмента, расположенных в разных вершинах графа, которые стремятся минимизировать время, необходимое для их встречи (рандеву) в одной вершине. В любое заданное время мобильные агенты занимают вершину графа и могут оставаться в ней либо перемещаться от вершины к вершине. Нашей задачей является минимизация времени, необходимого для рандеву. Естественным расширением задачи является исследование мобильных систем с несколькими агентами. Говоря в более общем контексте, пусть даны конкретная модель агентов и модель сети; мы говорим, что множество агентов, произвольным образом распределенных по вершинам сети, встречаются (организуют рандеву), если при выполнении своих программ по прошествии некоторого конечного времени все они занимают одну и ту же вершину сети в одно и то же время. Нас особо интересует высокосимметричный случай с анонимными агентами в анонимной сети, а простейшим вариантом является случай с двумя агентами, стремящимися организовать рандеву в кольцевой сети. В частности, в модели, изучавшейся Савчуком [16], агенты не могут различать вершины, вычисление выполняется посредством синхронных шагов, а ребра при каждой вершине имеют согласованную ориентацию. В таблице 2 приведены соотношения времени и памяти, известные для шести алгоритмов (см. Кранакис и др. [13], а также Флоччини и др. [10]) в случае, когда k мобильных агентов используют неразличимые камни (по одному на каждого мобильного агента) для обозначения своей позиции в кольце, состоящем из n вершин.

Кранакис и др. [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].

* ''[[Детерминированный алгоритм поиска на прямой]]