Алгоритм нахождения безопасных точек в контексте задачи планирования скорости для беспилотных транспортных средств

Автор(ы): Лившиц А.Б., Фадеев А.Ю.

Выпуск: 121

Рубрика: Управление подвижными объектами и навигация

Год: 2026

Библиография: Лившиц А.Б., Фадеев А.Ю. Алгоритм нахождения безопасных точек в контексте задачи планирования скорости для беспилотных транспортных средств // Управление большими системами. - 2026. - Вып. 121. - С.322-348.

Дата опубликования: 31.05.2026

Ключевые слова: беспилотные транспортные системы, профиль скорости, трюк выпуклой оболочки, дерево Ли Чао, динамическое программирование, ST-граф

Аннотация: Рассматривается задача онлайн-планирования скорости для наземных беспилотных транспортных средств, функционирующих в динамической и недетерминированной среде. Предлагается новый подход, основанный на концепции «безопасных точек» – состояний, из которых возможно выполнение манёвров торможения или ускорения без нарушения ограничений и возникновения коллизий. Для эффективного решения этой задачи предложен оригинальный алгоритм, который комбинирует метод построения выпуклой оболочки (Convex Hull Trick) с персистентной модификацией дерева Ли Чао. Данная комбинация позволяет в режиме реального времени агрегировать множественные ограничения от других участников движения и статические параметры пути, обеспечивая логарифмическую вычислительную сложность проверки. Результаты вычислительных экспериментов на реалистичных сценариях, включающих движение в плотном потоке и следование за лидером, демонстрируют его применимость для двунаправленной проверки безопасности в условиях взаимодействия с другими агентами и учёта статических ограничений, а также подтверждают высокую корректность, надёжность и производительность метода. Результаты работы могут быть использованы в качестве модуля валидации в системах реального времени для планирования скорости автономных транспортных средств.

Author(s): Livshits A., Fadeev A.

Article title: Approaches to speed planning for ground-based autonomous vehicles

Issue: 121

Year: 2026

Keywords: unmanned transport systems, speed profile, Convex Hull Trick, Li Chao tree, dynamic programming, ST graph

Abstract: The article addresses the problem of online speed planning for ground-based unmanned vehicles operating in a dynamic and non-deterministic environment. A novel approach is proposed, based on the concept of "safe points" – states from which braking or acceleration maneuvers can be performed without violating constraints or causing collisions. For the efficient solution of this problem, an original algorithm is introduced, which combines the Convex Hull Trick method with a persistent modification of the Li Chao tree. This combination enables the real-time aggregation of multiple constraints from other traffic participants and static path parameters, providing logarithmic computational complexity for safety verification. The results of computational experiments on realistic scenarios, including dense traffic flow and car-following, demonstrate its applicability for bidirectional safety verification under interaction with other agents and consideration of static constraints. The experiments also confirm the method's high accuracy, reliability, and performance. The results can be applied as a validation module in real-time speed planning systems for autonomous vehicles.