Алгоритм A* с учётом направления и самоадаптацией с эвристикой PPO для планирования маршрутов БПЛА в умном городе

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

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

Почему найти хороший путь так сложно

Для дрона выбор маршрута — это не просто проведение прямой линии от точки A до точки B. Он должен обходить здания, деревья и зоны с запретом полётов, соблюдая ограничения на повороты и высоту. Классические методы планирования маршрутов, такие как широко известный алгоритм A*, хорошо работают на простых картах, но испытывают трудности в реалистичных 3D‑городских условиях. Они часто проверяют слишком много возможных шагов, тратят вычислительные ресурсы впустую и могут выдавать зигзагообразные траектории, которые длиннее необходимого, а в очень загромождённых средах даже не найти решения. По мере усложнения умных городов эти слабые стороны становятся серьёзным препятствием для безопасного и эффективного воздушного движения.

Улучшение классического инструмента с учётом направления

Авторы опираются на алгоритм A* и предлагают улучшенную версию под названием DASA* (Direction‑Aware and Self‑Adaptive A*). Вместо того чтобы вслепую просматривать все направления вокруг дрона, DASA* учитывает, где находится цель. Он классифицирует ближайшие кандидатные позиции на три слоя: те, что преимущественно перед дроном в направлении цели, боковые и небольшой набор позади, который помогает выбраться из тупиков. Простой детектор застоя следит за признаками «залипания» поиска и автоматически расширяет зону поиска от узкого переднего конуса к более широкому окружению при необходимости. Такое целенаправленное расширение снижает ненужные проверки, при этом гарантируя, что допустимый маршрут будет найден, если он существует.

Адаптация к плотным и открытым пространствам

Ещё одна ключевая особенность DASA* — он меняет «шаг» в зависимости от окружения. Когда дрон далеко от препятствий, алгоритм делает большие шаги, быстро покрывая открытое пространство. По мере приближения к зданиям или другим опасностям он переключается на меньшие шаги, позволяя точно маневрировать в узких местах. Эта переменная «масштабность» позволяет планировщику быстро двигаться там, где это безопасно, и замедляться только там, где важна точность. После нахождения грубого маршрута специальный этап доработки удаляет лишние путевые точки и подбирает гладкую кривую через оставшиеся ключевые точки. В результате получается маршрут, который не только избегает столкновений, но и выглядит более естественным — как траектория, выбранная опытным пилотом, с меньшим количеством резких поворотов.

Обучение алгоритма заглядывать вперёд

Традиционный A* опирается на простые формулы расстояния для оценки того, как далеко каждая позиция от цели. DASA* заменяет эту накидку обучаемым путеводителем на основе Proximal Policy Optimization (PPO) — современной техники обучения с подкреплением. В тренировочной среде виртуальный агент многократно отрабатывает движение к цели в 3D‑пространстве, получая данные о расстояниях, разнице высот и направлении. Нейросеть постепенно учится оценивать перспективность каждой ситуации и после обучения служит «модулем интуиции» для DASA*. Эта обученная эвристика направляет поиск более прямо к хорошим решениям, особенно в сложных планировках, где простое эвклидово расстояние вводит в заблуждение.

Насколько хорошо это работает в виртуальных городах

Исследователи протестировали DASA* в нескольких смоделированных 3D‑городских сценариях, заполненных коробчатыми зданиями и цилиндрическими препятствиями, имитирующими реальные городские структуры. Они сравнили его с классическим A* и несколькими популярными альтернативами, включая улучшенные версии резко‑исследующих деревьев, рои частиц, дифференциальную эволюцию и другую вариацию A* под названием Theta*. Во множестве тестов DASA* стабильно находил более короткие пути, расширял значительно меньше кандидатных точек и работал гораздо быстрее — часто в 10–50 раз быстрее стандартного A*. Он также сохранял совершенный или почти совершенный уровень успеха даже в плотных, лабиринтоподобных средах, тогда как некоторые конкуренты чаще терпели неудачу или выдавали длинные петляющие объезды.

Что это значит для повседневной жизни

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

Цитирование: Zhang, X., Tan, L. & Chai, J. Direction aware and self-adaptive A* algorithm with PPO heuristic for UAV path planning of smart city. Sci Rep 16, 6174 (2026). https://doi.org/10.1038/s41598-026-36066-4

Ключевые слова: планирование маршрутов БПЛА, дроны в умном городе, алгоритм A*, автономная навигация, планирование движения роботов