Автоматика и телемеханика, № 5, 2019

Оптимизация, системный анализ

и исследование операций

В.Х. ПШИХОПОВ, д-р техн. наук (pshichop@rambler.ru)

(Научно-конструкторское бюро робототехникии систем управления, Таганрог)

К ОПРЕДЕЛЕНИЮ СЛОЖНОСТИ СРЕДЫ ФУНКЦИОНИРОВАНИЯ

ПОДВИЖНОГО ОБЪЕКТА НА ПЛОСКОСТИ¹

Рассматривается задача формального определения показателей слож-

ности среды подвижного объекта, функционирующего на плоскости при

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

ления сложности. Вводятся понятия локальной и интегральной сложно-

стей среды. Даны расчетные формулы для вычисления сложности. При-

водятся результаты моделирования.

Ключевые слова: подвижный объект, сцена, триангуляция, локальная

сложность, интегральная сложность.

DOI: 10.1134/S0005231019050088

1. Введение

Организации функционирования автономных подвижных объектов (ПО)

в неопределенных, априори недетерминированных, средах сегодня посвяще-

ны многие исследования [1, 2]. При этом выбор стратегий поведения ПО и

алгоритмов планирования траекторий их движений требует при реализации

их систем управления использования новых методов и подходов, привлече-

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

неопределенностей среды функционирования [3]. Причем процедура выбо-

ра этих подходов, адекватно отражающих состояние среды функционирова-

ния, часто носит эвристический характер. В частности, в [3] показано, что в

сложных средах такое комплексирование может приводить к существенному,

до 50%, увеличению значений показателя качества функционирования. Но,

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

средах приводит к незначительному, около 10%, изменению показателя ка-

чества. При этом понятие сложности среды на сегодняшний день во многом

является интуитивным, что не позволяет формализовать процедуру выбора

того или иного подхода к планированию движений подвижного объекта, соот-

ветствующего сложности среды и, следовательно, повысить эффективность

функционирования ПО. Другими словами, требуется формирование коли-

чественно измеримых характеристик среды функционирования подвижного

¹ Работа выполнена при поддержке Российского научного фонда (грант № 18-19-00621).

136

Цi + 1

ПО

Ц_i

Рис. 1. Сцена среды функционирования с ПО.

объекта, позволяющих обоснованно выбирать наиболее подходящий метод

планирования. Это соображение стало основной мотивацией данной статьи,

целью которой является построение меры сложности среды функционирова-

ния подвижного объекта.

Понятие сложности возникает в различных областях исследований. Од-

нако единообразно понимаемого определения сложности нет. “Значение этой

величины должно быть очень близко к определенным мерам сложности, свя-

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

объекта, сложность описания системы, трудность достижения цели, труд-

ность выполнения задачи и т.п.” [4]. Конкретные задачи порождают необ-

ходимость вводить специфические определения этого понятия.

В [5] рассматривается подход к определению сложности сцен с точки зре-

ния визуальной видимости образующих ее поверхностей и в условиях диф-

фузного освещения этих поверхностей. В [6] дается метод оценки сложности

полигональных сцен на основе графов достижимости. Публикация [7] посвя-

щена введению понятия сложности видимой части трехмерной сцены в зави-

симости от точки наблюдения. В [8] дается метод оценки видимой сложности

сцены при анимации, т.е. предпринята попытка разработать методы оценки

сложности изменяющихся сцен. При этом в [6] используется геометрический

подход к описанию сложности, который при большом количестве элементов

на сцене оказывается вычислительно трудоемким, а в [5, 7, 8] используется

вычислительно более простой статистический подход к введению понятия

сложности с точки зрения теории информации. Вместе с тем все эти методы

порождены и связаны с задачами машинной графики и имеют слабое от-

ношение к оценке сложности среды, в которой функционирует автономный

подвижный объект.

Представленная статья посвящена определению количественного показа-

теля сложности плоской среды (сцены) на основе данных системы техниче-

137

ского зрения, имеющей секторный обзор с дальностью H и углом обзора Ω,

как это представлено на рис. 1. Неформальная постановка задачи состоит в

следующем. ПО перемещается на плоской поверхности. Задача объекта — по-

пасть в целевую точку Ц. Как правило, при формировании глобальных тра-

екторий (миссий) ПО перемещается от точки Ц_i к точке Цi+1 вдоль отрезков

прямых, соединяющих эти точки. В случае наличия препятствий П, детекти-

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

сложность среды на основе некоторого скалярного показателя и принять ре-

шение об использовании той или иной стратегии поведения, соответствующей

этой сложности.

Статья организована следующим образом. В разделе 2 приводятся основ-

ные определения и допущения, в условиях которых строится модель сложно-

сти среды. В разделах 3, 4 и 5 вводится триангуляция сцены, ее топологиче-

ское и метрическое описания. В разделах 6, 7 и 8 определяются локальный

и интегральный показатели сложности среды соответственно. В разделе 9

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

сценах.

2. Основные определения и допущения

Примем некоторые упрощающие соглашения относительно подвижного

объекта и препятствий. Будем считать, что все препятствия и сам подвиж-

ный объект представляют собой круги. Круг обладает бесконечной группой

симметрий, что значительно упрощает многие связанные с ним рассужде-

ния и построения. Если реальное препятствие не является кругом, то будем

считать, что оно замещается в расчетах минимальным кругом, содержащим

внутри себя это препятствие. Поэтому размеры препятствий и объекта ха-

рактеризуются одним числом — радиусом представляющего их круга.

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

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

в процессе его функционирования в реальном времени. Для определенности

будем предполагать, что вершина сектора обзора системы технического зре-

ния находится в центре объекта. Сканируемый сектор S всегда симметричен

относительно оси объекта (совпадающей с направлением его движения) и

имеет фиксированный угол Ω при вершине.

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

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

Сторона, противолежащая вершине сектора, может быть произвольной, в том

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

ся результатом сканирования реального пространства. Однако для простоты

будем считать ее тоже прямой и будем называть эти стороны правой, левой

и фронтальной границами сектора S.

Все построения будем рассматривать в прямоугольной системе координат,

связанной с объектом, в которой начало координат совпадает с центром объ-

екта, ось ординат совпадает с осью объекта в направлении его движения, а

ось абсцисс направлена вправо.

Дополнительное допущение состоит в предположении, что пространство

сцены за пределами сканируемого сектора полностью занято препятствиями.

138

ПО

Рис. 2. Примеры предельно простой и предельно сложной среды.

В зависимости от положения цели Цi+1 и подвижного объекта, от коли-

чества, размеров и расположения в секторе препятствий сложность дости-

жения цели подвижным объектом будет различной. Эта “сложность” может

меняться от минимальной, если препятствий вообще нет в секторе S, до мак-

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

маршрут движения к цели (рис. 2).

Под показателем сложности среды δ, определяемым на секторе S, бу-

дем понимать меру, количественно характеризующую сложность достижения

объектом заданной цели в среде, содержащей препятствия. Важно отметить,

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

частности от размеров, количества и расположения препятствий, но и от раз-

меров самого подвижного объекта. Среда, являющаяся относительно простой

для небольшого объекта, может оказаться сложной для габаритного объек-

та, поскольку для него цель может оказаться недостижимой из-за отсутствия

достаточно широких проходов между препятствиями.

Естественно потребовать, чтобы мера сложности была неотрицательной

и удовлетворяла условию нормированности, т.е. 0 ≤ δ ≤ 1, причем равенство

нулю должно соответствовать максимально простой среде, на которой нет

препятствий и траектория движения объекта в которой может быть отрезком

прямой. Равенство единице должно соответствовать максимально сложной

среде, на которой невозможно реализовать движение к цели.

3. Триангуляция и плоское разбиение сектора

Будем считать, что подвижный объект всегда находится в вершине секто-

ра S и Ω = π/2. Введем некоторое полигональное разбиение сектора S:

⋃

S = S_i, m(S_i ∩ S_j) = 0, i = j,

где m(∗) - некоторая площадная мера².

² Введение площадной меры позволяет “расширить” понятие разбиения множества до

разбиения на множество пересекающихся не более чем по границам множеств. Тем самым

области разбиения можно рассматривать как замкнутые, полузамкнутые или открытые

множества.

139

ПО

Рис. 3. Триангуляция центров препятствий.

Две области разбиения называются смежными, если они имеют общую

границу ненулевой длины.

Разбиение сектора приобретает больший смысл и становится легко интер-

претируемым, если связать его с расположением препятствий.

Для определенности будем далее считать, что на сцене заданы n препят-

ствий Π₁, Π₂, . . . , Π_n. Каждое препятствие будем характеризовать тройкой

чисел Π_i = (x_i, y_i, r_i), где x_i, y_i — координаты центра препятствия, а r_i — его

радиус. Центр i-го препятствия будем обозначать p_i(x_i, y_i).

Пусть P = {p₁, p₂, . . . , p_n} — множество центров препятствий. Построим на

этом множестве триангуляцию Делоне [9]. Следует отметить, что триангуля-

ция Делоне, а также двойственная к ней конструкция — диаграмма Вороного

эффективно используются при планировании путей перемещения подвижных

объектов [10]. В частности, в [11, 12] все пространство состояний беспилот-

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

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

пути. Идея использования триангуляции Делоне, связанной с препятствиями

или в более общем случае с местами, представляющими угрозу для движу-

щегося объекта, реализована в [13-15]. Обозначим через

Γ = {γ₁,γ₂,...,γ_k} ⊆ P = {p₁,p₂,...,p_n}

упорядоченную последовательность центров препятствий, принадлежащих

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

порождает плоское разбиение внутренней части сектора, ограниченного кон-

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

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

собой некоторую нерегулярную, возможно, несвязную область (рис. 3). Что-

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

следующим образом.

Рассмотрим правую границу OA сектора S. Через среднюю точку C отрез-

ка OA проведем перпендикулярную к отрезку прямую и на внешней ее части

140

p_R

Рис. 4. Построение вспомогательных центров препятствий.

выберем точку p_R. Построим окружность с центром в точке p_R, проходящую

через точки O и A (рис. 4).

Отрезок OA можно рассматривать как хорду, стягивающую дугу окруж-

ности OA. При удалении точки p_R от сектора S дуга окружности будет

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

ности будетпрактическисовпадать с ней. Круг с центром в точке pR ра-

₌

диуса r_R =

pRA

pRO будем рассматривать как виртуальное препят-

ствие Π_R = (p_R, r_R) = (x_R, y_R, r_R). С помощью аналогичных построений вве-

дем виртуальные препятствия Π_L и Π_F с центрами в точках p_L и p_F для

левой и фронтальной границ сектора соответственно.

Нетрудно убедиться, что виртуальные препятствия будут определяться

следующими параметрами:

(

√

)

Π_R = (p_R,r_R) = (x_R,y_R,r_R) = t,H - t,

t² + (t - H)²

(

√

)

Π_L = (p_L,r_L) = (x_L,y_L,r_L) =

-t,H - t,

t² + (t - H)²

(

√

)

Π_F = (p_F ,r_F ) = (x_F ,y_F ,r_F ) =

0, t,

H² + (t - H)²

где H (см. рис. 1) — длина осевой линии сектора, а t — достаточно большая

положительная величина. Например, можно положить t = 100H.

Следует заметить, что виртуальные препятствия будут по построению пе-

ресекаться за пределами сектора S. Однако этот факт можно игнорировать,

поскольку препятствия виртуальны, их введение носит формальный харак-

тер и обусловлено необходимостью построить на основе триангуляции Делоне

правильное плоское разбиение всего сектора. Очевидно, что при введении

описанным образом дополнительных точек построенная ранее триангуляция

Делоне не изменится, но при этом добавятся новые треугольные области,

имеющие в качестве одной или двух своих вершин центры виртуальных пре-

пятствий.

141

В результате этих построений получим триангуляцию Делоне совокупно-

сти точек, определяемых центрами препятствий, и трех центров виртуальных

препятствий. При таком построении сектор S будет находиться строго внут-

ри выпуклой оболочки триангуляции (при достаточно большом значении t),

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

сечение сектора S с полученной триангуляцией порождает его плоское раз-

биение. Важно отметить, что все плоские области в секторе S окажутся по

построению во взаимно однозначном соответствии с треугольными областями

полученной триангуляции точек {p₁, p₂, . . . , p_n} ∪ {p_R, p_L, p_F }.

Все внутренние грани полученного разбиения сектора S будут треуголь-

никами Делоне, а граничные, т.е. имеющие одно или два ребра, совпадаю-

щих с границами сектора, — четырехугольниками. При этом можно считать

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

динных перпендикуляров. В этом случае граничные области (в том числе и

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

дикулярны к соответствующим границам, что упрощает в последующем их

метрический анализ³.

4. Топологическое описание триангуляции.

Ширина пути. Проходимость среды

Для описания полученного разбиения сектора S построим граф G =

= (X, U), |X| = N, |U| = M, следующим образом. Вершины графа взаимно

однозначно соответствуют N областям разбиения сектора. При этом две вер-

шины смежны в том и только в том случае, если соответствующие области

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

внутри некоторой области разбиения, отображаются в одну и ту же вершину

графа. Оказывается, что при описанном построении триангуляции количе-

ство n препятствий, количество M ребер и количество N плоских областей

разбиения сектора связаны между собой простыми соотношениями.

Утверждение.

1) N = 2n + 1;

2) M = 3n + 3.

Доказательство утверждения приведено в Приложении.

Точки, определяющие местоположение объекта и цели, окажутся внут-

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

дествлены с некоторыми вершинами построенного графа. Если они окажутся

отождествленными с одной и той же вершиной, то сложность сцены равна

нулю. Поэтому будем считать, что подвижный объект и цель соответствуют

различным вершинам графа.

³ Если говорить о свободных областях (не занятых препятствиями) при таком разби-

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

и пятиугольными (для угловых граней). Кроме того, помимо прямолинейных они будут

содержать также и криволинейные границы.

142

Возможный переход на графе из одной вершины в другую соответствует

перемещению объекта из одной области плоского разбиения в соседнюю об-

ласть. При этом объект неизбежно должен пересечь воображаемый отрезок,

соединяющий центры соседних препятствий. Надо учесть, что препятствия

имеют ненулевые габариты и по предположению являются кругами. Поэтому

если соседние препятствия имеют координаты центров (ξ_i, η_i) и (ξ_j , η_j ) и соот-

ветственно радиусы r_i и r_j, то для подвижного объекта радиуса ρ промежуток

между препятствиями будет доступным для прохождения, если выполняется

условие достаточности его “ширины”:

√

(ξ_i - ξ_j )² + (η_i - η_j )² - r_i - r_j - 2ρ > 0.

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

больше, чем удвоенный радиус подвижного объекта.

Каждое ребро на графе G = (X, U) взаимно однозначно соответствует

какому-то ребру на триангуляции. Поэтому каждому ребру на графе G =

= (X, U) можно приписать вес, характеризующий его “ширину”. Другими сло-

вами, можно ввести определенную на ребрах из U функцию w(u): если

w_ij = w(u_ij) = w ((x_i,x_j)) ,

то

{√

(ξ_i - ξ_j)² + (η_i - η_j )² - r_i - r_j - 2ρ, если это выражение больше нуля,

w_ij =

в противном случае.

Предположим теперь, что G = (X, U, w) — взвешенный граф триангуля-

ции Делоне, причем x_ПО — вершина, соответствующая области, содержащей

объект, а x_Ц — вершина, соответствующая области, содержащей цель. Пусть

P_i = xi1 xi2 ... xil+1 — некоторый путь из x_ПО в x_Ц длины l, т.е. xi1 = x_ПО,

xil+1 = x_Ц. Введем для удобства обозначение I_n = {1,2,... ,n}. Шириной пу-

ти будем называть величину w (P_i) = min w(uik,ik+1), где ui_k,ik+1 — ребро,

k∈I_l

соединяющее вершины xik и xik+1 . Другими словами, ширина пути равна

наименьшей ширине среди всех ребер, образующих этот путь.

Пусть теперь P = {P₁, P₂, . . . , P_L} — множество путей, соединяющих x_ПО

и x_Ц . Тогда под проходимостью среды можно понимать максимальную ши-

рину среди всех путей: γ(x_Ц ) = max w (P_i).

i∈I_L

5. Матричная процедура вычисления проходимости

Для вычисления проходимости γ (x_Ц ) можно воспользоваться простой

матричной процедурой [16]. Рассмотрим матрицу смежности R = ∥r_ij ∥ графа

G = (X,U,w), где

^{w(uij ), если xi и xj смежны,

r_ij =

в противном случае.

143

Матрица R имеет размеры N × N или в силу приведенного утверждения —

(2n + 1) × (2n + 1), а количество ненулевых элементов в ней равно 6n.

Максиминная композиция R2) =R ◦ R матрицы R с собой определяет-



ся по правилу: R⁽²⁾ = R ◦ R =

r⁽

, где r⁽

= max (min(r_ik,r_kj)). В этом

k∈I_N

случае r(2)ij равно максимальной ширине среди ширин всех путей длины 2,

соединяющих вершины x_i и x_j . В частности, это означает, что существует

по крайней мере один путь длины 2 из x_i в x_j, ширина которого равна r(2)ij.

Далее индуктивно определяем



n+1)



R⁽³⁾ = R⁽²⁾ ◦ R =

r⁽

 , ... , R(n+1) =R(n) ◦R=

r⁽

 , ...

Теперь заметим, что для любых i и j все пути из x_i в x_j распадаются на непе-

ресекающиеся классы путей топологической длины 1, 2, . . . При этом некото-

рые из этих классов могут быть пустыми. Поэтому поиск ширины наиболее

“безопасного” пути сводится к выбору наиболее “безопасного” пути среди наи-

более “безопасных” путей в каждом классе, т.е. max r(k)ij.

k∈I∞

Учитывая рефлексивность отношения, задаваемого графом G, при вычис-

лении максиминных “степеней” матрицы достаточно ограничиться лишь мат-

рицами R⁽¹⁾ = R, R⁽²⁾, . . . , R(N-1), поскольку R(N-1) = R(N) = R(N+1) = . . .

Поэтому если, например, x_ПО = x_i, а x_Ц = x_j , то γ (x_Ц ) = max r(k)ij.

k∈IN-1

6. Локальная мера сложности среды

Проходимость среды γ как характеристика сложности сцены неудобна, по-

скольку она, с одной стороны, выражается в абсолютных единицах расстоя-

ния, т.е. зависит от выбранного масштаба измерений, а с другой — не удо-

влетворяет требованию нормированности. Рассмотрим выражение для меры

сложности, связанное с вычисляемыми проходимостями и лишенное указан-

ных недостатков. Точнее, будем рассматривать меру сложности как функ-

цию δ(γ) от проходимости γ.

Заметим, что с ростом γ естественно считать, что сложность δ(γ) долж-

на уменьшаться. При этом если γ достаточно велико, а δ(γ) соответствен-

но мало, то дальнейшее увеличение γ будет лишь незначительно уменьшать

сложность. Напротив, при малых проходимостях сложность сцены должна

быть большой, а небольшие увеличения γ должны приводить к быстрому

уменьшению сложности. Таким образом, можно считать, что скорость изме-

нения сложности при любом значении достижимости γ обратно пропорцио-

нальна значению сложности при том же значении γ, т.е. δ^′(γ) = -αδ(γ), где

α — некоторая положительная константа, характеризующая эту зависимость.

Отсюда сразу получаем, что δ(γ) = Ce^-αγ, где C — постоянная интегриро-

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

При γ = 0 цель для объекта недостижима и сложность такой среды макси-

мальна. Принимая во внимание требование нормированности меры сложно-

сти 0 ≤ δ(γ) ≤ 1, получаем, что δ(0) = C = 1. Свойство неотрицательности

144

выполняется автоматически. Таким образом, δ(γ) = e^-αγ . При этом когда γ

увеличивается до бесконечности, то сложность стремится к нулю.

Параметр α определяет скорость убывания сложности с ростом γ. Выбор α

можно осуществить, например, следующим образом. Поскольку предельное

значение δ(γ) = 0 формально достигается только при γ = ∞, то для реаль-

ных задач можно считать, что сложность “практически” равна нулю, если

δ(γ) ≤ ε, где ε — малое положительное число. С другой стороны, можно пола-

гать, что сложность практически равна нулю, если проходимость превышает

радиус ρ подвижного объекта более чем в k раз. Другими словами, мож-

но считать, что ε = e^-α·kρ, откуда α = -lnεkρ . С учетом этого выражение для

меры сложности приобретает вид δ(γ) = ε^kρ . Полагая, например, ε = 0,01, а

k = 20, получаем δ(γ) = 10^-10ρ.

Значение проходимости среды, следовательно, и введенной меры сложно-

сти зависит от заданных координат p(x, y) цели. Поэтому выражение для

меры сложности следует понимать как функцию δ (γ(p)) = e-αγ(p). Другими

словами, при изменении положения цели или соответствующей ей точки в

секторе сложность будет, вообще говоря, меняться. По этой причине данное

выражение целесообразно назвать локальной мерой сложности среды, т.е.

сложностью относительно фиксированной точки, определяющей конкретное

положение цели.

7. Интегральная мера сложности с точечными препятствиями

Возникает вопрос, как охарактеризовать сложность среды вообще, т.е. без-

относительно к заданной цели. Один из возможных подходов состоит в том,

чтобы ввести некоторую характеристику, интегрально учитывающую слож-

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

ляться целью. Такую меру естественно назвать интегральной мерой слож-

ности среды. Подобная задача возникает, например, в том случае, если ко-

ординаты цели заранее неизвестны, но сообщаются подвижному объекту в

процессе его перемещения либо координаты могут изменяться с течением

времени. Построить интегральную меру можно следующим образом.

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

туальных) являются точечными, т.е. имеют нулевой радиус. Предположим

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

объект, имеет номер 1. Обозначим через δ∗1(p) сложность достижения по-

движным объектом, находящимся в вершине сектора S, произвольной точки

p(x, y) ∈ S. Тогда в качестве интегральной характеристики сложности среды

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

∫

Δ(S) =

δ∗1(p)dp,

m (S)

где m (S) — площадь сектора S.

Для всех точек p, которые находятся внутри треугольника Делоне с номе-

ром k, величина проходимости является постоянной, т.е. γ(p) = r1k и, значит,

145

Внутренние треугольники

Граничные области

Угловые области

ПО

Рис. 5. Классы областей.

δ∗1(p) = δ1k = e-αr1k . Таким образом, функция δ∗1(p) является кусочно-посто-

янной на S. Поэтому, обозначая через S_k k-ю область плоского разбиения

сектора S, а через m (S_k) — ее площадь, получаем:

∫

∑

Δ(S) =

δ∗1(p)dp =

m (S)

k=1 S_k

(1)

∑

m(S_k)

e-αr1k m(S_k) =

e-αr1k .

m(S)

m (S)

k=1

Здесь m (S) = H², где H — длина осевой линии сектора S.

Формула (1) получена в предположении, что препятствия являются точеч-

ными. В этом случае она допускает простую вероятностную интерпретацию.

Если точка, задающая цель, является равномерно распределенной в S случай-

ной величиной, тоm(Sk)m(S) — вероятность появления точки в области S_k. Тогда

выражение (1) есть математическое ожидание функции локальной сложно-

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

При известных координатах центров препятствий величины m (S_k) можно

вычислить геометрически. Однако формулы для их вычисления будут раз-

личными, поскольку области S_k являются фигурами нескольких разных гео-

метрических классов (рис. 5), а именно:

1) все внутренние области будут треугольниками;

2) граничные области будут трапециями (в предположении бесконечной

удаленности виртуальных препятствий), у которых одна из сторон совпадает

с границей сектора, причем углы, образуемые этой стороной, прямые;

3) три угловые области будут четырехугольниками, которые составлены

из двух прямоугольных треугольников, имеющих общую гипотенузу.

Во всех случаях площади m (S_k) легко определяются геометрически, если

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

146

Таблица

Области плоского

Площади m(S_k) областей

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

Внутренние треугольники

|(x₂ - x₁)(y₃ - y₁) - (x₃ - x₁)(y₂ - y₁)|

Правые граничные области

|(x₁ - y₂)² - (x₂ - y₁)²|

Левые граничные области

|(x₁ + y₂)² - (x₂ + y₁)²|

Фронтальные граничные области

|x₁ - x₂| · (2H - (y₁ + y₂))

Угловая область, содержащая начало

(y² - x²)

координат

Правая угловая область

(2(H - x)² - (x - y)²)

Левая угловая область

(2(H + x)² - (x + y)²)

ние области (треугольники) задаются координатами трех точек, граничные —

двух, а угловые — координатами одной единственной точки. Соответствую-

щие формулы для площадей указанных областей приведены в таблице.

В построенной триангуляции Делоне тип плоской области легко опреде-

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

область образована внутренними вершинами (центрами реальных препят-

ствий), то это внутренний треугольник. Если среди вершин имеется одна,

задающая центр виртуального препятствия, то это граничная область, при-

чем, если эта вершина — точка p_R, то это правая граничная область, если p_L —

левая граничная область, если p_F — фронтальная граничная область. Нако-

нец, если среди вершин имеются две точки, задающие центры виртуальных

препятствий, то это угловые области. Наличие точек p_R и p_L означает, что

это угловая область, содержащая начало координат, точки p_R и p_F означа-

ют, что область является правой угловой областью, а p_L и p_F — левая угловая

область.

8. Интегральная мера сложности с неточечными препятствиями

Построенная интегральная мера получена в предположении, что препят-

ствия являются точечными. Ею можно приближенно пользоваться и в том

случае, если размеры препятствий существенно меньше размеров сектора и

их можно примерно считать точечными. Если же размеры препятствий со-

измеримы с размерами сектора, то эта формула будет давать существенные

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

рассматривать разбиение области сектора, которая не занята препятствиями.

Если предположить, что каждое препятствие полностью находится внутри

сектора, то, очевидно, площадь области, не занятой препятствиями, равна

∑

m (S) = m (S) - (суммарная площадь всех препятствий) = H² - π r2i.

i=1

147

p^k2

^k3

^k2

^k1

r^k1

^k3

p^k3

Рис. 6. Площадь области, не занятая препятствиями.

Соответственно площадь m(Sk) области Sk, не занятая препятствиями

(рис. 6), равна

(

)

m(S_k) = m(S_k) -

r2k

ϕk₁ + rk2 ϕk₂ + rk3 ϕk₃

где rk1 , rk2 и rk3 — радиусы препятствий с центрами в соответствующих вер-

шинах pk1 , pk2 и pk3 треугольника S_k, а ϕk1 , ϕk2 и ϕk3 — внутренние углы при

этих вершинах.

Формула упрощается, если радиусы всех препятствий равны, т.е. r₁ = . . . =

= r_n = r. Тогда для всех треугольных областей и для четырехугольных гра-

ничных областей разбиения

m (S_k) = m (S_k) -πr22^{.Дляугловыхобластей}

выражения для площадей будут иметь вид:

πr

для угловой области, содержащей начало координат:

m(S_k) = m(S_k) -

3πr

для остальных угловых областей:

m (S_k) = m (S_k) -

Если количество препятствий достаточно велико, то, допуская некоторую

неточность, можно считать, что площади всех областей разбиения определя-

ются одинаковой формулой m (S_k) = m (S_k) -πr22^{.Вэтомслучаеполучаем,}

что

∑

m(S_k) -¹²πr²

Δ (S, r) =

e-αr1k .

H² - nπr²

k=1

Покажем, что при сравнительно небольших значениях радиусов r вместо

этой формулы можно приближенно пользоваться более простой формулой

для точечных препятствий. Для этого оценим относительную погрешность

такой замены. Перепишем выражение для Δ (S, r) так:

(

)

∑

m (S_k)

( r ⁾2

∑

Δ (S, r) =

e-αr1k -

e-αr1k

( r ⁾2

H²

1 - nπ

k=1

148

5000

4000

3000

2000

1000

0,6

0,8

1,0

1,2

1,4

1,6

1,8

2,0

Рис. 7. Гистограмма отношений средней сложности к интегральной сложности.

Заметим, что первое слагаемое в скобках — интегральная мера сложно-

сти Δ(S) для точечных препятствий. Обозначим

∑

e-αr1k и τ =

k=1

Величину A можно интерпретировать как среднюю сложность сцены. Тогда

(

)

Δ(S,r) =

Δ(S) -N2 πAτ²

1 - nπτ²

Поскольку τ значительно меньше единицы и положительно, то разложим

последнее выражение по формуле Маклорена, удержав три члена: Δ (S, r) ≈

(

)

≈Δ(S)+π

nΔ(S) -N2 A

τ² (линейный член отсутствует, поскольку первая

производная Δ (S, r) в точке ноль равна нулю). Учитывая, что в силу при-

веденного ранее утверждения N = 2n + 1, получаем выражение для относи-

тельной погрешности:



|Δ (S, r) - Δ (S)|



2n + 1



≈π

−

² =

ⁿ

^τ

Δ (S)

Δ(S)



π(2n + 1)



².

^τ

^ 2n + 1^-

Δ (S)

Исследуем статистически дробьAΔ(S) , которая представляет собой отно-

шение средней сложности к интегральной сложности сцены. Далее, на рис. 7

приведена гистограмма распределения значений этой дроби, полученная по

10000 реализаций. Из нее видно, что 0,85 ≤AΔ(S) ≤ 1,5. Поэтому при любых

значениях n = 1, 2, . . . выполняется неравенство



0≤^

^≤

2n + 1

Δ (S)

Следовательно,

|Δ (S, r) - Δ (S)|

π(2n + 1)

≤

τ².

Δ (S)

149

Это соотношение показывает, что относительная ошибка вычислений инте-

гральной сложности по формулам для точечных препятствий пропорцио-

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

Таким образом, чтобы относительная ошибка не превышала заданную по-

грешность ε, количество препятствий n и их радиус r должны удовлетворять

√

2ε

неравенству r ≤ H

. Например, для ε = 0,05, H = 100 и n = 10 полу-

π(2n+1)

чаем r ≤ 12.

9. Моделирование

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

сложности для двух типовых сцен [1], представленные на рис. 8 и 9. Для каж-

дой из сцен приведены графики изменения локального δ и интегрального Δ

показателей сложности и их производных^δ, Δ по времени в функции прой-

денного пути. На всех сценах положение цели фиксировано и имеет коорди-

наты (x, y) = (20, 20). Размер подвижного объекта ρ = 3. На рис. 8 случаи а-г

соответствуют: а — локальная сложность 0,04, интегральная сложность 0,07;

б — локальная сложность 0,35, интегральная сложность 0,35; в — локальная

сложность 0,22, интегральная сложность 0,16; г — локальная сложность 1,00,

интегральная сложность 1,00.

На рис. 9 случаи а-г соответствуют: а — локальная сложность 0,10, инте-

гральная сложность 0,07; б — локальная сложность 0,10, интегральная слож-

ность 0,14; в — локальная сложность 0,75, интегральная сложность 0,55; г —

локальная сложность 1,00, интегральная сложность 1,00.

10. Заключение

В статье рассмотрена задача формального определения количественных

оценок сложности среды функционирования подвижного объекта, переме-

щающегося на плоскости. На основе физически интерпретируемой величи-

ны, характеризующей возможность прохождения среды с препятствиями, по-

строена нормированная локальная мера сложности в секторе обзора системы

технического зрения, зависящая от расположения цели, к которой должно

осуществляться движение. Введена интегральная мера сложности сцены, не

зависящая от положения цели, но характеризующая сложность среды. При-

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

ложенных процедур.

Поскольку задача вычисления мер сложности решается достаточно быст-

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

ритмами планирования движения подвижного объекта в реальном времени в

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

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

в меняющихся сценах можно постоянно вычислять сложность или ее произ-

водные и выбирать алгоритм управления подвижным объектом в зависимо-

сти от изменяющихся условий в среде, в которой функционирует объект.

150

Очевидным обобщением полученных результатов является решение ана-

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

перемещающихся в трехмерном пространстве. Особый интерес представляет

также построение мер сложности для сред, информация о которых характе-

ризуется неполнотой и/или неопределенностью.

ПРИЛОЖЕНИЕ

Доказательство утверждения. Поскольку получаемое разбие-

ние является плоским графом, то оно удовлетворяет формуле Эйлера

V - M + N = 2, где V — общее количество вершин триангуляции, включая

виртуальные. В этой формуле учитывается также и внешняя грань. Если

ее не принимать во внимание, то V - M + N = 1. В рассматриваемом слу-

чае V = n + 3, поэтому n - M + N = -2. Заметим теперь, что количество

граней и количество ребер связаны очевидным равенством M =3N+J2 , где

J — количество ребер, лежащих на внешнем контуре триангуляции Делоне.

По описанному построению такими являются ребра, соединяющие вирту-

альные препятствия, т.е. J = 3, следовательно, M =3N+32 . Таким образом,

n - 3N+32 + N = -2, откуда следует первое доказываемое равенство. Второе

получается подстановкой найденного равенства в выражение для M. Утвер-

ждение доказано.

СПИСОК ЛИТЕРАТУРЫ

1. Интеллектуальное планирование траекторий подвижных объектов в средах с

препятствиями / Под ред. В.Х. Пшихопова. М.: Физматлит, 2014.

2. Path Planning for Vehicles Operating in Uncertain 2D Environments / Ed.

V. Pshikhopov. Elsevier, Butterworth-Heinemann, 2017.

3. Интеллектуальные технологии планирования перемещений подвижных объек-

тов в трехмерных недетерминированных средах / Под ред. В.Х. Пшихопова.

М.: Наука, 2017.

4. Li W. On the Relationship Between Complexity and Entropy for Markov Chains and

Regular Languages // Complex Syst. 1991. V. 5. P. 381-399.

5. Feixas M., del Acebo E., Bekaert Ph., Sbert M. An information Theory Framework

for the Analysis of Scene Complexity // EUROGRAPHICS’99. 1999. V. 18. No. 3.

6. Niepel L., Martinka J., Ferko A., Elias P. On Scene Complexity Definition for

Rendering // WSCG’95, Plzen. 1995. P. 209-217.

7. Plemenos D., Sbert M., Feixas M. On Viewpoint Complexity of 3D Scenes // Int.

Conf. Graphicon. 2004. Moscow, Russia. http://www.graphicon.ru/

8. Rigau J., Feixas M., Sbert M. Visibility Complexity of a Region in Flatland //

EUROGRAPHICS. 2000.

9. Скворцов А.В. Триангуляция Делоне и ее применение. Томск: Изд-во Томск.

ун-та, 2002.

10. Qu Yaohong, Zhang Yintao, Zhang Youmin. A Global Path Planning Algorithm

for Fixed-wing UAVs // Intell. Robot Syst. Springer Science+Business Media. 2018

V. 91. No. 3-4. P. 691-707.

11. Kim D., Sugihara K. Voronoi Diagram of a Circle Set from Voronoi Diagram of a

Point Set: I. Topology // Comput. Aided Geom. Des. 2001. V. 18. No. 6. P. 541-562.

153