Применение многоагентного подхода для автоматизации управления на предприятии

Далеко не на всех предприятиях существует автоматизация в кладовых и на складах. Да и поиск необходимой информации, пусть даже и в электронной картотеке, вызывает трудности. В связи с этим возникла идея создания универсального функционала, позволяющего производить поиск и доставку нужного объекта с минимальными временными и трудовыми затратами. Главной идеей такого функционала является создание многоагентной системы. Универсальность заключается в том, что алгоритм поиска нужного объекта будет одинаковый, независимо от вида искомого объекта и среды. Разница заключается в базе знаний, в подаваемых на вход данных и на обучающих сетах, с помощью которых будет произведено предварительное обучение многоагентной системы. При этом структура многоагентной системы будет универсальной.

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

Взаимодействие агентов в системе осуществляется за счет совокупности четких и нечетких правил. Четкие правила в данном случае это ограничения среды. Они непосредственно прописываются разработчиком при программировании. Например, таким правилом является: «если корзина полная, то иди к лотку» и другие. Нечеткие правила в данной задаче необходимы для разрешения конфликтов между агентами и внутри каждого агента при резервировании позиции в заявке.

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

Склад (или хранилище) в программе будет представлен в виде графа. Граф (G) – это совокупность вершин (V) и дуг (E), в зависимости от того, как они задаются, выделяют два основных способа представления: матрица смежности для графа из N вершин хранится в виде двумерного массива размером N×N. Вершины графа задаются номерами (индексами строк и столбцов матрицы), а ячейка графа matrix[i, j] отражает наличие дуги между соответствующими вершинами; матрица инцидентности для графа из N вершин и M дуг хранится в виде двумерного массива размером N×M. Ячейки матрицы matrix[i, j] отражает инцидентность ребра j вершине i, то есть ребро выходит или входит в вершину i. Если ребро не связано с вершиной, то в соответствующей ячейке матрицы записывается ноль, иначе единица.

Данные способы представления графов имеют такие недостатки, как: избыточность (в матрице смежности возможно большое количество нулей, а их также необходимо хранить; а в матрице инцидентности в каждом столбце может быть два ненулевых значения; недостаточная расширяемость: невозможность добавления в матрицы новых дуг и вершин. В связи с этим часто применяют списки смежности и инцидентности. Для каждой вершины хранится свой список с номерами смежных вершин или инцидентных ребер. В качестве структуры данных в таком случае могут использоваться массивы, связанные списки и хэш-массивы. Списки смежности и инцидентности решают проблему расширяемости графа, но для проверки существования дуги нужно перебрать все дуги, выходящие из некоторой вершины, что сравнительно снижает время выполнения.

При построении графа необходимо решить задачу нахождения кратчайшего пути в графе. Для решения данной задачи существует много алгоритмов, например:

• 1)    Алгоритм Дейкстры.

• 2)    Алгоритм Беллмана-Форда.

• 3)    Алгоритм поиска А*.

• 4)    Алгоритм Флойда-Уоршелла.

• 5)    Алгоритм Ли (волновой алгоритм).

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