БПЛА научили безопасно прокладывать маршрут среди неизвестных движущихся препятствий

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

SANDO — сокращение от Safe AutoNomous trajectory planning for Dynamic unknOwn environments («безопасное автономное планирование траектории для динамических неизвестных сред»). Система может быть полезна для поисково-спасательных операций в разрушенных зданиях, разведки шахтных выработок и сетей подземных туннелей, а также для автономной доставки в загруженных людьми районах.

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

SANDO объединяет эти подходы. Сначала система строит безопасный коридор — последовательность связанных областей трёхмерного пространства, через которые может пройти БПЛА. В отличие от обычного пространственного коридора, этот коридор учитывает ещё и время: для разных моментов полёта система оценивает, какие области потенциально могут оказаться заняты движущимися объектами.

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

На основе этих данных SANDO создаёт пространственно-временной безопасный коридор полёта. Это позволяет учитывать не только положение препятствия сейчас, но и пространство, в котором оно может оказаться в будущем. Поэтому траектория остаётся безопасной не только в момент её первоначального расчёта.

При построении общего маршрута система использует планировщик на основе алгоритма A* и карты рисков. Участки пространства с большим количеством препятствий получают более высокий «риск», поэтому глобальный планировщик старается прокладывать маршрут вокруг таких зон. Это важно: система не направляет БПЛА в наиболее опасные области, как можно было бы понять из исходного текста, а, напротив, использует тепловую карту, чтобы обходить участки с высокой концентрацией препятствий.

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

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

Одной из ключевых особенностей SANDO стала оптимизация самого процесса расчёта. Исследователи сформулировали задачу планирования траектории как смешанную целочисленную квадратичную задачу (MIQP), а затем применили методы сокращения числа переменных. Это позволило ускорить вычисления и сделать частое перепланирование возможным на бортовом компьютере. Согласно опубликованным результатам, применённый метод сокращения переменных способен ускорять оптимизацию до 7,4 раза.

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

В компьютерных симуляциях SANDO показала более высокую скорость достижения цели по сравнению с несколькими современными системами планирования, сохраняя отсутствие столкновений в исследованных сценариях. Систему также испытали на реальном БПЛА: планирование, восприятие окружающей среды и локализация выполнялись с использованием бортового оборудования. В испытаниях с динамическими препятствиями аппарат успешно перестраивал маршрут и избегал столкновений. MIT сообщает о 12 тестовых полётах, в которых SANDO обошла все динамические препятствия.

Таким образом, разработчики пытаются решить одну из фундаментальных проблем автономного полёта: безопасный маршрут нельзя считать неизменным, если сама окружающая среда постоянно меняется. SANDO объединяет пространственно-временное планирование, формальный анализ безопасности и быстрое бортовое перепланирование. Именно сочетание этих компонентов позволяет одновременно стремиться к высокой скорости движения и сохранять строгие ограничения на столкновения.

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

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

Однако остаётся принципиальный вопрос: насколько надёжной можно считать математическую гарантию безопасности в реальном мире, если она всё равно зависит от правильной оценки скорости препятствий, точности датчиков и предположений о поведении окружающих объектов?