Найти

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

• ПЛАНИРОВАНИЕ ПУТИ РОБОТА ДЛЯ НЕСКОЛЬКИХ ЦЕЛЕЙ НА ОСНОВЕ ГИБРИДНОГО АЛГОРИТМА PRM И AGA

  Альзубайри Шаймаа М. Джавад Кадим, А.А. Петунин , С.С. Уколов

  6-18

  2025-11-10

  Аннотация ▼

  Задачи планирования оптимального пути мобильных роботов особенно активно исследуются в последнее десятилетие. Цель состоит в том, чтобы найти оптимальный или близкий к оптимальному путь от начального терминала до одного или нескольких терминалов в среде с различными препятствиями. С точки зрения минимизации времени перемещения роботов, пройденного расстояния, энергетических затрат или других оптимизационных критериев. В данной работе предлагается гибридный алгоритм, сочетающий алгоритм вероятностной дорожной карты (PRM) и адаптированный генетический алгоритм (AGA) для решения задачи планирования пути с одной или несколькими независимыми целями. В качестве оптимизационного критерия используется длина пути робота. По сравнению с существующими подходами, используемыми в генетических алгоритмах (GA), предлагаемый подход имеет два основных различия. Первое – это представление среды, которое опирается на обработку изображений и морфологические операции, что оказалось более эффективным методом, чем методы на основе клеточного представления.
  В частности, предложенный способ устраняет необходимость поиска компромисса между точностью и скоростью обработки геометрической информации. Второе – это новая тактика создания начальной популяции генетического алгоритма для ускорения сходимости при наличии нескольких целей. за счёт использования возможностей вероятностного алгоритма дорожной карты. Еще одна особенность реализации алгоритма связана с адекватным (для исследуемой предметной области) выбором числовых параметров, определяющих особенности всех этапов эволюционной стратегии, включая временные затраты на выполнение каждого этапа. В частности, это касается, параметров оператора мутации и элитной стратегии. Предложенный алгоритм был протестирован на двух реальных картах с разной степенью сложности. Эффективность алгоритма подтверждена сравнением с результатами планирования пути для тестовых карт, полученными с помощью стандартного генетического алгоритма и алгоритма оптимизации муравьиной колонии. Экспериментальные результаты показывают, что гибридный алгоритм расширяет возможности обычного генетического алгоритма и находит рациональные варианты пути с лучшим значением целевой функции для одной и нескольких целей за гораздо меньшее время, чем другие традиционные реализации GA

• НОВЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ПУТИ ОБХОДА КОНЕЧНОГО МНОЖЕСТВА НЕПЕРЕСЕКАЮЩИХСЯ КОНТУРОВ НА ПЛОСКОСТИ

  А. А. Петунин, Е.Г. Полищук , С. С. Уколов

  2021-04-04

  Аннотация ▼

  Рассматривается проблема маршрутизации режущего инструмента машин листо-
  вой резки с ЧПУ для случая, когда точки врезки расположены на границах деталей, ограни-
  ченных отрезками прямых и дугами окружностей, при этом используется техника непрерывной резки (CCP), т.е. каждый контур вырезается целиком, но не используется предва-
  рительная дискретизация, то есть резка может начинаться с любой точки контура. Об-
  щая задача поиска оптимального маршрута в этом случае сводится к минимизации длины
  холостого хода. Показано, что она эквивалентна поиску кратчайшей ломаной с вершинами,
  расположенными на контурах. Предложен новый эвристический алгоритм построения
  такой ломаной для заранее заданного порядка обхода контуров. Показано, что получаю-
  щееся решение представляет собой локальный минимум. Описаны некоторые достаточ-
  ные условия, того, что решение является также глобальным минимумом, которые легко
  проверяются численно, а некоторые даже визуально. Описана методика автоматического
  учёта ограничений предшествования для практически важного случая наличия вложенных
  контуров, возникающих как за счёт отверстий в деталях, так и за счёт расположения
  мелких деталей в отверстиях крупных. При этом происходит также уменьшение размер-
  ности задачи, что положительно сказывается на времени оптимизации, особенно дис-
  кретной. Предложен эвристический алгоритм выбора порядка обхода контуров на основе
  метода переменных окрестностей (VNS). Описаны альтернативные подходы применения
  других методов дискретной оптимизации совместно с предложенным алгоритмом по-
  строения кратчайшей ломаной для решения полной задачи непрерывной резки и возникаю-
  щие при этом сложности как теоретического, так и практического характера. Описано
  обобщение задачи непрерывной резки до более широкого класс задач сегментной резки и
  обобщённой сегментной резки, что позволяет продвинуться в решении общей задачи пре-
  рывистой резки. Описана схема применения предложенного алгоритма для решения задач
  сегментной и обобщённой сегментной резки. Приведены некоторые результаты численных
  экспериментов в сравнении с точным решением задачи для дискретной модели GTSP.