Автор: Чжан Чжэнго, Мао Цзяньсюй, Тан Хаожань, Ван Яонань, Чжан Сюэбо, Цзян Имин

Источник: «Журнал автоматизации»

Редактор: Восточное побережье, потому что @ немного искусственного интеллекта, немного

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

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

Рисунок 1. Основные потребности в переработке оборудования

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

1) Высокая гибкость:многоробот Способен решать сложные проблемы посредством гибкой совместной работы。

2) Эффективность:通过многоробот Совместная работа над задачами для повышения эффективности работы。

3) Высокая надежность:当много个роботвыполнить задачу,Один из роботов неисправен,Другой робот все еще может выполнить эту задачу.

Эти преимущества привлекли многих академических и промышленных исследователей к изучению применимости мультироботов в промышленных и коммерчески важных областях, а в последние годы системы с несколькими роботами были на повестке дня в области робототехники. В 2011 году Гарвардский университет разработал Kilobot, недорогую систему из нескольких роботов, подходящую для крупномасштабных экспериментов, и провел групповые эксперименты с участием нескольких роботов [4]. Nature опубликовала отчет о самоорганизующемся бионическом мультироботе с более высокой масштабируемостью и надежностью [5]. В журнале Science было опубликовано исследование интеллектуального обучения с подкреплением с участием нескольких роботов, которое может выполнять обучение с подкреплением в динамически ограниченной среде [6].

Однако простое объединение нескольких роботов вместе не только не позволит реализовать преимущества системы из нескольких роботов, но также может вызвать конфликты и конфликты между роботами из-за параллельности и внезапности их поведения, конфликтов в позициях и т. д. Конфронтация снижает эффективность общая производительность, в результате чего общие преимущества крупномасштабных многороботных систем не могут быть полностью использованы [7]. Следовательно, необходимо изучить, в какое время, какие действия должны выполняться несколькими роботами и сколько роботов следует вызвать, чтобы обеспечить сотрудничество между несколькими роботами. То есть распределение задач нескольких роботов и планирование движения в сложных средах. центр принятия решений, определяющий основу для хорошего сотрудничества между несколькими роботами.

Как показано на рисунке 2, распределение задач и планирование движения нескольких роботов основаны на информации о карте окружающей среды и обеспечивают последовательность задач и траектории движения для производства крупных и сложных компонентов основного оборудования. Они играют важную роль в производственном процессе. Это связано с количеством и типом роботов. Оно тесно связано со сложной динамической средой, и объем вычислений, эффективность и безопасность в процессе распределения и планирования очень важны. С развитием науки и техники распределение задач и планирование движения между несколькими роботами постепенно применяются во всех сферах жизни. В области аддитивного производства Чжан и др. [8] создали масштабируемую систему распределения задач 3D-печати с несколькими роботами и систему планирования маршрутов, позволяющую рою роботов печатать произвольные геометрические фигуры на протяжении всего строительного задания. В области поиска и спасения в лесу Фён и др. [9] оптимизировали распределение времени и планирование траектории, вводя формулы вдоль траектории для выполнения таких задач, как обнаружение групп летающих роботов, поиск и спасение. В области взаимодействия человека и компьютера Али и др. [10] предложили метод распределения задач гетерогенной команды человек-машина, основанный на доверии робота-человека, для повышения эффективности распределения задач в команде человек-машина. В области совместной обработки Суарес-Руис и др. [11] использовали метод планирования траектории Bi-RRT для завершения полной сборки кресла. Ли и др. [12] завершили интеллектуальную задачу робота по приготовлению пищи, используя стратегию планирования движений, основанную на обучении с подкреплением.

Рисунок 2. Важность распределения задач и планирования движений в многопроцессном производственном процессе.

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

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

01  Исследование метода распределения задач между несколькими роботами

Как показано на рисунке 3, процесс распределения задач с участием нескольких роботов можно выразить как задачу оптимального распределения. Цель состоит в том, чтобы распределить задачи между роботами, одновременно оптимизируя общую производительность системы в условиях ограничений для достижения наилучшего общего эффекта выполнения задачи с несколькими роботами. Распределение — это совместный процесс. Одна из самых сложных задач в задании [13]. С одной стороны, распределение задач напрямую повлияет на эффективность всей системы, с другой стороны, когда один из роботов не может выполнить задачу, возможность совместной работы нескольких роботов для выполнения задачи посредством эффективных переговоров и распределения становится проблемой. обеспокоенность большего числа ученых [14]. Хотя в существующих исследованиях существует большое количество методов распределения задач, некоторым важным аспектам до сих пор уделяется мало внимания, включая распределение задач в сложных динамических средах, распределение задач региональных подразделений в крупномасштабных производственных средах, межрегиональное распределение задач и гетерогенное распределение задач робота.

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

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

Рис. 3. Проблема распределения задач для нескольких роботов

1.1 Режим выполнения распределения задач

1.1.1 Централизованное распределение задач

Централизованный метод — это более изученный тип метода. Основная идея — использовать центральный процессинговый центр для распространения и иметь каналы связи со всеми остальными серверами. Как показано на рисунке 4, этот процессинговый центр обладает глобальной информацией и определяет задачи, которые необходимо поручить другим серверам. В этих случаях часто считается, что глобальная функция полезности взаимодействует с другими серверами [15]. Например, методы централизованного распределения задач используются для производства и сборки автомобилей с участием нескольких роботов [16], задач обнаружения окружающей среды с использованием нескольких БПЛА [17], а задержки в доставке и выполнении задач сокращаются [18].

картина4 Централизованное распределение задачсистема

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

1.1.2 Распределенное распределение задач

Методы распределенного распределения задач преодолевают недостатки централизованного распределения задач и привлекли внимание исследователей в последние несколько лет. Как показано на рисунке 5, не существует центрального процессорного центра для распределенного распределения задач. Каждый робот имеет локальную осведомленность об окружающей среде и может общаться и договариваться друг с другом для выполнения задачи. Поэтому решение о распределении задач принимается локально. распределенным образом через полезность самой функции каждого робота [21]. Например, метод распределенного распределения задач можно использовать для уменьшения потребления задач несколькими роботами, сокращения времени распределения [22-23] и улучшения масштабируемости и эффективности производственного процесса [24].

картина5 Распределенное распределение задачсистема

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

1.2 Метод распределения задач для нескольких роботов

1.2.1 Метод распределения задач на основе линейного программирования

Оптимизация — это раздел прикладной математики. Цель состоит в том, чтобы найти оптимальное решение задачи из множества возможных решений. Этот набор возможных решений ограничен ограничениями. Целевая функция задачи определяется с помощью ограничений. Цель системы количественно описана [25]. Алгоритм, основанный на оптимизации, повышает адаптивность при обработке зашумленных входных данных и имеет более высокий потенциал при исследовании новых областей в неизвестном пространстве [26]. Методы, основанные на оптимизации, можно разделить на детерминированную оптимизацию и стохастическую оптимизацию в соответствии с целевыми категориями. Метод линейного программирования является одной из детерминистических оптимизаций. Идея состоит в том, чтобы преобразовать реальную проблему распределения задач в задачу решения математической модели и использовать линейную. Технология программирования. В последние годы смешанное целочисленное линейное программирование (MILP) стало одним из наиболее распространенных методов решения задач о назначениях благодаря своей строгости, гибкости и обширным возможностям моделирования [27].

Методы распределения на основе MILP первоначально использовались в химической инженерии и исследованиях операций. Реклайтис и др. рассмотрели распределение и планирование пакетных операций, сосредоточив внимание на основных компонентах распределения задач и доступных решениях [28]. В области распределения задач между несколькими роботами Берертон и др. использовали методы линейного программирования для решения проблемы распределения задач в совместных исследованиях с участием нескольких роботов [29]. Чтобы обеспечить существование решений для нескольких роботов в течение достаточно длительного времени, Шумахер и др. разработали оптимальный метод распределения задач и времени с использованием MILP, который можно использовать для оптимального распределения всех задач по связям с ограничениями по времени и порядку задач. Авиационная группа миссии [30]. Чтобы решить максимальную и минимальную задачу распределения задач, Не Минхонг и др. предложили матричный алгоритм, основанный на модели MILP, и сравнили вычислительную сложность с исчерпывающим решением и традиционным решением MILP. Теоретический анализ и численные эксперименты показывают, что. метод матричных операций эффективен для максимальных минимумов. Как задачи распределения задач с большим минимумом, так и задачи с общим минимумом могут эффективно обеспечивать оптимальные решения [31]. Чтобы минимизировать время цикла выполнения распределения задач, Облад и др. разработали пространственно-временную схему балансировки и координации нагрузки, используя модель MILP для управления распределением задач, последовательностью и движением робота (траекторией и скоростью) для предотвращения взаимодействия роботов. столкновения [32].

Хотя метод распределения задач, основанный на линейном программировании, позволяет получить глобальное оптимальное решение, из-за большого количества мультироботов и задач время решения увеличивается экспоненциально с увеличением размера задачи, что приводит к увеличению объема вычислений и низкая производительность в реальном времени. В этом случае расчет оптимального решения глобального распределения задач затруднен. Поэтому в последние годы его часто использовали вместе с другими методами в области многомашинного производства. Спенсьери и др. объединили метод смешанного целочисленного линейного программирования с рыночным методом обобщенной задачи коммивояжера, чтобы решить проблему совместного распределения задач нескольких промышленных роботов на заводе по производству автомобилей и избежать конфликтов задач между несколькими роботами [16]. Стремясь решить проблему, связанную с тем, что распределение задач и планирование последовательности операций в условиях внешних угроз снижают производительность и вероятность успеха, Ан и др. предложили метод распределения задач с планированием пути в реальном времени путем объединения методов MILP и потенциальных полей, а также разработали систему выбора задач. алгоритм компенсации модификаций. Последняя субоптимальная задача MILP [33]. Рассматривая проблему распределения задач между несколькими обнаружениями окружающей среды БПЛА, Ху и др. выполнили задачи атаки на набор заранее определенных наземных целей и разложили исходную проблему на три уровня подзадач: кластеризация целей, распределение кластеров и распределение целей. две подзадачи решаются централизованно с использованием алгоритма кластеризации и целочисленного линейного программирования соответственно, а третья подзадача решается с использованием модели смешанного целочисленного линейного программирования и улучшенного алгоритма муравьиной колонии распределенным и параллельным образом. Имитационные эксперименты подтверждают предложенный иерархический метод. может значительно снизить вычислительную сложность задач распределения задач [17].

Как показано на рисунке 6, метод, основанный на MILP, является очень строгим и может получить глобальное оптимальное решение. Однако, несмотря на это, решение проблемы большого объема вычислений и длительного времени вычислений алгоритма линейного программирования по-прежнему остается сложной проблемой. .

картина6 Метод распределения задач на основе линейного программирования[16-17,33]

1.2.2 Эвристический метод распределения задач

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

Алгоритм имитации отжига — это общий вероятностный алгоритм, предложенный Киркпатриком и др. Он используется для поиска оптимального решения предложения в большом пространстве поиска [34]. Оптимизируйте модель системы, установите целевую функцию, исходя из того, что количество областей задач поиска для каждого робота сбалансировано, и используйте метод распределенного моделирования отжига для решения проблемы распределения систем с несколькими роботами в больших сценариях [35]. Стремясь к проблеме распределения задач в гетерогенных распределенных системах, Аттия и др. предложили новый эвристический алгоритм моделирования отжига, создали модель распределения надежности функции стоимости и повысили надежность системы [36]. Однако метод моделирования отжига имеет такие недостатки, как медленная скорость сходимости, длительное время выполнения, производительность алгоритма, связанная с начальным значением, и чувствительные параметры. Когда время охлаждения установлено слишком быстро, глобальное оптимальное решение не может быть гарантировано.

Алгоритм роевого интеллекта — это биологический алгоритм. В природе отдельные организмы могут получать выгоду от действий групп. Модели индивидуального и коллективного поведения предполагают, что взаимодействия могут принимать форму групп, которые коллективно обрабатывают информацию и принимают решения. Обмениваясь информацией, группы могут принимать лучшие решения, чем отдельные люди, что называется «мудростью толпы» [37]. Алгоритм роевого интеллекта — это новая эволюционная вычислительная технология, которая привлекает внимание все большего числа исследователей. Она имеет особую связь с искусственной жизнью, особенно с эволюционными стратегиями и генетическими алгоритмами. Ли и др. рассмотрели проблему распределения задач в системе «умного склада», снизили общую стоимость робота за счет минимизации максимального времени выполнения и минимизировали сумму синергетического эффекта транспортировки всех заказов, учитывая предложенную ими степень агрегации. улучшенный алгоритм роя частиц для эффективного решения проблемы невыполненных заказов и задач, тем самым повышая эффективность системы хранения [38]. Панерати и др. предложили роевой эвристический алгоритм, в котором распределенный навигационный контроллер робота отвечает за обеспечение связи и выполнение нескольких задач, а контроллер глобального распределения задач аппроксимирует оптимальную стратегию с минимальной вычислительной нагрузкой для решения проблемы множества. -робот. Проблема пространственного охвата многозадачности [39]. Используя интерактивный процесс перемещения роботов в пространстве для распределения задач каждому роботу, Майя и др. создали аналитическую модель, основанную на алгоритме колонии муравьев, для описания столкновений, происходящих в плотной группе роботов, что позволяет нескольким роботам адаптироваться в зависимости от ситуации. расстояние между текущим заданием и ожидаемым значением. Скорость переключения между задачами в конечном итоге способствует тому, чтобы робот выполнял задачи без перерывов [22]. В процессе сборки колеса Гита и др., чтобы завершить оптимальное распределение допусков, распределили допуски компонентов путем минимизации производственных затрат (суммы затрат на допуск и потерю качества) и затрат на время простоя машины, а также разработали генетический алгоритм для распределение допусков на компоненты и определение оптимальной последовательности продуктов для распределения [40].

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

Рисунок 7. Распределение задач на основе эвристического алгоритма [34-40]

1.2.3 Рыночный метод распределения задач

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

Чтобы решить проблему скоординированного распределения задач в автономных транспортных средствах, Чой и др. использовали рыночную стратегию распределенного принятия решений в качестве механизма выбора задач, а также использовали процедуры консенсуса локальной связи в качестве механизма разрешения конфликтов для достижения консенсуса по выигравшей заявке. ценить. Доказано, что при разумных предположениях о схеме оценки разработанный метод способен сходиться к бесконфликтным назначениям с лучшими свойствами сходимости по сравнению с существующими алгоритмами распределения задач на основе аукционов [42]. Принимая во внимание фактор чрезмерного потребления энергии при совместной работе роботов, Ву и др. разработали метод распределения задач на основе коэффициента Джини. В метод на основе коэффициента Джини был интегрирован механизм рыночного распределения, который позволяет сократить количество раз. та же задача выполняется в соответствии с потреблением ресурсов приложения [43]. Стремясь решить проблему распределения задач для нескольких БПЛА в динамической среде с ограниченной дальностью связи, Ох и др. предложили новый рыночный метод распределенного распределения задач. масштабируемость и эффективность алгоритма [24]. Чтобы обеспечить эффективное использование совместных роботов и беспрепятственное распределение задач при выполнении задач по сборке самолетов, Терещук и др. использовали геометрию заготовки и структуру задачи для создания сбалансированного и бесконфликтного плана распределения роботов в номинальных условиях, а затем использовали. рыночный оптимизатор для распределения задач. Обработка сбоев задач для сокращения времени расчета распределения задач [23]. Чтобы решить проблему совместной обработки контейнеров, Чен и др. предложили рыночный подход, основанный на интеграции железнодорожных кранов и распределения AGV, и получили экономически эффективное решение путем итеративной корректировки исходной стоимости и двойной стоимости. каждой подзадачи [ 44 ].

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

1.2.4 Метод распределения задач на основе обучения

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

Обучение с подкреплением — это классический метод машинного обучения, в котором центральный обрабатывающий центр использует прошлую информацию, чтобы научиться действовать в различных средах. Внешнюю среду обычно описывают как марковские процессы принятия решений (MDP), которые центральный процессорный центр оптимизирует с помощью функции затрат или функции вознаграждения, что позволяет роботу учиться в окружающей среде. Уилсон и др. применили метод обучения с подкреплением к задаче многозадачного распределения и использовали иерархическую байесовскую модель бесконечной смеси для моделирования распределения MDP. Иерархическая байесовская структура обеспечивает мощные априорные условия и может быть основана на прошлой среде. характеристики новых сред при использовании непараметрических моделей для быстрой адаптации к неизвестным средам. Предложенный метод позволяет значительно ускорить сходимость к оптимальной стратегии распределения задач, когда наблюдается лишь небольшое количество задач [46]. Чтобы уменьшить задержку на этапах доставки и выполнения задач, Май и др. предложили метод обучения с подкреплением эволюционной стратегии, позволяющий распределять задачи в реальном времени между облачными серверами, чтобы уменьшить общую задержку вычислений в долгосрочной перспективе. Предлагаемый метод позволит сократить задержку примерно на 16,1%[18]. Чтобы назначить задачи соответствующим роботам для достижения различных целей, Сан и др. сначала использовали блок замкнутого контура модели глубокого обучения для прогнозирования типов и количества предстоящих задач и роботов, а затем изучили метод, основанный на Deep Q-сети (Deep Q-network). Deep Q-network, DQN) и Double DQN (Double deep Q-network, DDQN) стратегия адаптивной пакетной обработки для решения проблем адаптации к среде и динамического пакетного распределения при распределении задач [47]. Чтобы решить проблему вычислительной сложности эвристических методов для крупномасштабных и динамических процессов распределения задач, Ван и др. предложили метод распределения, основанный на графовой нейронной сети, для автоматического изучения характеристик проблемы процесса распределения, преодоления ограничений большого размера. масштабное распределение задач и полное высококачественное распределение задач [48]. Чоудхури и др. рассмотрели динамическое распределение задач между несколькими роботами в условиях ограничений временного окна и неопределенности выполнения задач и предложили алгоритм глубокого обучения со случайными конфликтами для нескольких роботов, который улучшил масштабируемость количества роботов и использовал многорычажные конвейерные ленты. Такие задачи, как выбор и размещение, подтверждают эффективность предложенного метода [49].

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

картина8 Метод распределения задач на основе обучения[46-49]

1.2.5 Алгоритм распределения гибридных задач

Обычно использование только одного алгоритма распределения задач сложно удовлетворить потребности распределения задач между несколькими роботами в сложных производственных сценариях, поэтому необходимо использовать два или более метода в комбинации. Воспользовавшись высокой строгостью алгоритма линейного программирования, Спенсьери и др. объединили его с рыночным методом для решения проблемы производства автомобилей [16], Ан и др. объединили его с методом потенциального поля для компенсации проблемы падения. в локальный оптимум [33] и сложность [17].

Чжоу и др. рассмотрели проблему распределения задач совместной точечной сварки с несколькими роботами и несколькими станциями и построили общую модель оптимизации для улучшения адаптивности и осуществимости связанных алгоритмов в практических приложениях, используя решатель, который использует итеративное трапециевидное ускорение и замедление для решения. На этой основе задача распределения задач одного робота принимает задачу распределения задач сварки со многими ограничениями между роботами и объединяет генетический алгоритм для итеративного решения многозадачной задачи сварки [50]. Терещук и др. рассмотрели возможность использования нескольких совместных роботов-манипуляторов для сборки крупных авиационных конструкций, требующих дискретных задач, таких как сверление и установка крепежных элементов, чтобы сократить большие временные затраты, связанные с заменой инструментов. Они предложили гибридный алгоритм распределения задач. Сначала настройте итеративный аукцион. Метод использует эвристику для кодирования отношений приоритетов, а во-вторых, разрабатывает метод машинного обучения для автоматического выбора эффективной эвристики распределения на основе характеристик проблемы [51]. Рассматривая сложные проблемы внутренней структуры больших космических кораблей, Лю предложил модель конфликта для описания конфликтных ограничений конкретной задачи, определил области взаимодействия в каждой рабочей области и разработал эвристический метод быстрого построения, сочетающий эвристику с итеративным локальным поиском. выполнение задачи с оптимальной эффективностью [52]. Пайва и др. предложили метод, который использует комбинацию алгоритма поиска по графу, эвристического метода и метода машинного обучения для решения проблемы сортировки заданий и переключения инструментов [53].

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

Рисунок 9. Метод распределения задач на основе гибридного алгоритма [50-53]

1.3 Распределение задач между несколькими роботами в сложных производственных сценариях

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

1.3.1 Метод разделения зон рабочей сцены

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

Рисунок 10 Региональное разделение по разному количеству роботов[54]

Ши и др. [55] рассмотрели влияние разнородных роев роботов на выборку и моделирование характеристик окружающей среды и предложили метод разделения среды в сочетании со структурой обучения модели гауссовского процесса для адаптивной выборки и моделирования окружающей среды эффективным и масштабируемым образом. Моделирование региональных подразделений подтвердило эффективность предложенного метода в условиях сотрудничества «воздух-земля».

1.3.2 Метод распределения задач на основе изготовления сложных сцен

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

Рисунок 11. Распределение нескольких задач в сложных сценариях эксплуатации [56, 58]

Митиче и др. [57] предложили эвристический алгоритм, основанный на плагине, для решения проблемы распределения задач статического расширения времени для нескольких роботов. Хэм и др. [58] использовали алгоритм поиска больших окрестностей для решения проблемы распределения последовательности работ при выполнении задач с участием нескольких роботов при сборке самолетов Boeing 777. Хуанг и др. [59] использовали модель обучения с подкреплением, основанную на алгоритме Distributed-Q, для решения проблемы распределения задач в процессе совместной обработки нескольких роботов. Гил и др. [60] использовали иерархическое обучение с подкреплением для решения проблемы распределения задач между несколькими роботами в крупномасштабных сложных средах.

1.3.3 Метод межрегионального распределения задач

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

Как показано на рисунке 12, Ю и др. [61] учли сложность распределения нескольких роботов в пространстве и времени и предложили новый улучшенный генетический алгоритм, основанный на новом формате кодирования хромосом, который может не только дополнять мультигетерогенность. БПЛА Координируйте распределение задач между регионами и учитывайте требования к задачам, возвращая роботов, выполняющих задачи, на подходящую базу, а не возвращаясь на исходную базу. Основываясь на улучшенном жадном алгоритме, Чжан и др. [62] предложили метод межрегионального распределения задач, основанный на модели онлайн-распределения, и оптимизировали процесс распределения задач с помощью автономного руководства и стратегий онлайн-распределения, которые могут выполнять больше задач в режиме онлайн. то же время.

Рисунок 12 Межрегиональное распределение задач с участием нескольких роботов[61-62]

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

Таблица 1. Анализ методов распределения задач

02  Планирование движения нескольких роботов

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

Планирование движения означает создание математического выражения пути функции, которое удовлетворяет конкретным ограничениям на основе уравнений движения робота в заданном начальном состоянии и целевом состоянии задачи. Ограничения в основном включают кинематические ограничения, ограничения динамики, ограничения пути, ограничения препятствий или ограничения. Энергетические ограничения и т. д. Планирование движения включает в себя планирование пути и планирование траектории и является одной из горячих точек исследований в области робототехники [64]. Цель планирования пути — найти стратегию соединения точек последовательности начального состояния и целевого состояния так, чтобы расстояние между найденной точкой последовательности и препятствием было как можно большим, а путь к месту назначения был как можно больше. как можно короче. Планирование траектории добавляет информацию о времени к планированию пути и использует форму квадратичного интегрального полинома по времени, чтобы получить скорость и ускорение робота от начального состояния до целевого состояния, взяв производные времени первого и второго порядка, чтобы определить Кривая движения робота Максимально плавная, время движения как можно короче, а стоимость движения как можно меньше. Когда планирование пути удовлетворяет временным ограничениям робота, планирование пути является планированием траектории [65].

Существующие исследования включали разработку и проверку методов планирования движения в подводных роботах[66-67], роботах, карабкающихся по стенам[68] и микросамолётах[69-70].,Он также использует различные методы для представления,Внес большой вклад в развитие роботизированного спортивного планирования. но,В приведенном выше исследовании проводился анализ планирования пути только для различных типов одиночных роботов. Как показано на рисунке 13.,Производство крупных и сложных деталей характеризуется большими сценами, множеством задач и ограниченным рабочим пространством.,Планирование движения по-прежнему представляет собой серьезную проблему в междисциплинарных областях.,Экспоненциальный рост пространства поиска, вызванный добавлением каждого нового робота, является одной из проблем, которую необходимо срочно решить. в настоящий момент,Планирование движения нескольких Метод роботов в основном делится на планирование движения на основе поиска, Планирование. движения на основе потенциального поля、Методы планирования движения на основе выборки и методы планирования движения на основе искусственного интеллекта.

Рисунок 13 Планирование в сложных сценариях движения нескольких роботов

2.1 Планирование движения нескольких роботовметод

2.1.1 Алгоритм планирования на основе поиска

Метод планирования движения на основе поиска обладает хорошей стабильностью и точностью. Это относительно зрелый метод планирования движения, который широко используется в области мобильных роботов и игр. Алгоритм поиска в ширину, алгоритм Дейкстры, алгоритм A*, алгоритм D* (динамический A*) и алгоритм поиска конфликтов — все это отличные представители, основанные на методах поиска.

Поиск в ширину [71] может найти оптимальное решение проблемы планирования движения. Этот алгоритм использует начальное состояние в качестве центра и постепенно исследует внешние слои. Алгоритм тратит много времени на исследование бесполезных областей, и эффективность поиска пути снижается. низкий. . Алгоритм Дейкстры [72], предложенный ученым-компьютерщиком Нг и др. в 1959 году, представляет собой жадный алгоритм, который сочетает в себе поиск в ширину и эвристический поиск. Он сначала вычисляет кратчайшее расстояние от начальной позиции до каждой позиции в среде, а затем инициализирует. расстояние. Ближайшая точка используется в качестве точки ретрансляции, затем обновляется кратчайшее расстояние от начальной позиции до каждой позиции, а затем описанные выше шаги повторяются до тех пор, пока все позиции в среде не будут пройдены как точки ретрансляции. получить кратчайшее расстояние от исходного положения до любого положения в окружающей среде. Однако алгоритм Дейкстры сохраняет проблему, заключающуюся в том, что поиск в ширину требует большого количества вычислений для поиска допустимого решения и менее эффективен. Алгоритм A* [73], предложенный Хартом и др., представляет собой эвристический алгоритм, основанный на алгоритме Дейкстры для улучшения сортировки по приоритетам. Алгоритм объединяет вес узла и расстояние до целевой точки в качестве правила сортировки по приоритету. требуется только доступ. Оптимальное решение проблемы планирования движения может быть получено с меньшим количеством узлов. В то время как алгоритм Дейкстры и алгоритм A* подходят только для сценариев, в которых среда известна, алгоритм D* [74], предложенный Стенцем, может применяться к неизвестным или динамически изменяющимся средам. Алгоритм D* является противоположностью алгоритма A*, начиная с целевой позиции и осуществляя поиск до тех пор, пока не будет найдена начальная позиция робота. Суть алгоритма D* заключается в вычислении функции состояния процесса оптимального пути и функции коррекции затрат в ответ на изменения экологической информации. Когда на рассчитанном допустимом пути появляется новое препятствие, алгоритму D* нужно только обработать близлежащие узлы и распространить воздействие на местоположение робота, тем самым уменьшая объем вычислений по перепланированию. Основанный на алгоритме D* алгоритм D* Lite, предложенный Кенигом и др., повышает эффективность поиска пути при планировании движения [75-76]. Алгоритм Field D*, предложенный Фергюсоном и др., не может быть ограничен направлением поиска. и делает путь планирования более плавным [77].

В последние годы методы планирования движения на основе поиска также получили определенное развитие в операциях с участием нескольких роботов, используя A*. В алгоритме используется центральный обрабатывающий центр для проверки всех путей, созданных глобальным планировщиком пути, во избежание столкновений. Центральный обрабатывающий центр анализирует данные о пути каждого робота и их влияние на траектории других роботов для определения глобальной траектории. Когда робот начинает двигаться к месту назначения, центральный обрабатывающий центр в режиме реального времени проверяет, не конфликтует ли его траектория с траекторией других роботов, чтобы достичь цели совместного предотвращения препятствий несколькими машинами [78]. Чтобы получить высококачественные траектории без столкновений для нескольких роботов, Чэнь Гуанъю и др. предложили метод, основанный на улучшенном A*. Алгоритм двухуровневого планирования с участием нескольких роботов и стратегия координации конфликтов вводят измерение времени на основе двумерного пути, создают график пути-времени робота и прогнозируют конфликты во временном измерении робота. Конфликты между роботами, а также между роботами и динамическими препятствиями координируются с помощью стратегий координации конфликтов [79]. Рен и др. предложили оценку D* на основе многоцелевых путей. Алгоритм (Многокритериальный path-based D* lite, MOPBD*), использует стратегию расширения на основе путей для вычисления доминирующего решения и представляет MOPBD*. Субоптимальный вариант, повышающий эффективность поиска в динамических средах [80]. Решить Планирование движения нескольких Конфликтные коллизии в процессе роботов и проблема низкой эффективности поиска пути алгоритма A* Шарон и др. предложили алгоритм поиска на основе конфликтов (Conflict. based поиск (CBS) — двухуровневый алгоритм, в котором поиск осуществляется по дереву конфликтов между индивидами высокого уровня. Каждый узел в дереве конфликтов представляет собой набор ограничений на процесс движения, а также быстрый одноуровневый поиск. машинный поиск выполняется на низком уровне для удовлетворения ограничений, налагаемых узлами дерева конфликтов высокого уровня. Благодаря двухуровневому алгоритму алгоритм CBS может иметь меньшую вычислительную сложность, чем алгоритм A*, сохраняя при этом оптимальность [81]. Однако при определении того, конфликтует ли узел, разделение и перепланирование узла занимает много времени. Чжан и др. предложили алгоритм параллельного поиска на основе конфликтов и разработали алгоритм глобального планирования пути и уровня датчика. соответствующие человеческому мозгу, глазам и ногам. Планирование пути и планирование пути на уровне действий ускоряют расширение узлов [82]. Чтобы завершить планирование захвата нескольких роботов для последовательных операций сборки, Догар и др. использовали алгоритм поиска конфликтов и сформулировали поиск как задачу удовлетворения ограничений (Constraint). satisfaction проблема, CSP), разделение CSP на независимые более мелкие задачи может быть решено экспоненциально [83].

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

Рисунок 14 Планирование движения на основе поиска [78-82]

2.1.2 Алгоритм планирования на основе потенциального поля

Метод планирования движения, основанный на потенциальном поле, направляет алгоритм на поиск возможных путей путем построения потенциальной функции без необходимости точного исследования информации об окружающей среде. Самый ранний алгоритм планирования, основанный на потенциальных полях, восходит к методу искусственного потенциального поля, предложенному Хатибом в 1985 году. На движение робота в космической среде влияет виртуальное искусственное силовое поле. Целевое положение оказывает гравитационное воздействие. робот и препятствия оказывают на робота отталкивающее воздействие, под действием силы тяжести и отталкивания движение робота контролируется алгоритмом для достижения целевого положения.

Лю и др. предложили метод потенциального поля, который сочетается с концепцией виртуальных препятствий [84]. Этот алгоритм рассчитывает среднюю точку как временную целевую точку для решения проблемы, связанной с тем, что традиционный метод искусственного потенциального поля легко попадает в локальную оптимальность. Ши Хонгян и др. объединили алгоритм хаотической оптимизации с методом искусственного потенциального поля и предложили метод хаотического искусственного потенциального поля, который позволяет роботу избегать препятствий в динамической среде в реальном времени, не попадая в поиск локального оптимального решения. путь [85]. Скотт и др. предложили новую форму потенциальной функции [86]. Эта потенциальная функция включает упругий потенциал, позволяющий избежать суставных ограничений, отталкивающий потенциал, позволяющий уводить манипулятор от препятствий, и потенциальный потенциал, предотвращающий падение манипулятора в сингулярное состояние. состояние. Три компонента объединены. Установлена ​​потенциальная функция руки робота по предотвращению препятствий, и на этом основании часть, заблокированная линией обзора камеры, рассматривается как виртуальное препятствие, что эффективно уменьшает проблему столкновения робота. рука, вызванная окклюзией камеры в динамической среде. Ли и др. предложили алгоритм планирования движения NP-APF (Новое точечно-искусственное потенциальное поле) [87]. Когда робот сталкивается с препятствием, алгоритм сначала выбирает подходящую позицию для создания притяжения к роботу, а затем на основе этого. Выбранная оптимизация положения размера и направления равнодействующей силы на роботе помогает роботу быстро избавиться от ограничений, связанных с препятствиями, и улучшает возможности планирования традиционных алгоритмов искусственного потенциального поля. Хан Вэй и др. предложили метод искусственного потенциального поля в сочетании с нечетким принятием решений, который позволяет адаптивно регулировать размер и направление результирующей силы, получаемой роботом в виртуальном искусственном потенциальном поле [88]. Мамани и др. применили метод потенциального поля к мультимобильным дифференциальным роботам и предложили список требований к управлению пластом. На этой основе они создали модель управления пластом с несколькими роботами, основанную на методе потенциального поля [89]. Чтобы завершить оптимальное планирование пути от исходной позиции до целевой точки, Пан и др. предложили метод планирования пути с участием нескольких роботов, который улучшает функцию искусственного потенциала. Путем введения вращающегося потенциального поля роботы могут эффективно уйти из зоны действия. общий минимум и колебание [90] . Матуи и др. использовали улучшенный метод искусственного потенциального поля, использовали алгоритм неминимальной скорости для решения минимальной локальной проблемы и решили проблему пересечения роботов, проходящих в одной и той же точке, с помощью метода распределения приоритетов между роботами. Во-вторых, технология обнаружения соседства используется для уменьшения зоны влияния каждого робота и оптимизации времени планирования планирования [91]. Ву и др. ввели ограничения усиления и случайные факторы, чтобы улучшить метод искусственного потенциального поля, подавить колебания траектории, избегая при этом локальных минимумов, и использовали оптимизацию кривой B-сплайна для сглаживания запланированной траектории [92].

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

Рисунок 15 Планирование движения на основе метода искусственного потенциального поля [88, 91]

2.1.3 Алгоритм планирования на основе выборки

Методы планирования движения на основе выборки получили широкое внимание в области планирования движения благодаря своим значительным преимуществам в многомерном пространстве [93]. В настоящее время методы планирования движения на основе выборки в основном делятся на улучшенные, основанные на вероятностных дорожных картах (PRM). версии алгоритма и улучшения на основе алгоритма быстрого исследования случайных деревьев (RRT) и т. д.

Алгоритм PRM [94], предложенный Кавраки и др. в 1996 году, в то время считался наиболее успешным методом решения сложных задач планирования движения в многомерном пространстве. Сложность алгоритма связана, в первую очередь, со сложностью поиска. возможные пути, а во-вторых, влияют размеры и размерность пространства. Алгоритм PRM разделен на два этапа: выборка и запрос. Процесс выборки выполняет случайную и равномерную выборку в свободной среде, ищет соседние узлы для каждой точки выборки и на этой основе устанавливает дорожную карту вероятности соединения без коллизий. В процессе запроса используется алгоритм поиска. Найдите подходящий путь из дорожной карты.

Алгоритм RRT, предложенный Ла Валлем в 1998 году, представляет собой метод случайной выборки с древовидной структурой [95]. Этот алгоритм использует начальную позицию задачи планирования движения в качестве корневого узла, добавляет ветви узлов посредством случайной выборки и генерирует случайное дерево поиска. в свободной среде, когда ветвь дерева случайного поиска расширяется до целевой позиции, можно получить путь движения от начальной позиции до целевой позиции. На основе алгоритма RRT Ван Леле и др. предложили улучшенный алгоритм планирования пути формирования нескольких роботов со случайным деревом быстрого расширения для решения проблемы планирования пути формирования нескольких роботов в сложных средах. При этом определяется структура лидер-последователь между роботами и устанавливается связь между направлением расширения дерева поиска и направлением формирования для решения проблемы изменения направления формирования в процессе планирования [96]. Чтобы решить проблемы алгоритма RRT, такие как ограниченная область поиска, большие затраты времени и плохая осуществимость результатов, Чэнь Цзиньтао и др. предложили алгоритм леса RRT путем случайного выбора корневых узлов, генерации случайных деревьев, а также соединения и слияния. случайные деревья, это делает пожаротушение на высотных зданиях более эффективным. Эффективность совместного планирования траектории движения БПЛА в сложных помещениях была значительно улучшена. Кроме того, для дальнейшего улучшения осуществимости маршрута используются двойное динамическое программирование и улучшенные методы обнаружения близости препятствий [97]. Алгоритм RRT имеет тенденцию расширять неисследованную область. По мере увеличения количества итераций поиска неисследованная область уменьшается. Можно сделать вывод, что алгоритм RRT обладает сильной способностью исследовать пространство и работает быстро. Этот алгоритм вероятностно полон и неоптимален и позволяет быстро находить возможные пути. Однако найденный путь обычно не является оптимальным и содержит множество ребер и углов.

Чтобы решить проблему, заключающуюся в том, что путь, запланированный алгоритмом RRT, не является оптимальным возможным путем, Караман и др. добавили функцию перемонтирования и функцию стоимости в алгоритм RRT в 2011 году и предложили алгоритм RRT* [98]. Этот алгоритм улучшает метод выбора родительского узла алгоритма RRT и выбирает каждый узел с минимальным значением функции стоимости. Поэтому, когда узлы выборки имеют тенденцию быть бесконечными, возможный путь, рассчитанный алгоритмом RRT*, должен сходиться к оптимальному пути. Стремясь к проблеме исследования океана подводным роботом, Cui и др. предложили метод многомерного планирования пути RRT* для определения положения выборки подводного робота путем максимизации информации между моделью скалярного поля и значениями наблюдения для улучшения. качество взятых проб [ 99 ]. Однако как алгоритм RRT, так и алгоритм RRT* имеют проблему, связанную с дорогостоящими вычислениями обнаружения столкновений, и на обнаружение столкновений тратится много времени [100-101], особенно в сложных средах с множеством препятствий. алгоритм значительно сокращается.

Алгоритм FMT* (быстро идущее дерево*) [102], предложенный Янсоном и др., сочетает в себе преимущества алгоритма PRM и алгоритма RRT для решения сложных задач планирования движения в многомерном пространстве. Этот алгоритм структурно уменьшает большое количество повторных обнаружений столкновений, а также уменьшает количество параметров, которые необходимо корректировать в процессе решения узлов. Алгоритм FMT* повышает скорость сходимости нескольких роботов к оптимальному пути при одновременном уменьшении количества. расчетов. Чтобы повысить эффективность и масштабируемость, Ле и др. предложили метод скоординированного расширенного дерева поиска, основанный на алгоритме RRT. Они сначала разработали метод выборки с одним роботом для отслеживания заданного маршрута, а затем разработали следящего по пути, чтобы гарантировать, что каждый. Робот следует по заданному маршруту. В то же время можно избежать столкновений с другими роботами, а предлагаемый метод может решить проблему составного пространства состояний высокого порядка, вызванную увеличением количества роботов, и имеет хорошую масштабируемость [103]. На основе непрерывного процесса планирования движения выборки нескольких роботов Даян и др. с помощью тензорных продуктов сконструировали несколько диаграмм PRM роботов в тензорные дорожные карты для поддержки высококачественных решений в течение ограниченного времени [104].

Как показано на рисунке 16, в последние годы постоянно предлагались улучшенные версии алгоритма PRM и алгоритма RRT, которые хорошо работают в области планирования движения роботов и имеют теоретическую поддержку, такую ​​как предотвращение препятствий и вероятностная полнота. Однако противоречие между корректировкой времени работы алгоритма и оптимальностью алгоритма, а также проблема слепоты при исследовании — это проблемы, которые должен решить алгоритм планирования на основе выборки.

Рисунок 16 Планирование движения на основе выборки [96, 99, 102]

2.1.4 Алгоритм планирования на основе искусственного интеллекта

С развитием технологий искусственного интеллекта алгоритмы искусственного интеллекта постепенно применяются к Планированию. движения нескольких роботовпод вопросом[105-106]。常见的人工智能运动规划метод有遗传算法、Алгоритм муравьиной колонии、алгоритм роя частиц、алгоритм искусственной нейронной сети、Алгоритмы машинного обучения и т. д.

Генетический алгоритм (ГА) [107], предложенный Бхадури в 1975 г., представляет собой алгоритм поиска оптимального решения, моделирующий процесс биологической эволюции природы. Этот алгоритм рассматривает возможные пути как индивидуумы в задачах планирования движения. Число возможных путей, содержащихся в каждой популяции, представляет собой количество особей, а количество точек пути в каждом возможном пути — это количество хромосом в особи. В процессе итеративной эволюции генетические операторы используются для выполнения таких операций, как селекция, скрещивание генов и мутация генов. Популяции с низкой приспособленностью исключаются, а популяции с высокой приспособленностью сохраняются. Конкуренция «выживает наиболее приспособленный». последний сохраненный путь: наилучший возможный путь, найденный алгоритмом. Назарахари и др. предложили улучшенный генетический алгоритм (EGA) для улучшения начального пути в непрерывном пространстве, поиска допустимого начального пути на основе детерминированной схемы, экономящей время, и гарантированного поиска допустимого пути (если он существует). В то же время алгоритм EGA использует пять настраиваемых операторов скрещивания и мутации для улучшения исходного пути [108]. Однако генетический алгоритм обладает высокой случайностью, а результаты выполнения каждого вызова различны, и существует даже вероятность несходимости.

Алгоритм колонии муравьев (ACA) [109], предложенный Дориго и др. в 1992 году, представляет собой бионический вероятностный алгоритм, который использует механизм положительной обратной связи для моделирования муравьев, постепенно находящих кратчайший путь на основе феромонов, выделяемых их товарищами при поиске пищи. Процесс продолжает сходиться, пока не приблизится к оптимальному допустимому пути [110]. Хасан и др. объединили алгоритм колонии муравьев с алгоритмом D*, рассмотрели динамические препятствия в свободном пространстве и построили функцию вероятности для выбора наилучшего пути для каждого робота для достижения динамического обхода препятствий [111].

Алгоритм оптимизации роя частиц [112] (PSO), предложенный Кеннеди в 1995 году, представляет собой алгоритм оптимизации для моделирования хищничества птиц. Этот алгоритм позволяет группе развиваться к оптимальному возможному решению посредством обмена информацией и сотрудничества между отдельными птицами. Алгоритм оптимизации роя частиц повышает скорость обнаружения оптимальных решений в сложных средах. Ван и др. предложили гибридный алгоритм роя частиц, состоящий из алгоритма непрерывного роя частиц и алгоритма роя дискретных частиц. Алгоритм непрерывного роя частиц оптимизирует центральное положение и угол вращения желаемого образования, а алгоритм роя дискретных частиц используется для этого. оптимизировать исходное положение и соотношение соответствия целевого положения [113]. Для задачи поиска цели несколькими роботами в неизвестных средах Дадгар и др. предложили распределенный алгоритм, основанный на оптимизации роя частиц, чтобы избежать попадания в локальную оптимальность [114].

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

В 2017 году Пфайффер и др. предложили метод планирования движения, основанный на обучении с учителем, и создали сетевую модель относительного положения цели на основе сверточной нейронной сети (CNN) на основе результатов лазерной локации [117], но структура обучения с учителем опирается на Отмеченные алгоритмы обладают слабой способностью к обобщению изменений окружающей среды. Обучение с подкреплением создает таблицу посредством итерации стоимости, которая используется для хранения сопоставления состояния с процессом действия, и направляет несколько роботов для перемещения в целевую позицию на основе информации таблицы. Столкнувшись с проблемой онлайн-планирования оптимального по времени пути для нескольких роботов, на которое влияют предотвращение столкновений и ограничения на входные данные, Он и др. включили искусственное потенциальное поле в приблизительную функцию стоимости и предложили метод интегрального обучения с подкреплением, чтобы минимизировать временную энергию конечного. горизонт с входными ограничениями. Задача преобразуется в задачу оптимального управления с приблизительно бесконечным горизонтом [118]. Однако в среде, где информация о препятствиях меняется, необходимо создавать большое количество таблиц, что занимает место в памяти. Тай и др. применили глубокое обучение с подкреплением для решения задач планирования движения. Им нужно только указать цель планирования движения, позволить им много пробовать в сценариях планирования моделирования, постоянно учиться и независимо итеративно обновлять сеть на основе полученных вознаграждений и штрафов. , тем самым решая более сложную задачу. Хороший допустимый путь [119]. В ответ на проблему, заключающуюся в том, что традиционными методами трудно идентифицировать других мобильных роботов как препятствия или коллаборативные роботы, Бэ и др. объединили сеть CNN и алгоритм глубокого обучения с подкреплением, в котором сеть CNN использует информацию об изображении окружающей среды для анализа. точную ситуацию, в то время как робот использует глубокое обучение с подкреплением для анализа ситуаций и планирования [120]. Чтобы решить проблему планирования движения в процессе сверления листового металла, Вирамани и др. смоделировали задачу идентификации оптимального пути как марковскую задачу принятия решений и выбрали независимую от модели стратегию планирования разницы во времени: стратегия «состояние-действие-вознаграждение-состояние-действие». алгоритма и были описаны на основе параметров задачи планирования пути [121].

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

Рисунок 17 Планирование движения на основе искусственного интеллекта [108, 114, 120]

2.1.5 Планирование движения на основе гибридного алгоритма

Эффективное объединение двух или более алгоритмов планирования может значительно повысить эффективность вычислений. Как показано на рисунке 18, для выполнения задачи точечной сварки с участием нескольких роботов Пеллегринелли и др. объединили алгоритм поиска конфликтов и рыночный метод для разработки траектории движения без столкновений для каждого робота, чтобы сократить время проектирования и количество ошибок при проектировании. 122]. Хартманн и др. объединили метод оптимизации с двунаправленным пространственно-временным планировщиком пути на основе выборки для совместного решения ограничений манипуляции, что позволило планировать совместные операции нескольких роботов с неизвестным временем прибытия [123]. Чтобы решить проблему совместного управления гибкими объектами, Алонсо-Мора предложил гибридный централизованный/распределенный метод. Планировщик низкого уровня предназначен для манипулятора, позволяющего сохранять контроль и избегать столкновений путем передачи сил между объектами на основе распределенной инверсии. горизонтальное планирование. Контроллер обеспечивает локальное управление и содержит ограничения для предотвращения столкновений и поддержания формы [124]. Для выполнения таких задач, как удаление заусенцев, резка и сварка в процессе производства автомобилей, Тузани и др. сначала использовали рыночный метод для сортировки задач, а затем использовали алгоритм PRM для автоматического планирования пути [125]. Объединив диверсификацию путей и оптимальные стратегии подзадач, Хан и др. предложили новый алгоритм централизованного разделения для решения однократной и динамической задачи оптимального планирования пути с участием нескольких роботов в складской среде [126]. Чтобы решить задачу оптического контроля крупномасштабных изделий с поверхностью произвольной формы, Лю и др. использовали динамический поиск в пространстве координат робота, учли нарушение положения зонда или локального пути в конфликтующем роботе и предложили метод столкновения. планирование свободного пути и планирование скоординированного движения [127]. Rigatos использует алгоритмы распределенного градиента и алгоритмы роевого интеллекта для решения проблемы совместной автономной сборки нескольких роботов. Начиная с разных точек пространства решений и взаимодействуя друг с другом по мере продвижения к целевой позиции, Rigatos может координировать действия между лучшими предыдущими моделями каждого робота. move и другие роботы ищутся итеративно в пределах региона, определенного их лучшими предыдущими ходами [128]. Чтобы завершить настройку автоматизированного склада, Хан и др. объединили диверсификацию путей и оптимальную базу данных решений подзадач, чтобы эффективно использовать все рабочее пространство для перемещения робота, в то время как оптимальная база данных решений подзадач помогает быстро разрешать конфликты локальных путей [129]. .

2.2 Планирование в сложных сценариях эксплуатации движения нескольких роботов

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

2.2.1 Планирование движения мобильного терминала с несколькими роботами

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

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

Вагнер и др. [131] использовали алгоритм A* в качестве базового планировщика пути для независимого планирования оптимального пути для каждого робота и в то же время поддерживали набор коллизий и набор обратного распространения ошибки для каждого узла, что значительно сократило количество узлов. в процессе расширения алгоритма A*.

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

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

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

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

Рисунок 19 Мобильное планирование движения с несколькими роботами[135]

2.2.2 Планирование рабочего конечного движения нескольких роботов

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

Тхакар и др. [136] рассмотрели высокую нелинейность и тесную связь мобильного манипулятора и определили его как неголономный мобильный манипулятор (НММ), во-первых, на основе информации об окружающей среде робота, манипуляторе и образцах. в целевой точке скоординированы и сфокусированы, а во-вторых, с учетом неголографических ограничений НММ, между двумя деревьями поиска устанавливается эвристический метод связи, тем самым улучшая скорость расчета пути и вероятность успеха.

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

Парди и др. [138] рассмотрели неголономные ограничения и кинематические ограничения системы мобильных рабочих роботов и сформулировали планирование пути при ограниченных ограничениях как задачу многокритериальной оптимизации, которая определялась расстоянием перемещения по поверхности, работоспособностью и мобильностью. конечного эффектора рабочей единицы. Функция стоимости, состоящая из скорости работы единицы, встроена в алгоритм RRT* для реализации планирования пути в пространстве задач. На основе совместного планирования движения рабочих терминалов с несколькими роботами T

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

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

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

Рисунок 18 Планирование движения на основе гибридных алгоритмов[122-129]

Рисунок 20 Планирование пути на стороне работы в условиях неполноты и ограничений задачи[136-138]

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

Таблица 2 Анализ методов планирования движения

03 Перспективы

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

В некоторых прошлых исследованиях алгоритмов был достигнут некоторый прогресс в распределении задач и планировании движения роевых роботов. Ян и др. использовали алгоритм колонии муравьев и модель порога ответа для распределения задач кластерных роботов, что отражает масштабируемость распределенного алгоритма [142]. Гассеми и др. учитывают сроки выполнения задач с учетом объема роботов и ограничений возможностей выполнения задач, а также допускают асинхронное принятие решений в динамических пространствах задач, предоставляя важные решения для различных практических приложений (например, реагирования на стихийные бедствия) [143]. Викмудо и др. сгенерировали кратчайший путь для каждого робота на основе генетического алгоритма, чтобы он мог достичь целевой точки без столкновений кластерных роботов друг с другом, и проверили эффективность безопасного пути без столкновений посредством моделирования [144]. Челла и др. усовершенствовали алгоритм колонии муравьев и предложили квантовый алгоритм планирования пути для роевых роботов, который количественно определяет входную позицию и информацию о вознаграждении (измеряется по близости робота к цели) и решения по планированию пути [145].

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

Хотя многие исследователи изучали роевые роботы, основываясь на анализе, приведенном в Таблицах 1 и Таблице 2, все еще существуют некоторые проблемы, которые необходимо решить в сценариях работы больших и сложных компонентов:

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

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

3) Сильные коммуникационные ограничения:Сетевой кластерробот制造过程середина容易出现通信的不确定性,而当前的部分метод如启发式算法、A* Алгоритмы сильно зависят от точности связи, а алгоритмы глубокого обучения требуют большого объема вычислений данных через облачные серверы. Следовательно, необходимо улучшить технологию планирования динамического распределения задач, чтобы добиться устойчивости в сценариях слабой связи или ограниченной связи в течение части периода времени.

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

5) Проблема замкнутого пространства:В сложных сценарияхробот На рабочем конце имеется небольшое пространство для перемещения.、Высокий размер планировочного пространства、约束条件много等问题,Поэтому разработка метода планирования совместного движения без помех для кластеров в небольших пространствах является одним из будущих направлений исследований.

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

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

Рисунок 21 Технический маршрут для распределения задач кластера и планирования движения в сложных средах

04  в заключение

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

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

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

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