1.4 Сравнительная характеристика

приведённых алгоритмов.

Для сравнения рассмотрим два имеющихся алгоритма планирования траектории: метод пробных траекторий и однослойная нейронная сеть. Метод пробных траекторий заключается в переборе вариантов траекторий, представляющих собой ломанные линии, соединяющие начальную и конечную точки по определённым правилам. Этот алгоритм применим только на достаточно простых площадках, допускающих небольшое количество вариантов траекторий. Преимуществом является то, что траектория планируется сразу от начала до конца, недостатки - 1) при необходимости внесения изменений в траекторию требуется её заново планировать, 2) невозможно спланировать разворот и подъезд задним ходом.

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

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

Сравнительная характеристика приведённых и предлагаемого алгоритмов приведена в таблице 1.1

Таблица 1.1 Сравнение алгоритмов планирования траектории.

2 Описание предлагаемого алгоритма

автоматического построения траектории

и навигации по счислению.

2.1 Предварительное планирование траектории.

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

Для ускорения планирования предполагается, что самосвал может поворачивать на угол 450 . т. е. Мы получаем восемь возможных направлений перемещения самосвала. Траектория строится по следующим критериям: минимальная длина, минимальное количество повротов.

Алгоритм заключается в следующем:

1) составляется массив 8 х a x b, где a и b - стороны прямоугольника, в который вписывается карта.

2) перед началом поиска этот массив заполняется нулями;

3) определяется точка конца траектории;

4) счётчик расстояния и искатель устанавливается на ноль;

5) из найденной точки делается шаг в любом возможном направлении;

6) если шаг параллельно осям координат - к счётчику расстояния прибавляется 10, иначе - 14;

7) значение счётчика записывается в ячейку N x X x Y, где N - направление; X, Y - координаты текущей позиции;

8) искатель увеличивается на 1;

9) происходит поиск ячеек со значением равным искателю;

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

11) если искатель достиг входа увеличиваем счётчик достижений на 1, иначе переход к пункту 8;

12) если счётчик достижений равен менее двух переходим к пункту 8;

13) обратный поиск маршрута: в точке входа находим направление, оценка расстояния которого минимальна;

14) делаем ход навстречу этому направлению;

15) если достигли входа - конец;

16) отыскиваем направление, оценка расстояния в котором минимальна;

17) переход к пункту 14.

Реальный поворот самосвала на карте и в виде траектории моделируется участком ломанной (приложение 2), содержащим излом на ±450 (в зависимости от направления) предполагается, что поворот начинается (заканчивается) раньше (позже) точки излома для ортогонального перемещения на одну дискрету, а для наклонного к осям координат на три. Вид поворота на карте приведён на рис. 2.1. В связи с этим длина прямого горизонтального участка допускается не менее трёх шагов, а наклонного - не менее семи шагов.