способ определения траектории движения автономного транспортного средства в динамической среде

Формула изобретения

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

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

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

Описание изобретения к патенту

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

Известен способ определения траектории движения автономного мобильного робота, при котором определяют траекторию движения, на основе траектории движения определяют параметры движения робота, причем непосредственное управление движением автономного робота осуществляют как с учетом спланированного направления движения, так и с учетом информации о препятствиях на пути робота, полученной с помощью сенсоров. Недостаток способа заключается в том, что на этапе определения траектории движения не учитываются возможные препятствия (Патент 2424892 С2 РФ, МПК B25J 5/00, B25J 13/08, A01D 46/00, G05B 13/00. Автономный мобильный робот для сбора дикоросов и способ управления им / Тырышкин А.В., Андраханов А.А., Орлов А.А. - заявл. 14.07.2009. - опубл. 20.01.2011. - № 2009127229/02. - 14 с.).

Известен способ управления автономным транспортным средством, заключающийся в том, что на основе начальной и конечной точек определяют первую траекторию движения, при детектировании препятствия сенсорами генерируют позиционный сигнал препятствия, на основе позиционного сигнала генерируют сигнал параллакса, на основе сигнала параллакса генерируют вторую траекторию, учитывающую детектированное препятствие. Недостаток способа заключается в том, что не учитываются ограничения на время определения траекторий, заданные динамикой внешней среды (Pub. No. 20110035086 Al United States, Int. C1. G06F 17/10. Steering method for vehicle and apparatus thereof / Kim H.J., Yoon Y. - Field 13.01.2009. -Pub. date 10.02.2011. - Appl. No. 12/937521. - 20 p.).

Известен способ планирования траекторий движения транспортного средства в пространстве состояний от начальной точки к конечной с уклонением от множества статических и/или динамических препятствий, заключающийся в том, что строят граф траекторий, соединяющий начальную точку с конечной, учитывающий возможное положение препятствий. При этом для расширения, приостановки расширения и остановки расширения узлов графа траекторий используют различные правила. Полученные траектории оценивают относительно заданных ограничений. На основе графа траекторий получают хотя бы одну траекторию, соединяющую начальную точку с конечной, удовлетворяющую заданным ограничениям. Осуществляют управление транспортным средством для движения по полученной траектории. Недостаток аналога заключается в том, что в процессе формирования дерева траекторий не учитываются ограничения на время планирования траекторий, заданные динамикой внешней среды (Pub. No. 7447593 В2 United States, Int. C1. G06G 7/78, G08G 1/16, G05B 19/04. System and method for adaptive path plannning / Estkowski R.I., Tinker P.A. - Field 26.03.2004. - Pub. date 04.11.2008. - Appl. No. 10/811460. - 34 p.).

Прототипом заявляемого изобретения является способ автономного управления транспортным средством (Pub. No. 7613553 Bl United States, Int. C1. G08G 9/02, G01C 22/00, G05B 19/18. Unmanned vehicle control system / Benjamin M. R. - Field 30.07.2004. - Pub. date 03.11.2009. - Appl. No. 10/911765. - 11 p.), заключающийся в том, что в процессе движения транспортного средства по текущей траектории в цикле сбора и обработки информации получают сенсорные сигналы, на основе которых обновляют модель текущего состояния внешней среды, отражающей наличие во внешней среде статических и динамических препятствий. На основе обновленной модели текущего состояния внешней среды обновляют модель прогнозируемого состояния внешней среды на момент достижения автономным транспортным средством конечной точки текущей траектории движения. На основе обновленной модели прогнозируемого состояния внешней среды определяют множество возможных траекторий дальнейшего движения из конечной точки текущей траектории движения. Для каждой траектории из сформированного множества возможных траекторий дальнейшего движения рассчитывают значение ожидаемой полезности с использованием заданной функции ожидаемой полезности. Из сформированного множества возможных траекторий дальнейшего движения выбирают траекторию движения с максимальной ожидаемой полезностью и реализуют ее при достижении конечной точки текущей траектории движения.

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

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

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

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

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

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

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

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

На фиг.1 представлены результаты первого цикла сбора и обработки информации, при этом положение автономного транспортного средства соответствует началу первого цикла сбора и обработки информации. По фиг.1: (1) - автономное транспортное средство, (2) - текущая траектория движения, (3) - конечная точка текущей траектории движения, (4а-4в) - статические препятствия, (5) - конечная точка определяемых возможных траекторий дальнейшего движения, (6а-6в) - возможные траектории дальнейшего движения определенные в первом цикле сбора и обработки информации.

На фиг.2 представлены результаты второго цикла сбора и обработки информации, при этом положение автономного транспортного средства соответствует началу второго цикла сбора и обработки информации. По фиг.2: (1) - автономное транспортное средство, (2) - текущая траектория движения, (6б-6ж) - возможные траектории дальнейшего движения, переопределенные во втором цикле сбора и обработки информации, (4а, 4г-4з) - статические препятствия, (7а, 7б) - дополнительные проезды, детектированные на основе полученных во втором цикле сбора и обработки информации сенсорных данных, (8) - динамическое препятствие, (8а-8в) - прогнозируемые положения динамического препятствия.

На фиг.3 представлены результаты третьего цикла сбора и обработки информации, при этом положение автономного транспортного средства соответствует началу третьего цикла сбора и обработки информации. По фиг.3: (1) - автономное транспортное средство, (2) - текущая траектория движения, (6г, 6ж-6и) - возможные траектории дальнейшего движения, переопределенные в третьем цикле сбора и обработки информации, (4и) - статическое препятствие.

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

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

Для получения сенсорных сигналов и преобразования их в сенсорные данные могут использоваться различные устройства, такие как: лазерный локатор, радиолокатор, инерциальный измерительный блок, система глобального позиционирования, видеокамеры. Для взаимодействия с сенсорами используются различные интерфейсы, такие как: Ethernet, RS-232, RS-422, IEEE-1394a, CAN (Controller Area Network, сеть контроллеров) и т.д. Известно применение лазерного локатора для получения измерений расстояний до различных объектов. Данный лазерный локатор генерируют около миллиона измерений в секунду, используя для передачи полученных данных Ethernet интерфейс (J.Leonard et al. A Perception-Driven Autonomous Urban Vehicle / В.M., Iagnemma K., Singh S. The DARPA urban challenge. Autonomous vehicle in city traffic // Springer Tracts in Advanced Robotics. - Berlin: Springer, 2009. - P.171-172).

Для взаимодействия различных подсистем автономного транспортного средства могут использоваться различные программно-аппаратные платформы. Известно использование системы межпроцессного взаимодействия Lightweight Communications and Marshaling (LCM) для передачи сообщений и маршалинга данных, в которой для передачи сообщений используется групповая передача UDP (J.Leonard et al. А Perception-Driven Autonomous Urban Vehicle / В. M., Iagnemma K., Singh S. The DARPA urban challenge. Autonomous vehicle in city traffic // Springer Tracts in Advanced Robotics. - Berlin: Springer, 2009. - P.173-174).

Полученные сенсорные данные преобразуют в модель внешней среды. Известны алгоритмы одновременной локализации и отображения (Simultaneous localization and mapping, SLAM), применяемые для формирования и обновления модели состояния внешней среды (Durrant-Whyte Н., Bailey Т. Simultaneous localization and mapping: part I the essential algorithms / Robotics & Automation Magazine. - V.2 - № 2. - 2006. - P.99-110).

Также известен способ преобразования сенсорных данных от лазерного локатора, инерциального измерительного блока и глобальной системы позиционирования в двухмерную карту препятствия (Thrun S., Montemerlo M., Aron A. Probabilistic Terrain Analysis For High-Speed Desert Driving / Proceedings of Robotics: Science and Systems. - Philadelphia, 2006. - 7 p.).

Для определения траекторий могут использоваться различные алгоритмы произвольного времени. Известен алгоритм произвольного времени AD* для построения траектории движения (Likhachev М. et al. Anytime Dynamic A*: An Anytime, Replanning Algorithm / International Conference on Automated Planning and Scheduling (ICAPS)-2005. - 10 p.).

Для иллюстрации одного из возможных вариантов реализации заявляемого способа рассмотрим следующий пример (фиг.1): автономное транспортное средство (1) движется по текущей траектории (2) в конечную точку (3).

В первом цикле сбора и обработки информации, в процессе движения автономного транспортного средства (1) по текущей траектории движения (2), в пределах ограниченной фиксированной длительности цикла сбора и обработки информации, осуществляют следующие действия:

Получают сенсорные сигналы, на основе которых обновляют модель текущего состояния внешней среды, которая представляет собой двухмерную карту препятствий (4а-4в).

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

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

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

В первом цикле сбора и обработки информации в течение фиксированного интервала времени, выделенного в пределах длительности цикла сбора и обработки информации, формируют три траектории Т₁-Т₃(6а-6в). Полагаем, что выделенного интервала времени не хватает для построения траектории обхода препятствия (4а) слева.

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

f_U=l/( D),

где D - максимальное отклонение от кратчайшего маршрута к целевой точке (5), который в данном случае совпадает с траекторией Т ₂(6б).

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

f _U(T₂)>f_U(T₁>f _U(T₃).

Во втором цикле сбора и обработки информации, в процессе движения автономного транспортного средства (1) по текущей траектории (2), в пределах ограниченной фиксированной длительности цикла сбора и обработки информации осуществляют следующие действия (фиг.2):

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

На основе обновленной модели текущего состояния внешней среды обновляют модель прогнозируемого состояния внешней среды. Для прогнозирования положения динамического препятствия (8) через заданный интервал времени используют следующую модель движения:

x=v_obst·cos( )·t+x₀,

y=v_obst ·sin( )·t+y₀,

где <х,y> - координаты прогнозируемого положения динамического препятствия (8),

<х₀,y₀> - координаты текущего положения динамического препятствия (8),

v_obst- текущая скорость движения динамического препятствия (8),

- угол, задающий направление движения динамического препятствия (8).

На основе обновленной модели прогнозируемого состояния внешней среды в течение фиксированного интервала времени, выделенного в пределах длительности цикла сбора и обработки информации, переформировывают сформированное в предыдущем цикле сбора и обработки информации множество возможных траекторий дальнейшего движения. Для этого, во-первых, уточняют определенные в предыдущем цикле сбора и обработки информации траектории дальнейшего движения, начиная с траектории с наибольшей ожидаемой полезностью, т.е. с траектории Т₂ (6б). На основе обновленной модели прогнозируемого состояния внешней среды определяют наиболее близкое прогнозируемое положение (8а) динамического препятствия (8) к траектории движения Т₂ (6б). Так как динамическое препятствие (8а) перекрывает движение по траектории Т₂ (6б), ее перестраивают в обход препятствия (4г), получая траекторию Т_2.1 (6г)

Далее переходят к траектории Т₃ (6в). Так как препятствие (4ж) перекрывает движение по данной траектории, то ее перестраивают, учитывая открывшийся проезд (7б), получая уточненную траекторию Т_3.1 (6д). Для полученной траектории на основе обновленной модели прогнозируемого состояния внешней среды определяют наиболее близкое прогнозируемое положение (8б) динамического препятствия (8). Так как уточненная траектория не приводит к столкновению с динамическим препятствием (8), ее включают во множество возможных траекторий дальнейшего движения.

Кроме того, во множество возможных траекторий дальнейшего движения добавляют еще одну траекторию Т₄ (6е), которая проходит через проезд (7б). На основе обновленной модели прогнозируемого состояния внешней среды определяют наиболее близкое прогнозируемое положение (8в) динамического препятствия (8) относительно данной траектории. Так как траектория Т ₄ (6е) приводит к столкновению с динамическим препятствием (8), ее перестраивают, получая траекторию Т_4.1 (6ж).

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

f_U(T_4.1)>f_U(T_2.1 >fu(T_3.1).

В третьем цикле сбора и обработки информации, в процессе движения автономного транспортного средства (1) по текущей траектории (2), в пределах ограниченной фиксированной длительности цикла сбора и обработки информации осуществляют следующие действия (фиг.3):

Получают сенсорные сигналы, на основе которых обновляют модель текущего состояния внешней среды, добавляя новое препятствие (4и).

На основе обновленной модели текущего состояния внешней среды обновляют модель прогнозируемого состояния внешней.

На основе обновленной модели прогнозируемого состояния внешней среды в течение фиксированного интервала времени, выделенного в пределах длительности цикла сбора и обработки информации, переформировывают сформированное в предыдущем цикле сбора и обработки информации множество возможных траекторий. Для этого уточняют траекторию Т_4.1 (6ж) как имеющую наибольшее значение ожидаемой полезности, перестраивая ее для обхода препятствия (4и). В результате получают две новые траектории Т_4.2 (6з), Т_4.3 (6и).

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

f_U(T_4.2)=f_U (T_4.3),

f_U(T_4.3 )>f_U(T_2.1).

Полагаем, что разница значений ожидаемой полезности для траекторий Т _4.2, Т_4.3 и Т_2.1 недостаточно велика, чтобы принять однозначное решение по выбору траектории. Тогда вводят дополнительный фактор - число поворотов, необходимых для выполнения каждой из траекторий, тогда:

f _Unew=k₁·l/ D+k2·1/N,

где N - количество поворотов, необходимых для выполнения траектории,

kl, k2 - весовые коэффициенты факторов.

Полагаем, что:

k2<kl, тогда

f_Unew(T _4.2)=f_Unew(T_4.3),

f_Unew (T_2.l)<f_Unew (t _4.3).

Для выбора траектории из множества {Т_4.2, Т_4.3} рассчитываем ожидаемую полезность для несовпадающих участков траекторий. Тогда:

f_Unew(T_4.2)>f_Unew(T_4.3 ).

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

Выбранная траектория преобразуется в систему команд управления агрегатами автономного транспортного средства. Известен способ управления агрегатами автономного транспортного средства, использующий контроллер для преобразования плана движения, который состоит из списка точек, задающего кусочно-заданную прямолинейную опорную траекторию, в команды управления (сигналы управления) газом, тормозом, рулем и переключением передач. Контроллер включает два компонента: контроллер рулевого управления и контроллер скорости. Полученные сигналы управления подают на блок автономного управления (Autonomous Driving Unit, ADU), который представляет собой интерфейс к системе электронного цифрового управления автомобилем (drive-by-wire) (J.Leonard et al. A.Perception-Driven Autonomous Urban Vehicle / В.M., Iagnemma K., Singh S. The DARPA urban challenge. Autonomous vehicle in city traffic // Springer Tracts in Advanced Robotics. - Berlin: Springer, 2009. - P.206-208).