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