Гибридный алгоритм оптимизации для решения задач планирования пути на основе алгоритма оптимизации серых волков

Более умные маршруты в густонаселённых городах

Каждый день водители, фургоны доставки и роботы сталкиваются с одной и той же задачей: как добраться из точки A в точку B быстро, безопасно и без лишних затрат времени и топлива? В этой статье предложен новый компьютерный метод, который прокладывает более короткие и плавные маршруты по сложным уличным сетям, заполненным препятствиями и пробками. Заимствуя идеи из охоты серых волков в стае и поиска золота старателями, авторы показывают, как эффективнее вести автомобили и робототехнику через оживлённые городские пространства.

Почему важны лучшие маршруты

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

Смешение волков, хаоса и золотодобытчиков

Чтобы преодолеть эти слабости, авторы разработали улучшенную версию под названием CGGWO. Она сохраняет базовую идею стаи виртуальных серых волков, ищущих лучший маршрут, но меняет способ рассредоточения и обучения стаи. Во-первых, вместо случайного размещения волков метод использует математический приём, называемый хаотическим отображением, чтобы более равномерно разбросать их по области поиска. Это повышает вероятность того, что хотя бы некоторые волки обнаружат перспективные области карты. Далее метод заимствует правило у другой техники, вдохновлённой поиском золота. Здесь ведущий «альфа»-волк направляется в особенно богатые области пространства поиска, подобно тому как старатели постепенно смещаются в зоны с большим содержанием золота. Этот шаг вносит контролируемую случайность и разнообразие, помогая стае выбираться из бедных локальных выборов.

Хитрое скрещивание и мягкие встряхивания

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

Проверка нового метода

Исследователи сначала проверяют CGGWO на 23 стандартных математических задачах, которые широко используются для оценки поисковых алгоритмов. Эти задачи варьируются от гладких ландшафтов с одной наилучшей впадиной до неровных территорий с множеством локальных минимумов. В большинстве этих тестов CGGWO находит лучшие решения, сходится быстрее и демонстрирует более стабильное поведение по сравнению с несколькими известными конкурентами, включая оригинальный алгоритм серых волков, оптимизацию роя частиц и генетические алгоритмы. Затем команда переходит к реалистичной задаче планирования пути на упрощённой уличной сетке возле оживлённой коммерческой зоны в Лхасе. Препятствия моделируют заблокированные или перегруженные участки, а цель — связать начальную и конечную точки коротким, плавным маршрутом, избегающим их.

Короткие, плавные поездки

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

Цитирование: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

Ключевые слова: планирование пути, алгоритм оптимизации, интеллектуальный транспорт, ройный интеллект, навигация роботов