РАЗРАБОТКА АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ЗАДАЧ МОБИЛЬНЫХ МАНИПУЛЯТОРОВ В ПРОИЗВОДСТВЕННОМ ЦЕХЕ СО СТАНКАМИ С ЧИСЛОВЫМ ПРОГРАММНЫМ УПРАВЛЕНИЕМ

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

Ключевые слова: мобильный манипулятор, распределение задач, станки ЧПУ, централизованный алгоритм, функция поощрения, венгерский алгоритм.

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

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

В работе рассматривается роботизированный производственный участок, включающий 25 станков с ЧПУ (рисунок 1), обслуживаемых двумя мобильными манипуляторами (рисунок 2). Схема расположения оборудования представлена на рисунке 3.

Рисунок 1. Модель токарного станка с ЧПУ

Рисунок 2. Модель мобильного манипулятора

Рисунок 3. Схема расположения оборудования

В процессе работы станки формируют задачи обслуживания, связанные с выполнением операции загрузки-выгрузки. Данные задачи должны быть распределены между доступными мобильными манипуляторами.

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

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

Применение простых критериев, основанных только на расстоянии или времени перемещения, в условиях производственного участка со станками ЧПУ приводит к неэффективным решениям и росту простоев оборудования.

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

1. Конфликты движения мобильных манипуляторов (рисунок 4)

Назначение задач, расположенных в одном ряду станков, может приводить к одновременному движению роботов по пересекающимся траекториям и взаимным блокировкам.

Рисунок 4. Конфликты движения мобильных манипуляторов

2. Неоптимальный порядок выполнения задач (рисунок 5)

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

Рисунок 5. Неоптимальный порядок выполнения задач

3. Ограниченность энергетических ресурсов мобильного манипулятора (рисунок 6)

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

Рисунок 6. Ограниченность энергетических ресурсов мобильного манипулятора

4. Риск неэффективного выбора мобильного манипулятора в будущем (рисунок 7)

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

Рисунок 7. Риск неэффективного выбора мобильного манипулятора в будущем

Для учёта влияния текущего назначения на последующие действия робота поощрение оценивается не только для отдельной задачи, но и для ограниченной последовательности операций обслуживания. Для робота  и задачи  рассматривается прогнозируемая последовательность задач , где индекс  обозначает номер задачи в множестве активных задач обслуживания, а  — её позицию в последовательности выполнения. Для обеспечения сопоставимости влияния различных факторов в функции поощрения используются нормированные параметры. Функция определения поощрения:

где:

·  — поощрение за выполнение задачи обслуживания станка ;

·  — нормированное расстояние от текущего положения робота  до станка задачи ;

·  — нормированные энергозатраты перемещения робота  от текущего положения к станку ;

·  — нормированные энергозатраты перемещения от станка  до зарядной станции;

·  — нормированный уровень заряд батареи;

·  — индикатор возможного конфликта движения роботов;

·  — нормированное время ожидания обслуживания станка;

·  — весовые коэффициенты.

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

Структура функции непосредственно связана с выявленными проблемными ситуациями.

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

Выражение  реализует учёт энергетических ограничений, обеспечивая назначение только тех задач, выполнение которых не приводит к невозможности возврата робота к зарядной станции.

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

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

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

После вычисления значений функций формируется матрица поощрения :

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

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

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

В рассматриваемой производственной системе ключевой целью является минимизация общего времени простоя станков, что требует глобальной оптимизации распределения задач между мобильными манипуляторами. Для решения задачи назначения используется венгерский алгоритм, позволяющий определить распределение задач по ранее составленной матрице с максимальной суммой поощрений [2][5].

Эффективность получаемого распределения при этом напрямую определяется структурой функции поощрений и значениями входящих в неё весовых коэффициентов. В связи с этим возникает задача определения таких значений коэффициентов, при которых достигается минимальное суммарное время простоя оборудования.

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

Подбор параметров выполняется на основе минимизации суммарного времени простоя оборудования. В качестве критерия эффективности используется интегральная величина

где  — время простоя -го станка.

Поскольку зависимость , ,  определяется результатами моделирования работы производственной системы и не имеет аналитического выражения, оптимизация параметров выполняется методом градиентного спуска с численной оценкой градиента [1]. Производные функции эффективности по весовым коэффициентам аппроксимируются методом конечных разностей:

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

В результате оптимизации получены следующие значения весовых коэффициентов:

Для наглядности чувствительности функции  к весовым коэффициентам были построены графики зависимости  от каждого веса при фиксированных оптимальных значениях остальных коэффициентов:

1. Зависимость  от  при фиксированных ,  на оптимальных значениях (рисунок 8, а) — наблюдается один локальный минимум, определяющий оптимальное .

а                                                            б

в

Рисунок 8. Зависимость функции Т: а – от коэффициента  при фиксированных  и ; б – от коэффициента  при фиксированных  и ; в – от коэффициента  при фиксированных  и 

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

3. Зависимость  от  при фиксированных ,  на оптимальных значениях (рисунок 8, в) — наблюдается два локальных минимума. При малом  робот обслуживает преимущественно ближайшие станки, формируя «кластерное» распределение и локально оптимальные маршруты, что может привести к накоплению больших простоев отдельных станков, следовательно оптимальный выбор — локальный минимум при большем значении , который обеспечивает баланс между учётом расстояний и временем простоя, создавая равномерное распределение обслуживания по цеху и минимизируя суммарное время простоя.

Для оценки эффективности предложенной структуры функции поощрения и выбранного метода распределения задач были проведены численные эксперименты, которые отражены на рисунке 11, с четырьмя вариантами формирования функции и вычисления суммарного времени простоя станков .

Рассматривалась система из 25 станков и 2 мобильных манипуляторов в течение 8-часовой рабочей смены. Суммарное время простоя  определялось как интеграл времени простоя каждого станка на протяжении всего периода работы.

В рамках экспериментов использовались следующие варианты функции стоимости:

1. Только энергетический критерий

Учитываются только затраты энергии на перемещение к станции и выполнение операции обслуживания, без учёта конфликтов движения и времени ожидания. Функция затрат имеет вид:

2. Энергетический критерий + предотвращение конфликтов движения

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

3. Полная структура функции поощрения без прогнозирования последовательности

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

4. Полная структура функции поощрения с прогнозированием последовательности из  задач

Этот вариант учитывает влияние текущего назначения на последующие задачи с ограниченным горизонтом планирования K=3, что обеспечивает более глобально оптимальное распределение задач между мобильными манипуляторами.

Рисунок 11. Влияние структуры функции поощрения на суммарное время простоя оборудования

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

Применение венгерского алгоритма для глобальной оптимизации распределения задач между мобильными манипуляторами позволяет найти оптимальное соответствие «робот–задача» по составленной матрице поощрений и гарантирует минимизацию суммарного времени простоя.

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