Решение семнадцатой проблемы Гильберта поможет беспилотным автомобилям избегать столкновений
В работе Амира Али Ахмади (Amir Ali Ahmadi) и Анирудхи Маджумдар (Anirudha Majumdar) из Принстонского университета (Princeton University) решение семнадцатой проблемы Гильберта использовано в алгоритме по избеганию препятствий в беспилотных автомобилях и дронах. Учёные используют разложение сложного полинома, который описывает пространство впереди, на сумму квадратов. Если такое разложение — успешно, это свидетельствует о наличии препятствия на пути.
Проблема звучит так: пусть дана рациональная функция от переменных с вещественными коэффициентами, которая во всех вещественных точках, где она определена, принимает неотрицательные значения. Для функции от двух переменных, если представлять её на графике, это будет значить, что при любом значении x её график будет лежать над осью y. Гильберт (David Hilbert) предположил, что такую функцию всегда можно представить в виде суммы квадратов рациональных функций, все коэффициенты которых вещественны.
Пример числовой суммы квадратов — это когда мы число 13 раскладываем на 32 + 22. Так же и функцию 5×2 + 16x + 13 можно разложить на (x + 2)2 + (2x + 3)2. Дело в том, что когда мы имеем функцию, представляющую собой сумму квадратов, мы точно знаем, что она никогда не принимает отрицательных значений. Когда у нас есть довольно длинный многочлен с переменными в разных степенях, довольно трудно сразу определить, неотрицательный ли он на всём пространстве или нет. С помощью функции разложения на сумму квадратов мы можем для любого многочлена определить его неотрицательность.
В 1984-м году было предложено решение, которое исследователи-информатики долго не могли взять на вооружение из-за ряда проблем. В 2000-м году учёные всё-таки наловчились и «научили» компьютеры разлагать функции на суммы квадратов — с помощью полуопределённых форм. Но эта реализация была математически затратной и могла оперировать только многочленами, примерно, до шести переменных, а дальше начинала тормозить. Учёные из Принстона предложили другой метод, вычислительно более экономный. «Мы выяснили, что во многих задачах в робототехнике, где нужно доказать неотрицательность, наш алгоритм работает гораздо быстрее старого», — говорит Маджумдар.
В случае с беспилотными машинами, скорость реакции очень важна. Математически, пространство перед машиной представлено как функция со многими параметрами, значения которой отражают, есть впереди преграда или нет. Каждый раз, когда на пути машины появляется барьер или что-то изменяется в пространстве, новый многочлен с новыми коэффициентами генерируется и проверяется на положительность. Когда машина приближается к преграде, в какой-то момент многочлен принимает положительное значение, — это фиксируется с помощью разложения на сумму квадратов — и машина не едет в сторону преграды. Образуется своеобразный математический барьер.
В данный момент есть много алгоритмов избегания препятствий, многие из которых основаны на системе детектирования входных сигналов LIDAR, и новый подход в сравнении с прочими кажется очень перспективным.
Источник: