Занимаясь разработкой ПО, и в первую очередь, разработкой алгоритмов для беспилотников, мы заинтересовались статьей про то, как решение 17-ой проблемы Гильберта помогает беспилотным автомобилям избегать столкновения с препятствием. Предлагаем краткий обзор и частичный перевод этой статьи от эксперта «АстроСофт».



В начале двадцатого века Давид Гильберт, знаменитый немецкий математик, сформулировал 23 фундаментальные проблемы математики, часть которых не решена и сегодня. Но 17-ая проблема, задающая вопрос: «Представимы ли определенные формы в виде суммы квадратов?» и решенная в 1927 году, позволила современным исследователям обеспечить безопасность беспилотным автомобилям, предупреждая их столкновения с препятствиями.

Журнал Quanta опубликовал статью Кевина Хартнетта (Kevin Hartnett) о работе Амира Али Ахмади (Amir Ali Ahmadi) и Анирудха Муджумдара (Anirudha Majumdar), которая направлена на использование 17-й проблемы Гильберта для решения современных технологических проблем, одной из которых является уклонение беспилотных автомобилей от препятствий и столкновений.



Хартнетт пишет:

«Представьте простой пример: беспилотный автомобиль на гигантской парковке. На парковке нет ничего, кроме будки охраны в дальнем углу. Ваша задача – запрограммировать автомобиль таким образом, чтобы он ни при каких обстоятельствах не врезался в будку.

В этом случае, стоит начать с нанесения координатной сетки на парковку. Затем, необходимо составить полином, который принимает точки на сетке в качестве исходных значений. Убедитесь, что значение полинома в точке, в которой находится автомобиль отрицательное, а в точке, в которой находится будка — положительное.



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

«Если я начну движение в определенной точке, я не пересеку линию, за которой находится препятствие. Именно это является формальной гарантией безопасности для предупреждения столкновений», — заявил Ахмади.

Если эта воображаемая стена расположена посередине парковки, вдали от будки, весь смысл теряется. Необходимо составить такой полином, при котором стена будет огибать препятствие настолько близко, насколько возможно. Таким образом, вокруг будки образуется невидимый барьер, который оставляет достаточно места для маневра автомобиля.

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

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