5.5.3.       Функционирование мобильного агента

Задача оптимальной развозки решается мобильным агентом в условиях, когда грузы для перевозки ему полностью определены внешней средой (в нашем случае — ГА). Ему необходимо решить, в какой последовательности необходимо увозить и привозить грузы, чтобы пройденный путь был минимальным. Решение находится с использованием механизма точек принятия решений, реализующего алгоритм поиска на графе состояний [37, 134]. Вершины графа — это состояния системы, а душ — продукционные правила. ЦФ мобильного агента представляет собой суммарный путь всех мобильных агентов, который они проходят, перевозя грузы.

В РДО механизм точек решений работает следующим образом: при имитации после наступления очередного события происходит останов модельного времени и осуществляется решение о продолжении имитации.

При этом осуществляется поиск на графе (в глубину, в ширину или информированный) заданном неявным образом.

Точки принятия решений в РДО описывают способы использования образцов для моделирования процесса и принятия решений на уровне событий. Объект точек принятия решений имеет следующий формат:

Описание каждой точки принятия решений имеет следующий формат:

В РДО имеются два типа точек принятия решений:

Some — просмотреть все активности данной точки, проверить предусловия, выполнить ту активность, предусловия которой удовлетворяются;

Search — реализовать поиск на графе состояний.

В случае планирования маршрута агента алгоритм поиска в ширину работает следующим образом: выбирается начальная вершина — пункт поступления грузов, т. е. начальная отправная точка движения мобильного агента. Затем раскрываются все вершины, инцидентные начальной, и подсчитывается стоимость пути от начальной вершины до каждой из этих, вершин (рис. 5.24).

При интерпретации графа поиска примем, что вершины, связанные с начальной вершиной, — это стеллажи, в которые необходимо доставить грузы, или пункт приема грузов, куда надо доставить грузы со стеллажей. В результате определяется груз, который нужно отвезти в первую очередь. Затем раскрываются все вершины, инцидентные этой вершине, и определяются стоимости путей до остальных нераскрытых вершин, и так до тех пор, пока не будут раскрыты все вершины. В результате такого поиска находим оптимальную по следовательно сть грузов, при этом грузам присваивается приоритет развоза по стеллажам и в пункт приема. Когда всем грузам, которые необходимо перевезти, присвоены приоритеты, начинается собственно развозка грузов и стоится новый граф, где в качестве стоимости пути выступает приоритет груза.

РДО-имитатор позволяет использовать не одну точку принятия решения, а несколько, если это необходимо. В результате в модели строятся два и более графа состояний, т. е. реализуются две и более системы управления, отдельно для каждого мобильного агента. Возможный вид графа поиска агентом приведен на рисунке (рис. 5.25).

При поиске новые вершины (или состояния) графа раскрываются от той вершины, в которой ЦФ минимальна независимо от того, сколько в данном состоянии перевезено грузов. Даже придя к такому состоянию, когда выполняется терминальное условие, поиск на графе будет продолжаться до тех пор, пока «будет возможно» найти меньший путь. На рисунке 5.25 представлен граф поиска оптимального пути мобильным агентом, при транспортировке трех грузов. Из графа видно, что последовательность развозки должна быть следующей (2-3-1).

Рассмотрим случай, когда мобильный агент может перевозить только один груз, но он обслуживает заявки, как на ввоз, так и на вывоз грузов со стеллажей склада. Здесь необходимо решить, в какой по следовательно сти необходимо увозить и привозить грузы, чтобы пройденный путь погрузчика был минимальным.

При планировании маршрута транспортных перевозок алгоритм поиска в ширину работает следующим образом: выбирается начальная вершина — пункт поступления грузов, т. е. начальная отправная точка движения транспортного устройства. Затем раскрываются все вершины, инцидентные начальной, и подсчитывается стоимость пути от начальной вершины до каждой из этих вершин. Вершины, связанные с начальной вершиной — это стеллажи, в которые необходимо доставить грузы или пункт приема грузов, куда надо доставить грузы со стеллажей. В качестве стоимости пути выступает путь, который должен пройти мобильный агент. В результате мы находим груз, который нужно отвезти в первую очередь. Затем раскрываются все вершины, инцидентные этой вершине, и определяются стоимости путей до остальных нераскрытых вершин, и так до тех пор, пока не будут раскрыты все вершины. В результате такого поиска мы находим оптимальную последовательность грузов, при этом грузам присваивается приоритет развоза по стеллажам и в пункт приема. Когда всем грузам, которые необходимо перевезти, присвоены приоритеты, начинается собственно развозка грузов и стоится новый граф, где в качестве стоимости пути выступает приоритет груза. Таким образом, каждый агент сам выбирает, какой груз привезти к стеллажу, а какой отвезти, в зависимости от его приоритета (приоритет меньше у того груза, ехать до места назначения которого меньше).

Так как РДО-имитатор позволяет использовать не одну точку принятия решения, а несколько, если это необходимо, то для каждого мобильного агента в модели строится граф поиска в пространстве состояний. В результате, если в системе всего два транспортных устройства, то в модели строятся два графа состояний, т. е. реализуются две системы управления.

В модели с двумя мобильными агентами описание точек принятия решения на РДО выглядит следующим образом:

Первый блок активностей необходим для случайного поступления запроса на заявку перевезти груз. Первая точка принятия решений «Мини™ мальный_путь» обеспечивает поиск на графе. Иначе говоря, ищется последовательность перевозки грузов таким образом, чтобы пройденный путь агентом был минимальным. Во второй точке принятия решений «Перевоз™ ка» осуществляется собственно имитация перевозки либо к стеллажу, либо от него, и поиск на графе происходит в зависимости от приоритета груза. Третья точка принятия решений — вспомогательная, с помощью нее случайным образом устанавливается, куда и откуда вести случайно появившийся в системе груз.

Пусть имеются три груза (рис. 5.26): Груз_1 — надо перевезти к стеллажу 2; Груз_2 — надо отвезти от стеллажа 26; Груз_3 — надо отвезти от стеллажа 3.

 

В результате моделирования получаем первый граф состояний (стоимость пути—пройденный путь), который наглядно показывает правильность принятия решения (рис. 5.27).

Таким образом, оптимальная последовательность грузов: Груз_1- -Груз_3-Груз_2. При этом пройденный путь транспортным устройством минимален и равен 71,02 м.