Введение

При случайных энергозатратах мобильному роботу может не хватить заряда для движения по запланированному маршруту и выполнения предусмотренных операций. Это требует алгоритмов распределения заданий и планирования подзарядки, учитывающих неопределенность энергозатрат. А. Б. Мигранов [1] рассмотрел нейродинамический алгоритм распределения заданий при погрешностях наблюдения координат. В настоящей работе геометрия считается известной, а неопределенность связана с энергозатратами. Рассматриваемая задача также отличается от исследованной в [1] источником случайности, ограничениями и критерием оценки.

F. Yang и N. Chakraborty [2] предложили алгоритм распределения заданий при вероятностных ограничениях на потребление ресурса. B. Fu, W. Smith, D. Rizzo, M. Castanier и K. Barton [3] применили вероятностный подход к построению маршрутов неоднородных роботов при гауссовской неопределенности энергозатрат. Таким образом, при планировании в условиях случайных энергозатрат необходимо учитывать не только их средние значения, но и разброс.

G. Notomista, S. Mayya, Y. Emam, C. Kroninger, A. Bohannon, S. Hutchinson и M. Egerstedt [4] рассмотрели распределение заданий с учетом энергозатрат и отказов оборудования. J. Herynek и S. Edelkamp [5] рассмотрели совместное планирование движения и пополнения энергии при неоднородном энергопотреблении. Эти результаты показывают взаимосвязь распределения заданий и планирования пополнения энергии.

H. Do, J. Jang и J. Kim [6] исследовали кооперативную подзарядку в гетерогенной группе роботов с выбором точек встречи, при которой выполнение миссии связано с организацией пополнения энергии. T. Ito, R. Funada, M. Sampei и G. Notomista [7] рассмотрели распределение заданий для роботов с несколькими режимами работы с учетом энергетических ограничений. Из этих работ следует, что энергетические ограничения влияют не только на допустимость отдельных маршрутов, но и на распределение заданий и координацию действий роботов. Поэтому энергетические ограничения следует учитывать непосредственно при построении группового плана.

B. P. Gerkey и M. J. Matarić [8] предложили классификацию задач распределения заданий. P. Mohajerin Esfahani и D. Kuhn [9] рассмотрели робастную оптимизацию при неопределенности распределения. M. C. Campi и S. Garatti [10] исследовали сценарный подход с вероятностными оценками допустимости решений. Подходы робастной и сценарной оптимизации показывают, что при выборе решения в условиях неопределенности необходимо учитывать не только значение выбранного критерия, но и устойчивость к неопределенности и вероятность выполнения ограничений. В настоящей работе этот принцип реализуется при настройке коэффициентов резервирования по доле успешных реализаций на отдельной настроечной выборке, а полученные решения оцениваются на независимой проверочной выборке.

N. Kumar, J. J. Lee, S. Rathinam, S. Darbha, P. B. Sujit и R. Raman [11] исследовали планирование подзарядки для длительной автономной работы роботов. T. Kundu и I. Saha [12] совместно рассмотрели маршрут робота, выполняющего подзарядку, и расписание зарядки. A. B. Asghar, S. Sundaram и S. L. Smith [13] исследовали длительное выполнение задач при ограничениях на подзарядку. K. B. Naveed, A. Dang, R. Kumar и D. Panagou [14] рассмотрели длительное выполнение заданий с учетом энергетических ограничений. M. S. Mondal, S. Ramasamy и P. Bhounsule [15] совместно планировали маршруты воздушных и наземных роботов при ограниченном запасе энергии. Анализ этих работ показывает, что распределение заданий и планирование подзарядки исследуются при различных энергетических ограничениях, однако влияние способа формирования энергетического резерва на групповой план отдельно не рассматривается.

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

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

Материалы и методы исследования

Постановка задачи. Заданы m роботов, n заданий и p зарядных станций. Индексы роботов, заданий и станций обозначены соответственно i = 1,…,m, j = 1,…,n, и h = 1,…,p. Каждое задание выполняется одним роботом один раз. План П задает для каждого робота упорядоченный список заданий πi и посещения станций. После выполнения заданий робот возвращается на свою базу. Кратчайшее расстояние dxy между узлами x, y, представляющими базы, задания и станции, находят поиском в ширину на сетке с четырьмя направлениями.

Для робота i заданы скорость vi, средние удельные энергозатраты ci, емкость Bimax, начальный заряд Bi0 и минимально допустимый заряд Bimin. Для задания j средние энергозатраты робота i равны wij, а длительность выполнения – τij. Скорость зарядки робота i на станции h равна γih. Для движения между узлами x, y время и средние энергозатраты равны соответственно dxy / vi и cidxy. Минимизируется номинальное время выполнения плана:

(1)

где Ti0(П) – время возврата робота, рассчитанное по средним энергозатратам с учетом ожидания освобождения зарядных станций. Минимизация выполняется по планам, удовлетворяющим ограничениям распределения заданий и выбранному условию резервирования. Между соседними заданиями допускается не более одного посещения станции. Зарядка также возможна до первого и после последнего задания. Переезд от одной зарядной станции к другой без выполнения задания не допускается.

Модель энергозатрат. Для действия a робота i средние энергозатраты μia равны cidxy при движении и wij при выполнении задания j. Одним действием движения считается весь переход между двумя узлами по найденному маршруту. Энергозатраты действия a робота i в отдельной реализации задаются выражением

(2)

В выражении (2) Zia – независимые стандартные нормальные величины, а υi = υqi – коэффициент вариации энергозатрат. Параметр υ задает общий уровень неопределенности, а qi определяет различия υi между роботами. Начальный заряд, время движения и длительность выполнения заданий считаются известными. Ожидание освобождения зарядной станции не сопровождается энергозатратами.

Резерв и подзарядка. Пусть Aiℓ – действия робота i на участке ℓ от старта или окончания зарядки до следующей станции либо базы. При независимых энергозатратах среднее и дисперсия их суммы равны

(3)

Участок считается допустимым, если выполняется условие

(4)

где Riℓ – энергетический резерв робота i на участке ℓ; – заряд робота в начале участка: Bi0 для первого участка и Bimax после полной зарядки. Сравниваются три варианта резервирования: D – без резерва, F – с постоянным резервом и U – с резервом по стандартному отклонению:

(5)

Коэффициенты η,κ ≥ 0 в (5) определяются на этапе настройки вариантов F и U. При вычислении Viℓ выполнение задания не разделяет участок на части. Минимально допустимый заряд Bimin учитывается один раз для каждого участка.

Станция обслуживает роботов в порядке прибытия, а при одновременном прибытии приоритет получает робот с меньшим индексом. Время зарядки робота i на станции h до полного заряда равно (Bimax – Bi) / γih. Для каждой реализации пересчитываются моменты прибытия, время ожидания освобождения станции и длительность зарядки. Распределение заданий, порядок их выполнения и посещения станций фиксированы. Реализация успешна, если все задания выполнены, роботы вернулись на базы и их заряд не снижался ниже Bimin. Энергия при выполнении каждого действия расходуется равномерно по времени.

Построение плана. Для заданной последовательности ni заданий робота i посещения станций выбираются динамическим программированием. Состояние (k,h) означает, что робот выполнил первые k = 0,…,ni заданий и завершил зарядку на станции h. Переход к следующей станции допускается после выполнения хотя бы одного задания при соблюдении условия (4). Зарядка перед стартом и старт без зарядки задаются отдельными состояниями. При выборе посещений станций учитываются время движения, выполнения заданий и зарядки без учета очередей других роботов. После выбора посещений станций групповой план оценивается по расписанию подзарядок, рассчитанному по средним энергозатратам.

Начальное распределение заданий получают жадным алгоритмом, выбирая робота с минимальным значением Li + dxi j / vi + τij, где Li – накопленное время, а xi – текущий узел. При построении начального распределения подзарядки не учитываются. На один запуск поиска отводится 320 оценок вариантов плана, включая начальный. Применяются операции переноса, обмена и инверсии с вероятностями 0,55; 0,30 и 0,15 соответственно. Допустимый план с большим по сравнению с текущим номинальным временем может быть принят с вероятностью exp(–ΔT / θb), где ΔT > 0 – увеличение номинального времени, b – номер оценки.

где T0best – номинальное время лучшего найденного плана.

Для недопустимого плана используется штраф

,

где Nf – число недопустимых маршрутов, а Pi = 1 + Ei0 / Bimax – для недопустимого маршрута и Pi = 0 иначе. Здесь Ei0 – номинальные энергозатраты по заданной последовательности база – задания – база без посещения станций. Для D, F и U одинаковы операции, число оценок и начальные состояния генератора случайных чисел. Для оценки влияния распределения и порядка заданий введен вариант UD: распределение и порядок фиксируются по D, а κ берется из настройки U. Посещения станций повторно выбираются динамическим программированием.

Настройка коэффициентов. Коэффициенты резервирования для F и U настраиваются независимо на настроечных картах. Для каждого коэффициента на каждой настроечной карте моделируются 1000 реализаций энергозатрат. Использовались значения η: 0; 0,04; 0,08; 0,12; 0,18; 0,24; 0,32; 0,40; 0,50; κ: 0; 0,5; 1; 1,5; 2; 2,5; 3; 3,75; 4,5.

Значение коэффициента считается допустимым, если для всех настроечных карт построены планы и нижняя односторонняя 95 %-я граница Уилсона для доли успешных реализаций каждого плана не ниже целевого уровня p*. Из допустимых выбирается значение с минимальным средним по настроечным картам значением критерия (1). Если допустимых значений нет, выбирается коэффициент, для которого наименьшая по настроечным картам нижняя граница Уилсона максимальна (максиминный критерий), а при равенстве значений этого критерия – коэффициент с минимальным средним номинальным временем.

Вычислительный эксперимент. Использованы 5 роботов, 30 заданий и 2 зарядные станции на сетке 70×70. Для каждого из двух типов карт сформированы 5 настроечных и 10 независимых проверочных карт. На рассеянных картах формировались 10 прямоугольных препятствий со сторонами 3–5 ячеек. На коридорных картах задавались две вертикальные стены толщиной 2 ячейки с двумя проходами высотой 5 ячеек. Базы и станции размещались в наибольшей свободной области у заданных опорных точек, обеспечивая достижимость и сопоставимое размещение. 30 заданий случайно выбирались без повторений из свободных ячеек, не занятых базами и станциями. На каждой проверочной карте выполнены три независимых запуска алгоритма поиска, а на каждой настроечной – один.

Емкости роботов задавались случайной перестановкой значений 225,4; 235,2; 245; 254,8 и 264,6. Начальный и минимально допустимый заряды составляли соответственно 90 и 8 % емкости батареи. Скорости и средние удельные энергозатраты задавались случайными перестановками значений 0,90; 0,97; 1,04; 1,11; 1,18 и 0,95; 1,00; 1,05; 1,10; 1,15 соответственно. Коэффициенты qi задавались случайной перестановкой значений 0,8; 0,9; 1; 1,1 и 1,2. Значения wij и τij независимо выбирались из равномерного распределения на [2; 5], а γih – на [2,6;3,2]. Размерные величины заданы в условных единицах.

Рис. 1. Проверочные карты и маршруты U при υ = 0,20, p* = 0,95: а – рассеянная карта (слева), б – коридорная карта (справа) Примечание: составлен автором по результатам вычислительных экспериментов

В основной серии исследовались значения υ: 0; 0,05; 0,10 и 0,20 при p* = 0,95 и по 500 реализаций на план. При υ = 0,20 дополнительно исследованы уровни p* = 0,90 и 0,99. Для p* = 0,99 использовано 1000 реализаций на план. Вариант UD проверялся на первых трех проверочных картах каждого типа: всего 6 карт, 18 планов и 9000 реализаций. Примеры планов варианта U на рис. 1, где круги – задания; квадраты – станции; треугольники – базы.

В эксперименте с коррелированными энергозатратами при υ = 0,20 использовалась модель

,

где ρ = 0,5, а Zi и – независимые стандартные нормальные величины. Параметр ρ задает общую случайную компоненту энергозатрат для действий одного робота. Использовались планы и коэффициенты, полученные при независимых энергозатратах и p* = 0,95. Для каждого плана выполнено 500 реализаций.

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

Повторные запуски усредняются по карте, затем карты учитываются с одинаковым весом. 95 %-е интервалы определяются по 2,5- и 97,5 %-м квантилям 2000 выборок с возвращением для каждого типа карт. Время сравнивается только для реализаций, успешных в обоих вариантах. Относительное изменение времени усредняется по запускам и картам.

Результаты исследования и их обсуждение

Для υ = 0,05 при целевом уровне p* = 0,95 по результатам настройки выбраны η = κ = 0. На проверочных картах варианты D, F и U дали одинаковые результаты (рис. 2), а сводная доля успешных реализаций составила 92,49 % [86,25; 97,52] %. На проверочной выборке точечная оценка ниже целевого уровня, но 95 %-й интервал его включает.

Рис. 2. Доля успешных реализаций плана и условное время его выполнения для двух типов карт. Интервалы построены по независимым картам Примечание: составлен автором по результатам вычислительных экспериментов

Таблица 1

Сравнение вариантов резервирования на 20 проверочных картах

Примечание: составлена автором по результатам вычислительных экспериментов.

Таблица 2

Парные различия показателей сравниваемых вариантов планирования

Примечание: составлена автором по результатам вычислительных экспериментов.

Для υ = 0,10 и p* = 0,95 выбраны η = 0,08 и κ = 1,5. Для υ = 0,20 при p* = 0,95 выбраны η = 0,18 и κ = 2,5, а при p* = 0,99 – η = 0,32 и κ = 3,75. При υ = 0,20 коэффициенты при p* = 0,90 и p* = 0,95 совпали.

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

Влияние распределения и порядка заданий на время выполнения плана. Для варианта UD доля успешных реализаций составила 99,133 % [98,733; 99,444] %, а условное время – 190,76 [167,14; 219,30]. На этих же шести картах условное время для U было меньше, чем для UD, на 18,83 единицы, или 9,11 % (табл. 2). Статистически значимых различий между U и UD по доле успешных реализаций не выявлено.

Коррелированные энергозатраты. При ρ = 0,5 сводная доля успешных реализаций плана составила 93,00 % [91,42; 94,50] % для F и 87,62 % [85,21; 89,90] % для U. В этом эксперименте корреляция энергозатрат не учитывалась при планировании: расчет по (3) выполнялся в предположении независимости энергозатрат отдельных действий.

Заключение

Предложен способ резервирования по стандартному отклонению суммарных энергозатрат между подзарядками, учитываемый при распределении заданий. При υ = 0,10 и υ = 0,20 у U условное время и число зарядок были меньше, чем у F, но доля успешных реализаций плана была ниже. На всех шести проверочных картах изменение распределения и порядка заданий уменьшило время выполнения плана. При υ = 0,05 точечная оценка доли успешных реализаций была ниже 95 %. При корреляции энергозатрат, не учитываемой при планировании, доля успешных реализаций была ниже 95 % для обоих вариантов.