СПОСОБ И УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ АВТОМОБИЛЕМ
METHOD AND DEVICE FOR VEHICLE CONTROL

Область техники
[0001] Настоящая технология в основном относится к беспилотным автомобилям (SDC); и, в частности, к электронному устройству и способу управления SDC.
Уровень техники
[0002] Беспилотные автомобили (SDC) - это транспортные средства, которые могут автономно перемещаться через частные и/или общественные места. Используя систему датчиков, которые определяют местоположение и/или окружение SDC, логическая схема внутри или связанная с SDC управляет скоростью, движением, торможением и рулевым управлением SDC на основе обнаруженного датчиком местоположения и окружения SDC. Например, компьютерная система может использовать данные датчиков для генерирования будущих траекторий для SDC на участке дороги и может управлять работой SDC, чтобы он следовал выбранной траектории на этом участке дороги.
[0003] Одной из основных технических проблем при реализации вышеупомянутых систем является способность компьютерной системы обнаруживать объект, потенциально присутствующий вокруг транспортного средства, например, транспортное средство впереди текущего транспортного средства (текущее транспортное средство является SDC, имеющим компьютерную систему на борту), какое транспортное средство впереди может представлять риск/опасность для текущего транспортного средства и может потребовать от компьютерной системы принятия корректирующих мер, будь то торможение или иное изменение скорости, остановка или смена полосы движения. На более детальном уровне проблема обнаружения объекта заключается не только в двоичном обнаружении (наличие или отсутствие объекта), но и в скорости и точности, связанных с таким анализом и определением (особенно во избежание «ложноотрицательных результатов», в результате чего система не идентифицирует объект, который действительно присутствует перед транспортным средством или около него).
[0004] Острота этой проблемы иллюстрируется следующим гипотетическим сценарием. Представьте себе, что по маршруту едет беспилотное или частично автономное транспортное средство. Ребенок (или взрослый, домашнее животное и т.п.) бежит впереди транспортного средства. Крайне важно, чтобы компьютерная система, управляющая транспортным средством, быстро обнаруживала присутствие объекта и предпринимала корректирующие действия, чтобы избежать столкновения. Естественно, чем быстрее компьютерная система обнаруживает присутствие объекта, тем больше времени у компьютерной системы будет для определения корректирующего действия и выдачи команды транспортному средству на выполнение корректирующего действия.
[0005] Как правило, SDC имеет множество датчиков, позволяющих SDC фиксировать и «понимать» окружающую его территорию. SDC может использовать различные системы датчиков, такие как, но без ограничений, системы камер, радарные системы и системы лидара. Различные системы датчиков могут использоваться для сбора различной информации и/или в другом формате о местоположении и окружении SDC. Например, системы камер могут использоваться для захвата данных изображения окружения SDC. В другом примере системы лидара могут использоваться для сбора данных облака точек для построения трехмерных картографических представлений окружения и других потенциальных объектов, расположенных поблизости от SDC.
[0006] Как правило, SDC обрабатывает данные, захваченные таким множеством датчиков, для генерирования прогноза, обычно с использованием алгоритма машинного обучения (MLA), в отношении присутствия одного или более объектов поблизости от SDC. Такое прогнозирование затем может использоваться SDC для определения наиболее оптимального текущего маневра, будь то продолжение движения, остановка, изменение направления, ускорение или тому подобное.
[0007] Публикация патента США US2020/159216 раскрывает способы и системы для планирования движения в автономном транспортном средстве (АВ), которые разделяют планирование пути и планирование скорости и могут использовать опорные линии в сочетании с планировщиками движения для определения путей. Способ может включать в себя опорные линии для данных планирования проекта в системе координат S-L. Алгоритм планировщика движения использует опорные линии и предыдущую историю планирования пути для генерирования пути в системе координат S-L. Скорость определяется для пути. AV-контроллер обновляет путь и скорость. В расчетах планирования движения используется динамическая справочная таблица транспортных средств для определения возможных движений транспортных средств на основе начального состояния и управляющих входных данных.
Сущность изобретения
[0008] Следовательно, существует потребность в системах и способах, которые позволяют избежать, уменьшить или преодолеть ограничения предшествующего уровня техники. Следует отметить, что для генерирования данных для управления работой беспилотного автомобиля (SDC), таких как, например, данные о траектории, может потребоваться структура графа участка дороги, на котором в настоящее время функционирует SDC. Например, электронное устройство может быть выполнено с возможностью сначала генерировать структуру графа, представляющую соответствующие потенциальные положения SDC на участке дороги и переходы между этими потенциальными положениями. В этом примере электронное устройство может определять данную последовательность ребер в структуре графа, которая (i) связана с приемлемой общей стоимостью ребер в последовательности, и (ii) представляет потенциальный путь, по которому SDC должен следовать на участке дороги. Затем электронное устройство может генерировать данные о траектории для SDC, чтобы фактически следовать по этому пути на участке дороги.
[0009] Генерирование структуры графа для участка дороги - это затратная с вычислительной точки зрения операция, которая может занять значительное количество времени. Это связано с тем, что электронному устройству необходимо вычислить множество атрибутов для соответствующих ребер структуры графа. По меньшей мере в некоторых вариантах осуществления настоящей технологии разработчики настоящей технологии разработали способы и электронные устройства для повышения эффективности процесса генерирования структуры графа. Разработчики настоящей технологии осознали, что уменьшение количества вычислений и/или количества времени, необходимого для генерирования структуры графа, позволяет сократить общее количество времени, необходимое для генерирования данных о траектории для работы SDC на участке дороги. Увеличение вычислительной скорости процесса генерирования структуры графа во время работы SDC выгодно для работы SDC.
[00010] По меньшей мере в некоторых вариантах осуществления настоящей технологии процесс генерирования структуры графа включает в себя (i) предварительную фазу и (ii) основную итерационную фазу. На предварительном этапе для участка дороги инициализируется «предварительная» структура графа. Генерирование этой предварительной структуры графа - относительно недорогая операция (с точки зрения вычислительных ресурсов) по сравнению с основной итерационной фазой. Затем электронное устройство конфигурируется для ранжирования ребер этой предварительной структуры графа в ранжированный список ребер, имеющих ребро с наивысшим приоритетом вверху списка и ребро с самым низким приоритетом внизу списка. Электронное устройство использует этот ранжированный список ребер для выполнения основной итерационной фазы. Во время основной итерационной фазы электронное устройство выполняет ряд итераций. Во время данной итерации электронное устройство выполнено с возможностью генерирования атрибутов для соответствующего ребра из списка. Предполагается, что электронное устройство генерирует атрибуты для соответствующих ребер во время соответствующих итераций, начиная с ребра с наивысшим приоритетом и идя вниз по ранжированному списку ребер, пока не будет достигнут заранее определенный предел. Следует отметить, что генерация данных для соответствующих ребер второй структуры графа - это затратная с вычислительной точки зрения операция. Разработчики настоящей технологии осознали, что итеративное генерирование атрибутов для ребер из ранжированного списка ребер позволяет установить приоритет генерирования атрибутов для ребер с высоким приоритетом по сравнению с генерированием атрибутов для ребер с низким приоритетом. Кроме того, разработчики настоящей технологии осознали, что итеративное генерирование атрибутов для ранжированного списка ребер до тех пор, пока не будет достигнут заранее определенный предел, позволяет сократить время, необходимое для генерирования второй структуры графа (т.е. Фактической структуры графа, которая будет использоваться во время работы SDC), обеспечивая при этом генерирование атрибутов для ребер с высоким приоритетом и/или избегая генерирования атрибутов для ребер с низким приоритетом.
[00011] В первом широком аспекте настоящей технологии предоставляется способ управления беспилотным автомобилем (SDC) на участке дороги. SDC движется по участку дороги, и SDC управляется электронным устройством. Упомянутый способ может исполняться электронным устройством. Способ включает в себя генерирование посредством электронного устройства первой структуры графа, имеющей узлы и ребра. Данный узел связан с соответствующим потенциальным положением SDC на участке дороги. Данное ребро представляет переход SDC между потенциальными положениями соответствующей пары узлов. Способ включает в себя ранжирование посредством электронного устройства ребер на основе логики приоритета в ранжированный список ребер. Ранжированный список ребер указывает на порядок приоритета переходов между соответствующими потенциальными положениями SDC для работы SDC на участке дороги. Способ включает в себя генерирование посредством электронного устройства второй структуры графа (i) путем итеративного генерирования атрибутов для соответствующих одних из ранжированного списка ребер, начиная с ребра с наивысшим приоритетом в ранжированном списке ребер, и (ii) до достижения заранее определенного предельного значения. Заранее определенное предельное значение указывает на общее количество ребер, которые должны быть включены во вторую структуру графа. Вторая структура графа имеет набор ребер из первой структуры графа, для которых генерируются атрибуты. Способ включает в себя предписывание посредством электронного устройства работы SDC на участке дороги с использованием второй структуры графа.
[00012] В некоторых вариантах осуществления способа генерирование второй структуры графа включает в себя выполнение посредством электронного устройства первой итерации и второй итерации. Выполнение первой итерации включает в себя генерирование посредством электронного устройства атрибутов для первого ребра в ранжированном списке ребер, где первое ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Выполнение первой итерации включает в себя сравнение посредством электронного устройства текущего количества ребер с заранее определенным предельным значением. В ответ на то, что текущее количество ребер ниже заранее определенного предельного значения, запускается выполнение второй итерации. Выполнение второй итерации включает в себя генерирование посредством электронного устройства атрибутов для второго ребра в ранжированном списке ребер, где второе ребро ранжируется сразу после первого ребра в ранжированном списке ребер, и второе ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Выполнение второй итерации включает в себя сравнение посредством электронного устройства текущего количества ребер с заранее определенным предельным значением. Выполнение второй итерации включает в себя, в ответ на то, что текущее количество ребер равно заранее определенному предельному значению, остановку генерирования второй структуры графа.
[00013] В некоторых вариантах осуществления способа предписывание работы SDC с использованием второй структуры графа включает в себя: генерирование посредством электронного устройства потенциального пути для SDC на участке дороги, где потенциальный путь представляет соответствующую последовательность ребер во второй структуре графа; генерирование посредством электронного устройства потенциальной траектории для SDC на участке дороги с использованием атрибутов ребер в соответствующей последовательности ребер; и предписывание посредством электронного устройства работы SDC для движения по участку дороги в соответствии с потенциальной траекторией.
[00014] В некоторых вариантах осуществления способа ранжирование ребер в ранжированный список ребер на основе логики приоритета включает в себя определение посредством электронного устройства взвешенной комбинации заранее определенных критериев приоритета. Заранее определенные критерии приоритета включают в себя по меньшей мере одно из следующего: позиционное смещение данного ребра от центра полосы движения, длина данного ребра, расстояние между данным ребром и текущим положением транспортного средства, связь ребра с одной из текущей полосы движения и целевой полосы движения, кривизна участка дороги, соответствующего данному ребру, текущая скорость транспортного средства и допустимое ограничение скорости на этом участке дороги.
[00015] В некоторых вариантах осуществления способа ранжирование ребер в ранжированный список ребер на основе логики приоритета включает в себя выполнение посредством электронного устройства алгоритма машинного обучения (MLA), обученного генерировать прогнозируемую оценку приоритета для данного ребра на основе множества заранее определенных критериев приоритета. Ребра должны быть ранжированы на основе соответствующих прогнозируемых оценок приоритета.
[00016] В некоторых вариантах осуществления способа атрибуты данного ребра содержат по меньшей мере, одно из следующего: расстояние до данного ребра от одного или более статических объектов на участке дороги и расстояние до данного ребра от одного или более динамических объектов на участке дороги.
[00017] В некоторых вариантах осуществления способа заранее определенным предельным значением является общее количество ребер.
[00018] В некоторых вариантах осуществления способа заранее определенное предельное значение представляет собой общее количество промежуточных точек вдоль ребер, для которых должны быть определены атрибуты.
[00019] В некоторых вариантах осуществления способа вторая структура графа используется для работы SDC на участке дороги во время первого цикла планирования, и при этом способ дополнительно включает в себя генерирование посредством электронного устройства другой второй структуры графа для второго цикла планирования и предписывание посредством электронного устройства работы SDC на участке дороги с использованием другой второй структуры графа во время второго цикла планирования.
[00020] В некоторых вариантах осуществления способа способ дополнительно включает в себя: прием посредством электронного устройства первых данных датчика в первый момент времени от системы датчиков, установленной на SDC, причем первые данные датчика указывают информацию об участке дороги в первый момент времени; инициирование посредством электронного устройства первого цикла планирования в первый момент времени для генерирования второй структуры графа на основе первых данных датчика; прием посредством электронного устройства вторых данных датчика во второй момент времени от системы датчиков, установленной на SDC, причем вторые данные датчика указывают на информацию об участке дороги во второй момент времени, причем второй момент времени наступает после первого момента времени; и инициирование посредством электронного устройства второго цикла планирования во второй момент времени для генерирования другой второй структуры графа на основе вторых данных датчика.
[00021] В некоторых вариантах осуществления способа генерирование второй структуры графа включает в себя выполнение электронным устройством первой итерации и второй итерации. Выполнение первой итерации включает в себя генерирование посредством электронного устройства атрибутов для первого ребра в ранжированном списке ребер, где первое ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Выполнение первой итерации включает в себя сравнение посредством электронного устройства текущего количества ребер с заранее определенным предельным значением. В ответ на то, что текущее количество ребер ниже заранее определенного предельного значения, запускается выполнение второй итерации. Выполнение второй итерации включает в себя генерирование посредством электронного устройства атрибутов для второго ребра в ранжированном списке ребер, где второе ребро является следующим ребром в ранжированном списке ребер после первого ребра и которое соединяется по меньшей мере с одним ребром, которое в настоящее время включено во вторую структуру графа, и второе ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Выполнение второй итерации включает в себя сравнение посредством электронного устройства текущего количества ребер с заранее определенным предельным значением. Выполнение второй итерации включает в себя, в ответ на то, что текущее количество ребер равно заранее определенному предельному значению, остановку генерирования второй структуры графа.
[00022] Во втором широком аспекте настоящей технологии предоставляется электронное устройство для управления беспилотным автомобилем (SDC) на участке дороги. SDC движется по участку дороги, и SDC управляется электронным устройством. Электронное устройство выполнено с возможностью генерирования первой структуры графа, имеющей узлы и ребра, причем данный узел связан с соответствующим потенциальным положением SDC на участке дороги, и причем данное ребро представляет переход SDC между потенциальными положениями соответствующей пары узлов. Электронное устройство выполнено с возможностью ранжирования ребер на основе логики приоритета в ранжированный список ребер, где ранжированный список ребер указывает порядок приоритета переходов между соответствующими потенциальными положениями SDC для работы SDC на участке дороги. Электронное устройство выполнено с возможностью генерирования второй структуры графа (i) путем итеративного генерирования атрибутов для соответствующих одних из ранжированного списка ребер, начиная с ребра с наивысшим приоритетом в ранжированном списке ребер, и (ii) до достижения заранее определенного предельного значения. Заранее определенное предельное значение указывает на общее количество ребер, которые должны быть включены во вторую структуру графа. Вторая структура графа имеет набор ребер из первой структуры графа, для которых генерируются атрибуты. Электронное устройство выполнено с возможностью предписывать работу SDC на участке дороги с использованием второй структуры графа.
[00023] В некоторых вариантах осуществления электронного устройства электронное устройство, выполненное с возможностью генерирования второй структуры графа, содержит электронное устройство, выполненное с возможностью выполнения первой итерации и второй итерации. Для выполнения первой итерации электронное устройство выполнено с возможностью генерирования атрибутов для первого ребра в ранжированном списке ребер, где первое ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Для выполнения первой итерации электронное устройство выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением. В ответ на то, что текущее количество ребер ниже заранее определенного предельного значения, запускается выполнение второй итерации. Для выполнения второй итерации электронное устройство выполнено с возможностью генерирования атрибутов для второго ребра в ранжированном списке ребер, где второе ребро ранжируется сразу после первого ребра в ранжированном списке ребер, и второе ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Для выполнения второй итерации электронное устройство выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением. Для выполнения второй итерации электронное устройство выполнено с возможностью остановки генерирования второй структуры графа в ответ на то, что текущее количество ребер равно заранее определенному предельному значению.
[00024] В некоторых вариантах осуществления электронного устройства электронное устройство, выполненное с возможностью предписывать работу SDC с использованием второй структуры графа, содержит электронное устройство, выполненное с возможностью: генерировать потенциальный путь для SDC на участке дороги, где потенциальный путь представляет соответствующую последовательность ребер во второй структуре графа; и генерировать потенциальную траекторию для SDC на участке дороги, используя атрибуты ребер в соответствующей последовательности ребер; и предписывать работу SDC для движения по участку дороги в соответствии с потенциальной траекторией.
[00025] В некоторых вариантах осуществления электронного устройства электронное устройство, выполненное с возможностью ранжирования ребер в ранжированный список ребер на основе логики приоритета, содержит электронное устройство, выполненное с возможностью определения взвешенной комбинации заранее определенных критериев приоритета. Заранее определенные критерии приоритета включают в себя по меньшей мере одно из следующего: позиционное смещение данного ребра от центра полосы движения, длина данного ребра, расстояние между данным ребром и текущим положением транспортного средства, связь ребра с одной из текущей полосы движения и целевой полосы движения, кривизна участка дороги, соответствующего данному ребру, текущая скорость транспортного средства и допустимое ограничение скорости на этом участке дороги.
[00026] В некоторых вариантах осуществления электронного устройства электронное устройство, выполненное с возможностью ранжирования ребер в ранжированный список ребер, содержит на основе логики приоритета электронное устройство, выполненное с возможностью выполнения алгоритма машинного обучения (MLA), обученного генерировать прогнозируемую оценку приоритета для данного ребра на основе множества заранее определенных критериев приоритета. Ребра должны быть ранжированы на основе соответствующих прогнозируемых оценок приоритета.
[00027] В некоторых вариантах осуществления электронного устройства атрибуты данного ребра содержат по меньшей мере одно из следующего: расстояние данного ребра от одного или более статических объектов на участке дороги и расстояние данного ребра от одного или более динамических объектов на участке дороги.
[00028] В некоторых вариантах осуществления электронного устройства заранее определенным предельным значением является общее количество ребер.
[00029] В некоторых вариантах осуществления электронного устройства заранее определенное предельное значение представляет собой общее количество промежуточных точек вдоль ребер, для которых должны быть определены атрибуты.
[00030] В некоторых вариантах осуществления электронного устройства вторая структура графа используется для работы SDC на участке дороги во время первого цикла планирования, и при этом электронное устройство дополнительно выполнено с возможностью генерирования другой второй структуры графа для второго цикла планирования, и предписывания работы SDC на участке дороги с использованием другой второй структуры графа во время второго цикла планирования.
[00031] В некоторых вариантах осуществления электронного устройства электронное устройство дополнительно выполнено с возможностью: принимать первые данные датчика в первый момент времени от системы датчиков, установленной на SDC, где первые данные датчика указывают информацию об участке дороги в первый момент времени; инициировать первый цикл планирования в первый момент времени для генерирования второй структуры графа на основе первых данных датчика; принимать вторые данные датчика во второй момент времени от системы датчиков, установленной на SDC, причем вторые данные датчика указывают информацию об участке дороги во второй момент времени, второй причем момент времени наступает после первого момента времени; и инициировать второй цикл планирования во второй момент времени для генерирования другой второй структуры графа на основе вторых данных датчика.
[00032] В некоторых вариантах осуществления электронного устройства электронное устройство, выполненное с возможностью генерирования второй структуры графа, содержит электронное устройство, выполненное с возможностью выполнения первой итерации и второй итерации. Для выполнения первой итерации электронное устройство выполнено с возможностью генерирования атрибутов для первого ребра в ранжированном списке ребер, где первое ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Для выполнения первой итерации электронное устройство выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением. В ответ на то, что текущее количество ребер ниже заранее определенного предельного значения, запускается выполнение второй итерации. Чтобы выполнить вторую итерацию, электронное устройство выполнено с возможностью генерирования атрибутов для второго ребра в ранжированном списке ребер, где второе ребро является следующим ребром в ранжированном списке ребер после первого ребра и соединено по меньшей мере с одним ребром, в настоящее время включенным во вторую структуру графа, а второе ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Для выполнения второй итерации электронное устройство выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением. Для выполнения второй итерации электронное устройство выполнено с возможностью остановки генерирования второй структуры графа в ответ на то, что текущее количество ребер равно заранее определенному предельному значению.
[00033] В контексте настоящего описания термин «окружение» данного транспортного средства относится к области или объему вокруг данного транспортного средства, включая часть его текущей окружающей среды, доступную для сканирования с использованием одного или более датчиков, установленных на данном транспортном средстве, например, для генерирования трехмерной карты такого окружения или обнаружения в нем объектов.
[00034] В контексте настоящего описания «интересующая область» может в широком смысле включать в себя часть наблюдаемой среды системы лидара, в которой один или более объектов могут быть обнаружены. Следует отметить, что на интересующую область системы лидара могут влиять различные условия, такие как, но, не ограничиваясь ими: ориентация системы лидара (например, направление оптической оси системы лидара); положение системы лидара по отношению к окружении (например, расстояние над землей и прилегающий рельеф местности и препятствия); рабочие параметры системы лидара (например, мощность излучения, вычислительные настройки, заданные углы работы) и т.д. ROI системы лидара может быть определен, например, плоским углом или телесным углом. В одном примере ROI также может быть определена в пределах определенного диапазона расстояний (например, до 200 м или около того).
[00035] В контексте настоящего описания «сервер» - это компьютерная программа, которая выполняется на соответствующем аппаратном обеспечении и способна принимать запросы (например, от клиентских устройств) по сети и выполнять эти запросы или вызывать выполнение этих запросов. Аппаратное обеспечение может быть реализовано как один физический компьютер или одна физическая компьютерная система, но ни то, ни другое не требуется в отношении настоящей технологии. В данном контексте использование выражения «сервер» не предназначено для обозначения того, что каждая задача (например, принятые инструкции или запросы) или любая конкретная задача была принята, выполнена или вызвана к выполнению одним и тем же сервером (то есть тем же программным и/или аппаратным обеспечением); это означает, что любое количество программных элементов или аппаратных устройств может быть вовлечено в прием/отправку, выполнение или обеспечение выполнения любой задачи или запроса или последствий любой задачи или запроса; и все это программное и аппаратное обеспечение может быть одним сервером или несколькими серверами, оба случая из которых включены в выражение «по меньшей мере один сервер».
[00036] В контексте настоящего описания «электронное устройство» - это любое компьютерное оборудование, которое способно запускать программное обеспечение, подходящее для соответствующей решаемой задачи. В контексте настоящего описания термин «электронное устройство» подразумевает, что устройство может функционировать как сервер для других электронных устройств и клиентских устройств, однако это не обязательно в отношении настоящей технологии. Таким образом, некоторые (не ограничивающие) примеры электронных устройств включают в себя персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.д.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует понимать, что в данном контексте тот факт, что устройство функционирует как электронное устройство, не означает, что оно не может функционировать как сервер для других электронных устройств. Использование выражения «электронное устройство» не исключает использования нескольких клиентских устройств для приема/отправки, выполнения или обеспечения выполнения любой задачи или запроса, а также последствий любой задачи или запроса или этапов любого способа, описанных здесь.
[00037] В контексте настоящего описания «клиентское устройство» - это любое компьютерное оборудование, которое способно запускать программное обеспечение, подходящее для соответствующей решаемой задачи. В контексте настоящего описания термин «клиентское устройство» обычно ассоциируется с пользователем клиентского устройства. Таким образом, некоторые (не ограничивающие) примеры клиентских устройств включают в себя персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.д.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что устройству, действующему как клиентское устройство в данном контексте, не запрещается действовать как сервер для других клиентских устройств. Использование выражения «клиентское устройство» не исключает использования нескольких клиентских устройств для приема/отправки, выполнения или обеспечения выполнения любой задачи или запроса, а также последствий любой задачи или запроса или этапов любого способа, описанных здесь.
[00038] В контексте настоящего описания выражение «информация» включает в себя информацию любого характера или вида, которая может быть сохранена в базе данных. Таким образом, информация включает в себя, но без ограничения, аудиовизуальные произведения (изображения, фильмы, звуковые записи, презентации и т.д.), данные (данные о местоположении, численные данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, электронные таблицы и т.д.
[00039] В контексте настоящего описания выражение «программный компонент» подразумевает включение программного обеспечения (подходящего для конкретного аппаратного контекста), которое является одновременно необходимым и достаточным для выполнения конкретной(ых) функции(й), на которую делается ссылка.
[00040] В контексте настоящего описания выражение «компьютерный носитель информации» (также называемый «носитель информации») предназначен для включения носителей любого характера и типа, включая, без ограничения, RAM, ROM, диски (CD-ROM), DVD, дискеты, жесткие диски и т.д.), USB-ключи, твердотельные накопители, ленточные накопители и т.д. Множество компонентов могут быть объединены для формирования компьютерных носителей информации, включая два или более компонентов носителей одного типа и/или два или более компонентов носителей разных типов.
[00041] В контексте настоящего описания «база данных» представляет собой любой структурированный набор данных, независимо от его конкретной структуры, программного обеспечения для управления базой данных или компьютерного оборудования, на котором данные хранятся, реализуются или иным образом предоставляются для использования. База данных может находиться на том же аппаратном обеспечении, что и процесс, который хранит или использует информацию, хранящуюся в базе данных, или она может находиться на отдельном оборудовании, например на выделенном сервере или множестве серверов.
[00042] В контексте настоящего описания слова «первый», «второй», «третий» и т.д. использовались в качестве прилагательных только с целью обеспечения различия между существительными, которые они изменяют относительно друг от друга, а не для цели описания каких-либо конкретных отношений между этими существительными. Таким образом, например, следует понимать, что использование терминов «первая база данных» и «третий сервер» не предназначено для обозначения какого-либо конкретного порядка, типа, хронологии, иерархии или ранжирования (например) серверов/между серверами и их использование (само по себе) не подразумевает, что любой «второй сервер» обязательно должен существовать в любой данной ситуации. Кроме того, как обсуждается здесь в других контекстах, ссылка на «первый» элемент и «второй» элемент не препятствует тому, чтобы эти два элемента были одним и тем же фактическим элементом реального мира. Таким образом, например, в некоторых случаях «первый» сервер и «второй» сервер могут быть одним и тем же программным и/или аппаратным компонентами, в других случаях они могут быть разными программными и/или аппаратными компонентами.
[00043] Каждая из реализаций настоящей технологии имеет по меньшей мере один из вышеупомянутых объектов и/или аспектов, но не обязательно имеет все из них. Следует понимать, что некоторые аспекты настоящей технологии, которые возникли в попытке достичь вышеупомянутой цели, могут не удовлетворять этой цели и/или удовлетворять другим целям, которые не описаны в данном документе явным образом.
[00044] Дополнительные и/или альтернативные признаки, аспекты и преимущества реализаций настоящей технологии станут очевидными из нижеследующего описания, сопроводительных чертежей и приложенной формулы изобретения.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[00045] Эти и другие признаки, аспекты и преимущества настоящей технологии станут более понятными из нижеследующего описания, приложенной формулы изобретения и сопроводительных чертежей, на которых:
[00046] Фиг. 1 изображает принципиальную схему примерной компьютерной системы, конфигурируемой для реализации некоторых неограничивающих вариантов осуществления настоящей технологии.
[00047] Фиг. 2 изображает принципиальную схему сетевой вычислительной среды, подходящей для использования с некоторыми неограничивающими вариантами осуществления настоящей технологии.
[00048] Фиг. 3 изображает представление транспортного средства, движущегося по участку дороги, в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00049] Фиг. 4 изображает представление первой структуры графа, сгенерированной электронным устройством по фиг. 2, для участка дороги в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00050] Фиг. 5 изображает представление ранжированного списка ребер, сгенерированного электронным устройством в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00051] Фиг. 6 изображает представление итерационного процесса, выполняемого электронным устройством для генерирования второй структуры графа для участка дороги в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00052] Фиг. 7 изображает представление второй структуры графа и путей, генерируемых электронным устройством для участка дороги в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00053] Фиг. 8 изображает представление циклов планирования, во время которых электронное устройство генерирует соответствующие вторые структуры графов для участка дороги в соответствии с некоторыми вариантами осуществления настоящей технологии.
[00054] Фиг. 9 представляет собой схематическое представление способа, выполняемого электронным устройством в соответствии по меньшей мере с некоторыми неограничивающими вариантами осуществления настоящей технологии.
Подробное описание
[00055] Приведенные в данном документе примеры и условные формулировки призваны главным образом помочь читателю понять принципы настоящей технологии, а не ограничить ее объем такими конкретно приведенными примерами и условиями. Должно быть понятно, что специалисты в данной области смогут разработать различные механизмы, которые, хоть и не описаны в данном документе явным образом, тем не менее воплощают принципы настоящей технологии и включаются в ее суть и объем.
[00056] Кроме того, нижеследующее описание может описывать реализации настоящей технологии в относительно упрощенном виде для целей упрощения понимания. Специалисты в данной области поймут, что различные реализации настоящей технологии могут иметь большую сложность.
[00057] В некоторых случаях также могут быть изложены примеры модификаций настоящей технологии, которые считаются полезными. Это делается лишь для содействия пониманию и, опять же, не для строгого определения объема или очерчивания границ настоящей технологии. Эти модификации не являются исчерпывающим списком, и специалист в данной области может осуществлять другие модификации, все еще оставаясь при этом в рамках объема настоящей технологии. Кроме того, случаи, когда примеры модификаций не приводятся, не следует толковать так, что никакие модификации не могут быть осуществлены и/или что описанное является единственным способом реализации такого элемента настоящей технологии.
[00058] Более того, все утверждения в данном документе, излагающие принципы, аспекты и реализации технологии, а также их конкретные примеры, предназначены для охвата как их структурных, так и функциональных эквивалентов, независимо от того, известны они в настоящее время или разрабатываются в будущем. Таким образом, например, специалисты в данной области осознают, что любые блок-схемы в данном документе представляют концептуальные виды иллюстративной схемы, воплощающей принципы настоящей технологии. Аналогичным образом, будет понятно, что любые блок-схемы, схемы последовательности операций, схемы изменения состояний, псевдо-коды и подобное представляют различные процессы, которые могут быть по сути представлены на считываемых компьютерам носителях и исполнены компьютером или процессором вне зависимости от того, показан такой компьютер или процессор явным образом или нет.
[00059] Функции различных элементов, показанных на фигурах, включая любой функциональный блок, обозначенный как «процессор», могут быть обеспечены за счет использования специализированного аппаратного обеспечения, а также аппаратного обеспечения, способного выполнять программное обеспечение в сочетании с соответствующим программным обеспечением. При обеспечении процессором функции могут быть обеспечены одним выделенным процессором, одним совместно используемым процессором или множеством отдельных процессоров, некоторые из которых могут быть совместно используемыми. Кроме того, явное использование термина «процессор» или «контроллер» не должно истолковываться как относящееся исключительно к аппаратному обеспечению, способному исполнять программное обеспечение, и может в неявной форме включать в себя, без ограничений, аппаратное обеспечение цифрового сигнального процессора (DSP), сетевой процессор, интегральную схему специального назначения (ASIC), программируемую пользователем вентильную матрицу (FPGA), постоянную память (ROM) для хранения программного обеспечения, оперативную память (RAM) и энергонезависимое хранилище. Другое аппаратное обеспечение, традиционное и/или специализированное, также может быть включено в состав.
[00060] Программные модули, или просто модули, в качестве которых может подразумеваться программное обеспечение, могут быть представлены в настоящем документе как любая комбинация элементов блок-схемы последовательности операций или других элементов, указывающих выполнение этапов процесса и/или текстовое описание. Такие модули могут выполняться аппаратным обеспечением, которое явно или неявно показано.
[00061] Учитывая эти основополагающие вещи, рассмотрим некоторые неограничивающие примеры, чтобы проиллюстрировать различные реализации аспектов настоящей технологии.
Компьютерная система
[00062] Ссылаясь сначала на фиг. 1, на ней изображена принципиальная схема компьютерной системы 100, подходящей для использования с некоторыми реализациями настоящей технологии. Компьютерная система 100 включает в себя различные аппаратные компоненты, включая один или более одноядерных или многоядерных процессоров, совместно представленных процессором 110, твердотельным накопителем 120 и памятью 130, которая может быть оперативной памятью или любым другим типом памяти.
[00063] Связь между различными компонентами компьютерной системы 100 может быть обеспечена одной или несколькими внутренними и/или внешними шинами (не показаны) (например, шиной PCI, универсальной последовательной шиной, шиной Firewire IEEE 1394, шиной SCSI, шиной Serial-ATA и т.д.), с которыми различные аппаратные компоненты электронно связаны. Согласно вариантам осуществления настоящей технологии твердотельный накопитель 120 хранит программные инструкции, подходящие для загрузки в память 130 и выполнения процессором 110 для определения присутствия объекта. Например, программные инструкции могут быть частью приложения управления транспортным средством, выполняемого процессором 110. Следует отметить, что компьютерная система 100 может иметь дополнительные и/или опциональные компоненты (не показаны), такие как модули сетевой связи, модули локализации и т.п.
Сетевая вычислительная среда
[00064] Со ссылкой на фиг.2 изображена сетевая вычислительная среда 200, подходящая для использования с некоторыми неограничивающими вариантами осуществления настоящей технологии. Сетевая вычислительная среда 200 включает в себя электронное устройство 210, связанное с транспортным средством 220 и/или связанное с пользователем (не изображен), который связан с транспортным средством 220 (например, в качестве оператора транспортного средства 220). Среда 200 также включает в себя сервер 235, поддерживающий связь с электронным устройством 210 через сеть 240 связи (например, Интернет и т.п., как будет более подробно описано ниже).
[00065] По меньшей мере в некоторых неограничивающих вариантах осуществления настоящей технологии электронное устройство 210 связано с возможностью осуществления связи с системами управления транспортного средства 220. Электронное устройство 210 может быть выполнено с возможностью управления различными операционными системами транспортного средства 220, включая, помимо прочего: ECU (блок управления двигателем), системы рулевого управления, тормозные системы, а также системы сигнализации и освещения (т.е. фары, стоп-сигналы, и/или указатели поворота). В таком варианте осуществления транспортное средство 220 может быть беспилотным транспортным средством 220.
[00066] В некоторых неограничивающих вариантах осуществления настоящей технологии сетевая вычислительная среда 200 может включать в себя спутник GPS (не показан), передающий и/или принимающий сигнал GPS на/от электронного устройства 210. Следует понимать, что настоящая технология не ограничивается GPS и может использовать технологию определения местоположения, отличную от GPS. Следует отметить, что спутник GPS можно вообще не использовать.
[00067] Транспортное средство 220, с которым связано электронное устройство 210, может быть любым транспортным средством для отдыха или иного, например, частным или коммерческим автомобилем, грузовиком, мотоциклом и т.п. Хотя транспортное средство 220 изображено как наземное транспортное средство, это может быть не так во всех без исключения неограничивающих вариантах осуществления настоящей технологии. Например, в некоторых неограничивающих вариантах осуществления настоящей технологии транспортное средство 220 может быть водным транспортным средством, таким как лодка, или летательным аппаратом, например летающим дроном.
[00068] Транспортное средство 220 может управляться пользователем или может быть транспортным средством без водителя. В некоторых неограничивающих вариантах осуществления настоящей технологии предполагается, что транспортное средство 220 может быть реализовано как беспилотный автомобиль (SDC). Следует отметить, что конкретные параметры транспортного средства 220 не являются ограничивающими, эти конкретные параметры включают в себя, например: производителя транспортного средства, модель транспортного средства, год выпуска транспортного средства, вес транспортного средства, размеры транспортного средства, распределение веса транспортного средства, площадь поверхности транспортного средства, высоту транспортного средства, тип трансмиссии (например, 2-x или 4-x), тип шин, тормозную систему, топливную систему, пробег, идентификационный номер транспортного средства и объем двигателя.
[00069] Согласно настоящей технологии реализация электронного устройства 210 особо не ограничивается. Например, электронное устройство 210 может быть реализовано как блок управления двигателем транспортного средства, центральный процессор транспортного средства, навигационное устройство транспортного средства (например, TomTom™, Garmin™),планшет, персональный компьютер, встроенный в транспортное средство 220, и т.п. Таким образом, следует отметить, что электронное устройство 210 может быть или может не быть постоянно связано с транспортным средством 220. Дополнительно или альтернативно электронное устройство 210 может быть реализовано в устройстве беспроводной связи, таком как мобильный телефон (например, смартфон или радиотелефон). В определенных вариантах осуществления электронное устройство 210 имеет дисплей 270.
[00070] Электронное устройство 210 может включать в себя некоторые или все компоненты компьютерной системы 100, изображенной на Фиг.1, в зависимости от конкретного варианта осуществления. В некоторых вариантах осуществления электронное устройство 210 представляет собой бортовое компьютерное устройство и включает в себя процессор 110, твердотельный накопитель 120 и память 130. Другими словами, электронное устройство 210 включает в себя аппаратное обеспечение, и/или программное обеспечение, и/или микропрограммное обеспечение, или их комбинацию для обработки данных, как будет более подробно описано ниже.
[00071] В некоторых неограничивающих вариантах осуществления настоящей технологии сеть 240 связи представляет собой Интернет. В альтернативных неограничивающих вариантах осуществления настоящей технологии сеть 240 связи может быть реализована как любая подходящая локальная сеть (LAN), глобальная сеть (WAN), частная сеть связи и т.п. Следует четко понимать, что реализации для сети 240 связи приведены только в целях иллюстрации. Между электронным устройством 210 и сетью 240 связи предоставляется линия связи (отдельно не пронумерована), реализация которой будет зависеть, среди прочего, от того, как реализовано электронное устройство 210. Просто в качестве примера, а не ограничения, в тех неограничивающих вариантах осуществления настоящей технологии, где электронное устройство 210 реализовано как устройство беспроводной связи, такое как смартфон или навигационное устройство, линия связи может быть реализована как линия беспроводной связи. Примеры линий беспроводной связи могут включать в себя, без ограничения, линию связи сети 3G, линию связи 4G и т.п. Сеть 240 связи также может использовать беспроводное соединение с сервером 235.
[00072] В некоторых вариантах осуществления настоящей технологии сервер 235 реализован как компьютерный сервер и может включать в себя некоторые или все компоненты компьютерной системы 100 на Фиг.1. В одном неограничивающем примере сервер 235 реализован как сервер Dell™ PowerEdge™, работающий под управлением операционной системы Microsoft™ Windows Server™, но также может быть реализован в любом другом подходящем аппаратном обеспечении, программном обеспечении и/или микропрограммном обеспечении или их комбинации. В проиллюстрированном неограничивающем варианте осуществления настоящей технологии сервер 235 является единственным сервером. В альтернативных неограничивающих вариантах осуществления настоящей технологии функциональные возможности сервера 235 могут быть распределены и могут быть реализованы посредством нескольких серверов (не показаны).
[00073] В некоторых неограничивающих вариантах осуществления настоящей технологии процессор 110 электронного устройства 210 может поддерживать связь с сервером 235 для приема одного или более обновлений. Такие обновления могут включать, помимо прочего, обновления программного обеспечения, обновления карт, обновления маршрутов, обновления погоды и т.п. В некоторых неограничивающих вариантах осуществления настоящей технологии процессор 110 также может быть выполнен с возможностью передачи на сервер 235 некоторых рабочих данных, таких как пройденные маршруты, данные дорожного движения, данные производительности и т.п.. Некоторые или все такие данные, передаваемые между транспортным средством 220 и сервером 235, могут быть зашифрованы и/или анонимизированы.
[00074] Следует отметить, что электронное устройство 210 может использовать различные датчики и системы для сбора информации об окружении 250 транспортного средства 220. Как видно на Фиг.2, транспортное средство 220 может быть оборудовано множеством систем 280 датчиков. Следует отметить, что различные системы датчиков из множества систем 280 датчиков могут использоваться для сбора различных типов данных, касающихся окружения 250 транспортного средства 220.
[00075] В одном примере множество систем 280 датчиков может включать в себя различные оптические системы, включая, среди прочего, одну или несколько систем датчиков типа камеры, которые установлены на транспортном средстве 220 и связаны с возможностью осуществления связи с процессором 110 электронного устройства 210. Вообще говоря, одна или несколько систем датчиков типа камеры могут быть выполнены с возможностью сбора данных изображения о различных частях окружения 250 транспортного средства 220. В некоторых случаях данные изображения, предоставленные одной или несколькими системами датчиков типа камеры, могут использоваться электронным устройством 210 для выполнения процедур обнаружения объекта. Например, электронное устройство 210 может быть выполнено с возможностью подачи данных изображения, предоставленных одной или несколькими системами датчиков типа камеры, в нейронную сеть обнаружения объектов (ODNN, Object Detection Neural Network), которая обучена локализовать и классифицировать потенциальные объекты в окружении 250 транспортного средства 220.
[00076] В другом примере множество систем 280 датчиков может включать в себя одну или несколько систем датчиков радарного типа, которые установлены на транспортном средстве 220 и связаны с возможностью осуществления связи с процессором 110. Вообще говоря, одна или несколько систем датчиков радарного типа могут быть выполнены с возможностью использования радиоволн для сбора данных о различных частях окружения 250 транспортного средства 220. Например, одна или несколько систем датчиков радарного типа могут быть выполнены с возможностью сбора радиолокационных данных о потенциальных объектах в окружении 250 транспортного средства 220, такие данные потенциально представляют расстояние объектов от системы датчиков радарного типа, ориентацию объектов, быстроту и/или скорости объектов и т.п.
[00077] В дополнительном примере множество систем 280 датчиков может включать в себя одну или несколько систем оптического обнаружения и определения дальности (LIDAR, лидар), которые установлены на транспортном средстве 220 и связаны с возможностью осуществления связи с процессором 110. Вообще говоря, система лидара выполнена с возможностью сбора данных об окружении 250 транспортного средства 220, используемых, например, для построения многомерной карты объектов в окружении 250 транспортного средства 220. Система лидара может быть установлена или модифицирована на транспортном средстве 220 в различных местоположениях и/или в различных конфигурациях для сбора информации об окружении 250 транспортного средства 220.
[00078] Например, в зависимости от реализации транспортного средства 220 и системы лидара, система лидара может быть установлена на внутренней, верхней части лобового стекла транспортного средства 220. Тем не менее, другие места для установки системы лидара входят в объем настоящего раскрытия, в том числе на заднем окне, боковых окнах, переднем капоте, крыше, передней решетке, переднем бампере или сбоку транспортного средства 220.
[00079] В контексте настоящей технологии электронное устройство 210 выполнено с возможностью обнаружения одного или более объектов в окружении 250 транспортного средства 220 на основе данных, полученных от одной или нескольких систем камер и одной или нескольких систем лидара. Например, электронное устройство 210, выполненное с возможностью обнаружения данного объекта в окружении 250 транспортного средства 220, может быть выполнено с возможностью идентифицировать данные лидара и данные камеры, связанные с данным объектом, генерировать «внедрение», представляющее особенности, связанные с данным объектом, и обнаружить объект, создав ограничивающую рамку для объекта.
[00080] Со ссылкой на Фиг. 3, есть иллюстративный пример 300 транспортного средства 220 в окружении 250. Предположим, что транспортное средство 220 движется по участку 350 дороги. Электронное устройство 210 может принимать от системы 280 датчиков информацию об окружении 250 транспортного средства 220 и, в частности, об участке 350 дороги и об одном или нескольких «действующих лицах» (также иногда называемых «агентами») на участке 350 дороге, например, соседние объекты в окружении транспортного средства 220.
[00081] Электронное устройство 210 может быть выполнено с возможностью использования информации, принятой от системы 280 датчиков, для генерирования «предварительной» структуры графа. Со ссылкой на Фиг.4 изображено представление 400 предварительной структуры 450 графа, которую электронное устройство 210 выполнено с возможностью генерировать на основе информации об окружении 250 транспортного средства 220.
[00082] Предварительная структура 450 графа имеет множество узлов (не пронумерованных) и множество ребер (не пронумерованных), соединяющих соответствующие узлы из множества узлов. Например, ребро 430 предварительной структуры 450 графа соединяет первый узел 410 и второй узел 420. Данный узел связан с соответствующим потенциальным положением транспортного средства 220 на участке 350 дороги. Заданное ребро представляет переход транспортного средства 220 между потенциальными положениями соответствующей пары узлов. Например, ребро 430 представляет переход транспортного средства 220 между его потенциальными положениями первого узла 410 и второго узла 420.
[00083] Следует отметить, что электронное устройство 210 может быть выполнено с возможностью хранения информации в ассоциации с соответствующим узлом и соответствующим ребром предварительной структуры 450 графа. Например, электронное устройство 210 может быть выполнено с возможностью хранения позиционных данных в ассоциации с данным узлом. В другом примере электронное устройство 210 может быть выполнено с возможностью хранения, в ассоциации с данным ребром, позиционных данных соответствующей пары узлов.
[00084] Кроме того, предполагается, что дополнительные данные могут храниться в ассоциации с соответствующим узлом предварительной структуры 450 графа. Можно сказать, что дополнительные данные могут храниться в ассоциации с соответствующим узлом предварительной структуры 450 графа и указывают по меньшей мере на некоторую информацию о потенциальном состоянии транспортного средства 220 на участке 350 дороги.
[00085] В контексте настоящей технологии электронное устройство 210 выполнено с возможностью ранжирования множества ребер предварительной структуры 450 графа на основе «логики приоритета» 502, как показано на фиг. 5. Вообще говоря, логика приоритета может быть реализована как один или более алгоритмов, выполняемых электронным устройством 210, которые выполнены с возможностью генерировать «оценку приоритета» для соответствующего ребра на основе (i) информации, связанной с соответствующим ребром, и (ii) одного или более заранее определенных критериев 504 приоритета. Электронное устройство 210 может использовать сгенерированные таким образом оценки приоритета для ранжирования множества ребер предварительной структуры графа в ранжированный список ребер 550. Предполагается, что электронное устройство 210 может генерировать данную оценку приоритета с учетом заранее определенных критериев 504 приоритета, таких как, например:
- позиционное смещение ребра от центра полосы движения;
- изменение позиционного смещения от центра полосы движения в пределах ребра;
- длина ребра;
- расстояние между ребром и текущим положением транспортного средства;
- ассоциация ребра с одной из текущей полосы движения, целевой полосы движения или другой соседней полосы движения;
- кривизна самого участка дороги (например, для потенциального добавления ребер при выполнении маневров поворота);
- текущая скорость транспортного средства;
- установленное законом ограничение скорости на участке дороги;
- предварительная оценка атрибутов ребер (например, «грубая» оценка расстояния между ребром и данным объектом на участке дороги, для возможного добавления дополнительных ребер рядом с объектом для более точной работы поблизости от объекта); и
- т.п.
[00086] По меньшей мере в некоторых вариантах осуществления настоящей технологии электронное устройство 210 может быть выполнено с возможностью генерирования оценки приоритета для данного ребра на основе взвешенной комбинации значений, определенных для одного или более критериев приоритета, не исчерпывающе перечисленных выше. В одном варианте осуществления настоящей технологии предполагается, что веса, присвоенные соответствующим критериям приоритета во взвешенной комбинации, также могут быть скорректированы на основе значения данного одного из критериев приоритета. Например, соответствующие веса, приписываемые первому критерию приоритета и второму критерию приоритета, могут быть скорректированы во взвешенной комбинации на основе текущей скорости транспортного средства, поскольку разные ребра могут быть более или менее желательными в зависимости от того, насколько быстро или медленно двигается транспортное средство.
[00087] По меньшей мере в некоторых вариантах осуществления настоящей технологии предполагается, что электронное устройство 210 может быть выполнено с возможностью генерирования «легких» атрибутов для соответствующих узлов предварительной структуры графа. Эти атрибуты для соответствующих пар узлов могут использоваться электронным устройством 210 для целей ранжирования данного ребра в предварительной структуре графа, как это будет описано более подробно ниже в данном документе. В некоторых вариантах осуществления можно сказать, что первое подмножество атрибутов может быть сгенерировано для соответствующих узлов предварительной структуры графа для определения порядка приоритета его ребер, и во время итеративного процесса, описанного ниже, второе подмножество атрибутов может быть сгенерировано для его ребер. Например, второе подмножество атрибутов может содержать атрибуты, которые генерируются электронным устройством 210 для промежуточных потенциальных положений, связанных с соответствующими ребрами. Можно сказать, что определение первого подмножества атрибутов менее затратно с вычислительной точки зрения по сравнению с определением второго подмножества атрибутов.
[00088] В других вариантах осуществления логика приоритета может быть реализована электронным устройством 210 в качестве обученного алгоритма машинного обучения (MLA). MLA, реализуемый электронным устройством 210, может быть любым подходящим традиционным MLA. Например, MLA может быть любым из различных традиционных MLA, включая, без ограничения, алгоритмы «глубокого обучения», другие типы нейронных сетей или «коннекционные» системы, деревья решений, леса решений, байесовские сети или другие известные или разработанные позже MLA, которые используют наборыобучающих данных (например, контролируемые или частично контролируемые алгоритмы обучения). Способ, в котором прогноз, метка и метод обучения, используемые для обучения MLA, могут зависеть, среди прочего, от конкретных реализаций настоящей технологии.
[00089] После обучения MLA информация, представляющая MLA, может быть отправлена на электронное устройство, связанное с беспилотным транспортным средством, такое как электронное устройство 210. Затем MLA может использоваться для ранжирования ребер данной предварительной структуры графа.
[00090] В некоторых вариантах осуществления MLA может быть обучен генерировать прогнозируемую оценку приоритета для данного ребра на основе вектора признаков, сгенерированного на основе значений заранее определенных критериев приоритета. MLA может быть обучен таким образом на помеченном наборе данных ребер с соответствующими обучающими значениями заранее определенных критериев приоритета, и где метки указывают эталонный порядок приоритета обучающих ребер.
[00091] Предполагается, что электронное устройство 210 может использовать MLA для определения весов для соответствующих критериев приоритета в формуле приоритизации. По меньшей мере в некоторых вариантах осуществления предполагается, что MLA может быть обучен на основе набора сценариев обучения, которые произошли ранее. Для каждого сценария может быть сгенерирована обучающая структура графа, которая включает в себя все возможные ребра для участка дороги этого сценария обучения, и целевой путь (эталонный) может быть выбран в этой структуре графа для этого сценария обучения. Ребра такой обучающей структуры графа могут быть ранжированы на основе весов и значений соответствующих критериев приоритета в соответствии с формулой приоритизации. В одном примере, если ребра из этого целевого пути не являются ребрами с наивысшим рейтингом в ранжированном порядке ребер, MLA может быть оштрафован за обучение на этой итерации обучения. Независимо от конкретной используемой функции потерь, цель состоит в том, чтобы обучить MLA определять веса для соответствующих критериев приоритета в формуле приоритизации, чтобы ребра с наивысшим рейтингом для соответствующих сценариев соответствовали ребрам соответствующих целевых путей.
[00092] В контексте настоящей технологии электронное устройство 210 выполнено с возможностью использования ранжированного списка ребер 550 для генерирования «фактической» структуры графа, используемой электронным устройством 210 для управления транспортным средством 220 на участке дороги. Следует отметить, что электронное устройство 210 может использовать ранжированный список ребер 550 для выполнения итеративного процесса генерирования, во время которого электронное устройство 210 выполняет множество итераций для итеративного генерирования атрибутов для ребер второй (фактической) структуры графа.
[00093] Как будет обсуждаться более подробно ниже, с каждой итерацией данное ребро из ранжированного списка ребер 550 добавляется к текущему количеству ребер второй структуры графа, и электронное устройство 210 определяет, удовлетворяет ли добавление данного ребра «условию остановки» итерационного процесса. Например, во время данной итерации электронное устройство 210 может вычислить по меньшей мере некоторые данные для данного ребра из ранжированного списка ребер 550 и добавить это данное ребро к текущему количеству ребер во второй структуре графа. Предполагается, что условие остановки итеративного процесса может указывать на общее количество ребер, которое должна иметь вторая структура графа. В одном варианте осуществления, если электронное устройство 210 определяет, что текущее количество ребер в структуре графа превышает заранее определенное количество ребер, электронное устройство 210 может остановить итерационный процесс генерирования второй структуры графа.
[00094] Следует отметить, что генерирование данных для соответствующих ребер второй структуры графа - это затратная с вычислительной точки зрения операция. Как будет описано ниже, электронное устройство 210 может быть выполнено с возможностью генерирования множества атрибутов для соответствующих ребер второй структуры графа. Разработчики настоящей технологии осознали, что итеративное генерирование атрибутов для ребер из ранжированного списка ребер позволяет установить приоритет генерирования атрибутов для ребер с высоким приоритетом по сравнению с генерированием атрибутов для ребер с низким приоритетом. Кроме того, разработчики настоящей технологии поняли, что итеративная генерация атрибутов для ранжированного списка ребер до тех пор, пока не будет достигнут заранее определенный предел, позволяет сократить время, необходимое для генерирования второй структуры графа, при этом гарантируя, что атрибуты для ребер с высоким приоритетом генерируется и/или избегая генерирование атрибутов для ребер с низким приоритетом.
[00095] Чтобы лучше проиллюстрировать этот итерационный процесс генерирования, теперь будет сделана ссылка на фиг. 6, которая изображает представление 600 итеративного процесса, выполняемого электронным устройством 210 для генерирования второй структуры 680 графа. Как видно, изображены первая итерация 601, вторая итерация 602, третья итерация 603, четвертая итерация 604 и i-я итерация 699 итерационного процесса.
[00096] Для начала предположим, что ребро с наивысшим рейтингом (наивысший приоритет) в ранжированном списке ребер 550 является первым ребром 651. Во время первой итерации 601 электронное устройство 210 выполнено с возможностью генерирования атрибутов для первого ребра 651.
[00097] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 может быть выполнено с возможностью генерирования атрибутов для множества промежуточных точек вдоль первого ребра 651. Например, электронное устройство 210 может определять набор промежуточных точек между соответствующей парой узлов и вдоль первого ребра 651 и может генерировать атрибуты для соответствующих одних из набора промежуточных точек первого ребра 651.
[00098] Атрибуты, связанные с данным ребром и/или соответствующей промежуточной точкой вдоль данного ребра, могут включать статические атрибуты и динамические атрибуты. По меньшей мере в некоторых вариантах осуществления настоящей технологии атрибуты включают в себя, но не ограничиваются:
- расстояние данного ребра или его промежуточной точки от одного или более статических объектов (ям, камней на дороге, упавших деревьев, дорожных конусов, бордюров);
- расстояние данного ребра или его промежуточной точки до одного или более динамических объектов: других автомобилей, мотоциклистов, велосипедистов, пешеходов (идущих как по дороге, так и по тротуару);
- расстояние данного ребра или его промежуточной точки от центра полосы движения;
- кривизна части участка дороги, соответствующего данному ребру или его промежуточной точке;
- положение руля для данного ребра или его промежуточной точки;
- скорость и ускорение транспортного средства для данного ребра или его промежуточной точки;
- установленное законом ограничение скорости для данного ребра или его промежуточной точки;
- физическое предельное значение одного или более параметров транспортного средства для данного ребра или его промежуточной точки;
- прогнозируемое количество времени для движения по данному ребру; и
- другие свойства, основанные на правилах дорожного движения (пересекает ли данное ребро сплошную линию).
[00099] Независимо от типов генерируемых атрибутов электронное устройство 210 выполнено с возможностью генерирования данных 671 ребра, содержащих атрибуты, сгенерированные для первого ребра 651 (и/или соответствующего набора промежуточных положений).
[000100] Продолжая проиллюстрированный пример итеративного процесса генерирования, следует также предположить, что в ранжированном списке ребер 550 второе ребро 653, третье ребро 654 и ребро 430 ранжируются после первого ребра 651 в этом порядке. Таким образом, с помощью того же маркера, что и для первой итерации 601, электронное устройство 210 может быть выполнено с возможностью генерирования данных 672 ребра для второго ребра 652 во время второй итерации 602, данных 673 ребра для третьей ребра 654 во время третьей итерации 603, и данных 674 ребра для ребра 430 во время четвертой итерации 604 в этом порядке.
[000101] Продолжая проиллюстрированный пример, следует предположить, что электронное устройство 210 итеративно сгенерировало данные ребра для ребер 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664 аналогично тому, как электронное устройство 210 выполнено с возможностью генерировать данные ребра для соответствующих ребер из первого ребра, второй ребра, третьей ребра и ребра 430.
[000102] Электронное устройство 210 может быть выполнено с возможностью выполнения ряда таких итераций при проверке того, было ли выполнено условие остановки во время каждой соответствующей итерации. Например, предположим, что электронное устройство 210 во время i-й итерации699 генерирует данные 675 ребра для ребра 662. Можно сказать, что во время i-йитерации 699 электронное устройство 210 добавляет ребро 662 к текущему количеству ребер второй структуры 680 графа.
[000103] Электронное устройство 210 может быть выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением, выраженным, например, в терминах по меньшей мере одного из (i) максимального общего количества ребер, которое должно быть включено в структуру 680 графа и (ii) максимальное общее количество промежуточных точек, которые должны быть покрыты ребрами в структуре 680 графа.
[000104] Например, предположим, что, как только электронное устройство 210 добавляет ребро 662 к текущему количеству ребер структуры 680 графа, текущее количество ребер оказывается ниже заранее определенного предельного значения. В таком случае электронное устройство 210 может продолжить другую итерацию и сгенерировать данные ребра для следующего ребра с наилучшим ранжированием в ранжированном списке 550 ребер. Однако, если текущее количество ребер равно или превышает заранее определенный предел, электронное устройство 210 может остановить процесс генерирования структуры 680 графа.
,
[000105] Следует отметить, что ранжированный порядок ребер в неограничивающем примере, проиллюстрированном на фиг. 6, является только одним возможным примером порядка, в котором ребра могут быть ранжированы электронным устройством 210. Порядок ранжирования ребер данной предварительной структуры графа может зависеть, среди прочегоот конкретных реализаций настоящей технологии. В одном другом неограничивающем примере ранжированный порядок ребер может включать в себя наверху ребра данной предварительной структуры графа, которые находятся ближе всего к центру полосы движения, в которой в настоящее время работает транспортное средство 220, а затем периферийные ребра данной предварительной структуры графа. Продвижение периферийных ребер в ранжированном списке может позволить увеличить площадь участка дороги, покрытого данной второй структурой графа, поскольку их продвижение увеличивает вероятность того, что они будут выбраны во время итеративного процесса генерирования.
[000106] По меньшей мере в некоторых вариантах осуществления настоящей технологии электронное устройство 210 также может быть выполнено с возможностью учета «связности» между ребрами, которые итеративно выбираются из ранжированного порядка ребер. Например, на данной итерации электронное устройство 210 может быть выполнено с возможностью выбора следующего ребра с самым высоким рейтингом из ранжированного списка ребер (для генерирования соответствующих атрибутов) и которое также соединено по меньшей мере с одним другим ребром, которое уже было выбрано электронным устройством 210 во время предыдущей итерации. В некоторых вариантах осуществления, если следующее ребро с самым высоким рейтингом в ранжированном списке ребер не соединено с каким-либо другим ребром, которое уже было выбрано, электронное устройство 210 может «пропустить» это ребро и может проверить, соединяется ли второе следующее ребро с самым высоким рейтингом в ранжированном списке ребер с любым другим ребром, которое уже было выбрано. Такое различение ребер в ранжированном порядке ребер может гарантировать, что окончательная структура графа, полученная в результате итеративного процесса генерирования, будет единой связанной структурой графа, то есть каждое ребро данной второй структуры графа соединено по меньшей мере с одним другим ребром данной второй структуры графа.
[000107] Как упомянуто выше, электронное устройство 210 может использовать вторую структуру 680 графа для управления транспортным средством 220 на участке дороги. С этой целью электронное устройство 210 может генерировать «путь» для транспортного средства 220 на участке дороги, который представляет соответствующую последовательность ребер во второй структуре 680 графа.
[000108] Вообще говоря, электронное устройство 210 выполнено с возможностью генерирования одного или более потенциальных путей, по которым транспортное средство 220 может следовать на участке дороги. Эти пути также могут быть ранжированы между собой на основе общей стоимости, связанной с соответствующей последовательностью ребер. Например, критерии стоимости ребер могут применяться к атрибутам соответствующих ребер в данной последовательности для определения в некотором смысле общей «стоимости» для последовательности ребер. Электронное устройство 210 может ранжировать пути на основе того, насколько затратной является соответствующая последовательность ребер.
[000109] Со ссылкой на фиг. 7 изображено представление 700 того, как электронное устройство 210 может быть выполнено с возможностью генерирования первого пути 710 и второго пути 720. Электронное устройство 210 может использовать ребра 651, 652, 653 и 654 для генерирования первого пути 710 и ребра 651, 663, 659 и 662 для генерирования второго пути 720. Электронное устройство 210 может выбрать данный путь из первого пути 710 и второго пути 720, причем по данному пути должно следовать транспортное средство 220 во время работы на участке 350 дороги.
[000110] С этой целью электронное устройство 210 может применять критерии стоимости ребра к данным ребра, связанным с ребрами соответствующей последовательности ребер, и использовать общую стоимость для соответствующей последовательности ребер, оценку ранжирования для выбора пути, по которому будет следовать транспортное средство 220 на участке 350 дороги.
[000111] Предположим, что электронное устройство 210 выбирает второй путь 720 как путь, по которому должно следовать транспортное средство 220. Электронное устройство 210 может использовать атрибуты соответствующей последовательности ребер для генерирования траектории для транспортного средства 220, которое следует по второму пути 720. Это означает, что электронное устройство 210 может быть выполнено с возможностью генерирования данных о траектории для управления транспортным средством 220 на участке 350 дороги на основе данных ребер, связанных с последовательностью ребер 651, 663, 659 и 662, так что транспортное средство 220 следует по второму пути 720 на участке 350 дороги. Электронное устройство 210 также может предписывать работу транспортного средства 220 в соответствии с определенной таким образом траекторией на участке 350 дороги.
,
[000112] Следует отметить, что электронное устройство 210 может быть выполнено с возможностью периодического генерирования вторых структур графов в соответствующие моменты времени во время работы транспортного средства 220 аналогично тому, как электронное устройство 210 генерирует вторую структуру 680 графа. Например, со ссылкой на фиг. 8 изображено представление 800 первого цикла 810 планирования и второго цикла 820 планирования. Каждый цикл планирования соответствует так называемому «тику» («такту»), во время которого электронное устройство 210 выполнено с возможностьюсреди прочего, генерировать данную предварительную структуру графа, а затем соответствующую вторую структуру графа для управления транспортным средством 220, и до следующего тика выполняется электронным устройством 210.
[000113] Первый цикл 810 планирования может быть инициирован в момент 801, в течение которого электронным устройством 210 генерируется вторая структура 830 графа. Во время первого цикла 810 планирования электронное устройство 210 может использовать вторую структуру 830 графа для управления транспортным средством 220. Точно так же второй цикл 820 планирования может быть инициирован в момент 802, в течение которого электронным устройством 210 генерируется (новая) вторая структура 840 графа. Во время второго цикла 820 планирования электронное устройство 210 может использовать структуру 840 второго графа для управления транспортным средством 220. Такая циклическая генерация вторых структур графов может выполняться в заранее определенные интервалы времени во время работы транспортного средства 220.
[000114] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 выполнено с возможностью выполнения способа 900, который схематично проиллюстрирован на Фиг. 9. Различные этапы способа 900 теперь будут обсуждаться более подробно.
ЭТАП 902: генерирование первой структуры графа, имеющей узлы и ребра
[000115] Способ 900 начинается на этапе 900 с электронным устройством 210, выполненным с возможностью генерирования первой структуры графа, имеющей узлы и ребра. Можно сказать, что первая структура графа - это предварительная структура графа, сгенерированная электронным устройством 210. Например, электронное устройство 210 может быть выполнено с возможностью генерирования первой структуры 450 графа (см. Фиг. 4).
[000116] Данный узел в первой структуре графа связан с соответствующим потенциальным положением SDC на участке дороги, и данное ребро представляет переход SDC между потенциальными положениями соответствующей пары узлов.
ЭТАП 904: ранжирование ребер на основе логики приоритета в ранжированный список ребер
[000117] Способ 900 продолжается до этапа 904 с электронным устройством 210, выполненным с возможностью ранжирования ребер первой структуры графа в ранжированный список ребер, указывающий порядок приоритета переходов между соответствующими потенциальными положениями транспортного средства 220 для управления транспортным средством 220 на участке 350 дороги. Например, электронное устройство 210 может ранжировать ребра первой структуры 450 графа в ранжированный список ребер 550.
[000118] В некоторых вариантах осуществления настоящей технологии, как часть этапа 904, электронное устройство 210 может быть выполнено с возможностью определения данной ранжированной оценки для соответствующего ребра на основе взвешенной комбинации заранее определенных критериев приоритета. Заранее определенные критерии приоритета, включают в себя по меньшей мере одно из следующего: позиционное смещение данного ребра от центра полосы движения, длина данного ребра, расстояние между данным ребром и текущим положением транспортного средства, связь ребра с одной из текущей полосы движения и целевой полосы движения, кривизны участка дороги, соответствующего данному ребру, текущая скорость транспортного средства и допустимое ограничение скорости на этом участке дороги.
[000119] В дополнительных вариантах осуществления настоящей технологии, как часть этапа 904, электронное устройство 210 может выполнять MLA, обученное генерировать прогнозируемую оценку приоритета для данного ребра на основе множества заранее определенных критериев приоритета, и при этом ребра могут быть ранжированы на основе соответствующих прогнозируемых оценок приоритета.
ЭТАП 906: генерирование второй структуры графа (i) путем итеративного генерирования атрибутов для соответствующих одних из ранжированного списка ребер, начиная с ребра с наивысшим приоритетом в ранжированном списке ребер, и (ii) до достижения заранее определенного предельного значения.
[000120] Способ 900 переходит к этапу 906 с электронным устройством 210, выполненным с возможностью генерирования второй структуры графа путем итеративного генерирования атрибутов для соответствующих одних из ранжированного списка ребер, начиная с ребра с наивысшим приоритетом в ранжированном списке ребер и до достижения заранее определенного предельного значения. Вторая структура графа имеет набор ребер из первой структуры графа, для которых генерируются атрибуты.
[000121] Следует отметить, что заранее определенное предельное значение указывает на общее количество ребер, которые должны быть включены во вторую структуру графа. В некоторых вариантах осуществления заранее определенным предельным значением может быть общее количество ребер, которые должны быть включены во вторую структуру графа. В других вариантах осуществления заранее определенное предельное значение может представлять собой общее количество промежуточных точек вдоль ребер, для которых должны быть определены атрибуты.
[000122] По меньшей мере в некоторых вариантах осуществления атрибуты, сгенерированные для данного ребра, могут включать в себя расстояние данного ребра от одного или более статических объектов на участке дороги и расстояние данного ребра от одного или более динамических объектов на участке дороги.
[000123] Можно сказать, что электронное устройство 210 может быть выполнено с возможностью выполнения итеративного процесса генерирования второй структуры графа. Например, как часть этапа 906, электронное устройство 210 может быть выполнено с возможностью выполнения первой итерации и второй итерации итеративного процесса генерирования второй структуры графа. Во время первой итерации электронное устройство 210 может быть выполнено с возможностью генерирования атрибутов для первого ребра в ранжированном списке ребер. Это первое ребро добавляется к текущему количеству ребер, которые в настоящее время включены во вторую структуру графа. Во время первой итерации электронное устройство 210 также может быть выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением.
[000124] В ответ на то, что текущее количество ребер ниже заранее определенного предельного значения, электронное устройство 210 может запустить вторую итерацию. Во время второй итерации электронное устройство 210 может быть выполнено с возможностью генерирования атрибутов для второго ребра в ранжированном списке ребер, причем второе ребро ранжируется сразу после первого ребра в ранжированном списке ребер. Второе ребро добавляется к текущему количеству ребер, включенных в данный момент во вторую структуру графа. Во время второй итерации электронное устройство 210 также может быть выполнено с возможностью сравнения текущего количества ребер с заранее определенным предельным значением. В ответ на то, что текущее количество ребер равно заранее определенному предельному значению, электронное устройство 210 может быть выполнено с возможностью останавливать генерирование второй структуры графа.
ЭТАП 908: предписывание работы SDC на участке дороги с использованием второй структуры графа
[000125] Способ 900 переходит к этапу 908 с электронным устройством 210, выполненным с возможностью предписывать работу транспортного средства 220 на участке дороги с использованием второй структуры графа. В некоторых вариантах осуществления на этапе 908 электронное устройство 210 может быть выполнено с возможностью генерирования потенциального пути для транспортного средства 220 на участке дороги, который представляет соответствующую последовательность ребер во второй структуре графа. Электронное устройство 210 может также генерировать потенциальную траекторию для транспортного средства 220 на участке дороги, используя атрибуты ребер в соответствующей последовательности ребер, и предписывать работу транспортного средства 220 для движения по участку дороги в соответствии с потенциальной траекторией.
[000126] В некоторых вариантах осуществления электронное устройство 210 может быть выполнено с возможностью периодического генерирования вторых структур графов во время работы транспортного средства 220. Например, электронное устройство 210 может быть выполнено с возможностью генерирования соответствующей второй структуры графа для соответствующих циклов планирования транспортного средства 220.
[000127] Модификации и улучшения вышеописанных реализаций настоящей технологии могут стать очевидными для специалистов в данной области техники. Предшествующее описание предназначено для того, чтобы быть примерным, а не ограничивающим. Поэтому предполагается, что объем настоящей технологии ограничен лишь объемом прилагаемой формулы изобретения.
[000128] Хотя вышеописанные реализации были описаны и показаны со ссылкой на конкретные этапы, выполняемые в определенном порядке, следует понимать, что некоторые из этих этапов могут быть объединены, разделены на части или переупорядочены без отклонения от принципов настоящая технология. Соответственно, порядок и группировка упомянутых этапов ограничениями настоящей технологии не являются.