СПОСОБ ОПРЕДЕЛЕНИЯ ПОСАДОЧНЫХ ТРАЕКТОРИЙ ЛЕТАТЕЛЬНЫХ АППАРАТОВ, СООТВЕТСТВУЮЩИХ ОДНОЙ ВЗЛЕТНО-ПОСАДОЧНОЙ ПОЛОСЕ

Изобретение относится к области анализа данных, в частности, многомерных траекторий движения объектов - летательных аппаратов (ЛА), и может быть использовано при обнаружении скрытых целей движущихся объектов, для решения задачи секторизации пространства в трехмерном случае и идентификации установившихся потоков движения, при проектировании воздушных коридоров, моделировании захода ЛА на посадку (в том числе при посадке в условиях сложного географического ландшафта, плохой видимости, на палубу корабля) и определении оптимальных (опорных) траекторий движения ЛА в пространстве.

В настоящее время в различных областях все более актуальной становится задача идентификации в потоке групп объектов со сходными характеристиками движения и определения типичных маршрутов (характерных паттернов движения). Для решения этой задачи применяется обширный ряд методов. Например, в работе [1] предлагается подход к определению типичных паттернов, основанный на кластеризации схожих траекторий, а в патенте US 7688349 В2 группы социально-взаимосвязанных людей (groups of socially interrelated people) определяются с помощью анализа траекторий движения, выполняемого на основании данных, полученных с камер видеослежения.

Однако наибольший интерес представляют задачи, связанные с анализом многомерных пространственных траекторий движения. В частности, эти задачи приобретают все большее значение в авиации в связи постоянным увеличением воздушного трафика, необходимостью оптимизации загруженности взлетно-посадочных полос (ВПП) и совершенствования существующих систем управления воздушным движением (СУВД).

Из патента US 6393358 В1 известна автоматическая радиолокационная система TRACON (Terminal Radar Approach Control) [2, 3], использование которой направлено на упрощение работы диспетчерских служб, обеспечение безопасности полетов и более эффективной загруженности воздушного пространства в расширенной зоне вокруг аэропорта. Подобные системы позволяют обеспечивать безопасность движения в воздушном пространстве и улучшать пропускную способность аэропорта. С помощью радара TRACON фиксируются мета-данные, содержащие информацию о пространственных координатах положения центра масс ЛА, на основании которых вычисляются траектории их движения.

Особенность задачи управления воздушным движением состоит в том, что в связи с разделительными ограничениями (separation constraints), различные по весу самолеты не могут следовать в караване к одной ВПП. Из заявки US 20140019033 А1 известен способ планирования воздушного движения, включающий определение сети, состоящей из узловых точек и основных направлений посадки (an arrival network of nodes and legs), который применяется для оптимизации расписания прибывающих самолетов.

Важно также заметить, что траектории посадки самолетов представляют собой данные высокой размерности (high dimensional data), но учитывая отмеченные недостатки методов обработки, в настоящее время их анализ осуществляется в двумерном пространстве - проекции на плоскость посадки. Такое сокращение размерности данных зачастую приводит к существенной потере информации и искажению результата.

Задача, решаемая в рамках настоящего изобретения, связана с дальнейшим совершенствованием методов управления и контроля движения объектов в заданных направлениях в случае захода летательных аппаратов (ЛА) на посадку. Технический результат, достигаемый при решении такой задачи, заключается в определении числа целей движения ЛА - посадочных полос и выделении областей пространства, соответствующих траекториям движения ЛА к таким целям. Практический аспект такого результата может быть связан с повышением безопасности полетов ЛА, например, предотвращением конфликтных ситуаций при задании траекторий движения объектов в ограниченной области пространства при заходе на посадку и снижением числа внештатных (аварийных) ситуаций.

Поставленный результат в общем виде достигается заявленным способом определения числа асимптотически сходящихся пучков многомерных пространственных посадочных траекторий движения летательных аппаратов (ЛА) при заданном параметре порога, включающем регистрацию упомянутых многомерных пространственных посадочных траекторий движения ЛА, определение необходимости выравнивания зарегистрированных траекторий во времени и, при необходимости, выравнивание, формирование выборки зарегистрированных траекторий, представление выборки траекторий в виде набора точек, составлявших каждую траекторию, формирование двумерной ортогональной проекции набора точек, по меньшей мере, однократное упорядочение точек сформированной проекции в направлении возрастания или убывания значения одной из координат, анализ для упорядоченных точек сформированной проекции наиболее правдоподобной модели ортогональной линейной регрессии с определением геометрической асимптоты при заданном параметре порога, не превышающем ширины взлетно-посадочной полосы, и выделение в сформированной выборке пучка траекторий на основании меры близости траекторий выборки к определенной выше геометрической асимптоте, при этом мера близости определяется по мере косинуса при заданном параметре порога, не превышающем ширины взлетно-посадочной полосы, и вычисляется в диапазоне значений от 0 до +1, при этом, по результатам каждого предыдущего упорядочения последующие упорядочение и анализ проводят, удаляя траектории выделенного пучка из сформированной выборки траекторий.

Предпочтительный, но не обязательный вариант реализации способа предполагает, что первоначально определенный пучок содержит наибольшее число посадочных траекторий.

Изобретение иллюстрируется принципиальной блок-схемой, отображающей этапы реализации способа (фиг. 1), и фиг. 2-5, иллюстрирующими практическую осуществимость заявленного способа. В частности, на фиг. 2а показан общий вид пучков многомерных пространственных траекторий посадки самолетов на полосы аэродрома, на фиг. 2б - пучки посадочных траекторий, соответствующие различным взлетно-посадочным полосам (ВПП). Трехмерное представление посадочных траекторий, регистрируемых радаром, представлено на фиг. 3а, на фиг. 3б - разбиение этих траекторий на пять кластеров, выполняемое по методу полиномиальных регрессий [4, 5]. Далее траектории каждого кластера считаются выборкой траекторий, в которой возможно выделение пучков. На фиг. 4 рассматриваются проекции на координатные оси траекторий выборки, соответствующей розовому кластеру на фиг. 3б. Фиг. 5 иллюстрирует последовательные этапы выделения пучков многомерных пространственных траекторий в выборке, представленной на фиг. 4.

Раскрывая возможность реализации заявленного назначения и практической осуществимости заявленного решения, в настоящем описании устанавливается, что многомерные траектории движения летательных аппаратов (ЛА), представляемые многомерными векторами, вычисляются на основании регистрируемых в соответствующие моменты времени мета-данных, содержащих, в частности, пространственные координаты (например, координаты положения центра масс). Последовательность регистрируемых метаданных определяет многомерные пространственные траектории движения объекта (которые далее кратко называются траекториями движения). Многомерность определяется длинной траектории и числом используемых параметров мета-данных.

Необходимо отметить, что настоящее изобретение применяется при анализе данных о движении объектов к определенным (одинаковым, заданным) целям. Примером такого движения являются посадки ЛА на заданные взлетно-посадочные полосы (ВПП). В общем случае, если объекты движутся к общей цели, то траектории их движения образуют пучок многомерных пространственных траекторий движения (который далее кратко называется пучок траекторий), при этом в пучке траектории движения могут пересекаться. Для целей раскрытия осуществимости настоящего изобретения устанавливается, что пучок траекторий считается сходящимся (и кратко называется сходящимся пучком траекторий), если траектории движения в пучке имеют общую цель и близки по конечным координатам (например, при анализе посадочных траекторий ЛА - на плоскости посадки), при этом схождение пучка траекторий определяется параметром порога. При анализе траекторий посадок ЛА в зоне аэропорта (см. фиг 2а) возможно выделение сходящихся пучков траекторий - посадок на заданные ВПП (см. фиг. 2б), при этом, в общем случае, параметр порога не превышает ширины ВПП.

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

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

Формально пучок траекторий N_k, (K₀ - эмпирический параметр), считается асимптотически сходящимся с параметром порога, если для векторов {х[i]∈R_3xL, i∈N_k}, представляющих пучок траекторий N_k, , выполняется условие асимптотического схождения пучка

где - координаты точек траекторий, которые почти совпадают, т.е. параметры L_i, i∈N_k подлежат определению, - евклидова мера расстояния в трехмерном пространстве R³, ε - порог (который при рассмотрении сходящихся пучков, образуемых траекториями посадки ЛА, не превосходит ширины ВПП).

Рассматривая заявленный подход к определению числа сходящихся пучков многомерных траекторий, первоначально следует принять во внимание, что траектории в асимптотически сходящихся пучках имеют типичную форму (профиль) и характерную геометрическую асимптоту в области сходимости траекторий (1) [6]. Геометрической асимптотой сходящегося пучка многомерных посадочных траекторий самолетов является линия в R³ (трехмерное пространство координат), удовлетворяющая условию (1). Траектории в асимптотически сходящихся пучках имеют касательную в окрестности конечных точек всех траекторий пучка с порогом ε (1)) [6], так что асимптотически сходящиеся пучки траекторий могут быть идентифицированы посредством определения касательных им геометрических асимптот в точках их фокусов.

Поскольку дискретные точки траекторий пучка плотно лежат в окрестности асимптоты, основа предлагаемого способа определения числа пучков сходящихся многомерных пространственных траекторий движения объектов состоит в том, что набор векторов выборки многомерных траекторий рассеивается во множество точек этих траекторий

Множество точек (2) должно быть упорядочено по значениям одной из координат (в направлении возрастания - ascend или убывания - descend). При этом происходит упорядочение по остальным координатам всех точек, представляющих сходящийся пучок траекторий по определенному профилю. После этого для рассеянных трехмерных данных например, с помощью алгоритма RANSAC (Random Sample and Consensus - случайная выборка и консенсус) [7, 8], анализируются модели ортогональной линейной регрессии

где - конъюнкция, θ={a_l, b_l, c_l, d₁, a₂, b₂, c₂,d ₂} - вектор параметров этих моделей при заданном пороге евклидового расстояния , вычисляемого по ортогональной проекции точки z=(x, y, z) из (2) на линию . Таким образом, модель (3) симметрична относительно координат x, y, z. Для выдвижения гипотезы относительно модели ортогональной линейной регрессии (3) достаточно любой пары точек из (2). Окончательная модель (3) подтверждается наибольшим относительным количеством (процентом) рассеянных данных (2). Для данных целей может быть использован алгоритм MLESAC (Maximum Likelihood Estimation Sample Consensus - консенсус выборок с оценкой по максимуму правдоподобия) [9, 10] - вероятностная версия алгоритма RANSAC. Этот алгоритм оценивает правдоподобие модели (3), представляя распределение расстояния рассеянных данных от модели (3), как смесь распределения данных, подтверждающих модель (3) (inliers), и распределения данных, отклоняющих эту модель (outliers). Считая, что рассеянные данные Z (2) независимые, получаем выражение для логарифма правдоподобия в виде

где γ - параметр смешивания. Распределение расстояний до данных, подтверждающих модель (3), представляется гауссовым распределением

где σ - стандартное отклонение. Распределения расстояний до данных, отклоняющих модель (3), описывается равномерным распределением

где ρ_max - наибольшее расстояние до данных (определяется контекстом). Минимизация логарифма правдоподобия (4) позволяет оценить вектор параметров θ и параметр смешивания γ, что обеспечивается итерациями алгоритма ожидания-максимизации правдоподобия.

Для специалиста очевидно, что при определении геометрической асимптоты (3) одного из пучков при условии (1), помимо рассматриваемых в настоящей заявке алгоритмов могут быть использованы и другие методы.

Наиболее правдоподобная линейная регрессия рассеянных данных выборки траекторий определяет геометрическую асимптоту (3) одного из его пучков при условии (1). Полученная таким образом геометрическая асимптота удовлетворяет условию

Касательный ей пучок траекторий определяется в результате нахождения минимума целевой функции

где - набор бинарных индикаторных переменных (т.е. если вектор x[i] назначен пучку k, то r[i; k]=1 и r[i; k]=0 в противном случае). Расстояние между геометрической асимптотой и траекториями выборки вычисляется по мере косинуса

После удаления из рассеянных данных (2) тех точек, которые представляют траектории выделенного пучка, процедура определения геометрической асимптоты повторяется и выделяется следующий пучок траекторий. Поскольку определение модели (3) должно быть симметричным относительно координат x, y, z, при формировании рассеянных данных оставшихся траекторий в (2) производится сортировка по очередной пространственной координате по сравнению с использованной в (2) при определении предыдущей асимптоты (3). Возможная зависимость результата (3) от направления координат устраняется изменением направления сортировки в (2) с возрастания на убывание или наоборот. Анализ траекторий кластера завершается определением всех пучков в кластере.

Возможность практической реализации заявленного способа рассматривается на примере анализа данных 116 посадочных траекторий ЛА, зарегистрированных радаром TRACON 1 января 2006 г над заливом Сан-Франциско (находятся в свободном доступе https://c3.nasa.gov/dashlink/resources/132/). Начало координат совпадает с положением радара, интервал времени между точками регистрации составляет порядка 5c. В работе учитываются только 160 последних точек каждой траектории, что исключает случайные маневры самолетов перед заходом на посадку.

На фиг. 3а представлено исходное трехмерное представление анализируемых данных. Далее эти данные разбиваются на кластеры (см. фиг. 3б) по методу полиномиальных регрессий [4, 5] в соответствии со сходством формы и скоростных режимов. Распределение траекторий по кластерам следующее: 16 траекторий в розовом кластере, 13 - в зеленом, в синем, черном и красном кластерах - 3, 37 и 38, соответственно. Траектории каждого кластера соответствуют определенной выборке траекторий, в которой возможно выделение пучков траекторий, соответствующих определенным профилям посадки.

В качестве примера определим пучки траекторий выборки, определяемой розовым кластером (см. фиг. 4). Следует отметить, что пучки траекторий анализируемой выборки существенно пересекаются. Другой их особенностью является присутствие практически линейных участков в их хвостах вдали от фокуса. Поскольку все траектории в выборке имеют одинаковое направление времени, то при анализе этих траекторий используются рассеянные данные сокращенных траекторий с частью точек quotum ≈0.4, считая от фокусов пучков.

На фиг. 5а показаны выравненные во времени рассеянные данные двумерных проекций сокращенных траекторий выборки. На фиг. 5б - результат их линейной регрессии с использованием алгоритма MLESAC. На фиг. 5в определена асимптота первого пучка (голубая линия). Следует отметить, что в этом случае результаты ортогональной линейной регрессии рассеянных данных сокращенных и полных траекторий совпадают. Траектории первого (голубого) пучка (см. фиг. 5г) удаляются из выборки на основании близости траекторий к голубой асимптоте (рис. 5в) по мере косинуса. После удаления из выборки траекторий первого выделенного пучка, в оставшейся части выборки аналогично определяется следующая асимптота (см. фиг. 5д-з) и соответствующий ей пучок траекторий. Далее траектории второго (зеленого) пучка удаляются из рассматриваемой выборки на основе близости траекторий движения к зеленой асимптоте по мере косинуса. На фиг 5з представлены выделенные в рассматриваемой выборке в результате последовательных итераций три пучка траекторий движения (голубой, зеленый и синий). Толстая красная линия в центре каждого пучка соответствует центральной траектории в пучке.

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

Литература

1. Hung С.С., Peng W.С., Lee W.С. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes //The VLDB Journal-The International Journal on Very Large Data Bases. - 2015. - V. 24. - №. 2. - P. 169-192.

2. Erzberger H., Davis T.J., Green S. Design of center-TRACON automation system //In AGARD, Machine Intelligence in Air Traffic Management - 1993.

3. Williams D.H., Green S.M. Flight evaluation of Center-TRACON Automation System trajectory prediction process. - National Aeronautics and Space Administration, Langley Research Center, 1998.

4. Gaffhey S., Smyth P. Joint probabilistic curve clustering and alignment / Saul L., Weiss Y., Bottou L., eds. Proceedings of Neural Information Processing Systems (NIPS 2004). December 13-18, 2004, Vancouver, British Columbia, Canada. Advances in Neural Information Processing Systems. V. 17. Cambridge, MA: MIT Press. 2005. P. 473-180.

5. Кухаренко Б.Г., Солнцева M.O. Кластеризация управляемых объектов на основе сходства их многомерных траекторий // Информационные технологии. 2014. №5. С. 3-7.

6. Погорелов А. И. Дифференциальная геометрия. 6-ое изд. М.: Наука. 1974.

7. Fischler М.A., Bolles R.С.Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography //Communications of the ACM. - 1981. - T. 24. - №. 6. - C. 381-395.

8. Zuliani M. RANSAC for Dummies //Vision Research Lab, University of California, Santa Barbara. - 2009.

9. Torr P.H.S., Zisserman A. MLESAC: A new robust estimator with application to estimating image geometry // Journal of Computer Vision and Image Understanding. 2000. V.78, No. 1. P. 138-156.

10. Кухаренко Б.Г. Алгоритмы анализа изображений для определения локальных особенностей и распознавания объектов и панорам. Информационные технологии. 2011. №7. Приложение. С. 1-32.