Проблемы управления движением виртуальных автомобилей на сети дорог

Ярославский Государственный Университет имени

П.Г.Демидова

Кафедра теоретической информатики и  вычислительной техники

Дисциплина  «Русский Язык» 

 

 

 

 

 

 

Реферат

по  статье: «Проблемы управления движением  виртуальных автомобилей на сети дорог »

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Студент группы ИТ-31Бо

Горшков С.Б.

 

 

 

 

 

Содержание

Введение 

Граф дорог

Задачи на графе  дорог

Параметрические полиномиальные кривые

• Общие подходы
• Нахождение ближайшей точки

Автомобили  –непротиворечивость положения

Заключение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

Автомобильный симулятор состоит из нескольких подсистем.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Граф дорог

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

Граф дорог  вместе с атрибутами ребер и узлов  задает логические и топологические свойства моделируемой местности.

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

Удобство графа  объясняется тем, что граф можно  наращивать и модифицировать по модулям.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задачи на графе дорог

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Параметрические полиномиальные кривые

Общие подходы

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

Параметрическая полиномиальная кривая представляется полиномом действительной переменной с векторными коэффициентами.

Для вычисления полинома нужно всего лишь N сложений и N умножений, где N- степень полинома.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Нахождение ближайшей точки

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

Эта задача сводится к нахождению минимума квадрата расстояния от точки Х пространства до кривой P(t).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Автомобили-непротиворечивость положения

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

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

При переходе автомобиля в зону видимости наблюдателя  используется более детальный и  сложный алгоритм.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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