8. Пример

Рассмотрим пример работы алгоритма трехмерного вертикального разделения ячеек. Путь дано пространство обобщенных координат с известными запрещенными точками, точками q⁰ и q^T (рис. 19).

Рисунок 19 – Пространство обобщенных координат

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

2) Построим матрицы TFR для каждой плоскости:

TFR1	TFR2	TFR3
1 2 1 1-3 2 1-1 3-3 3 1-1 3-3	1 2 1 1-3 2 1-1 3 1-1 3-3	1 2 1 1-3 2 1-1 3-3 3 1-3

3) Построим матрицы LCR для каждой плоскости:

4) Построим матрицы ETFR для каждой плоскости:

5) Построим ELCR:

6) Построим матрицу TUR и проверим достижимость q⁰ и q^T:

Так как точки q⁰ и q^T принадлежат одной единой области, то они достижимы.

7) Построим маршрут (рис. 20):

№ шага	Координата: плоскость, строка TFR, столбец TFR, номер узла (снизу вверх)	Количество шагов
1	1, 1, 1, 3 1, 3, 2, 3 Так как эти шаги равнозначны, то выберем первый	1 1
2	2, 1,1, 2	1
3	3, 2,1, 1 qT достигнута	1

Рисунок 20 – Построение маршрута

Библиографический список

1. Корицкий А.В., Алгоритм разделения ячеек. Отчет по гранту РФФИ №05-08-01199а. Красноярск. СибГАУ, 2007.

Примеры решения задач

Рассмотрим рабочую сцену

Точки, указанные на рабочей сцене, имеют следующие координаты:

E=(-40,30), F=(-40,130), G=(-20,130), H=(20,130), K=(40,130), L=(40,30), P=(20,30), R=(20,70), Q=(-20,70), S=(-20,40), T=(-40,30), W=(-20,30), N₁=(-40,-1), N₂=(40,-1), N₃=(-40,-10), N₄=(40,10).

Длина каждого звена – 25 точек.

Необходимо вычислить все конфигурации, в которых МР налегает хотя бы на одно препятствие. Расставим на звеньях МР системы координат в соответствии с алгоритмом Денавита-Хартенберга.

Поскольку МР двухзвенный, то его конфигурационное пространство будет двухмерным. Дискретизируем конфигурационное пространство, то есть наложим на него сетку (см.рис.2). Обобщённые координаты должны удовлетворять ограничениям

0^o≤ q_i<360^o, i=1,2. (1)

Возьмём точку А, её координаты равны :

q^A=(q₁^A, q₂^A)=(0^o, 0^o).

Это какая-то конкретная конфигурация МР (см. рис. 1). Теперь для этой конфигурации будем проверять каждую точку МР, принадлежит ли она внутренней области хотя бы одного препятствия.

Координаты точек Р_о, Р₁, Р₂ в системе (x₀, y₀) вычисляем по формулам:

=0

=0

=

Если известны координаты r^Pi и r ^Pi+1 концов Р_i и Р_i+1 отрезка P_i P_i+1 , (i=0,1) (см. рис.3) , то вычисление координат произвольной точки A_i осуществляется по формуле:

^{= = ,}

t[0;1]

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

Теперь нужно вычислить координаты этой точки в системе координат, связанной с препятствием. Учитывая то, как расставлены системы координат на препятствиях, выведем формулы для получения координат точки в системах координат, связанных с препятствиями, из системы координат (x₀, y₀) (Таблица 1).

Таблица 1

xП1=x0+40	xП2=x0+20	xП3=x0-20	xП4=x0+40
yП1=y0-30	yП2=y0-70	yП3=y0-30	yП4=y0+10

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

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

Если

х_п^о≤ ≤х_п²

И (2)

у_п^о≤ ≤у_п¹ ,

то точка A_i принадлежит внутренней области препятствия и, следовательно, вся конфигурация q^A является запрещённой.

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

Для рабочей сцены, приведенной на рис.1, был спланирован путь на основе алгоритма A*. Стартовая конфигурация q⁰=(0º, 0º), целевая конфигурация q^T=(30º, 140º), шаг дискретизации равен 10º, длина каждого звена составляет 27 точек. Ограничения на обобщенные координаты соответствуют (1). Спланированный программой путь представлен на рис.5. Путь соединяет точки q⁰ и q^T. Можно видеть, что значительная работа была потрачена на вычисление всех запрещенных конфигураций, большинство из которых манипулятор на своем пути не встретил. В декартовом пространстве путь выглядит так, как показано на рис. ?.