Сто лет назад великий математик Давид Гильберт задал исследовательский вопрос из области чистой математики. Недавние разработки теории оптимизации выносят работу Гильберта в мир робомобилей




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

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

«Даётся полная, 100% доказуемая гарантия того, что ваша система» сможет избежать столкновений, сказала Джорджина Холл, аспирант из Принстона, сотрудничавшая с Ахмади по этой работе.

Амир Али Ахмади, профессор из Принстона

Гарантия берётся в неожиданном месте – в математической задаче, известной, как "сумма квадратов". Её поставил в 1900-м году великий математик Давид Гильберт. Он спросил, всегда ли определённые уравнения можно выразить в виде суммы из двух отдельных членов, каждый из которых возведён в квадрат.

Математики ответили на вопрос Гильберта через несколько десятилетий. Затем, почти 90 лет спустя, специалисты по информатике и инженеры обнаружили, что это математическое свойство – выразимость уравнения через сумму квадратов – помогает решать множество реальных проблем, которые они хотели бы решить.

«В том, что я делаю, используется много классической математики XIX века, вместе с очень современной вычислительной математикой», — сказал Ахмади.

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

Положительно гарантировано


Что означает, что некая величина является суммой квадратов? Возьмём число 13. Это сумма двух квадратов – 22 и 32. Число 34 равно сумме 32 и 52.

Вместо чисел, вопрос Гильберта – 17-я из 23-х проблем, которые он предложил на заре XX века – имеет дело с многочленами, такими, как 5x2 + 16x + 13. Такие многочлены иногда также можно представить в виде суммы квадратов. К примеру, 5x2 + 16x + 13 можно переписать, как (x + 2)2 + (2x + 3)2.

Когда выражение является суммой квадратов, вам известно, что оно всегда положительное (все [действительные] числа, возведённые в квадрат, дают положительное число или ноль, а сумма положительных чисел – положительна). Гильберт хотел узнать, работает ли это в другую сторону: можно ли все неотрицательные многочлены выразить в виде суммы квадратов рациональных функций. В 1927 математик Эмиль Артин доказал, что гипотеза Гильберта была верна.

Это взаимоотношение оказывается довольно полезным. Если вам дают сложный многочлен, с десятками переменных, возведённых в высшие степени – довольно сложно сразу же определить, является ли он всегда неотрицательным. «Некоторые многочлены очевидно неотрицательны, другие – нет. Сложно проверить их на неотрицательность», — сказал Ахмади.

Но как только вы покажете, что этот многочлен можно выразить через сумму квадратов, то неотрицательность просто станет следствием этого. «Сумма квадратов даёт вам красивый сертификат положительности», — сказал Пабло Паррило, специалист по информатике и инженер из Массачусетского технологического института, участвовавший в перетягивании вопроса о сумме квадратов в прикладной мир.

Знание того, что определённый многочлен всегда неотрицателен, может показаться математической тривиальностью. Но сто лет спустя после того, как Гильберт задал свой вопрос, неотрицательность многочленов оказалась ответом на прикладные задачи, влияющие на всех нас.

Лучший способ


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

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

Джорджина Холл

Поскольку минимальное значение многочлена сложно вычислить напрямую, исследователи делают предположения об этой величине другими методами. Именно тут и вступает в игру неотрицательность, и вопрос того, является ли многочлен суммой квадратов. «Гарантирование неотрицательности – суть всех проблем оптимизации», — сказал Реха Томас, математик из Вашингтонского университета.

Один из способов найти минимальное значение – это задать вопрос: какое максимальное значение можно вычесть из неотрицательного многочлена, чтобы он не стал в какой-то точке отрицательным? Для ответа на вопрос необходимо проверять различные значения – можно ли вычесть 3, чтобы он не стал отрицательным? А 4? А 5? Повторяя процедуру, на каждом шаге вам нужно знать, остаётся ли многочлен неотрицательным. Проверяется это через возможность его выражения в виде суммы квадратов.

«Вопрос, который надо задать – это „является ли многочлен неотрицательным?“ Проблема в том, что с большим количеством переменных на этот вопрос сложно ответить, — сказал Ахмади. – Поэтому мы используем сумму квадратов в качестве замены неотрицательности».

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

Разбивая проблему


17-я проблема Гильберта перешла из мира чистой математики в прикладную плоскость примерно в 2000-м году. Именно тогда несколько исследователей придумали алгоритм проверки того, представим ли многочлен через сумму квадратов. Они дошли до этого, решая вопрос с квадратами через "полуопределённое программирование", благодаря которому компьютеры способны справиться с такой задачей. Это сделало возможным для исследователей из таких областей, как информатика и инженерное дело, использовать возможности неотрицательности для направления своих поисков в сторону оптимальных путей решения задач.

Анируда Маджумдар

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

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

Задачи такого типа называют «линейными», и они были разработаны в 1940-х для решения проблем оптимизации, связанных с военными вопросами. Линейные программы сейчас хорошо понимают и быстро решают. В новой работе Ахмади и Маджумдар показывают, что можно решить множество связанных линейных программ (или, в некоторых случаях, проблему другого типа, программу конуса второго порядка), и скомбинировать результаты для того, чтобы получить нечто, почти настолько же хорошее, как и ответ, который могла бы дать программа для полуопределённого программирования. В итоге, у инженеров появился новый, практичный инструмент, который они могут использовать для проверки на неотрицательность и быстро находить разложение на сумму квадратов.

«Мы изучили несколько задач робототехники и теория контроля, и показали, что качество получаемых решений оказывается полезным для практического использования, и что их гораздо быстрее вычислять», — сказал Маджумдар.

Доказательство безопасности


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

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

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

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

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

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

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

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

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

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

Комментарии (14)


  1. napa3um
    24.06.2018 14:33
    +2

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


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


    1. vassabi
      24.06.2018 14:56

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


      1. potan
        24.06.2018 19:15

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


        1. imm
          25.06.2018 10:33
          +1

          большинство проблем будут решены, если убрать всех человеков (произносится голосом Бендера)


          1. potan
            25.06.2018 13:31

            Пока роботы к этому не готовы.


  1. Halt
    24.06.2018 16:24
    +2

    Как же, однако, избирательна память.

    Задачи такого типа называют «линейными», и они были разработаны в 1940-х для решения проблем оптимизации, связанных с военными вопросами.
    Выдающиеся результаты, много улыбающихся лиц. Прямо гордость берет за торжество науки. Упомянули десяток фамилий, но почему-то, Канторовича упомянуть забыли. Или посчитали очень неудобным, ограничившись скромными «военными вопросами», как бы намекая, что подробности тут неуместны.


    1. Mike_soft
      25.06.2018 11:04

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


  1. Peacemaker
    24.06.2018 17:18
    +3

    Когда выражение является суммой квадратов, вам известно, что оно всегда положительное
    <ЗанудаМоде>И всё-таки, оно всегда неотрицательное</Занудамоде>


    1. sasha1024
      25.06.2018 12:05

      Кстати, в оригинале (несмотря на то, что там есть свои огрехи) в этом месте всё-таки стои?т «nonnegative».


  1. KiloLeo
    24.06.2018 17:51

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


  1. k_s
    25.06.2018 10:32
    +1

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

    качество получаемых решений оказывается полезным для практического использования

    Даётся полная, 100% доказуемая гарантия


    Хм…


  1. strcpy
    26.06.2018 00:19
    +1

    История с автомобилями похожа на пиар, чтобы создать шум вокруг исследований и привлечь финансирование. Насколько я знаю, проблема в том чтобы верно детектировать то, что находится вокруг автомобиля. Веб камеры плохо работают в темноте, а лидар датчики слишком дороги и могут ослепить пешеходов, если они будут на каждом автомобиле. Про полиномы любопытно то, что это на самом деле NP сложная задача, поэтому решать ее для полиномов больше 10 на практике не получалось. Интересно, какая сложность у алгоритмов, которые были предложены в качестве альтернативы?


  1. opetrenko
    26.06.2018 05:18

    Это ж какой многочлен надо соорудить, что бы оценить трезвость велосипедиста и соответственно объехать бедолагу хоть по встрече? Или заметить заметил ли тачку чел который подошел к краю дороги, что бы перейти.
    Хулиганы — что пешеходы, что водители будут тролить роботов: перебегать дорогу, безнаказанно подрезать будучи в полной уверености, что умный робот оттормозит даже лучше обычной АБС.
    Хотя, на водителей-хулиганов можно автоматически жаловаться в страховую.
    А вот пешодов прийдется чипировать. Шутка.


  1. olgerdovich
    26.06.2018 12:26

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