Способ и система для управления работой самоуправляемого автомобиля Российский патент 2022 года по МПК G01C21/34 

Область техники, к которой относится изобретение

[1] Настоящая технология относится к самоуправляемым автомобилям и, в частности, к способу и системе для управления работой самоуправляемых автомобилей.

Уровень техники

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

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

[4] Некоторые из наиболее передовых систем обеспечивают полностью автономное движение транспортного средства без непосредственного участия оператора (т.е. водителя) в управлении так называемым самоуправляемым автомобилем (SDC, Self-Driving Car). Автомобиль SDC содержит компьютерные системы, способные ускорять, замедлять, останавливать, перестраивать в другой ряд и самостоятельно парковать автомобиль SDC.

[5] Одна из технических проблем, возникающих при реализации вышеупомянутых компьютерных систем, заключается в планировании работы автомобиля SDC при его движении по маршруту.

Раскрытие изобретения

[6] Целью настоящего изобретения является устранение по меньшей мере некоторых недостатков известных решений. Варианты осуществления настоящей технологии способны обеспечить и/или расширить арсенал подходов к способам достижения целей в настоящей технологии.

[7] Автомобиль SDC может управляться с целью перемещения из пункта A в пункт Б. Например, электронное устройство может управлять работой автомобиля SDC так, чтобы он двигался из пункта A отправления в пункт Б назначения. С этой целью электронное устройство способно определять навигационный маршрут, который автомобиль SDC может использовать для движения из пункта A в пункт Б, а также может управлять работой автомобиля SDC для выполнения такого движения.

[8] Разработчики настоящей технологии реализовали способы и системы для снижения вероятности перестроений в другой ряд во время работы автомобиля SDC при его движении по навигационному маршруту. Следует отметить, что для движения по маршруту (из пункта A отправления в пункт Б назначения) может быть доступно большое количество альтернативных вариантов полосы движения и некоторые из них могут предусматривать большее или меньшее количество перестроений в другой ряд.

[9] Разработчики настоящей технологии также реализовали способы и системы, способные использовать две модели оценки для оценивания альтернативного варианта полосы движения, который должен использовать автомобиль SDC для уменьшения количества перестроений в другой ряд. В по меньшей мере некоторых вариантах осуществления настоящей технологии можно сказать, что электронное устройство может использовать первую «глобальную модель оценки» для определения степени желательности переходов между полосами движения, которые автомобиль SDC может потенциально выполнять при движении по навигационному маршруту, а затем использовать «локальную модель оценки» для корректировки степени желательности некоторых переходов между полосами движения на основе текущей информации об окрестности автомобиля SDC так, чтобы уменьшить вероятность выполнения автомобилем SDC перестроений в другой ряд и/или уменьшить общее количество перестроений в другой ряд, выполняемых автомобилем SDC при движении по маршруту.

[10] В по меньшей мере некоторых вариантах осуществления изобретения разработчики настоящей технологии реализовали систему, содержащую модуль планирования полосы движения, планировщик маршрута, модуль правил дорожного движения, модуль восприятия, модуль планирования траектории и набор датчиков. Эта система может быть реализована в сочетании с автомобилем SDC. Модуль планирования полосы движения может содержать различные субмодули, такие как разделитель полос движения, глобальная модель оценки, запоминающее устройство и/или база данных, хранящая графовую структуру, вторая модель оценки и т.д.

[11] Набор датчиков способен непрерывно получать данные, представляющие окрестность автомобиля SDC, включая данные о текущем местоположении автомобиля SDC, состояние занятости соседней полосы движения, данные о статических и динамических препятствиях, их соответствующие местоположения на соседних полосах, геометрические размеры и кинематические характеристики и т.п., но не ограничиваясь ими. Данные, сформированные набором датчиков, могут быть предоставлены модулю восприятия. Модуль восприятия также может быть связан с модулем планировщика полосы движения. Модуль планировщика полосы движения может получать данные об окрестности и окружающей обстановке для их дальнейшей обработки.

[12] Следует отметить, что в некоторых вариантах осуществления изобретения планировщику маршрута может быть доступна схема дорог. Планировщик маршрута может формировать навигационный маршрут, начинающийся в пункте A отправления и заканчивающийся в пункте Б назначения. Следует также отметить, что планировщик маршрута может формировать так называемую информацию «уровня маршрута», указывающую на одну или несколько дорог, которые автомобиль SDC должен использовать для прибытия в пункт Б назначения из пункта A отправления.

[13] Предполагается, что модулю правил дорожного движения могут быть доступны правила дорожного движения для одной или нескольких дорог из навигационного маршрута, включая виды разделителей полос движения, количество полос движения, направление движения по соответствующим полосам движения и т.д. Правила дорожного движения могут использоваться модулем разделения полос движения для разделения маршрута на полосы движения согласно правилам дорожного движения. Следует отметить, что модуль разделения полос движения может определять так называемую информацию «уровня полосы движения» о навигационном маршруте, указывающую на наличие одной или нескольких полос движения на соответствующей дороге из числа одной или нескольких дорог навигационного маршрута. Например, модуль разделения полос движения способен связывать дорогу из маршрута с ее полосой (или полосами) движения.

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

[15] В некоторых вариантах осуществления изобретения система также может использовать вторую модель оценки. Как более подробно описано ниже, вторая модель оценки может использоваться, чтобы различать переходы между полосами движения различных видов и корректировать стоимость переходов между полосами движения по меньшей мере одного вида. Следует отметить, что вторая модель оценки может использоваться во время работы автомобиля SDC. Следовательно, предполагается, что вторая модель оценки способна различать переходы между полосами движения различных видов, по меньшей мере частично, на основе текущей информации об окрестности автомобиля SDC.

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

[17] Система может использовать первую модель оценки для назначения значений стоимости ребрам графовой структуры, указывающих на степень желательности соответствующих переходов, как описано выше. Предполагается, что система может использовать первую модель оценки перед началом работы на маршруте. Таким образом, можно сказать, что системе для использования первой модели оценки может не требоваться информация об окрестности автомобиля SDC.

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

[19] Предполагается, что система может использовать вторую модель оценки в реальном времени в процессе работы автомобиля SDC на навигационном маршруте. Как более подробно описано ниже, система может получать данные, представляющие «пути полосы движения», доступные для автомобиля SDC в текущий момент времени (как часть информации, указывающей на окрестность автомобиля SDC), при этом путь полосы движения указывает на участок полосы движения, начинающийся от текущего местоположения, по которому автомобиль SDC может следовать без перестроения в другой ряд. Также следует отметить, что вторая модель оценки способна различать ребра на структуре графа, соответствующие следованию по пути полосы движения, и ребра на структуре графа, соответствующие съезду с пути полосы движения. Соответственно, вторая модель оценки может быть использована для назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения.

[20] Согласно первому аспекту настоящей технологии, реализован способ управления работой автомобиля SDC. Автомобиль SDC связан с электронным устройством. Электронному устройству доступны данные, представляющие пункт отправления и пункт назначения. Способ выполняется электронным устройством. Способ включает в себя определение электронным устройством навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения, указывающей на по меньшей мере одну дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения. По меньшей мере одна дорога связана с правилами дорожного движения. Способ включает в себя использование электронным устройством правил дорожного движения для определения информации уровня полосы движения, указывающей на наличие по меньшей мере одной полосы движения на каждой дороге из числа по меньшей мере одной дороги. Способ включает в себя использование электронным устройством информации уровня полосы движения для формирования графовой структуры, содержащей множество вершин и множество ребер. Вершина связана с соответствующим потенциальным местоположением автомобиля SDC на полосе движения дороги из числа по меньшей мере одной дороги. Множество вершин содержит вершину пункта отправления, связанную с пунктом отправления, и вершину пункта назначения, связанную с пунктом назначения. Ребро соединяет пару вершин в графовой структуре и указывает на переход между потенциальным местоположением, связанным с первой вершиной в этой паре вершин, и потенциальным местоположением, связанным со второй вершиной в этой паре вершин. Способ включает в себя применение электронным устройством глобальной модели оценки в отношении графовой структуры. Глобальная модель оценки связана с первым набором критериев для назначения значений стоимости соответствующим ребрам. Стоимость, связанная с ребром, указывает на степень желательности соответствующего перехода согласно первому набору критериев. Способ включает в себя определение электронным устройством глобальной оценки штрафа для каждой вершины в графовой структуре. Глобальная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Глобальная оценка штрафа указывает на наименьшую глобальную стоимость движения автомобиля SDC в пункт назначения, если автомобиль SDC оказывается в потенциальном местоположении этой вершины. Способ включает в себя сохранение электронным устройством ребер в графовой структуре в сочетании с соответствующими значениями стоимости и вершин в графовой структуре в сочетании с соответствующими глобальными оценками штрафа. Способ включает в себя получение электронным устройством по меньшей мере одного пути полосы движения для текущего местоположения в момент времени в процессе работы автомобиля SDC, когда автомобиль SDC находится в текущем местоположении между пунктом отправления и пунктом назначения. По меньшей мере один путь полосы движения указывает на участок полосы движения без перестроения в другой ряд, начинающийся от текущего местоположения. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения. Последовательность вершин (а) начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению автомобиля SDC, и (б) заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующим концу участка полосы движения. Способ включает в себя применение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения локальной модели оценки в отношении графовой структуры. Локальная модель оценки предназначена для назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения, для последовательности вершин, и для определения таким образом локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, для этой последовательности вершин. Ребра, соответствующие съезду с пути полосы движения, соединяют последовательность вершин с другими вершинами в графовой структуре за исключением этой последовательности вершин. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения локально скорректированной оценки штрафа для каждой вершины в последовательности вершин. Локально скорректированная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения оценки этого пути полосы движения. Оценка пути полосы движения представляет собой локально скорректированную оценку штрафа для текущей вершины в последовательности вершин на этом пути полосы движения. Оценка пути полосы движения указывает на стоимость движения автомобиля SDC по участку полосы движения на этом пути полосы движения без перестроения в другой ряд.

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

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

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

[24] В некоторых вариантах осуществления способа первый набор критериев указывает на то, что переход, соответствующий сохранению автомобилем SDC своего ряда движения, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC перестроения в другой ряд.

[25] В некоторых вариантах осуществления способа первый набор критериев указывает на то, что переход, соответствующий выполнению автомобилем SDC медленного перестроения в другой ряд, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC быстрого перестроения в другой ряд.

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

[27] В некоторых вариантах осуществления способа первый путь полосы движения из числа по меньшей мере одного пути полосы движения связан с первой последовательностью вершин, а второй путь полосы движения из числа по меньшей мере одного пути полосы движения связан со второй последовательностью вершин. Первая и вторая последовательности вершин содержат по меньшей мере одну общую вершину в графовой структуре, а ребра, соответствующие съезду с пути полосы движения, для по меньшей мере одной общей вершины в первой последовательности вершин на первом пути полосы движения отличаются от ребер, соответствующих съезду с пути полосы движения, для по меньшей мере одной общей вершины во второй последовательности вершин на втором пути полосы движения.

[28] В некоторых вариантах осуществления способ дополнительно включает в себя определение электронным устройством оценок путей полосы движения для путей полосы движения, полученных в различные моменты времени в процессе работы автомобиля SDC.

[29] Согласно второму аспекту настоящей технологии реализовано электронное устройство для управления работой автомобиля SDC. Автомобиль SDC связан с электронным устройством. Электронному устройству доступны данные, представляющие пункт отправления и пункт назначения. Электронное устройство способно определять навигационную информацию уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения. Навигационная информация уровня маршрута указывает на по меньшей мере одну связанную с правилами дорожного движения дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения. Электронное устройство способно использовать правила дорожного движения для определения информации уровня полосы движения. Информация уровня полосы движения указывает на наличие по меньшей мере одной полосы движения на каждой дороге из числа по меньшей мере одной дороги. Электронное устройство способно использовать информацию уровня полосы движения для формирования графовой структуры. Графовая структура содержит множество вершин и множество ребер. Вершина связана с потенциальным местоположением автомобиля SDC на полосе движения дороги из числа по меньшей мере одной дороги. Множество вершин содержит вершину пункта отправления, связанную с пунктом отправления, и вершину пункта назначения, связанную с пунктом назначения. Ребро соединяет пару вершин в графовой структуре. Ребро указывает на переход между потенциальным местоположением, связанным с первой вершиной в этой паре вершин, и потенциальным местоположением, связанным со второй вершиной в этой паре вершин. Электронное устройство способно применять глобальную модель оценки в отношении графовой структуры. Глобальная модель оценки связана с первым набором критериев для назначения значений стоимости соответствующим ребрам. Стоимость, связанная с ребром, указывает на степень желательности соответствующего перехода согласно первому набору критериев. Электронное устройство способно определять глобальную оценку штрафа для каждой вершины в графовой структуре. Глобальная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Глобальная оценка штрафа указывает на наименьшую глобальную стоимость движения автомобиля SDC в пункт назначения, если автомобиль SDC оказывается в потенциальном местоположении этой вершины. Электронное устройство способно сохранять ребра в графовой структуре в сочетании с соответствующими значениями стоимости и вершины в графовой структуре в сочетании с соответствующими глобальными оценками штрафа. Электронное устройство способно получать по меньшей мере один путь полосы движения для текущего местоположения в момент времени во время работы автомобиля SDC, когда автомобиль SDC находится в текущем местоположении между пунктом отправления и пунктом назначения. По меньшей мере один путь полосы движения указывает на участок полосы движения без перестроения в другой ряд, начинающийся от текущего местоположения. Электронное устройство способно определять для каждого пути из числа по меньшей мере одного пути полосы движения последовательность вершин в графовой структуре, покрываемых соответствующим участком полосы движения на пути полосы движения. Последовательность вершин (а) начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению автомобиля SDC, и (б) заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующим концу участка полосы движения. Электронное устройство способно для каждого пути из числа по меньшей мере одного пути полосы движения применять локальную модель оценки в отношении графовой структуры. Локальная модель оценки предназначена для назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения, для последовательности вершин и для определения таким образом локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, для этой последовательности вершин. Ребра, соответствующие съезду с пути полосы движения, соединяют последовательность вершин с другими вершинами в графовой структуре за исключением этой последовательности вершин. Электронное устройство способно определять для каждого пути из числа по меньшей мере одного пути полосы движения локально скорректированную оценку штрафа для каждой вершины в последовательности вершин. Локально скорректированная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Электронное устройство способно определять для каждого пути из числа по меньшей мере одного пути полосы движения оценку пути полосы движения. Оценка пути полосы движения представляет собой локально скорректированную оценку штрафа для текущей вершины в последовательности вершин на этом пути полосы движения. Оценка пути полосы движения указывает на стоимость движения автомобиля SDC по участку полосы движения на этом пути полосы движения без перестроения в другой ряд.

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

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

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

[33] В некоторых вариантах осуществления электронного устройства первый набор критериев указывает на то, что переход, соответствующий сохранению автомобилем SDC своего ряда движения, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC перестроения в другой ряд.

[34] В некоторых вариантах осуществления электронного устройства первый набор критериев указывает на то, что переход, соответствующий выполнению автомобилем SDC медленного перестроения в другой ряд, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC быстрого перестроения в другой ряд.

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

[36] В некоторых вариантах осуществления электронного устройства первый путь полосы движения из числа по меньшей мере одного пути полосы движения связан с первой последовательностью вершин, а второй путь полосы движения из числа по меньшей мере одного пути полосы движения связан со второй последовательностью вершин. Первая и вторая последовательности вершин содержат по меньшей мере одну общую вершину в графовой структуре. Ребра, соответствующие съезду с пути полосы движения, для по меньшей мере одной общей вершины в первой последовательности вершин на первом пути полосы движения отличаются от ребер, соответствующих съезду с пути полосы движения, для по меньшей мере одной общей вершины во второй последовательности вершин на втором пути полосы движения.

[37] В некоторых вариантах осуществления электронное устройство дополнительно способно определять оценки путей полосы движения для путей полосы движения, полученных в различные моменты времени в процессе работы автомобиля SDC.

[38] Согласно третьему аспекту настоящей технологии реализован способ управления работой автомобиля SDC. Автомобиль SDC связан с электронным устройством. Электронному устройству доступны данные, представляющие пункт отправления и пункт назначения. Способ выполняется электронным устройством. Способ включает в себя определение электронным устройством навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения. Навигационная информация уровня маршрута указывает на по меньшей мере одну дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения. По меньшей мере одна дорога связана с правилами дорожного движения. Способ включает в себя использование электронным устройством правил дорожного движения для определения информации уровня полосы движения, указывающей на наличие по меньшей мере одной полосы движения на каждой дороге из числа по меньшей мере одной дороги. Способ включает в себя использование электронным устройством информации уровня полосы движения для формирования графовой структуры. Графовая структура содержит множество вершин и множество ребер. Вершина связана с потенциальным местоположением автомобиля SDC на полосе движения дороги из числа по меньшей мере одной дороги. Множество вершин содержит вершину пункта отправления, связанную с пунктом отправления, и вершину пункта назначения, связанную с пунктом назначения. Ребро соединяет пару вершин в графовой структуре. Ребро указывает на переход между потенциальным местоположением, связанным с первой вершиной в этой паре вершин, и потенциальным местоположением, связанным со второй вершиной в этой паре вершин. Способ включает в себя применение электронным устройством глобальной модели оценки в отношении графовой структуры. Глобальная модель оценки связана с первым набором критериев для назначения значений стоимости соответствующим ребрам. Стоимость, связанная с ребром, указывает на степень желательности соответствующего перехода согласно первому набору критериев. Способ включает в себя сохранение электронным устройством ребер в графовой структуре в сочетании с соответствующими значениями стоимости. Способ включает в себя получение электронным устройством по меньшей мере одного пути полосы движения для текущего местоположения в момент времени в процессе работы автомобиля SDC, когда автомобиль SDC находится в текущем местоположении между пунктом отправления и пунктом назначения. По меньшей мере один путь полосы движения указывает на участок полосы движения без перестроения в другой ряд, начинающийся от текущего местоположения. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения. Последовательность вершин (а) начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению автомобиля SDC, и (б) заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующим концу участка полосы движения. Способ включает в себя применение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения локальной модели оценки в отношении графовой структуры. Локальная модель оценки предназначена для назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения, для последовательности вершин и для определения таким образом локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, для этой последовательности вершин. Ребра, соответствующие съезду с пути полосы движения, соединяют последовательность вершин с другими вершинами в графовой структуре за исключением этой последовательности вершин. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения локальной оценки штрафа для каждой вершины в последовательности вершин на основе локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, для этой последовательности вершин. Локальная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Способ включает в себя определение электронным устройством для каждого пути из числа по меньшей мере одного пути полосы движения оценки этого пути полосы движения. Оценка пути полосы движения на пути полосы движения представляет собой локальную оценку штрафа для текущей вершины в последовательности вершин на этом пути полосы движения. Оценка пути полосы движения указывает на стоимость движения автомобиля SDC по участку полосы движения на этом пути полосы движения без перестроения в другой ряд.

[39] В контексте настоящего описания термин «сервер» означает компьютерную программу, выполняемую соответствующими аппаратными средствами и способную принимать запросы (например, от клиентских устройств) через сеть и выполнять эти запросы или инициировать их выполнение. Аппаратные средства могут быть реализованы в виде одного физического компьютера или одной компьютерной системы, что не существенно для настоящей технологии. В настоящем контексте выражение «сервер» не означает, что каждая задача (например, принятая команда или запрос) или некоторая определенная задача принимается, выполняется или запускается одним и тем же сервером (т.е. одними и теми же программными и/или аппаратными средствами). Это выражение означает, что любое количество программных средств или аппаратных средств может принимать, отправлять, выполнять или запускать выполнение любой задачи или запроса либо результатов любых задач или запросов. Все эти программные и аппаратные средства могут представлять собой один сервер или несколько серверов, причем оба эти случая подразумеваются в выражении «по меньшей мере один сервер».

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

[41] В контексте настоящего описания термин «клиентское устройство» означает любое компьютерное аппаратное средство, способное выполнять программы, подходящие для решения поставленной задачи. В контексте настоящего описания термин «клиентское устройство» в общем случае связан с пользователем клиентского устройства. Таким образом, некоторые (не имеющие ограничительного характера) примеры клиентских устройств включают в себя персональные компьютеры (настольные, ноутбуки, нетбуки и т.п.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте устройство, функционирующее как клиентское устройство, также может функционировать как сервер для других клиентских устройств. Использование выражения «клиентское устройство» не исключает использования нескольких клиентских устройств для приема, отправки, выполнения или инициирования выполнения любой задачи или запроса либо результатов любых задач или запросов либо шагов любого описанного здесь способа.

[42] В контексте настоящего описания выражение «информация» включает в себя информацию любого рода или вида, допускающую хранение в базе данных. Таким образом, информация включает в себя аудиовизуальные произведения (изображения, фильмы, звукозаписи, презентации и т.д.), данные (данные о местоположении, числовые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, электронные таблицы и т.д., но не ограничивается ими.

[43] В контексте настоящего описания выражение «программный компонент» включает в себя обозначение программного обеспечения (подходящего для определенных аппаратных средств), необходимого и достаточного для выполнения указанной определенной функции или нескольких функций.

[44] В контексте настоящего описания выражение «носитель компьютерной информации» (также называется «носителем информации») означает носители любого рода и вида, включая оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д. Для формирования носителя компьютерной информации может объединяться множество элементов, включая два или более элементов носителя информации одного вида и/или два или более элементов носителя информации различных видов.

[45] В контексте настоящего описания термин «база данных» означает любой структурированный набор данных, независимо от его конкретной структуры, программного обеспечения для управления базой данных или компьютерных аппаратных средств для хранения этих данных, их применения или обеспечения их использования иным способом. База данных может располагаться в тех же аппаратных средствах, где реализован процесс, обеспечивающий хранение или использование информации, хранящейся в базе данных, либо база данных может располагаться в отдельных аппаратных средствах, таких как специализированный сервер или множество серверов.

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

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

[48] Дополнительные и/или альтернативные признаки, аспекты и преимущества вариантов осуществления настоящей технологии содержатся в дальнейшем описании, в приложенных чертежах и в формуле изобретения.

Краткое описание чертежей

[49] Эти и другие признаки, аспекты и преимущества настоящей технологии иллюстрируются в дальнейшем описании, в приложенной формуле изобретения и на следующих чертежах.

[50] На фиг. 1 представлена схема примера компьютерной системы для реализации некоторых вариантов осуществления систем и/или способов согласно настоящей технологии.

[51] На фиг. 2 представлена вычислительная сетевая среда, пригодная для использования с некоторыми вариантами осуществления настоящей технологии.

[52] На фиг. 3 представлена навигационная информация уровня маршрута, которую представленное на фиг. 2 электронное устройство может определять и/или получать согласно некоторым вариантам осуществления настоящей технологии.

[53] На фиг. 4 представлена информация уровня полосы движения, которую представленное на фиг. 2 электронное устройство может определять на основе правил дорожного движения, связанных с навигационной информацией уровня маршрута, согласно некоторым вариантам осуществления настоящей технологии.

[54] На фиг. 5 показана графовая структура, которую представленное на фиг. 2 электронное устройство может формировать и сохранять согласно некоторым вариантам осуществления настоящей технологии.

[55] На фиг. 6 представлены три упрощенные графовые структуры, которые показанное на фиг. 2 электронное устройство может формировать согласно некоторым вариантам осуществления настоящей технологии.

[56] На фиг. 7 представлены три упрощенные графовые структуры, показанные на фиг. 6, с глобальными оценками штрафа, связанными с соответствующими вершинами, согласно некоторым вариантам осуществления настоящей технологии.

[57] На фиг. 8 представлена графовая структура, показанная на фиг. 5, со значениями стоимости, назначенными соответствующим ребрам, и с глобальными оценками штрафа, назначенными соответствующим вершинам, согласно некоторым вариантам осуществления настоящей технологии.

[58] На фиг. 9 представлены первый путь полосы движения и второй путь полосы движения, которые показанное на фиг. 2 электронное устройство может получать во время работы согласно некоторым вариантам осуществления настоящей технологии.

[59] На фиг. 10 представлена первая последовательность вершин на первом пути полосы движения, которую электронное устройство 210 может получать во время работы согласно некоторым вариантам осуществления настоящей технологии.

[60] На фиг. 11 представлена вторая последовательность вершин на втором пути полосы движения, которую электронное устройство 210 может получать во время работы согласно некоторым вариантам осуществления настоящей технологии.

[61] На фиг. 12 представлена третья последовательность вершин для третьего пути полосы движения, которую электронное устройство 210 может получать во время работы согласно некоторым вариантам осуществления настоящей технологии.

[62] На фиг. 13 представлена четвертая последовательность вершин для четвертого пути полосы движения, которую электронное устройство 210 может получать во время работы согласно некоторым вариантам осуществления настоящей технологии.

[63] На фиг. 14 представлены ребра, соответствующие съезду с пути полосы движения и определенные для показанной на фиг. 10 первой последовательности вершин, с соответствующими локально скорректированными оценками штрафа в первой последовательности вершин согласно некоторым вариантам осуществления настоящей технологии.

[64] На фиг. 15 представлены ребра, соответствующие съезду с пути полосы движения и определенные для показанной на фиг. 11 второй последовательности вершин, с соответствующими локально скорректированными оценками штрафа во второй последовательности вершин согласно некоторым вариантам осуществления настоящей технологии.

[65] На фиг. 16 представлены ребра, соответствующие съезду с пути полосы движения и определенные для показанной на фиг. 12 третьей последовательности вершин, с соответствующими локально скорректированными оценками штрафа в третьей последовательности вершин согласно некоторым вариантам осуществления настоящей технологии.

[66] На фиг. 17 представлены ребра, соответствующие съезду с пути полосы движения и определенные для показанной на фиг. 13 четвертой последовательности вершин, с соответствующими локально скорректированными оценками штрафа в четвертой последовательности вершин согласно некоторым вариантам осуществления настоящей технологии.

[67] На фиг. 18 представлена блок-схема способа, выполняемого электронным устройством, показанным на фиг. 2 и управляющим работой показанного на фиг. 2 транспортного средства, согласно некоторым вариантам осуществления изобретения.

Осуществление изобретения

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

[69] Кроме того, чтобы способствовать лучшему пониманию, последующее описание может содержать упрощенные варианты реализации настоящей технологии. Специалистам в данной области должно быть понятно, что другие варианты осуществления настоящей технологии могут быть значительно сложнее.

[70] В некоторых случаях приводятся полезные примеры модификаций настоящей технологии. Они способствуют пониманию, но также не определяют объем или границы настоящей технологии. Представленный перечень модификаций не является исчерпывающим и специалист в данной области может разработать другие модификации в пределах объема настоящей технологии. Кроме того, если в некоторых случаях модификации не описаны, это не означает, что они невозможны и/или что описание содержит единственно возможный вариант реализации того или иного элемента настоящей технологии.

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

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

[73] Функции различных элементов, показанных на чертежах, включая любой функциональный блок, обозначенный как «процессор», могут быть реализованы с использованием специализированных аппаратных средств, а также аппаратных средств, способных выполнять соответствующее программное обеспечение. Если используется процессор, эти функции могут выполняться одним выделенным процессором, одним совместно используемым процессором или множеством отдельных процессоров, некоторые из которых могут использоваться совместно.

[74] Кроме того, явное использование термина «процессор» или «контроллер» не должно трактоваться как указание исключительно на аппаратные средства, способные выполнять программное обеспечение, и может подразумевать, помимо прочего, аппаратные средства цифрового сигнального процессора (DSP), сетевой процессор, специализированную интегральную схему (ASIC), программируемую вентильную матрицу (FPGA), ПЗУ для хранения программного обеспечения, ОЗУ и энергонезависимое запоминающее устройство. Также могут подразумеваться другие аппаратные средства, общего назначения и/или заказные.

[75] Программные модули или просто модули, реализация которых предполагается в виде программных средств, могут быть представлены здесь как любое сочетание элементов блок-схемы или других элементов, указывающих на выполнение шагов процесса и/или содержащих его текстовое описание. Такие модули могут выполняться аппаратными средствами, показанными явно или подразумеваемыми.

[76] Далее с учетом вышеизложенных принципов рассмотрены некоторые не имеющие ограничительного характера примеры, иллюстрирующие различные варианты реализации аспектов настоящей технологии.

Компьютерная система

[77] На фиг. 1 представлена компьютерная система 100, пригодная для использования с некоторыми вариантами осуществления настоящей технологии и содержащая различные элементы аппаратных средств, включая один или несколько одно- или многоядерных процессоров, совместно представленных процессором 110, твердотельный накопитель 120, память 130, которая может представлять собой ОЗУ или память любого другого вида. Связь между различными элементами компьютерной системы 100 может осуществляться через одну или несколько внутренних и/или внешних шин (не показаны) (таких как шина PCI, шина USB, шина FireWire стандарта IEEE 1394, шина SCSI, шина Serial-ATA и т.д.), с которыми различные аппаратные элементы соединены электронными средствами.

[78] В по меньшей мере некоторых вариантах осуществления настоящей технологии твердотельный накопитель 120 хранит программные команды, пригодные для загрузки в память 130 и исполнения процессором 110 с целью определения наличия объекта. Например, программные команды могут входить в состав управляющего приложения транспортного средства, выполняемого процессором 110.

[79] В по меньшей мере некоторых вариантах осуществления настоящей технологии предполагается, что компьютерная система 100 может содержать дополнительные и/или опциональные элементы, такие как модуль 140 передачи данных по сети для соединения через сеть связи (например, через сеть 240 связи, представленную на фиг. 2) с другими электронными устройствами и/или серверами, модули определения местоположения (не показаны) и т.п.

Компьютерная сетевая среда

[80] На фиг. 2 представлена компьютерная сетевая среда 200, пригодная для использования с некоторыми вариантами осуществления систем и/или способов согласно настоящей технологии. Компьютерная сетевая среда 200 содержит электронное устройство 210, связанное с транспортным средством 220 или с пользователем (не показан), который может управлять транспортным средством 220, сервер 235, соединенный с электронным устройством 210 через сеть 240 связи (например, через сеть Интернет и т.п., как более подробно описано ниже). Компьютерная сетевая среда 200 также может содержать спутник системы GPS (не показан), передающий сигнал GPS электронному устройству 210 и/или принимающий сигнал GPS от него. Должно быть понятно, что настоящая технология не ограничивается системой GPS и может использовать технологию определения местоположения, отличную от системы GPS. Следует отметить, что спутник GPS может вообще отсутствовать.

[81] Транспортное средство 220, с которым связано электронное устройство 210, может представлять собой любое транспортное средство для отдыха или транспортировки грузов, такое как личный или служебный автомобиль, грузовой автомобиль, мотоцикл и т.д. Транспортное средство может управляться пользователем или представлять собой самоуправляемое транспортное средство. Следует отметить, что не накладывается каких-либо ограничений на конкретные параметры транспортного средства 220, такие как производитель транспортного средства, модель транспортного средства, год выпуска транспортного средства, масса транспортного средства, размеры транспортного средства, распределение массы транспортного средства, площадь поверхности транспортного средства, высота транспортного средства, вид трансмиссии (например, привод на два или четыре колеса), вид шин, тормозная система, топливная система, пробег, идентификационный номер транспортного средства, рабочий объем двигателя и т.д.

[82] На реализацию электронного устройства 210 также не накладывается каких-либо ограничений. Например, электронное устройство 210 может быть реализовано в виде блока управления двигателем транспортного средства, центрального процессора транспортного средства, автомобильного навигатора (например, TomTom™, Garmin™), планшета, персонального компьютера, встроенного в транспортное средство 220, и т.д. Следует отметить, что электронное устройство 210 может быть связано или не связано с транспортным средством 220 постоянным образом. Дополнительно или в качестве альтернативы, электронное устройство 210 может быть реализовано в устройстве беспроводной связи, таком как мобильный телефон (например, смартфон или радиотелефон). В некоторых вариантах осуществления изобретения электронное устройство 210 содержит дисплей 270.

[83] Электронное устройство 210 может содержать некоторые или все элементы компьютерной системы 100, представленной на фиг. 1. В некоторых вариантах осуществления изобретения электронное устройство 210 представляет собой бортовое компьютерное устройство и содержит процессор 110, твердотельный накопитель 120 и память 130. Иными словами, электронное устройство 210 содержит аппаратные средства и/или прикладное программное обеспечение и/или встроенное программное обеспечение либо их сочетание для определения траектории транспортного средства 220 на участке дороги с учетом препятствий на нем, как более подробно описано ниже.

Система датчиков

[84] В не имеющих ограничительного характера вариантах осуществления настоящей технологии электронное устройство 210 содержит систему 230 датчиков или имеет доступ к ней. Согласно этим вариантам осуществления изобретения, система 230 датчиков может содержать множество датчиков, обеспечивающих различные варианты реализации настоящей технологии. Примеры множества датчиков в числе прочего включают камеры, лидарные датчики, радиолокационные датчики и т.д. Система 230 датчиков функционально связана с процессором 110 для передачи зафиксированной информации в процессор 110 с целью ее обработки, как более подробно описано ниже.

[85] Система 230 датчиков может быть установлена с внутренней стороны в верхней части ветрового стекла транспортного средства 220. В пределах объема настоящего изобретения также возможны другие положения, включая заднее окно, боковые окна, передний капот, крышу, переднюю решетку или передний бампер транспортного средства 220. В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии система 230 датчиков может быть установлена в специальном кожухе (не показан), установленном сверху транспортного средства 220.

[86] Кроме того, пространственное расположение системы 230 датчиков может учитывать ее техническую конфигурацию, конструкцию кожуха, погодные условия (такие как частые дожди, снег и другие элементы) региона, где должно эксплуатироваться транспортное средство 220, и т.п.

[87] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии система 230 датчиков может содержать датчик, способный фиксировать изображение окружающей зоны 260. В этой связи система 230 датчиков может представлять собой камеру или множество камер (отдельно не показаны).

[88] На реализацию камеры не накладывается каких-либо особых ограничений. Например, в некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии камера может быть реализована в виде черно-белой камеры с разрешением, достаточным для обнаружения объектов на заранее заданных расстояниях приблизительно до 30 м (тем не менее, без выхода за границы настоящего изобретения могут использоваться камеры с другими значениями разрешения и дальности действия).

[89] В некоторых вариантах осуществления настоящей технологии камера (или одна или несколько камер, в виде которых реализована система 230 датчиков) способна фиксировать заранее заданную часть окружающей зоны 260 вблизи транспортного средства 220. В некоторых вариантах осуществления настоящей технологии камера способна фиксировать изображение (или последовательность изображений), соответствующее приблизительно 90 градусам расположенной вблизи транспортного средства 220 окружающей зоны 260 вдоль траектории движения транспортного средства 220.

[90] В других вариантах осуществления настоящей технологии камера способна фиксировать изображение (или последовательность изображений), соответствующее приблизительно 180 градусам расположенной вблизи транспортного средства 220 окружающей зоны 260 вдоль траектории движения транспортного средства 220. В других вариантах осуществления настоящей технологии камера способна фиксировать изображение (или последовательность изображений), соответствующее приблизительно 360 градусам расположенной вблизи транспортного средства 220 окружающей зоны 260 вдоль траектории движения транспортного средства 220 (иными словами, всю окружающую зону вблизи транспортного средства 220).

[91] В конкретном не имеющем ограничительного характера примере камера может соответствовать камере, поставляемой компанией FLIR Integrated Imaging Solutions Inc., 12051 Riverside Way, Richmond, BC, V6W 1K7, Canada (Канада). Очевидно, что камера может быть реализована в виде любого другого подходящего оборудования.

[92] В не имеющих ограничительного характера вариантах осуществления настоящей технологии система 230 датчиков может дополнительно содержать лидар (отдельно не показан). Лидар (LIDAR, Light Detection And Ranging) представляет собой лазерную систему для обнаружения и измерения дальности. Предполагается, что специалисту в данной области понятно функционирование лидара, тем не менее, вкратце, передатчик (не показан) лидара отправляет лазерный импульс и отраженные фотоны возвращаются в приемник (не показан) лидара. Фотоны, попавшие в приемник, собираются с использованием оптической системы и подсчитываются в виде функции времени. Затем с учетом скорости света (~3⋅10⁸ м/с) процессор 110 может рассчитать дистанцию перемещения фотонов (в прямом и обратном направлении). Фотоны могут отражаться в обратном направлении от большого количества различных окружающих транспортное средство 220 элементов, таких как частицы в атмосфере (аэрозоли или молекулы), другие автомобили, неподвижные объекты или потенциальные препятствия впереди транспортного средства 220.

[93] В некотором не имеющем ограничительного характера примере лидар, содержащийся в системе 230 датчиков, может быть реализован в виде датчика на основе лидара, поставляемого компанией Velodyne LiDAR, Inc., 5521 Hellyer Avenue, San Jose, CA 95138, USA (США). Очевидно, что лидар может быть реализован в виде любого другого подходящего оборудования.

[94] В некоторых вариантах осуществления настоящей технологии лидар, содержащийся в системе 230 датчиков, может быть реализован в виде множества датчиков на основе лидара, например, трех или любого другого подходящего количества датчиков.

[95] В не имеющих ограничительного характера вариантах осуществления настоящей технологии система 230 датчиков может дополнительно содержать радиолокатор (отдельно не показан). Вкратце, радиолокатор представляет собой прибор для обнаружения, использующий радиоволны с целью определения дальности, угла и/или скорости объектов. Радиолокатор содержит передатчик, генерирующий электромагнитные волны, антенну, используемую для передачи и приема электромагнитных волн, приемник и процессор для определения свойств обнаруженных объектов.

[96] В других вариантах осуществления настоящей технологии может быть предусмотрена отдельная антенна для приема радиоволн и отдельная антенна для передачи радиоволн. Процессор, используемый для определения свойств окружающих объектов, может представлять собой процессор 110.

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

[98] В некотором не имеющем ограничительного характера примере вид радиолокатора, содержащегося в системе 230 датчиков, может соответствовать радиолокатору, поставляемому компанией Robert Bosch GmbH, Robert-Bosch-Platz 1, 70839 Gerlingen, Germany (Германия). Очевидно, что радиолокатор может быть реализован в виде любого другого подходящего оборудования.

[99] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии система 230 датчиков может быть использована процессором 110 для калибровки изображения. Например, с использованием изображения, зафиксированного камерой, и облака лидарных точек, зафиксированного лидаром, процессор 110 может определять область изображения, соответствующую области облака лидарных точек, зафиксированного лидаром. В других вариантах осуществления настоящей технологии система 230 датчиков может быть откалибрована так, что для изображения, зафиксированного камерой, облака лидарных точек, зафиксированного лидаром, и радиолокационных данных, зафиксированных радиолокатором, процессор 110 способен определять область изображения, соответствующую области облака лидарных точек и радиолокационных данных.

[100] В не имеющих ограничительного характера вариантах осуществления настоящей технологии транспортное средство 220 дополнительно содержит другие датчики (отдельно не показаны) или имеет доступ к ним. Другие датчики включают в себя один или несколько датчиков из числа блока инерциальных измерений (IMU, Inertial Measurement Unit), прибора глобальной навигационной спутниковой системы (ГЛОНАСС), радиолокаторов скорости хода, ультразвуковых сонаров, одометрических датчиков, включая акселерометры и гироскопы, механических датчиков наклона, магнитного компаса и других датчиков, обеспечивающих работу транспортного средства 220.

[101] В не имеющем ограничительного характера примере блок IMU может быть смонтирован на транспортном средстве 220 и содержать три гироскопа и три акселерометра для предоставления данных о вращательном движении и о прямолинейном движении транспортного средства 220, которые могут быть использованы для расчета перемещения и положения транспортного средства 220.

Сеть связи

[102] В некоторых вариантах осуществления настоящей технологии сеть 240 связи представляет собой сеть Интернет. В альтернативных не имеющих ограничительного характера вариантах осуществления изобретения сеть 240 связи может быть реализована в виде любой подходящей локальной сети (LAN, Local Area Network), глобальной сети (WAN, Wide Area Network), частной сети связи и т.п. Очевидно, что варианты осуществления сети 240 связи приведены лишь в иллюстративных целях. Реализация линии связи (отдельно не обозначена) между электронным устройством 210 и сетью 240 связи зависит, среди прочего, от реализации электронного устройства 210. В качестве примера, не имеющего ограничительного характера, в тех не имеющих ограничительного характера вариантах осуществления настоящей технологии, где электронное устройство 210 реализовано в виде устройства беспроводной связи, такого как смартфон или навигационное устройство, линия связи может быть реализована в виде беспроводной линии связи. Примеры беспроводных линий связи включают в себя канал сети связи 3G, канал сети связи 4G и т.п. В сети 240 связи также может использоваться беспроводное соединение с сервером 235.

Сервер

[103] В некоторых вариантах осуществления настоящей технологии сервер 235 реализован в виде традиционного компьютерного сервера и может содержать некоторые или все элементы компьютерной системы 100, представленной на фиг. 1. В одном не имеющем ограничительного характера примере сервер 235 реализован в виде сервера Dell™ PowerEdge™, работающего под управлением операционной системы Microsoft™ Windows Server™, но он также может быть реализован с использованием любых других подходящих аппаратных средств, прикладного программного обеспечения и/или встроенного программного обеспечения либо их сочетания. В представленных не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 235 представляет собой один сервер. В других не имеющих ограничительного характера вариантах осуществления настоящей технологии (не показаны) функции сервера 235 могут быть распределены между несколькими серверами.

[104] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии процессор 110 устройства 210 может быть соединен с сервером 235 для получения одного или нескольких обновлений. Обновления могут представлять собой обновления программного обеспечения, обновления карт, обновления маршрутов, обновления погодных данных и т.д.

[105] В некоторых вариантах осуществления настоящей технологии процессор 110 также может отправлять серверу 235 некоторые рабочие данные, такие как пройденные маршруты, данные о дорожном движении, рабочие характеристики и т.д. Некоторые или все данные, передаваемые между транспортным средством 220 и сервером 235, могут быть зашифрованы и/или обезличены.

Запоминающее устройство

[106] На фиг. 2 также представлено запоминающее устройство 250, соединенное с сервером 235. Тем не менее, в некоторых вариантах осуществления изобретения запоминающее устройство 250 может быть соединено с электронным устройством 210 и/или может быть реализовано в электронном устройстве 210 и/или может быть соединено с любым другим процессором компьютерной сетевой среды 200.

[107] В по меньшей мере некоторых вариантах осуществления изобретения предполагается, что запоминающее устройство 250 может использоваться сервером 235, электронным устройством 210 и/или любым другим процессором компьютерной сетевой среды 200 в качестве запоминающего устройства для хранения информации. Запоминающее устройство 250 способно хранить информацию, извлеченную, определенную и/или сформированную процессором 110 сервера 235 и/или электронного устройства 210. В целом, запоминающее устройство 250 способно получать от процессора 110 данные, сформированные процессором 110 во время обработки, для временного и/или постоянного хранения и выдавать хранящиеся данные процессору 110 для их использования. Предполагается, что без выхода за границы настоящей технологии запоминающее устройство 250 может быть разделено на несколько распределенных запоминающих устройств, например, для реализации отказоустойчивой системы хранения данных.

[108] Следует отметить, что в по меньшей мере некоторых вариантах осуществления настоящей технологии запоминающее устройство 250 может быть реализовано локально в электронном устройстве 210 и/или на сервере 235 (например, в виде локального запоминающего устройства). Тем не менее, также предполагается, что запоминающее устройство 250 может быть реализовано удаленно от электронного устройства 210 и/или от сервера 235 (например, в виде удаленного запоминающего устройства).

Электронное устройство

[109] В общем случае электронное устройство 210 способно управлять работой транспортного средства 220. Например, электронному устройству 210 могут быть доступны (а) данные, представляющие пункт отправления, и (б) данные, представляющие пункт назначения, и электронное устройство 210 может формировать данные для управления работой транспортного средства 220 так, чтобы транспортное средство 220 двигалось из пункта отправления в пункт назначения.

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

[111] Для лучшей иллюстрации этого на фиг. 3 приведено представление 300 навигационной информации уровня маршрута, которую электронное устройство 210 может определять и/или получать от внешнего устройства (например, от сервера 235). Представлен пункт 302 отправления, указывающий на «начальную точку» для транспортного средства 220. В некоторых случаях пункт 302 отправления может соответствовать текущему местоположению транспортного средства 220. Также представлен пункт 304 назначения, указывающий на «конечную точку» для транспортного средства 220.

[112] Кроме того, навигационная информация уровня маршрута может содержать данные, представляющие маршрут 306 для движения из пункта 302 отправления в пункт 304 назначения. В некоторых случаях навигационная информация уровня маршрута может содержать данные, представляющие несколько маршрутов для движения из пункта 302 отправления в пункт 304 назначения, например, набор альтернативных маршрутов. В таких случаях маршрут 306 может представлять собой наиболее эффективный по времени маршрут, например, среди нескольких маршрутов для движения из пункта 302 отправления в пункт 304 назначения.

[113] Следует отметить, что здесь описание обработки данных электронным устройством 210 приведено для маршрута 306. Тем не менее, предполагается, что без выхода за границы настоящей технологии электронное устройство 210 может выполнять обработку данных для других маршрутов из числа нескольких маршрутов подобно тому, как электронное устройство выполняет обработку данных для маршрута 306.

[114] Маршрут 306 содержит несколько дорог и/или их участков, по которым транспортному средству 220 может потребоваться двигаться для перемещения из пункта 302 отправления в пункт 304 назначения (см. фиг. 3). Следует отметить, что электронное устройство 210 может определять и/или получать в дополнение к маршруту 306 правила дорожного движения, связанные с по меньшей мере одной дорогой маршрута 306. Предполагается, что в некоторых вариантах осуществления изобретения электронное устройство 210 может получать данные, представляющие маршрут 306, и/или данные, представляющие правила дорожного движения, от сервера 235 и/или из локальных и/или удаленных устройств хранения данных.

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

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

[117] Для лучшей иллюстрации этого можно рассмотреть часть 350 маршрута 306. На фиг. 4 приведено увеличенное представление 400 части 350 маршрута. Как показано, часть 350 маршрута 306 указывает на то, что транспортное средство 220 движется по части 410 дороги в направлении перекрестка 402 и что на перекрестке 402 транспортное средство 220 должно повернуть налево и продолжать движение по части 406 дороги. Таким образом, можно сказать, что эта информация представляет собой часть навигационной информации уровня маршрута для транспортного средства 220.

[118] На фиг. 4 также приведено представление 450 информации уровня полосы движения, которую электронное устройство 210 может определять на основе правил дорожного движения, связанных с частью 410 дороги, с перекрестком 402 и с частью 406 дороги. Например, электронное устройство 210 может определить (а) наличие двух полос движения на части 410 дороги, (б) полосу (или обе полосы) движения из числа двух полос движения, с которой разрешен поворот налево на перекрестке 402, (в) наличие двух полос движения на части 406 дороги и (г) тому подобное. Электронное устройство 210 может определять эту информацию как часть информации уровня полосы движения для части 350 маршрута 306.

[119] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 может использовать информацию уровня полосы движения о маршруте 306 для формирования «графовой структуры». На фиг. 5 приведены данные, представляющие графовую структуру 500, которую электронное устройство 210 может формировать и сохранять в запоминающем устройстве 250 (и/или в локальном запоминающем устройстве). В общем случае графовая структура 500 содержит множество вершин (не обозначены) и множество ребер (не обозначены), соединяющих соответствующие пары вершин из множества вершин. Например, ребро 506 из множества ребер соединяет пару вершин из множества вершин, содержащую первую вершину 502 и вторую вершину 504.

[120] Следует отметить, что вершина связана с потенциальным местоположением транспортного средства 220 на полосе движения дороги из числа по меньшей мере одной дороги маршрута 306. Например, первая вершина 502 связана с первым потенциальным местоположением транспортного средства 220 на полосе движения дороги маршрута 306, а вторая вершина 504 связана со вторым потенциальным местоположением транспортного средства 220 на полосе движения дороги маршрута 306.

[121] Следует отметить, что ребро указывает на переход между потенциальными местоположениями соответствующей пары вершин, которые оно соединяет. В этом примере ребро 506 указывает на переход между (а) первым потенциальным местоположением, связанным с первой вершиной 502, и (б) вторым потенциальным местоположением, связанным со второй вершиной 504.

[122] Также следует отметить, что множество вершин в графовой структуре 500 содержит вершину пункта отправления, связанную с пунктом 302 отправления (маршрута 306) и вершину пункта назначения, связанную с пунктом 304 назначения (маршрута 306). Таким образом, можно сказать, что графовая структура 500 может содержать данные, указывающие:

- на количество потенциальных местоположений (а) между пунктом 302 отправления и пунктом 304 назначения на маршруте 306, (б) в которых транспортное средство 220 может оказаться при движении по маршруту 306, когда оно может использовать различные полосы движения соответствующих дорог маршрута, и

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

[123] Для лучшей иллюстрации этого на фиг. 6 представлены три упрошенные графовые структуры: первая упрощенная графовая структура 600, вторая упрощенная графовая структура 620 и третья упрощенная графовая структура 650. Как описано ниже, графовая структура 500 может содержать очень большое количество вершин и ребер, а первая, вторая и третья упрощенные графовые структуры 600, 620 и 650 показаны как содержащие лишь небольшое количество вершин и ребер исключительно для простоты.

[124] В первом примере первая упрощенная графовая структура 600 содержит вершину 605 пункта отправления, вершину 608 пункта назначения и две промежуточных вершины (не обозначены). Первая упрощенная графовая структура 600 также содержит три ребра (не обозначены), каждое из которых соединяет вершины в соответствующей паре. В этом первом примере четыре вершины первой упрощенной графовой структуры 600 соответствуют четырем потенциальным местоположениям (не обозначены) транспортного средства 220 на первой дороге 602, которые представлены кругами на первой дороге 602. Таким образом, ребро между вершинами соответствующей пары на первой упрощенной графовой структуре 600 указывает на переход между потенциальными местоположениями соответствующей пары, в которых транспортное средство 220 может оказаться на первой дороге 602.

[125] Во втором примере вторая упрощенная графовая структура 620 содержит вершину 705 пункта отправления, вершину 734 пункта назначения и шесть промежуточных вершин. Шесть промежуточных вершин включают в себя вершину 731, вершину 732, вершину 735 и вершину 736. Вторая упрощенная графовая структура 620 также содержит несколько ребер, соединяющих соответствующие пары вершин.

[126] Во втором примере восемь вершин второй упрощенной графовой структуры 620 соответствуют восьми потенциальным местоположениям (не обозначены) транспортного средства 220 на второй дороге 622 с двумя полосами движения, которые представлены кругами на второй дороге 622.

[127] Например, вершина 731 соединена соответствующими ребрами (а) с вершиной пункта отправления 705, (б) с вершиной 732, (в) с вершиной 734, (г) с вершиной 735 и (д) с вершиной 736. В этом примере:

- ребро 740 указывает на переход из (а) местоположения пункта отправления вершины 705 пункта отправления в (б) потенциальное местоположение транспортного средства 220 на второй дороге 622, связанное с вершиной 731;

- ребро 741 указывает на переход из (а) потенциального местоположения транспортного средства 220 на второй дороге 622, связанного с вершиной 731, в (б) потенциальное местоположение транспортного средства 220 на второй дороге 622, связанное с вершиной 732;

- ребро 742 указывает на переход из (а) потенциального местоположения транспортного средства 220 на второй дороге 622, связанного с вершиной 731, в (б) местоположение пункта назначения транспортного средства 220 на второй дороге 622, связанное с вершиной 734 пункта назначения;

- ребро 743 указывает на переход из (а) потенциального местоположения транспортного средства 220 на второй дороге 622, связанного с вершиной 731, в (б) потенциальное местоположение транспортного средства 220 на второй дороге 622, связанное с вершиной 735; и

- ребро 744 указывает на переход из (а) потенциального местоположения транспортного средства 220 на второй дороге 622, связанного с вершиной 731, в (б) потенциальное местоположение транспортного средства 220 на второй дороге 622, связанное с вершиной 736.

[128] Можно сказать, что ребро 740 указывает на переход, согласно которому транспортное средство 220 находится в местоположении вершины 705 пункта отправления и движется по соответствующей полосе движения дороги 622 для прибытия в потенциальное местоположение вершины 731, которое также находится на соответствующей полосе движения дороги 622.

[129] Можно сказать, что ребро 741 указывает на переход, согласно которому транспортное средство 220 находится в потенциальном местоположении вершины 731 пункта отправления и движется по соответствующей полосе движения дороги 622 для прибытия в потенциальное местоположение вершины 732, которое также находится на соответствующей полосе движения дороги 622.

[130] Можно сказать, что ребро 744 указывает на переход, согласно которому транспортное средство 220 находится в потенциальном местоположении вершины 731 и выполняет «быстрое» перестроение в другой ряд для прибытия в потенциальное местоположение вершины 736 на соседней полосе движения дороги 622.

[131] Можно сказать, что ребро 742 указывает на переход, согласно которому транспортное средство 220 находится в потенциальном местоположении вершины 731 и выполняет «медленное» перестроение в другой ряд для прибытия в местоположение пункта назначения вершины 734 пункта назначения на соседней полосе движения дороги 622.

[132] Можно сказать, что ребро 743 указывает на переход, согласно которому транспортное средство 220 находится в потенциальном местоположении вершины 731 и выполняет перестроение в другой ряд («менее быстрое», чем соответствующее ребру 744 и «более быстрое», чем соответствующее ребру 742) для прибытия в потенциальное местоположение вершины 735 на соседней полосе движения дороги 622.

[133] Следует отметить, что в некоторых вариантах осуществления настоящей технологии пара вершин может быть соединена несколькими ребрами. Например, пара вершин может быть соединена двумя ребрами: одно может указывать на переход из первой вершины во вторую вершину в паре вершин, а другое может указывать на переход из второй вершины в первую вершину в этой паре вершин. Таким образом, можно сказать, что ребро в графовой структуре также может указывать на «направленность» соответствующего перехода в паре вершин.

[134] В третьем примере третья упрощенная графовая структура содержит двенадцать вершин, включая вершину пункта отправления (не обозначена) и вершину пункта назначения (не обозначена). Третья упрощенная графовая структура 650 также содержит много ребер (не обозначены), каждое из которых соединяет соответствующую пару вершин из числа двенадцати вершин третьей упрощенной графовой структуры 650.

[135] В третьем примере двенадцать вершин третьей упрощенной графовой структуры 650 соответствуют двенадцати потенциальным местоположениям (не обозначены) транспортного средства 220 на третьей дороге 652 с одной полосой движения, разделяющейся на две полосы движения. Таким образом, ребро между соответствующей парой вершин на третьей упрощенной графовой структуре 650 указывает на переход между потенциальными местоположениями этой пары, в которых транспортное средство 220 может оказаться на третьей дороге 652.

[136] Следует отметить, что в третьем примере вершина 651 соединена (а) с вершиной 656 ребром 654 и (б) с вершиной 653 ребром 655. Можно сказать, что ребро 654 указывает на переход, согласно которому транспортное средство 220 находится в потенциальном местоположении вершины 651 (на участке третьей дороги 652 с одной полосой движения) и перемещается в потенциальное местоположение вершины 656 (на левой полосе движения третьей дороги 652) без перестроения в другой ряд. Переход ребра 654 не соответствует переходу, требующему перестроения в другой ряд, поскольку транспортное средство 220 при выполнении перехода ребра 654 не должно перемещаться между полосами движения третьей дороги 652. Аналогично, можно сказать, что ребро 655 указывает на переход, в котором транспортное средство 220 находится в потенциальном местоположении вершины 651 (на участке третьей дороги 652 с одной полосой движения) и перемещается в потенциальное местоположение вершины 653 на правой полосе движения третьей дороги 652 без перестроения в другой ряд.

[137] Вкратце, электронное устройство 210 может использовать информацию уровня полосы движения (о маршруте 306) для формирования графовой структуры 500, представленной на фиг. 5. Графовая структура 500 содержит (а) множество вершин (связанных с потенциальными местоположениями на различных полосах движения маршрута 306), и (б) множество ребер, каждое из которых указывает на переход между потенциальными местоположениями вершин пары, которые оно соединяет.

[138] Некоторые ребра могут указывать на переходы, не требующие перестроения в другой ряд (полоса движения не изменяется), а другие ребра могут указывать на переходы, требующие перестроения в другой ряд. Кроме того, некоторые ребра могут указывать на быстрые перестроения в другой ряд, другие ребра могут указывать на медленные перестроения в другой ряд, и еще одни ребра могут указывать на перестроения в другой ряд, «промежуточные» между быстрыми и медленными перестроениями в другой ряд.

Глобальная модель оценки

[139] Разработчики настоящей технологии установили, что некоторые переходы между потенциальными местоположениями одних пар менее желательны, чем других. Например, переход, соответствующий быстрому перестроению в другой ряд, может быть менее желательным, чем переход, соответствующий медленному перестроению в другой ряд, т.е. выполнение быстрого перестроения в другой ряд более опасно по сравнению с медленным перестроением в другой ряд. В другом примере переход, соответствующий перестроению в другой ряд, где правила дорожного движения допускают это, более желателен, чем переход, соответствующий перестроению в другой ряд, где правила дорожного движения запрещают это (например, где соответствующая пара полос движения разделена разделительной линией, пересечение которой запрещено). Иными словами, выполнение маневра, запрещенного правилами дорожного движения, не только опасно, но и противозаконно. В еще одном примере переход, соответствующий перестроению в другой ряд, может быть менее желательным, чем переход, соответствующий сохранению транспортным средством 220 своего ряда движения. Иными словами, для уменьшения риска столкновения и по другим соображениям безопасности во время работы обычно желательно уменьшать количество выполняемых транспортным средством 220 перестроений в другой ряд (даже если они допускаются правилами дорожного движения).

[140] По этой причине электронное устройство 210 может применять глобальную модель оценки в отношении графовой структуры 500. В общем случае глобальная модель оценки соответствует модели, позволяющей назначать различные значения стоимости ребрам графовой структуры 500, указывающие на степень желательности соответствующего перехода. Эти значения стоимости назначаются электронным устройством 210, использующим глобальную модель оценки, соответствующим ребрам согласно первому набору критериев, которые выбираются для оценивания степени желательности потенциальных переходов и/или для сравнения степени желательности различных переходов. Таким образом, можно сказать, что электронное устройство 210 может применять глобальную модель оценки, связанную с первым набором критериев, в отношении графовой структуры 500 для назначения значений стоимости ребрам этой структуры.

[141] Кроме того, как описано ниже, электронное устройство может использовать значения стоимости (назначенные ребрам графовой структуры 500) для определения глобальных оценок штрафа для соответствующих вершин в графовой структуре 500. Ниже со ссылками на фиг. 6 и 7 описано назначение электронным устройством 210 значений стоимости ребрам, использование значений стоимости электронным устройством 210 для определения глобальных оценок штрафа для соответствующих вершин и того, на что указывают эти глобальные оценки штрафа.

[142] На фиг. 7 приведено первое представление 702 первой упрощенной графовой структуры 600 (см. фиг. 6) (а) со значениями стоимости, назначенными соответствующим ребрам, и (б) с глобальными оценками штрафа, определенными для соответствующих вершин. Также приведено второе представление 722 второй упрощенной графовой структуры 620 (а) со значениями стоимости, назначенными соответствующим ребрам, и (б) с глобальными оценками штрафа, определенными для соответствующих вершин. Кроме того приведено третье представление 752 третьей упрощенной графовой структуры 650 (а) со значениями стоимости, назначенными соответствующим ребрам, и (б) с глобальными оценками штрафа, определенными для соответствующих вершин.

[143] Для лучшей иллюстрации назначения значений стоимости ребрам графовой структуры можно рассмотреть вершину 731 второго представления 722 и ее ребра. Как описано выше, четыре ребра представляют переходы из вершины 731 в другие вершины, а именно:

- ребро 741 указывает на переход из (а) потенциального местоположения вершины 731 в (б) потенциальное местоположение вершины 732 (например, соответствующий сохранению транспортным средством 220 своего ряда движения);

- ребро 742 указывает на переход из (а) потенциального местоположения вершины 731 в (б) местоположение пункта назначения вершины 734 пункта назначения (например, соответствующий выполнению транспортным средством 220 медленного перестроения в другой ряд);

- ребро 743 указывает на переход из (а) потенциального местоположения вершины 731 в (б) потенциальное местоположение вершины 735 (например, соответствующий выполнению транспортным средством 220 среднего по времени (не медленного, но и не быстрого) перестроения в другой ряд); и

- ребро 744 указывает на переход из (а) потенциального местоположения вершины 731 в (б) потенциальное местоположение вершины 736 (например, соответствующий выполнению транспортным средством 220 быстрого перестроения в другой ряд).

[144] В этом примере, когда электронное устройство 210 применяет глобальную модель оценки в отношении второй упрощенной графовой структуры 620, электронное устройство 210 может использовать первый набор критериев для назначения (а) стоимости «2» ребру 744, (б) стоимости «1» ребру 743, (в) стоимости «0» ребру 742 и (г) стоимости «0» ребру 741. Назначенные стоимости указывают на степень желательности соответствующих переходов согласно первому набору критериев, связанных с первой моделью оценки. Как описано выше, быстрое перестроение в другой ряд ребра 744 менее желательно, чем среднее по времени перестроение в другой ряд ребра 743. Кроме того, среднее по времени перестроение в другой ряд ребра 743 менее желательно, чем медленное перестроение в другой ряд ребра 742. Также можно сказать, что сохранение транспортным средством 220 своего ряда движения может быть столь же желательным, что и медленное перестроение в другой ряд и поэтому ребра 742 и 741 могут иметь одинаковую связанную с ними стоимость.

[145] Следует отметить, что первый набор критериев может содержать множество критериев, которые могут изменяться в зависимости от конкретного варианта реализации настоящей технологии. Тем не менее, независимо от конкретных критериев, содержащихся в первом наборе критериев, первый набор критериев содержит критерии, позволяющие оценивать степень желательности (безопасность, плавность, законность и т.п.) различных переходов и/или обеспечивать возможность различения степеней желательности, связанных с различными переходами, без выхода за границы настоящей технологии.

[146] Электронное устройство 210 может назначить таким образом значения стоимости (а) каждому ребру второй упрощенной графовой структуры 620, (б) каждому ребру первой упрощенной графовой структуры 600 (см. значения стоимости на представлении 702 на фиг. 7) и (в) каждому ребру третьей упрощенной графовой структуры 650 (см. значения стоимости на представлении 752 на фиг. 7) подобно тому, как описано выше. Тем не менее, следует отметить, что для ребер 654 и 655 третьей упрощенной графовой структуры 650 электронное устройство 210 может назначить стоимость «0», поскольку они указывают на переходы, не требующие перестроения в другой ряд, как описано выше, так как транспортное средство 220 может перемещаться из потенциального местоположения вершины 651 в любое из потенциальных местоположений вершин 656 и 653 без перестроения в другой ряд.

[147] В некоторых вариантах осуществления настоящей технологии, назначив стоимости соответствующим ребрам графовой структуры, электронное устройство 210 может определять глобальные оценки штрафа для соответствующих вершин этой графовой структуры. Следует отметить, что глобальная оценка штрафа для вершины в графовой структуре имеет значение, соответствующее наименьшей суммарной стоимости ребер, соединяющих эту вершину с вершиной пункта назначения графовой структуры. Предполагается, что в некоторых вариантах осуществления изобретения определение этих глобальных оценок штрафа может выполняться электронным устройством 210 с использованием способа (или способов) динамического программирования.

[148] В качестве примера можно рассмотреть первое представление 702 (см. фиг. 7). После назначения значений стоимости ребрам электронное устройство 210 может начать определение глобальной оценки штрафа для вершины 608 пункта назначения. Можно сказать, что электронное устройство 210 может определять оценки штрафа в обратном направлении (или в направлении обратного распространения), т.е. это определение выполняется, начиная с глобальной оценки штрафа для вершины 608 пункта назначения, переходя далее к вершинам, представляющим собой непосредственных соседей, и так далее до глобальной оценки штрафа для вершины 605 пункта отправления.

[149] Таким образом, электронное устройство 210 может определить, что вершина 608 пункта назначения должна быть связана с глобальной оценкой штрафа «0», поскольку текущая вершина, для которой электронное устройство 210 определило глобальную оценку штрафа, фактически представляет собой вершину 608 пункта назначения. Предполагается, что в некоторых случаях электронное устройство 210 может по умолчанию назначать вершине 608 пункта назначения глобальную оценку штрафа «0». Затем электронное устройство 210 может перейти к определению глобальных оценок штрафа для вершин, представляющих собой непосредственных соседей в первой упрощенной графовой структуре 600, и продолжать его, пока не будет определена глобальная оценка штрафа для вершины 605 пункта отправления. Таким образом, в этом примере электронное устройство 210 может определить, что вершина 605 пункта отправления должна быть связана с глобальной оценкой штрафа «0», поскольку суммарная стоимость ребер, соединяющих вершину 608 пункта назначения с вершиной 605 пункта отправления, равна «0».

[150] Далее в качестве примера можно рассмотреть второе представление 722 (см. фиг. 7). Как и в предыдущем примере, после назначения значений стоимости ребрам электронное устройство 210 может начать определение глобальных оценок штрафа в обратном порядке, начиная с глобальной оценки штрафа для вершины 734 пункта назначения и заканчивая глобальной оценкой штрафа для вершины 705 пункта отправления. По той же причине, что и в предыдущем примере, электронное устройство 210 может определить (и/или назначить по умолчанию), что вершина 734 пункта назначения должна быть связана с глобальной оценкой штрафа «0».

[151] Во втором примере можно рассмотреть определение электронным устройством 210 глобальной оценки штрафа для вершины 731. Следует отметить, что имеются различные последовательности ребер, соединяющих вершину 731 с вершиной 734 пункта назначения. Например, последовательности ребер, соединяющих вершины 731, 736, 735 и 734, соответствует суммарная стоимость ребер «2», последовательности ребер, соединяющих вершины 731, 735 и 734, соответствует суммарная стоимость ребер «1», и т.д.

[152] В этом примере вторая упрощенная графовая структура 620 также содержит ребро 742, которое непосредственно соединяет вершину 731 с вершиной 734 пункта назначения и имеет стоимость «0». Следовательно, суммарная стоимость ребра (или ребер), соединяющего вершину 731 с вершиной 734 пункта назначения, для этой последовательности ребер (даже содержащей лишь одно ребро) равна «0». В результате наименьшая суммарная стоимость ребер, соединяющих вершину 731 с вершиной 734 пункта назначения, равна «0».

[153] Таким образом, можно сказать, что при определении глобальной оценки штрафа для вершины электронное устройство 210 может сравнивать суммарные значения стоимости нескольких различных последовательностей ребер, соединяющих эту вершину с вершиной 734 пункта назначения, и может выбирать наименьшую из соответствующих суммарных значений стоимости. Это означает, что при определении глобальной оценки штрафа для вершины электронное устройство 210 может рекурсивно определять суммарные значения стоимости для последовательности ребер, соединяющих эту вершину с вершиной пункта назначения, и может выбирать наименьшую из этих значений стоимости в качестве глобальной оценки штрафа.

[154] Также следует отметить, что глобальная оценка штрафа «0» для вершины 731 указывает на наименьшую глобальную стоимость движения транспортного средства 220 в пункт назначения, связанный с вершиной 734 пункта назначения, если транспортное средство 220 оказывается в потенциальном местоположении, связанном с вершиной 731. Иными словами, электронное устройство 210 может определять, что наименьшая глобальная стоимость движения транспортного средства 220 из потенциального местоположения вершины 731 в местоположение вершины 734 пункта назначения связана с выполнением транспортным средством 220 медленного перестроения в другой ряд.

[155] Также можно сказать, что в этом случае электронное устройство 210 может определять, что быстрое перестроение в другой ряд с последующим сохранением соседней полосы движения до достижения пункта назначения (т.е. переход, соответствующий последовательности ребер, соединяющих вершины 731, 736, 735 и 734 и имеющий суммарную стоимость ребер «2») с глобальной точки зрения менее желательно, чем медленное перестроение в другой ряд (т.е. переход, соответствующий ребру 742).

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

[157] Следует отметить, что электронное устройство 210 может определять глобальные оценки штрафа для вершин третьей упрощенной графовой структуры 752 (см. фиг. 7) подобно тому, как электронное устройство 210 определяет глобальные оценки штрафа для вершин первой упрощенной графовой структуры 600 и второй упрощенной графовой структуры 620.

[158] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 может сохранять графовую структуру в сочетании с (а) значениями стоимости соответствующих ребер и (б) глобальными оценками штрафа для соответствующих вершин в запоминающем устройстве 250 и/или в локальном запоминающем устройстве.

[159] Можно предположить, что представление 800 (см. фиг. 8) иллюстрирует графовую структуру 500 со значениями стоимости соответствующих ребер и с глобальным оценками штрафов соответствующих вершин. В этом случае графовая структура 500 содержит вершину 802 пункта отправления, связанную с пунктом 302 отправления (см. фиг. 3), и вершину 804 пункта назначения, связанную с пунктом 304 назначения (см. фиг. 3). Графовая структура 500 также содержит несколько других вершин и ребер, при этом каждое ребро связано с соответствующей стоимостью, а каждая вершина связана с соответствующей глобальной оценкой штрафа.

[160] Следует отметить, что глобальная оценка штрафа, связанная с вершиной 802 пункта отправления, равна «0», поскольку наименьшая суммарная стоимость ребер, соединяющих вершину 804 пункта назначения с вершиной 802 пункта отправления, связана с последовательностью ребер (содержащихся в выделенной части 806), имеющей суммарную стоимость «0». Также следует отметить, что электронное устройство 210 может сохранять графовую структуру 500 с соответствующими значениями стоимости и глобальными оценками штрафа в запоминающем устройстве 250 для дальнейшей обработки во время работы транспортного средства 220.

Локальная модель оценки

[161] Электронное устройство 210 может использовать графовую структуру (со значениями стоимости и глобальными оценками штрафа) для определения последовательности потенциальных местоположений, способной обеспечить наименьшую глобальную стоимость движения из пункта отправления в пункт назначения, если транспортное средство 220 движется согласно последовательности потенциальных местоположений, как описано выше. Тем не менее, разработчики настоящей технологии установили, что во время работы транспортного средства 220 некоторые переходы между потенциальными местоположениями такой последовательности могут быть невозможны (из-за препятствий, дорожного движения, дорожно-транспортных происшествий и т.п.) и/или могут содержать слишком много перестроений в другой ряд, несмотря на то, что имеют меньшую глобальную стоимость, чем другие последовательности потенциальных местоположений, позволяющие двигаться из пункта отправления в пункт назначения.

[162] Для таких случаев разработчики настоящей технологии разработали способы и системы, которые вместо движения согласно последовательности потенциальных местоположений, обеспечивающих наименьшую глобальную стоимость, позволяют применять локальную модель оценки в отношении части графовой структуры во время работы транспортного средства 220 для локальной корректировки значений стоимости по меньшей мере некоторых ребер в графовой структуре 500 с целью определения локально скорректированных оценок штрафа для по меньшей мере некоторых вершин в графовой структуре 500 на основе текущей информации об окрестности транспортного средства 220.

[163] В по меньшей мере некоторых вариантах осуществления настоящей технологии эта локальная корректировка значений стоимости и оценок штрафа электронным устройством 210 позволяет определять альтернативные варианты полосы движения (и/или выполнять их ранжирование) для продолжения движения к пункту 304 назначения при следовании по маршруту 306. Как описано ниже, в по меньшей мере в некоторых случаях такая локальная корректировка ранее определенных значений стоимости и глобальных оценок штрафа позволяет электронному устройству 210 уменьшать вероятность перестроений в другой ряд во время работы транспортного средства 220 при движении в направлении пункта 304 назначения по маршруту 306. В некоторых вариантах осуществления изобретения можно сказать, что такая локальная корректировка ранее определенных значений стоимости и глобальных оценок штрафа позволяет электронному устройству 210 управлять работой транспортного средства 220 так, чтобы уменьшить общее количество перестроений в другой ряд, которые транспортное средство 220 должно выполнить при движении по маршруту 306.

[164] Ниже более подробно описана локальная корректировка электронным устройством 210 значений стоимости и глобальных оценок штрафа во время работы транспортного средства 220 на основе текущей информации, предоставленной электронному устройству 210.

[165] Можно предположить, что в момент времени t_i транспортное средство 220 находится на дороге 900, содержащей общую часть 902 с одной полосой движения, которая разделяется на левую часть 904 и правую часть 906. Электронное устройство 210 может получить текущую информацию об окрестности транспортного средства 220 в виде первого пути 914 полосы движения и второго пути 916 полосы движения. В общем случае путь полосы движения для текущего местоположения транспортного средства 220 указывает на участок полосы движения, начинающийся от текущего местоположения транспортного средства 220, по которому транспортное средство 220 может двигаться без перестроения в другой ряд.

[166] Например, первый путь 914 полосы движения указывает на участок полосы движения, начинающийся от текущего местоположения транспортного средства 220 в момент времени t_i, по которому транспортное средство 220 может двигаться без перестроения в другой ряд. Действительно, транспортному средству 220 не требуется выполнять перестроения в другой ряд для перемещения из общей части 902 в левую часть 904 дороги 900. В этом примере второй путь 916 полосы движения указывает на другой участок полосы движения, начинающийся от текущего местоположения транспортного средства 220 в момент времени t_i, по которому транспортное средство 220 может двигаться без перестроения в другой ряд. Действительно, транспортному средству 220 не требуется выполнять маневр перестроения в другой ряд для перемещения из общей части 902 в правую часть 906 дороги 900. В этом примере первый путь 914 полосы движения и второй путь 916 полосы движения частично перекрываются (в общей части 902).

[167] Следует отметить, что информация, указывающая на пути полосы движения, может быть получена от внешнего устройства (не показано). Предполагается, что информация, указывающая на пути полосы движения, может быть сформирована внешним устройством, в числе прочего, на основе данных датчика, предоставленных этому устройству системой 230 датчиков транспортного средства 220. По этой причине количество и длины путей полосы движения могут изменяться в зависимости от конкретной ситуации, в которой транспортное средство 220 оказывается в текущий момент времени, и в зависимости от различных вариантов реализации настоящей технологии. В одном примере длины путей полосы движения могут быть ограничены горизонтом обнаружения системы 230 датчиков. В другом примере количество путей полосы движения может быть ограничено конкретной ситуацией, в которой транспортное средство 220 оказывается во время его работы.

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

[169] Можно предположить, что в некоторый момент времени транспортное средство 220 находится в пункте 302 отправления маршрута 306 (например, транспортное средство 220 начинает движение по маршруту 306) и электронное устройство 210 в этот момент времени получает четыре различных пути полосы движения, начинающихся из пункта 302 отправления, каждый из которых указывает на участок полосы движения, начинающийся от текущего местоположения (из пункта 302 отправления), и по каждому из которых транспортное средство 220 потенциально может двигаться без перестроения в другой ряд. В этом случае электронное устройство 210 может определять для каждого из четырех путей полосы движения соответствующие последовательности вершин в графовой структуре 500 (например, из части графовой структуры 500), покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения.

[170] Для лучшей иллюстрации этого на фиг. 10-13 представлена графовая структура 500 со значениями стоимости и глобальными оценками штрафа (как описано выше), где определены четыре последовательности вершин, связанные с соответствующими путями из числа четырех путей полосы движения, полученных электронным устройством 210. В частности, электронное устройство 210 может определять:

- первую последовательность 1010 вершин (см. фиг. 10), связанную с соответствующими потенциальными местоположениями, которые покрываются участком полосы движения первого пути полосы движения, полученного электронным устройством 210;

- вторую последовательность 1020 вершин (см. фиг. 11), связанную с соответствующими потенциальными местоположениями, которые покрываются участком полосы движения второго пути полосы движения, полученного электронным устройством 210;

- третью последовательность 1030 вершин (см. фиг. 12), связанную с соответствующими потенциальными местоположениями, которые покрываются участком полосы движения третьего пути полосы движения, полученного электронным устройством 210; и

- четвертую последовательность 1040 вершин (см. фиг. 13), связанную с соответствующими потенциальными местоположениями, которые покрываются участком полосы движения четвертого пути полосы движения, полученного электронным устройством 210.

[171] Следует отметить, что каждый путь полосы движения указывает на участок полосы движения, начинающийся от текущего местоположения транспортного средства 220, по которому транспортное средство 220 может двигаться без перестроения в другой ряд. Таким образом, это означает, что некоторые из ребер, соединяющих (а) первую последовательность 1010 вершин и/или (б) вторую последовательность 1020 вершин и/или (в) третью последовательность 1030 вершин и/или (г) четвертую последовательность 1040 вершин, указывают на переход, соответствующий перестроению в другой ряд.

[172] Также следует отметить, что каждая последовательность из числа первой, второй, третьей и четвертой последовательностей 1010, 1020, 1030 и 1040 вершин начинается в текущем местоположении транспортного средства 220, соответствующем пункту 302 отправления. Иными словами, каждая последовательность из числа первой, второй, третьей и четвертой последовательностей 1010, 1020, 1030 и 1040 вершин начинается в вершине 802.

[173] Кроме того, следует отметить, что каждая последовательность из числа первой, второй, третьей и четвертой последовательностей 1010, 1020, 1030 и 1040 вершин заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующем концу участка полосы движения на соответствующем пути полосы движения. В частности, следует отметить, что первая последовательность 1010 вершин содержит первую конечную вершину 1012, вторая последовательность 1020 вершин содержит вторую конечную вершину 1022, третья последовательность 1030 вершин содержит третью конечную вершину 1032, а четвертая последовательность 1040 вершин содержит четвертую конечную вершину 1042.

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

[175] Следует отметить, что, как описано ниже, электронное устройство 210 может выполнять это (т.е. определять локально увеличенные стоимости и локально скорректированные оценки штрафа) независимо для каждой последовательности вершин и/или для каждого пути полосы движения. Иными словами, локально увеличенные стоимости и локально скорректированные оценки штрафа, определенные для последовательности вершин, определяются независимо от локально увеличенных значений стоимости и локально скорректированных оценок штрафа, определенных для других последовательностей вершин. Также можно сказать, что определение локально увеличенных значений стоимости и локально скорректированных оценок штрафа для последовательности вершин не влияет на определение локально увеличенных значений стоимости и локально скорректированных оценок штрафа для других последовательностей вершин и наоборот. Также можно сказать, что определение локально увеличенных значений стоимости и локально скорректированных оценок штрафа может выполняться итеративно для каждой последовательности вершин и/или пути полосы движения, при этом итерация не зависит от предыдущей итерации.

[176] На фиг. 14-17 приведены четыре представления графовой структуры 500 (первое представление 1102 (см. фиг. 14), второе представление 1104 (см. фиг. 15), третье представление 1106 (см. фиг. 16) и четвертое представление 1108 (см. фиг. 17)), каждое из которых связано с соответствующим путем полосы движения и с соответствующей последовательностью вершин.

[177] На первом представлении 1102 приведена первая последовательность 1010 вершин, связанная с первым путем полосы движения. Как описано выше, электронное устройство 210 может применять локальную модель оценки в отношении графовой структуры 500 для назначения дополнительных значений стоимости по меньшей мере некоторым ребрам, связанным с первой последовательностью 1010 вершин. Следует отметить, что локальная модель оценки может быть использована для назначения дополнительных значений стоимости только ребрам, соответствующим съезду с пути полосы движения и связанным с первой последовательностью 1010 вершин.

[178] Например, вершины первой последовательности вершин 1010 соединены друг с другом ребрами, соответствующими следованию по пути полосы движения, которые указывают на переходы, позволяющие транспортному средству 220 следовать по первому пути полосы движения. Тем не менее, некоторые вершины в последовательности 1010 вершин имеют другие связанные с ними ребра, которые не являются ребрами, соответствующими следованию по пути полосы движения. Это означает, что эти другие ребра указывают на переходы, позволяющие транспортному средству 220 покидать первый путь полосы движения. Эти другие ребра, представленные утолщенными линиями на первом представлении 1102, могут быть определены электронным устройством 210 как ребра, соответствующие съезду с пути полосы движения, на первом пути полосы движения.

[179] Таким образом, можно сказать, что электронное устройство 210, использующее локальную модель оценки, может (а) определять ребра в графовой структуре 500, представляющие собой ребра, соответствующие съезду с пути полосы движения, для первой последовательности 1010 вершин, и (б) назначать дополнительные стоимости ребрам, соответствующим съезду с пути полосы движения, для первой последовательности 1010 вершин в дополнение к стоимостям, раннее назначенным глобальной моделью оценки ребрам, соответствующим съезду с пути полосы движения, для первой последовательности 1010 вершин.

[180] Для лучшей иллюстрации этого можно рассмотреть три ребра, соответствующие съезду с пути полосы движения, для вершины 1014 в последовательности 1010 вершин. Как описано выше, электронное устройство 210 может использовать глобальную модель оценки для назначения этим трем ребрам, соответствующим съезду с пути полосы движения, значений стоимости «1», «0» и «0», указывающих на степень желательности соответствующих переходов. Далее электронное устройство 210 может назначать дополнительные значения стоимости каждому из этих ребер вершины 1014, соответствующих съезду с пути полосы движения. Например, электронное устройство 210 может назначить дополнительную стоимость «2» каждому из этих ребер, соответствующих съезду с пути полосы движения. В результате электронное устройство 210 может определить локально увеличенные значения стоимости «3», «2» и «2» для этих ребер, соответствующих съезду с пути полосы движения.

[181] В этом же примере можно рассмотреть три ребра, соответствующие съезду с пути полосы движения, для вершины 1016 в последовательности 1010 вершин. Как описано выше, электронное устройство 210 может использовать глобальную модель оценки для назначения этим трем ребрам, соответствующим съезду с пути полосы движения, значений стоимости «1», «0» и «0», указывающих на степень желательности соответствующих переходов. Далее электронное устройство 210 может назначать дополнительные значения стоимости каждому из этих ребер вершины 1016, соответствующих съезду с пути полосы движения. Например, электронное устройство 210 может назначить дополнительную стоимость «4» каждому из этих ребер, соответствующих съезду с пути полосы движения. В результате электронное устройство 210 может определить локально увеличенные значения стоимости «5», «4» и «4» для этих ребер, соответствующих съезду с пути полосы движения.

[182] В этом же примере можно рассмотреть ребро, соответствующее съезду с пути полосы движения, для вершины 1018 в последовательности 1010 вершин. Как описано выше, электронное устройство 210 может использовать глобальную модель оценки для назначения этому ребру, соответствующему съезду с пути полосы движения, стоимости «0», указывающей на степень желательности соответствующего перехода. Далее электронное устройство 210 может назначать дополнительную стоимость этому ребру вершины 1018, соответствующему съезду с пути полосы движения. Например, электронное устройство 210 может назначить дополнительную стоимость «10» этому ребру, соответствующему съезду с пути полосы движения. В результате электронное устройство 210 может определить локально увеличенную стоимость «10» для этого ребра, соответствующего съезду с пути полосы движения.

[183] В некоторых вариантах осуществления настоящей технологии предполагается, что электронное устройство 210, использующее локальную модель оценки, может взвешивать значения дополнительных значений стоимости для ребер, соответствующих съезду с пути полосы движения, в зависимости от того, насколько «раньше» или «позже» соответствующая вершина расположена в первой последовательности 1010 вершин. Например, следует отметить, что вершина 1018 представляет собой «более раннюю» вершину в первой последовательности 1010 вершин по сравнению с вершиной 1016 и/или что вершина 1016 представляет собой «более позднюю» вершину в первой последовательности 1010 вершин по сравнению с вершиной 1018. С учетом того, что электронное устройство 210 назначило наполнительную стоимость «10» ребру вершины 1018, соответствующему съезду с пути полосы движения и назначило дополнительную стоимость «4» ребрам вершины 1016, соответствующим съезду с пути полосы движения, электронное устройство 210 может взвешивать таким образом значения дополнительных значений стоимости для увеличения значения стоимости ранних съездов с первого пути полосы движения в большей степени, чем стоимости поздних съездов с первого пути полосы движения.

[184] Предполагается, что после определения локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, в первой последовательности 1010 вершин электронное устройство 210 может определять локально скорректированные оценки штрафа для соответствующих вершин в первой последовательности 1010 вершин, которые указывают на значение, представляющее собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной 804 пункта назначения.

[185] Например, для этого электронное устройство 210 может использовать способ (или способы) динамического программирования, как описано выше. Несмотря на то, что способ (или способы) динамического программирования может быть использован для определения локально-скорректированной оценки штрафа подобно тому, как описано выше, локально скорректированные оценки штрафа могут отличаться от соответствующих глобальных оценок штрафа, поскольку значения стоимости ребер, соответствующих съезду с пути полосы движения, не равны определенным глобальным оценкам штрафа.

[186] Для лучшей иллюстрации этого можно рассмотреть второе представление 1104, где показана вторая последовательность 1020 вершин, связанных со вторым путем полосы движения. Электронное устройство 210 может применять локальную модель оценки в отношении графовой структуры 500 для назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения, во второй последовательности 1020 вершин.

[187] Прежде всего важно отметить, что назначение дополнительных значений стоимости для ребер, соответствующих съезду с пути полосы движения, во второй последовательности 1020 вершин выполняется электронным устройством 210 независимо от назначения дополнительных значений стоимости для ребер, соответствующих съезду с пути полосы движения, в первой последовательности 1010 вершин. Действительно, поскольку первая последовательность 1010 вершин содержит вершины, отличные от вершин второй последовательности 1020 вершин, то ребра, соответствующие съезду с пути полосы движения, в первой последовательности 1010 вершин не совпадают с ребрами, соответствующими съезду с пути полосы движения, во второй последовательности 1020 вершин (хотя некоторые из них могут совпадать).

[188] Можно сказать, что (а) на первой итерации электронное устройство 210 может определять локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, в первой последовательности 1010 вершин и локально скорректированные оценки штрафа для соответствующих вершин в первой последовательности 1010 вершин и (б) во время второй итерации электронное устройство 210 может выполнять то же самое для второй последовательности 1020 вершин без учета результатов определения, полученных на первой итерации.

[189] После того, как электронное устройство 210 назначило дополнительные стоимости ребрам, соответствующим съезду с пути полосы движения, во второй последовательности 1020 вершин и таким образом сформировало локально увеличенные стоимости этих ребер, соответствующих съезду с пути полосы движения, подобно тому, как электронное устройство 210 назначило дополнительные стоимости ребрам, соответствующим съезду с пути полосы движения, в первой последовательности 1010 вершин, электронное устройство 210 может использовать способ (или способы) динамического программирования для определения локально скорректированных оценок штрафа для каждой вершины во второй последовательности 1020 вершин.

[190] В некоторых вариантах осуществления настоящей технологии можно сказать, что определение локально скорректированных оценок штрафа может включать в себя использование некоторых из ранее использовавшихся при определении глобальных оценок штрафа способов динамического программирования и/или отличающихся от них способов динамического программирования, при этом такой способ (или способы) динамического программирования может быть применен в отношении локально скорректированной информации о ребрах, соответствующих съезду с пути полосы движения, во второй последовательности 1020 вершин.

[191] Например, электронное устройство 210 может определить, что локально скорректированная оценка штрафа для вершины 1014 во второй последовательности 1020 вершин равна «2», а соответствующая глобальная оценка штрафа для вершины 1014 равна «0». Здесь это отличие обусловлено тем фактом, что, поскольку ребра, соответствующие съезду с пути полосы движения, во второй последовательности 1020 вершин связаны с увеличенными (отличающимися) значениями стоимости, то наименьшая суммарная стоимость ребер, соединяющих вершину 1014 с вершиной 804 пункта назначения, во второй последовательности 1020 вершин также увеличена. Тем не менее, это не обязательно для всех вариантов осуществления настоящей технологии. В другом примере локально скорректированная оценка штрафа для вершины 1014 в первой последовательности 1010 вершин равна «0» и совпадает с соответствующей глобальной оценкой штрафа (см. первое представление 1102). Здесь это объясняется тем фактом, что первая последовательность 1010 вершин связана с ребрами, соответствующими съезду с пути полосы движения, отличными от ребер второй последовательности 1020 вершин, что влияет на наименьшую суммарную стоимость ребер для соединения вершины 1014 в первой последовательности 1010 вершин с вершиной 804 пункта назначения способом, отличным от того, который влияет на наименьшую суммарную стоимость ребер для соединения вершины 1014 во второй последовательности 1020 вершин с вершиной 804 пункта назначения. Действительно, на наименьшую суммарную стоимость для вершины 1014 не могут влиять локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, в первой последовательности 1010 вершин, тогда как наименьшая суммарная стоимость для вершины 1014 во второй последовательности 1020 вершин увеличена до «2» вследствие локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, во второй последовательности 1020 вершин.

[192] Электронное устройство 210 может определять локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, в третьей последовательности 1030 вершин, связанной с третьим путем полосы движения, и локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, в четвертой последовательности 1040 вершин, связанной с четвертым путем полосы движения, подобно тому как электронное устройство 210 определяет локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, в первой последовательности 1010 вершин, связанной с первым путем полосы движения, и локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, во второй последовательности 1020 вершин, связанной со вторым путем полосы движения. Электронное устройство 210 может определять локально скорректированные оценки штрафа для вершин в третьей последовательности 1030 вершин и локально скорректированные оценки штрафа для вершин в четвертой последовательности 1040 вершин подобно тому, как электронное устройство 210 определяет локально скорректированные оценки штрафа для вершин в первой последовательности 1010 вершин и локально скорректированные оценки штрафа для вершин во второй последовательности 1020 вершин. При этом учитываются локально скорректированные стоимости ребер, соответствующих съезду с пути полосы движения, и не учитываются локально скорректированные стоимости ребер, соответствующих съезду с пути полосы движения и связанных с другими последовательностями вершин.

[193] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 может определять оценку пути полосы движения для каждого из четырех путей полосы движения, полученных электронным устройством 210. В общем случае оценка пути полосы движения для некоторого пути полосы движения представляет собой локально скорректированную оценку штрафа для текущей вершины (или, как в этом примере, вершины 802 пункта отправления) в соответствующей последовательности вершин.

[194] Например, первая оценка пути полосы движения на первом пути полосы движения равна «0», поскольку она представляет собой значение локально скорректированной оценки штрафа для вершины 802 пункта отправления в первой последовательности 1010 вершин, связанной с первым путем полосы движения. В этом же примере вторая оценка пути полосы движения на втором пути полосы движения равна «2», поскольку она представляет собой значение локально скорректированной оценки штрафа для вершины 802 пункта отправления во второй последовательности 1020 вершин, связанной со вторым путем полосы движения. В том же примере третья оценка пути полосы движения для третьего пути полосы движения равна «4», поскольку она представляет собой значение локально скорректированной оценки штрафа для вершины 802 пункта отправления в третьей последовательности 1030 вершин, связанной с третьим путем полосы движения. В том же примере четвертая оценка пути полосы движения для четвертого пути полосы движения равна «7», поскольку она представляет собой значение локально скорректированной оценки штрафа для вершины 802 пункта отправления в четвертой последовательности 1040 вершин, связанной с четвертым путем полосы движения.

[195] Следует отметить, что оценка пути полосы движения указывает на стоимость движения транспортного средства 220 по соответствующему участку полосы движения на соответствующем пути полосы движения (по которому транспортное средство 220 может следовать без перестроения в другой ряд).

[196] В некоторых вариантах осуществления изобретения электронное устройство 210 может использовать оценки путей полосы движения для ранжирования четырех путей полосы движения согласно соответствующим оценкам путей полосы движения и/или для выбора целевого пути полосы движения среди четырех путей полосы движения, который далее должен использоваться для управления работой транспортного средства 220. В этом примере первый путь полосы движения связан с наименьшей оценкой пути полосы движения среди четырех оценок путей полосы движения. Соответственно, электронное устройство 210 может ранжировать четыре пути полосы движения, при этом первый путь полосы движения получает наивысший ранг, и/или выбирать первый путь полосы движения в качестве целевого пути полосы движения. Затем электронное устройство 210 может формировать одну или несколько траекторий для транспортного средства 220 на соответствующем участке полосы движения на целевом пути полосы движения (первого пути полосы движения) и также может управлять работой транспортного средства 220 так, чтобы транспортное средство 220 следовало по одной из траекторий на соответствующем участке полосы движения на целевом пути полосы движения.

[197] Тем не менее, можно предположить, что электронное устройство 210 в дополнение к информации, указывающей на четыре пути полосы движения, получает текущую информацию о своей окрестности, которая указывает на дорожно-транспортное происшествие на соответствующем участке полосы движения на первом пути полосы движения. В этом случае электронное устройство 210 может выбрать «следующий наилучший» путь полосы движения в качестве целевого пути полосы движения. В этом примере электронное устройство 210 может выбрать второй путь полосы движения в качестве нового целевого пути полосы движения, поскольку он связан с предпоследней по величине оценкой пути полосы движения из числа четырех оценок путей полосы движения.

[198] В некоторых вариантах осуществления настоящей технологии электронное устройство 210 может выполнять способ 1200 управления работой транспортного средства 220 (см. фиг. 18). Далее более подробно описаны шаги способа 1200.

Шаг 1202: определение навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения.

[199] Способ 1200 начинается с шага 1202, на котором электронное устройство 210 способно определять навигационную информацию уровня маршрута для движения транспортного средства 220 из пункта 302 отправления в пункт 304 назначения. Например, как описано выше, навигационная информация уровня маршрута может содержать данные, представляющие маршрут 306 (см. фиг. 3), содержащий одну или несколько дорог, которые транспортное средство 220 может использовать для прибытия из пункта 302 отправления в пункт 304 назначения.

Шаг 1204: использование правил дорожного движения для определения информации уровня полосы движения.

[200] Способ 1200 продолжается на шаге 1204, на котором электронное устройство 210 использует правила дорожного движения, связанные с одной или несколькими дорогами маршрута 306, для определения информации уровня полосы движения. Например, электронное устройство 210 может определять информацию уровня полосы движения о маршруте 306, которая, среди прочего, указывает на наличие полос движения на каждой дороге маршрута 306.

Шаг 1206: использование информации уровня полосы движения для формирования графовой структуры.

[201] Способ 1200 продолжается на шаге 1206, на котором электронное устройство 210 использует информацию уровня полосы движения для формирования графовой структуры 500. Как описано выше, графовая структура содержит множество вершин и множество ребер. Каждая вершина графовой структуры связана с потенциальным местоположением транспортного средства 220 на полосе движения дороги из числа по меньшей мере одной дороги маршрута (например, см. фиг. 6).

[202] Множество вершин содержит вершину пункта отправления, связанную с соответствующим пунктом отправления, и вершину пункта назначения, связанную с соответствующим пунктом назначения. Ребро соединяет пару вершин в графовой структуре. Ребро указывает на переход между потенциальным местоположением, связанным с первой вершиной в этой паре вершин, и потенциальным местоположением, связанным со второй вершиной в этой паре вершин.

Шаг 1208: применение глобальной модели оценки в отношении графовой структуры.

[203] Способ 1200 продолжается на шаге 1208, на котором электронное устройство 210 способно применять глобальную модель оценки в отношении графовой структуры 500. Глобальная модель оценки связана с первым набором критериев для назначения значений стоимости соответствующим ребрам. При этом стоимость, назначенная ребру, указывает на степень желательности соответствующего перехода согласно первому набору критериев.

[204] Например, на фиг. 8 представлена графовая структура 500 со значениями стоимости, назначенными ее ребрам. В некоторых вариантах осуществления изобретения первый набор критериев указывает на то, что переход, соответствующий сохранению автомобилем SDC своего ряда движения, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC перестроения в другой ряд. В другом варианте осуществления изобретения первый набор критериев указывает на то, что переход, соответствующий выполнению автомобилем SDC медленного перестроения в другой ряд, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC быстрого перестроения в другой ряд.

Шаг 1210: определение глобальной оценки штрафа для каждой вершины в графовой структуре.

[205] Способ 1200 продолжается на шаге 1210, на котором электронное устройство 210 способно определять глобальную оценку штрафа для каждой вершины в графовой структуре 500. Например, на фиг. 8 представлена графовая структура 500 с глобальными оценками штрафа, назначенными ее вершинам.

[206] Следует отметить, что глобальная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Глобальная оценка штрафа указывает на наименьшую глобальную стоимость движения автомобиля SDC в пункт назначения, если автомобиль SDC оказывается в потенциальном местоположении этой вершины.

Шаг 1212: сохранение ребер в графовой структуре в сочетании с соответствующими значениями стоимости и вершин в графовой структуре в сочетании с соответствующими глобальными оценками штрафа.

[207] Способ 1200 продолжается на шаге 1212, на котором электронное устройство 210 способно сохранять графовую структуру 500 со значениями стоимости соответствующих ребер и с глобальными оценками штрафа для соответствующих вершин. Например, электронное устройство 210 может сохранить графовую структуру 500 со значениями стоимости соответствующих ребер и с глобальными оценками штрафа для соответствующих вершин в локальном и/или удаленном запоминающем устройстве для последующего их использования. Например, эта информация может быть сохранена электронным устройством 210 для использования во время работы транспортного средства 220.

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

[208] Способ 1200 продолжается на шаге 1214, на котором электронное устройство 210 способно получать по меньшей мере один путь полосы движения для текущего местоположения в данный момент времени в процессе работы транспортного средства 220, когда транспортное средство 220 находится в текущем местоположении между пунктом отправления и пунктом назначения.

[209] Как описано выше, электронное устройство 210 может получить в некоторый момент времени информацию о своей текущей окрестности и данные, указывающие на по меньшей мере один путь полосы движения, которые могут представлять собой часть этой информации. Например, по меньшей мере один путь полосы движения указывает на участок полосы движения, начинающийся от текущего местоположения транспортного средства 220, по которому транспортное средство 220 может двигаться без перестроения в другой ряд.

Шаг 1216: определение для каждого пути из числа по меньшей мере одного пути полосы движения последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения.

[210] Способ 1200 продолжается на шаге 1216, на котором электронное устройство 210 способно определять для каждого пути полосы движения последовательности вершин в графовой структуре 500, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения. Например, на фиг. 10-13 представлены первая последовательность 1010 вершин на первом пути полосы движения, вторая последовательность 1020 вершин на втором пути полосы движения, третья последовательность 1030 вершин на третьем пути полосы движения и четвертая последовательность 1040 вершин на четвертом пути полосы движения.

[211] Следует отметить, что последовательность вершин (а) начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению транспортного средства 220, и (б) заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующим концу участка полосы движения (на соответствующем пути полосы движения).

Шаг 1218: применение для каждого пути из числа по меньшей мере одного пути полосы движения локальной модели оценки в отношении графовой структуры.

[212] Способ 1200 продолжается на шаге 1218, на котором электронное устройство 210 способно применять для каждого пути полосы движения локальную модель оценки в отношении графовой структуры 500 с целью назначения дополнительных значений стоимости ребрам, соответствующим съезду с пути полосы движения, для соответствующей последовательности вершин, определяя таким образом локально увеличенные значения стоимости ребер, соответствующих съезду с пути полосы движения, для этой последовательности вершин.

[213] Следует отметить, что ребра, соответствующие съезду с пути полосы движения, представляют собой ребра, соединяющие последовательность вершин с другими вершинами в графовой структуре за исключением этой последовательности вершин. В некоторых вариантах осуществления изобретения электронное устройство 210, применяющее локальную модель оценки в отношении графовой структуры 500, может определять для пути полосы движения и соответствующей последовательности вершин ребра в графовой структуре 500, которые представляют собой ребра этого пути полосы движения, соответствующие следованию по пути полосы движения, и ребра в графовой структуре 500, которые представляют собой ребра на этом пути полосы движения, соответствующие съезду с пути полосы движения.

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

Шаг 1220: определение для каждого пути из числа по меньшей мере одного пути полосы движения локально скорректированной оценки штрафа для каждой вершины в последовательности вершин.

[215] Способ 1200 продолжается на шаге 1220, на котором электронное устройство 210 способно определять для каждого пути полосы движения локально скорректированную оценку штрафа для каждой вершины в соответствующей последовательности вершин. Например, электронное устройство 210 может определять локально скорректированные оценки штрафа для вершин в первой последовательности вершин, связанных с первым путем полосы движения.

[216] Следует отметить, что локально скорректированная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения. Предполагается, что электронное устройство 210 может использовать способ (или способы) динамического программирования для определения локально скорректированных оценок штрафа на основе локально увеличенных значений стоимости ребер, соответствующих съезду с пути полосы движения, как описано выше.

Шаг 1222: определение оценки пути полосы движения для каждого пути из числа по меньшей мере одного пути полосы движения.

[217] Способ 1200 продолжается на шаге 1222, на котором электронное устройство 210 способно определять оценку пути полосы движения для каждого пути полосы движения. Оценка пути полосы движения для пути полосы движения представляет собой локально скорректированную оценку штрафа для текущей вершины в последовательности вершин на этом пути полосы движения. Оценка пути полосы движения указывает на стоимость движения автомобиля SDC по участку полосы движения на этом пути полосы движения без перестроения в другой ряд.

[218] В некоторых вариантах осуществления изобретения электронное устройство 210 может определять первую оценку пути полосы движения на первом пути полосы движения и вторую оценку пути полосы движения на втором пути полосы движения. В таких случаях электронное устройство 210 может использовать первую оценку пути полосы движения и вторую оценку пути полосы движения для выбора целевого пути полосы движения среди первого пути полосы движения и второго пути полосы движения. Целевой путь полосы движения связан с наименьшей оценкой из числа первой оценки пути полосы движения и второй оценки пути полосы движения. Затем электронное устройство 210 может сформировать траекторию для автомобиля SDC на участке полосы движения на целевом пути полосы движения. Электронное устройство 210 также может управлять работой автомобиля SDC так, чтобы автомобиль SDC следовал по траектории на участке полосы движения на целевом пути полосы движения.

[219] Предполагается, что электронное устройство 210 может получать пути полосы движения в различные моменты времени в процессе работы транспортного средства 220. Таким образом, электронное устройство 210 может определять соответствующие оценки пути полосы движения для этих путей полосы движения в различные моменты времени в процессе работы транспортного средства 220.

[220] Следует отметить, что в по меньшей мере некоторых вариантах осуществления настоящей технологии электронное устройство 210 может опускать по меньшей мере некоторые шаги способа 1200. Например, электронное устройство 210 может опускать шаг 1210 и в качестве части шага 1212 сохранять значения стоимости с соответствующими ребрами графовой структуры 500 (без сохранения глобальных оценок штрафа из опущенного шага 1210).

[221] В этом примере, определив локально увеличенные стоимости ребер, соответствующих съезду с пути полосы движения, для последовательности вершин на пути полосы движения, электронное устройство 210 может использовать (а) локально увеличенные значения стоимости этих ребер, соответствующих съезду с пути полосы движения, и (б) значения стоимости других ребер в графовой структуре 500 (определенные и сохраненные) с целью определения локальных оценок штрафа для каждой вершины в последовательности вершин. Это может достигаться путем применения одного или нескольких способов динамического программирования, описанных выше.

[222] Предварительный расчет и сохранение глобальных оценок штрафа позволяют уменьшить требования к вычислительным ресурсам электронного устройства 210 во время работы транспортного средства 220. В этом случае при определении локально скорректированной оценки штрафа для вершины в последовательности вершин электронное устройство 210 может использовать глобальные оценки штрафа (в этом случае уже определенные и сохраненные) для по меньшей мере некоторых соседних вершин с целью уменьшения количества вычислений во время выполнения одного или нескольких способов динамического программирования для определения наименьшей суммарной стоимости ребер, соединяющих эту вершину с вершиной пункта назначения.

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

[224] Очевидно, что не все упомянутые в данном описании технические эффекты должны присутствовать в каждом варианте осуществления настоящей технологии.

[225] Для специалиста в данной области могут быть очевидными возможные изменения и усовершенствования описанных выше вариантов осуществления настоящей технологии. Предшествующее описание приведено лишь в иллюстративных целях, а не для ограничения объема изобретения. Объем охраны настоящей технологии определяется исключительно объемом приложенной формулы изобретения.

Определяют информацию уровня маршрута и информацию уровня полосы движения для формирования графовой структуры. Применяют первую модель для назначения значений стоимости соответствующим ребрам. Определяют оценки для вершин на основе значений стоимости, и сохраняют ребра со значениями стоимости и вершин с оценками. Способ также включает в себя получение в некоторый момент времени в процессе работы пути полосы движения, указывающего на участок полосы движения без перестроения в другой ряд, начинающийся от текущего местоположения. Для пути полосы движения способ включает в себя: определение последовательности вершин, покрываемых участком полосы движения; применение второй модели для назначения дополнительных значений стоимости ребрам для последовательности вершин, соответствующим съезду с пути полосы движения, и определение таким образом локально увеличенных значений стоимости; определение локально скорректированных оценок для вершин в последовательности вершин на основе локально увеличенных значений стоимости и определение оценки пути полосы движения на основе локально скорректированных оценок. Достигается навигация движения автомобиля при движении по дорожной сети. 3 н. и 16 з.п. ф-лы, 18 ил.

1. Способ управления работой самоуправляемого автомобиля (SDC), связанного с электронным устройством, имеющим доступ к данным, которые представляют пункт отправления и пункт назначения, причем способ выполняется электронным устройством и включает в себя:

- определение электронным устройством навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения, при этом навигационная информация уровня маршрута указывает на по меньшей мере одну дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения, и эта по меньшей мере одна дорога связана с правилами дорожного движения;

- использование электронным устройством правил дорожного движения для определения информации уровня полосы движения, указывающей на наличие по меньшей мере одной полосы движения на каждой дороге из числа по меньшей мере одной дороги;

- использование электронным устройством информации уровня полосы движения для формирования графовой структуры, содержащей множество вершин и множество ребер, при этом вершина связана с соответствующим потенциальным местоположением автомобиля SDC на полосе движения дороги из числа по меньшей мере одной дороги, множество вершин включает в себя вершину пункта отправления, связанную с пунктом отправления, и вершину пункта назначения, связанную с пунктом назначения, а ребро соединяет соответствующую пару вершин в графовой структуре и указывает на переход между потенциальным местоположением, связанным с первой вершиной в этой соответствующей паре вершин, и потенциальным местоположением, связанным со второй вершиной в этой соответствующей паре вершин;

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

- определение электронным устройством глобальной оценки штрафа для каждой вершины в графовой структуре, при этом глобальная оценка штрафа для вершины представляет собой наименьшую суммарную стоимость ребер, соединяющих эту вершину с вершиной пункта назначения, и указывает на наименьшую глобальную стоимость движения автомобиля SDC в пункт назначения, если автомобиль SDC оказывается в потенциальном местоположении этой соответствующей вершины;

- сохранение электронным устройством ребер в графовой структуре в сочетании с соответствующими значениями стоимости и вершин в графовой структуре в сочетании с соответствующими глобальными оценками штрафа;

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

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

- идентификацию электронным устройством последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения, при этом последовательность вершин начинается в текущей вершине, связанной с соответствующим потенциальным местоположением, относящимся к текущему местоположению автомобиля SDC, и заканчивается в соответствующей конечной вершине, связанной с соответствующим потенциальным местоположением, относящимся к концу соответствующего участка полосы движения;

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

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

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

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

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

- использование электронным устройством первой оценки пути полосы движения и второй оценки пути полосы движения для выбора целевого пути полосы движения среди первого пути полосы движения и второго пути полосы движения, при этом целевой путь полосы движения связан с наименьшей оценкой среди первой оценки пути полосы движения и второй оценки пути полосы движения;

- формирование электронным устройством траектории для автомобиля SDC на участке полосы движения на целевом пути полосы движения; и

- управление электронным устройством работой автомобиля SDC так, чтобы автомобиль SDC следовал по траектории вдоль участка полосы движения на целевом пути полосы движения.

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

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

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

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

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

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

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

- определения навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения, при этом навигационная информация уровня маршрута указывает на по меньшей мере одну дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения, и эта по меньшей мере одна дорога связана с правилами дорожного движения;

- использования правил дорожного движения для определения информации уровня полосы движения, указывающей на наличие по меньшей мере одной полосы движения на каждой дороге из по меньшей мере одной дороги;

- использования информации уровня полосы движения для формирования графовой структуры, включающей в себя множество вершин и множество ребер, при этом вершина связана с соответствующим потенциальным местоположением автомобиля SDC на полосе движения дороги из по меньшей мере одной дороги, при этом множество вершин включает в себя вершину отправления, связанную с пунктом отправления, и вершину назначения, связанную с пунктом назначения, а ребро соединяет соответствующую пару вершин в графовой структуре и указывает на переход между потенциальным местоположением, связанным с первой вершиной из соответствующей пары вершин, и потенциальным местоположением, связанным со второй вершиной из соответствующей пары вершин;

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

- определения глобальной оценки штрафа для каждой вершины в графовой структуре, при этом глобальная оценка штрафа для соответствующей вершины представляет собой наименьшую совокупную стоимость ребер, соединяющих соответствующую вершину с вершиной назначения, и указывает на наименьшую глобальную стоимость движения автомобиля SDC в пункт назначения, если автомобиль SDC оказывается в потенциальном местоположении этой соответствующей вершины;

- сохранения ребер в графовой структуре в сочетании с соответствующими значениями стоимости и вершин в графовой структуре в сочетании с соответствующими глобальными оценками штрафа;

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

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

- идентификации последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения, при этом последовательность вершин начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению автомобиля SDC, и заканчивается в соответствующей конечной вершине, связанной с потенциальным местоположением, соответствующим концу соответствующего участка полосы движения;

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

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

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

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

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

- использования первой оценки пути полосы движения и второй оценки пути полосы движения для выбора целевого пути полосы движения среди первого пути полосы движения и второго пути полосы движения, при этом целевой путь полосы движения связан с наименьшей оценкой среди первой оценки пути полосы движения и второй оценки пути полосы движения;

- формирования траектории для автомобиля SDC на участке полосы движения на целевом пути полосы движения; и

- управления работой автомобиля SDC так, чтобы автомобиль SDC следовал по траектории на участке полосы движения на целевом пути полосы движения.

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

14. Электронное устройство по п. 10, отличающееся тем, что первый набор критериев указывает на то, что переход, соответствующий сохранению автомобилем SDC своей полосы движения, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC маневра по перестроению в другую полосу движения.

15. Электронное устройство по п. 10, отличающееся тем, что первый набор критериев указывает на то, что переход, соответствующий выполнению автомобилем SDC медленного маневра перестроения в другую полосу движения, более желателен, чем другой переход, соответствующий выполнению автомобилем SDC быстрого маневра перестроения в другую полосу движения.

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

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

18. Электронное устройство по п. 10, отличающееся тем, что оно дополнительно выполнено с возможностью определения оценок путей полосы движения для путей полосы движения, полученных в различные моменты времени в процессе работы автомобиля SDC.

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

- определение электронным устройством навигационной информации уровня маршрута для движения автомобиля SDC из пункта отправления в пункт назначения, при этом навигационная информация уровня маршрута указывает на по меньшей мере одну дорогу, по которой автомобиль SDC должен двигаться из пункта отправления в пункт назначения, и эта по меньшей мере одна дорога связана с правилами дорожного движения;

- использование электронным устройством правил дорожного движения для определения информации уровня полосы движения, указывающей на наличие по меньшей мере одной полосы движения на каждой дороге из по меньшей мере одной дороги;

- использование электронным устройством информации уровня полосы движения для формирования графовой структуры, включающей в себя множество вершин и множество ребер, при этом вершина связана с потенциальным местоположением автомобиля SDC на полосе движения дороги из по меньшей мере одной дороги, при этом множество вершин включает в себя вершину отправления, связанную с пунктом отправления, и вершину назначения, связанную с пунктом назначения, а ребро соединяет соответствующую пару вершин в графовой структуре и указывает на переход между потенциальным местоположением, связанным с первой вершиной в соответствующей паре вершин, и потенциальным местоположением, связанным со второй вершиной в соответствующей паре вершин;

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

- сохранение электронным устройством ребер в графовой структуре в сочетании с соответствующими значениями стоимости;

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

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

- идентификацию электронным устройством последовательности вершин в графовой структуре, покрываемых соответствующим участком полосы движения на соответствующем пути полосы движения, при этом последовательность вершин начинается в текущей вершине, связанной с потенциальным местоположением, соответствующим текущему местоположению автомобиля SDC, и заканчивается в конечной вершине, связанной с потенциальным местоположением, соответствующим концу участка полосы движения;

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

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

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