Найти

Результаты поиска

• МЕТОД ПРОСТРАНСТВЕННО-ВРЕМЕННОГО РАЗНЕСЕНИЯ ТРАЕКТОРИЙ ГРУППЫ РОБОТОВ В УСЛОВИЯХ ПРЕПЯТСТВИЙ

  В.А. Костюков

  92-102

  2025-10-01

  Аннотация ▼

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

• РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЦЕЛЕРАСПРЕДЕЛЕНИЯ В МНОГОАГЕНТНОЙ СИСТЕМЕ

  В.А. Костюков , Ф.А. Хуссейн

  144-155

  2025-10-01

  Аннотация ▼

  Рассматривается задача целераспределения в рамках многоагентной системы, где каждый агент представляется автономным роботом, а каждая задача соответствует позиции в двухмерной среде, которую должен посетить один из агентов. Эта задача по своей сути схожа с многоагентной версией классической задачи коммивояжёра, где вместо одного участника задействуется несколько агентов. Каждый из них должен пройти уникальный маршрут, охватывающий определённое множество городов. В связи с этим проводится исследование многоагентной задачи коммивояжёра как одного из форматов постановки задачи целерапределения. Эта задача имеет большое значение в области маршрутизации и оптимального распределения задач. Её решение включает две тесно связанные подзадачи: определение набора точек, закрепляемых за каждым агентом, и построение оптимального маршрута их посещения. В научной литературе представлены три основных подхода к решению этой задачи: подход одновременной оптимизации, при котором обе подзадачи решаются совместно; подход Cluster-First, Route-Second, где сначала распределяются города между агентами, а затем определяется порядок посещения городов каждого агента; подход Route-First, Cluster-Second, предполагающий изначальную оптимизацию порядка посещения всех городов с последующим его делением между агентами без изменения порядка посещения. В данной работе предлагается гибридный метод, сочетающий элементы подходов Cluster-First, Route-Second и Route-First, Cluster-Second. Цель – объединить сильные стороны обеих подходов и избавится от их недостатков. Для проверки эффективности разработанного метода проведено сравнительное исследование с методами, реализующие подходов Cluster-First, Route-Second и Route-First, Cluster-Second. Оценка проводилась по трём основным метрикам: время, затраченное на построение решения, суммарная длина всех маршрутов, а также максимальная длина маршрута среди всех агентов. Результаты экспериментов показали, что применение предложенного метода позволяет сократить максимальную длину маршрута (тем самым снизив дисбаланс нагрузки между агентами) в среднем на 26%.

• ГИБРИДНЫЙ МЕТОД РЕШЕНИЯ МНОГОАГЕНТНОЙ ЗАДАЧИ КОММИВОЯЖЁРА

  В.А. Костюков , Ф.А. Хуссейн

  2025-04-27

  Аннотация ▼

  Рассматривается проблема распределения задач в многоагентной системе, где каждый
  агент представляет собой робота, а каждая задача представляется позицией, которая должна
  быть посещена одним агентом. Эта задача очень похожа на многоагентную задачу коммивояжё-
  ра, которая в отличие от знаменитой задачи коммивояжера, задействует несколько коммивоя-
  жёров, которые посещают заданное количество городов ровно один раз и возвращаются в исход-
  ное положение с минимальными затратами на поездку. Поэтому проводится анализ многоагент-
  ной задачи коммивояжёра как представителя задачи целераспределения. Многоагентная задача
  коммивояжера является важной для области оптимизации маршрутов и распределения задач
  между несколькими агентами. Она включает в себе две различные, однако, взаимосвязанные под задачи: распределение городов между агентами и определение порядка посещения городов каж-
  дым агентом. В литературе существуют три концепции решения этой проблемы относительно
  решения ее двух составляющих подзадач: оптимизационная концепция, где обе подзадачи реша-
  ются одновременно; концепция Cluster-First, Route-Second – где сначала решается вопрос о назна-
  чении задач каждому коммивояжеру, а потом - вопрос о порядке посещений пунктов назначений
  для каждого коммивояжёра; концепция Route-First, Cluster-Second – где сначала решается вопрос
  о порядке посещения пунктов назначения, а затем происходит разделение этого цикла между
  агентами без изменения порядка посещений. В этой работы предлагается гибридный подход к
  решению многоагентной задачи коммивояжера, который объединяет идеи двух известных кон-
  цепций: Cluster-First, Route- econd и Route-First, Cluster- econd чтобы получить их позитивные
  аспекты и избавиться от их негативных сторон. Для оценки эффективности разработанного
  метода было проведено сравнительное исследование. Оценка результатов осуществлялась на
  основе трех ключевых критериев: вычислительного времени получения решения многоагентной
  задачи коммивояжера, суммарной длины пройденных маршрутов коммивояжерами и максималь-
  ной длины маршрута среди них. Анализ экспериментальных данных показал, что при использова-
  нии предложенного метода максимальная длина пути среди пройдённых агентами маршрутов
  (дисбаланс нагрузки) уменьшается в среднем на 26%.

• МЕТОД РЕШЕНИЯ ПРОБЛЕМЫ МУЛЬТИ-КОММИВОЯЖЁРА В СРЕДЕ БЕЗ ПРЕПЯТСТВИЙ НА ОСНОВЕ УМЕНЬШЕНИЯ РАЗМЕРА ПРОСТРАНСТВА РЕШЕНИЙ

  В.А. Костюков , Ф. А. Хуссейн , И.Д. Евдокимов

  2024-04-15

  Аннотация ▼

  Проводится анализ проблемы мульти коммивояжера, которая в отличие от знаме-
  нитой задачи коммивояжера, задействует несколько коммивояжёров, которые посещают
  заданное количество городов ровно один раз и возвращаются в исходное положение с ми-
  нимальными затратами на поездку. Задача мульти коммивояжера является важной для
  области оптимизации маршрутов и распределения назначений между несколькими аген-
  тами. Основной целью исследования является разработка эффективного метода решения
  данной проблемы, который позволит сократить время выполнения задач и оптимизиро-
  вать использование ресурсов. В ходе исследования был создан инновационный метод, осно-
  ванный на уменьшении размерности пространства решений. Этот метод позволяет более
  эффективно управлять нагрузкой и ресурсами, что в свою очередь способствует миними-
  зации общего времени выполнения задач. Особенностью метода является его универсаль-
  ность и применимость в различных сценариях, включая ситуации с разным количеством
  задач и коммивояжеров. Такой подход обеспечивает более широкий охват и позволяет
  оценить применимость метода в различных контекстах, что является важным преиму-
  ществом данного исследования. Для оценки эффективности разработанного метода было
  проведено сравнительное исследование с использованием классического метода решения
  проблемы мульти коммивояжера. Оценка результатов осуществлялась на основе трех
  ключевых критериев: вычислительного времени получения решения задачи мульти комми-
  вояжера, суммарной длины пройденных маршрутов коммивояжерами и максимальной дли-
  ны маршрута среди них. Анализ экспериментальных данных показал, что разработанный
  метод значительно превосходит классический подход по всем рассматриваемым критери-
  ям в большинстве экспериментов, так как при использовании предложенного метода сред-
  нее время расчета для задачи мульти коммивояжера уменьшается на 56% по сравнению с
  наилучшим известным классическим результатом, при этим средняя сумма длины прой-
  денных маршрутов коммивояжерами соответственно уменьшается на 12% и максималь-
  ная длина пути среди пройдённых агентами маршрутов (дисбаланс нагрузки) уменьшается
  на 8%, что подтверждает высокую эффективность предложенного метода и перспек-
  тивность для практического применения в различных сферах, где требуется оптимизация
  маршрутов и распределения задач между несколькими исполнителями

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

  В.А. Костюков , М.Ю. Бутенко , В.Г. Гисцов , И. Д. Евдокимов

  2024-01-05

  Аннотация ▼

  В связи с ускоренным ростом объемов использования групп автономно функциони-
  рующих беспилотных летательных аппаратов (БпЛА) в различных средах решение пробле-
  мы оптимизации функционирования групп таких аппаратов по критерию минимума за-
  трачиваемой энергии является актуальной научной задачей. В настоящей статье развива-
  ется новый подход обеспечения энергосбережения группы беспилотных летательных ап-
  паратов (БпЛА) за счет использования распределенной системы модулей подзарядки БпЛА,
  обеспечивающих необходимую универсальность в обслуживании разных типов аппаратов.
  Предполагается, что модули подзарядки установлены на подмножестве станций обслу-
  живания, между которыми курсируют БпЛА мультикоптерного типа, выполняя миссию
  по развозу грузов. Необходимо определить такие число и непосредственно указанное под-
  множество станций обслуживания, снабженных такими модулями, которые бы достав-
  ляли оптимум некоторого функционала качества, характеризующего функционирование
  группы БпЛА. В статье предлагается в качестве такого функционала отношение числа
  БпЛА, успешно отработавших выданные им задания по развозу грузов, к числу станций с
  модулями подзарядки. Модель движения БпЛА между пунктами назначения предполагает
  учет не только крейсерского режима, но и маневрирования аппарата при взлете и посадке;
  также учитывается зависимость скорости расходования энергии от текущих кинемати-
  ческих величин аппарата. Предусмотрено падение аппарата в случае расходования им
  энергии ниже предельного порогового значения. Разработана упрощенная модель станции
  обслуживания с модулем подзарядки (МП), подразумевающим замену разряженных аккуму-
  ляторных батарей. Учтен режим ожидания БпЛА в очереди. Для исследования разрабо-
  танных алгоритмов планирования движения и выбора оптимального распределения моду-
  лей подзарядки по станциям обслуживания создано и апробировано программное обеспече-
  ние на базе среды Unity. Гибкость последнего позволяет моделировать различные алго-
  ритмы информационных взаимодействий элементов внутри группы БпЛА, группы МП,
  а также перекрестных взаимодействий между БпЛА и МП.

• АЛГОРИТМ ПЛАНИРОВАНИЯ ПУТИ В ДВУХМЕРНОЙ СРЕДЕ С ПОЛИГОНАЛЬНЫМИ ПРЕПЯТСТВИЯМИ НА КЛАССЕ КУСОЧНО-ЛОМАНЫХ ТРАЕКТОРИЙ

  В.А. Костюков , М.Ю. Медведев , В. Х. Пшихопов

  2023-12-11

  Аннотация ▼

  Актуальной проблемой, возникающей при разработке алгоритмов автоматического
  планирования пути, является рост вычислительных затрат при увеличении сложности
  среды функционирования. Не лишены этого недостатка графовые методы планирования, в
  частности, метод диаграмм видимости. Он позволяет сформировать в качестве узлов
  графа вершины полигональных границ каждого препятствия, а ребрами графа являются
  все те отрезки, соединяющие эти вершины, которые не имеют пересечений с препятст-
  виями. При увеличении количества препятствий возрастает сложность такого графа,
  причем этот рост очень быстрый. Поэтому наиболее важной задачей становятся приемы
  сокращения сложности графа видимости. В данной статье предлагается гибридный алго-
  ритм, строящийся на методе диаграмм видимости и семействе Bug-алгоритмов.
  Bug-алгоритм относится к классу локальных, поскольку каждый раз имеет дело с огибани-
  ем одного препятствия, появляющегося на пути следования робота, и этот алгоритм не
  может предсказать заранее, какое следующее препятствие придется обходить. Предла-
  гаемый в данной статье метод планирования траектории движения сочетает графовый
  алгоритм с Bug-алгоритмами, что позволяет построить специальный граф с узлами в виде
  характерных точек препятствий. При этом Bug-алгоритм является шагом итерационного
  процесса оптимизации на графе, позволяющего за конечное число шагов прийти к опти-
  мальному решению на классе кусочно-ломаных кривых. Предлагаемый метод решает зада-
  чу глобального поиска пути на классе кусочно-линейных траекторий с полигональными
  препятствиями; а в отличие от классического методов диаграмм прямой видимости, су-
  щественно снижает размерность графа за счет специального выбора ограниченного коли-
  чества характерных точек соответствующих препятствий. В статье проводится разра-
  ботка и теоретическое обоснование предлагаемого метода. Приводятся расчетные соот-
  ношения алгоритма, обосновывается оптимальность получаемой траектории. Аналити-
  ческие соотношения подтверждаются результатами численного моделирования в различ-
  ных средах, заполненных полигональными препятствиями. При этом эффективность пред-
  лагаемых алгоритмов подтверждается на примерах среды, заполненной препятствиями
  до 70–80%. Показано, что для прокладывания пути на сценах лабиринтного типа с одним
  распространенным видом препятствий рассматриваемый алгоритм на 10% превосходит
  оптимальный алгоритм Дейкстры.

• АППАРАТНО-АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПЕРСПЕКТИВНОЙ СИСТЕМЫ ЭНЕРГОСБЕРЕЖЕНИЯ АВТОНОМНОЙ ГРУППЫ БПЛА

  М.Ю. Медведев , В.А. Костюков , М.Ю. Бутенко , В.Г. Гисцов , И.Д. Евдокимов

  2023-02-17

  Аннотация ▼

  В связи с ускоренным ростом объемов использования групп автономно функционирующих
  беспилотных летательных аппаратов (БпЛА) в различных средах решение проблемы оптими-
  зации функционирования групп таких аппаратов по критерию минимума затрачиваемой энер-
  гии является актуальной научной задачей. В настоящей статье развивается новый подход
  обеспечения энергосбережения группы беспилотных летательных аппаратов (БпЛА) за счет
  использования станций подзарядки БпЛА, обеспечивающих необходимую универсальность в
  обслуживании разных типов аппаратов. Рассматриваются наиболее эффективные варианты
  систем приземления, точного позиционирования, выработки энергии на станции, а также
  обосновывается гибридная система обеспечения подзарядки, сочетающая контактный и бес-
  контактный способы. Приводится обобщенная схема многоэтапного взаимодействия БпЛА со
  станцией подзарядки, предусматривающая возможность повторения одного из этапов в случае
  не полного его завершения в течение определенных интервалов времени, а также учитывающая
  особенности взаимодействия между агентами по доступным им каналам связи. Поставлена и
  решена задача оптимального распределения по энергетическому критерию БпЛА группы меж-
  ду пунктами назначения (ПН), совмещенными со станциями подзарядки (СП). Учитывается
  как крейсерский режим, так и маневрирование аппарата при взлете и посадке, когда мощность
  расходования энергии возрастает. Введено понятие эффективного расстояния до пункта на-
  значения, учитывающего оценочные затраты энергии каждого БпЛА на достижение данного
  ПН с учетом его произвольного текущего положения и имеющейся очереди заданий на данный
  момент. Для исследования разработанных подходов и алгоритмов целераспределения и плани-
  рования движения БпЛА группы создано и апробировано программное обеспечение на базе сре-
  ды Unity. Гибкость последнего позволяет моделировать различные алгоритмы информацион-
  ных взаимодействий элементов внутри группы БпЛА, группы СП, а также перекрестных взаи-
  модействий между БпЛА и СП. В частности, Программное обеспечение позволяет определять
  в каждый дискретный момент степень заряда каждого БпЛА, очереди ПН для каждого БпЛА,
  его историю пополнения заряда на станциях.

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

  В. А. Костюков, М. Ю. Медведев , В.Х. Пшихопов, Е. Ю. Косенко

  2021-04-04

  Аннотация ▼

  В настоящее время началось активное использование групп роботов для решения
  целого ряда задач гражданского и военного назначений. В этой связи возникают пробл е-
  мы, связанные с групповым управлением, организацией надежных каналов связи и обесп е-
  чением эффективного функционирования группы при ограниченных энергетических р е-
  сурсах. При решении задачи об оптимизации энергопотребления возникает проблема
  повышения эффективности взаимодействия элементов группы со стационарными стан-
  циями подзарядки. Эта проблема может быть решена только при рассмотрении объ е-
  диненной системы, в которую входят роботы и станции подзарядки. Централизованное
  управление такой системой оправдано в случае небольшого числа ее элементов. Однако с
  ростом числа элементов группы повышается сложность управления, поэтому более
  приоритетным решением становится сочетание централизованного и децентрализо-
  ванного методов управления. В комплекс проблем децентрализованного управления такой
  группой входит задача организации оптимального взаимодействия её элементов с целью
  достижения цели своего функционирования. При организации энергетического обмена
  между роботами и станциями подзарядки решение этой задачи играет ключевую рол ь в
  оптимизации энергопотребления. В данной статье работе разрабатывается концепция
  взаимодействия подвижных и стационарных объектов, подразумевающая возможность
  выбора каждым агентом взаимодействия соответствующего компаньона. Такой выбор
  производится с учетом текущего состояния системы и оценки истории результатов
  взаимодействия. Разработанная концепция детализируется для системы, включающей
  БЛА и станции их подзарядки. Предлагается алгоритм децентрализованного выбора пар
  взаимодействующих элементов «БЛА– станция подзарядки» на основе двух показателей
  – энергетической эффективности процесса заряда, и времени, затрачиваемго БЛА на
  достижение целевой точки. Оба показателя учитываются при выборе весовых коэффи-
  циентов, назначаемых каждой станции подзарядки в качестве степеней её эффективно-
  сти. Также данные показатели входят в оптимизируемый критерий качества. Разраб о-
  тана процедура оптимизации, результатом которой является номер станции подзаря д-
  ки, наиболее подходящей данному мобильному объекту для взаимодействи я.

• МЕТОД ОЦЕНКИ КООРДИНАТ БЛА ПО ИЗМЕРЕННЫМ ЛОКАЛЬНЫМ РАССТОЯНИЯМ МЕЖДУ ЭЛЕМЕНТАМИ ГРУППЫ

  В. А. Костюков , Е.Ю. Косенко , М. Ю. Медведев , В.Х. Пшихопов , М. В. Мамченко

  2021-04-04

  Аннотация ▼

  В связи с развитием средств мобильной робототехники проблема корректного реше-
  ния навигационных задач является одной из первостепенных, наряду с проблемами авто-
  матического управления и обеспечения информационного канала связи заданных надежно-
  сти, быстродействия и пропускной способности. Для осуществления навигации беспилот-
  ный летательный аппарат (БЛА) может использовать собственную инерциальную нави-
  гационную систему (ИНС), а также систему спутниковой навигации (СНС). Целью данной
  статьи является разработка метода уменьшения погрешностей работы инерциальной
  навигационной системы БЛА, вызванных наличием случайной и систематической погреш-
  ностей. При этом рассматривается случай монотонного возрастания систематической
  погрешности со временем. Навигационные данные, полученные со спутника, как правило, не
  содержат значительной систематической погрешности определения координат. Однако
  спутниковый сигнал может пропадать на время, значительно большее периода трансля-
  ции со спутника навигационных данных в обычном режиме. В следствие этого возникает
  проблема увеличения точности данных, получаемых от инерциальной навигационной сис-
  темы. Данная проблема особенной актуальная при групповом использовании БЛА. При ре-
  шении задач группового управления возникает необходимость предотвращать столкнове-
  ния аппаратов и возможные коллизии уже на стадии планирования движения. Кроме того,
  для решения целого ряда групповых задач, таких как мониторинг местности, проведение
  спасательных операций, поиск объектов на заданной территории, совместное транспор-
  тирование груза, отдельные объекты группы должны слаженно перемещаться в про-
  странстве с большой точностью. Это накладывает еще более жесткие ограничения по
  точности отработки ИНС и частоте информационного обмена по СНС. В настоящей
  статье предлагается метод, позволяющий по данным, полученным от локальных систем,
  осуществляющих измерение взаимных расстояний между объектами группы, скорректи-
  ровать оценки собственных координат таким образом, чтобы в результате уменьшить
  среднеквадратическое отклонение скорректированного набора точек от истинных поло-
  жений объектов в данный момент времени. Также метод позволяет уменьшить макси-
  мальное значение соответствующего отклонения по сравнению с исходным набором оце-
  нок, полученных из навигационных данных ИНС. Метод демонстрируется на примере по-
  вышения точности определения глобальных координат в группе БЛА.