ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2014, том 54, № 2, с. 224-255
УДК 519.626
АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ОПЕРАТОРОВ МИНКОВСКОГО И ИХ ПРИМЕНЕНИЕ В ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ1
© 2014 г. П. Е. Двуреченский, Г. Е. Иванов
(141700 М.о., Долгопрудный, Институтский пер., 9, МФТИ (гос. ун-т)) e-mail: givanov@mail.mipt.ru, pavel.dvurechensky@gmail.com Поступила в редакцию 26.06.2013 г.
Исследованы свойства операторов Минковского, обобщающих понятия суммы и разности Минковского на случай, когда одно из множеств—слагаемых суммы (разности) зависит от элемента другого слагаемого. Для операторов Минковского развиты конволюционные методы компьютерной геометрии и разработаны алгоритмы вычисления значений этих операторов. Алгоритмы вычисления операторов Минковского использованы для построения эпсилон-оптимальных стратегий управления в нелинейной дифференциальной игре с невыпуклым целевым множеством. Даны детальные оценки погрешностей предложенных алгоритмов. Приведены результаты численных расчетов для задачи конфликтного управления нелинейным маятником. Библ. 16. Фиг. 3.
Ключевые слова: сумма и разность Минковского, оператор Минковского, дифференциальная игра, оптимальная стратегия управления, вычислительные алгоритмы, погрешность алгоритмов.
DOI: 10.7868/S0044466914020057
1. ВВЕДЕНИЕ
Пусть E — линейное пространство. Суммой и разностью Минковского множеств X с E и Yс E называются соответственно множества
X + Y = {х + y\x е X, y е Y}, X- Y = {x е E\x + Yс X}.
Операторами Минковского многозначного отображения G : E —»- 2E называются операторы Ag : 2E —- 2E и BG : 2E —»- 2E, заданные формулами
AgS = U (x + G(x)), (1.1)
x e S
BgS = E\ (AG( E\ S)) (1.2)
для любого множества S с E.
Заметим, что в случае, когда многозначное отображение G постоянно, т.е. G(x) = G0 при всех x е S, значения операторов Минковского совпадают соответственно с суммой и разностью Минковского:
AGS = S + G0, BGS = S - (-G0).
Таким образом, понятие операторов Минковского представляет собой естественное обобщение понятий суммы и разности Минковского. Известно, что сумма Минковского и алгоритмы ее вычисления широко применяются во многих разделах прикладной математики, таких как вычислительная геометрия (см. www.cgal.org), системы числового программного управления (numerical control), планирование движения роботов (motion planning), теория оптимального управ-
1) Работа выполнена при поддержке РФФИ (код проекта 13-01-00295-а), и ФЦП "Кадры" (соглашение 14.132.21.1347).
ления (optimal control theory) и др. В данной работе рассматривается применение операторов Минковского в нелинейных дифференциальных играх.
„2
Пусть задан набор точек ak е Ire , k = 1, m , причем ak +1 Ф ak для любого k е 1, m - 1. Упорядоченный набор отрезков {[ab a2], [a2, а3], ..., [am— 1, am]} называется ломаной Г(аь ..., am), точки ak называются вершинами, а отрезки [ak, ak +1] — звеньями этой ломаной. Ломаная T(ab ..., am) называется замкнутой, если am = a1. Ломаная r(a1, ..., am) называется простой замкнутой, если m > 1,
am = a1 и из того, что г е [aj, a, +1] n [ak, ak +1], 1 < j < k < m, следует, что k = j + 1 и г = ak. Простым
2
многоугольником называется ограниченное замкнутое множество S с I такое, что его границей dS является простая замкнутая ломаная. Вершинами простого многоугольника S называются вершины ломаной dS. Через d+S и d_S будем обозначать границу простого многоугольника S, ориентированную, соответственно, против часовой стрелки и по часовой стрелке.
2
Выпуклым многоугольником называется выпуклая оболочка конечного числа точек в I . Через (a, Ъ) будем обозначать скалярное произведение векторов a = (a1, ..., an ) е I и Ъ = (Ъ1, ..., bn) е е In: (a, Ъ) = a^ + ... + anbn.
Нормальным конусом выпуклого множества X с I в точке x0 е дХназывается множество
N(x0, X) = {p е W\ (p, х) < (p, xo) Ух е X}.
2
Для любого ненулевого вектора г е I через (0, г ■ да) обозначим луч {tz\t е (0, +да)}. Для любых
22
двух ненулевых векторов a е I и Ъ е I через ZaЪ обозначим множество всех ненулевых векторов, лежащих на лучах, полученных путем вращения луча (0, a ■ да) против часовой стрелки до луча (0, Ъ ■ да).
В следующем разделе описаны алгоритмы вычисления значений операторов Минковского AGS и BGS при выполнении таких предположений: пространство E двумерно; S — простой (вообще говоря невыпуклый) многоугольник; G(x) — выпуклый многоугольник. Предложенные алгоритмы представляют собой развитие известного алгоритма вычисления суммы Минковского двух невыпуклых многоугольников, основанного на построении конволюты.
Понятие конволюты многоугольников введено в [1] и состоит в следующем. Пусть имеются два многоугольника: X с вершинами xi и Yс вершинами у, пронумерованными против часовой стрелки. Конволютой многоугольников X и Y называется упорядоченный набор отрезков вида [X + у, Xi + 1 + у], где Xj + 1 - Xj е Z(y - у,_1)(у + 1 - у), а также отрезков вида X + у, Xj + у + 1], где вектор у, +1 — у, е Z(x, — Xi_ 1)(Xi +1 — Xi). В [2], [3] описаны алгоритмы, позволяющие построить конволюту двух многоугольников и извлечь из нее сумму Минковского этих многоугольников. На сайте www.cgal.org можно найти подробное описание этих алгоритмов, а также программные коды.
2. АЛГОРИТМ ВЫЧИСЛЕНИЯ ЗНАЧЕНИЙ ОПЕРАТОРА МИНКОВСКОГО
Адаптируем алгоритм вычисления суммы Минковского к задаче приближенного вычисления значений операторов Минковского AGS и BGS (см. (1.1), (1.2)).
Через intS, S и dS будем обозначать соответственно внутренность, замыкание и границу мно-
22
жества S. Заметим, что для любой замкнутой ломаной у с I ее дополнение I \у состоит из конечного числа непересекающихся областей, одна из которых неограниченна. Дополнение к этой неограниченной области называется доменом у и обозначается Domain у. Граница домена замкнутой ломаной у называется внешним контуром домена и обозначается через ExtCy: ExtCy = = d(Domainy).
2
Пусть заданы замкнутая ломаная у с I и точка x0 е (Domainy)\y. Замыкание множества всех
2
точек X е I , которые можно соединить с точкой x0 ломаной, не пересекающейся с у, называется внутренним (относительно точки x0) доменом у и обозначается через IntDom^у. Граница внутреннего домена замкнутой ломаной у называется внутренним контуром домена у и обозначается через IntCx у: IntCx у = d(IntDomx у).
Легко видеть, что домен и внутренний домен любой замкнутой ломаной у с [ являются замкнутыми ограниченными связными множествами, причем
ус Domainy, yn int (IntDom^y) = 0 , ExtC усу, IntCXo усу. (2.1)
Следующий простой алгоритм позволяет эффективно вычислять внешний контур замкнутой ломаной.
Алгоритм вычисления внешнего контура
Алгоритм вычисления внешнего контура замкнутой ломаной у = Г(х1, ..., xk, x1), ориентированной против часовой стрелки, состоит из следующих шагов.
Шаг 1. Найдем вершину Xj (1 < i0 < k) с наименьшей ординатой (если таких точек несколько, то выберем среди них точку с наименьшей абсциссой); положим i = i0, l = i0 + 1 (по модулю k), a = xt . Переходим к шагу 2.
Шаг 2. Если на отрезке [a, xl] нет точек пересечения с другими звеньями ломаной у (кроме соответствующих концов соседних звеньев), то переходим к шагу 3, иначе переходим к шагу 4.
Шаг 3. Добавляем отрезок [a, xl] в контур ExtCy, полагаем i = l, a = xl и увеличиваем индекс l на 1 (по модулю k). Если i = i0, то выходим из алгоритма. Иначе переходим к шагу 2.
Шаг 4. Находим г — точку самопересечения ломаной у, лежащую на [a, xl], ближайшую к точке a. Добавляем отрезок [a, z] в контур ExtCy. Находим V — множество таких вершин xj ломаной у, что г е [xy-_ 1, xy], z Ф xj. Среди всех вершин xj е Vнаходим ту, для которой угол между векторами a — z и х} — z, отсчитываемый против часовой стрелки, минимален. Полагаем l = j, a = z, переходим к шагу 2.
Внутренний контур замкнутой ломаной может быть вычислен аналогичным алгоритмом.
2
Правым перпендикуляром для вектора a = (ax, ay) е [ называется вектор
aL = (ay, -ax). (2.2)
2
Заметим, что для любого вектора a е [ справедливо равенство (a1, a) = 0.
2
Пусть задана пара векторов a, b е [ , a = (ax, ay), b = (bx, by). Будем говорить, что пара a, b правая, если (a, b1) > 0, т.е. axby — aybx > 0 и левая, если (a, b1) < 0.
2
Пусть многозначное отображение G каждому вектору x е [ ставит в соответствие выпуклый многоугольник G(x). Пусть Г0 = r(x1, ..., xn, xn +1) — замкнутая ломаная. Для любого j е 1, n обозначим через pj = (xj +1 — xj)1 правый перпендикуляр к j-му звену ломаной Г0, положим p0 = pn.
Для каждого j е 1, n рассмотрим gl , ..., gJm — пронумерованные против часовой стрелки все вер-
шины многоугольника G(xj) такие, что
М(£т, О(х,)) п ар,- р Ф 0 , т е 1, т,. (2.3)
Если условию (2.3) удовлетворяют все вершины многоугольника О(х), то вершину ¿1 будем
определять из условияр, е Щ(¿1 , О(х,)).
Конволютой для многозначного отображения О и замкнутой ломаной Г0 будем называть замкнутую ломаную
^е(Г>) = Г(Х1 + gl, ..., Х1 + Х2 + g1, - -5 Х2 + §Ш25 . • Хп
+ ..., Х„ + gm , Х1 + gl ). (2.4)
Предполагая связность множеств А¡Б, и их дополнений, определим многоугольник АоБ как домен, а многоугольник Во,х0Б — как внутренний (относительно точки х0) домен конволют ^(д+Б) и соответственно:
ВоБ = Domian(^о(д+5)), Во, х0 Б = 1пШотЯо (^о(д-Б)), (2.5)
где х0 — точка, лежащая заведомо во внутренности множества ВСБ.
Используя описанные выше алгоритмы вычисления внешнего и внутреннего контуров, найдем границу многоугольников АоБ и Во, х0 Б:
д(ВоБ) = ЕхЮ(^е(д+Б)), д(Во, х0 Б) = 1п1Сх0(^е(д-Б)). (2.6)
Тем самым мы определим вершины многоугольников АоБ и Во,х0Б, аппроксимирующих соответственно множества А&Б и В&Б.
3. ОЦЕНКИ БЛИЗОСТИ ГРАНИЦ ВЫЧИСЛЯЕМОГО И ИДЕАЛЬНОГО МНОЖЕСТВ
Через Юг будем обозначать замкнутый евклидов шар в [ (круг при n = 2) с центром в нуле и радиусом r:
Ъг = {х е ["||х| < г}.
Здесь и далее |х| — евклидова норма (длина) вектора х е [n.
Отклонением множества Xс [ от множества Yс [ называется величина
h+(X, Y) = inf{г > 0|Xс Y+ ®г}. (3.1)
Хаусдорфовым расстоянием между множествами X с [ и Y с [ называется
h (X, Y) = max
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.