Содержание

Алимов Н. А., Ерофеева В. А. , Шалымов Д. С. (СПбГУ, ИПМАШ) Анализ возможностей методов классификации для автоматизации работы дефибриллятора                            3

Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В. (СПбГУ, ИПМАШ) Экспериментальный стенд для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока              31

Барковский Е. А. Реализация менеджера памяти в work-stealing балансировщике                  56

Сазонов А. М. (ИПМИ КарНЦ РАН) Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей  66

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 13

Выпуск 1

Издательство С.-Петербургского университета

2 0 1 7

УДК 519.712

БКК 32.811.7

С82

Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия: Б. Т. Поляк (ИПУ РАН),

А. В. Соколов (ИПМИ КарНЦ РАН),

П. С. Щербаков (ИПУ РАН)

С82 Стохастическая оптимизация в информатике. Том 13 (Вып. 1) / Под ред. О. Н. Граничина — СПб.:

Издательство С.-Петербургского университета, 2017. — 80 с. ISSN 1992–2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2–12 — в 2006–16 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск двенадцатого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2016–17 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №16-07-00890-а.

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

ББК 32.811.7

© Авторы статей, 2017

 

Анализ возможностей методов классификации для автоматизации работы дефибриллятора[1]

Н. А. Алимов, В. А. Ерофеева, Д. С. Шалымов[2]

Санкт-Петербургский государственный университет Институт проблем машиноведения РАН alimov.nsm@gmail.com victoria@grenka.net dmitry.shalymov@gmail.com

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

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

       1.      Введение

Фибрилляция желудочков является одним из самых распространенных случаев нарушения работы сердца, приводящим к внезапной сердечной смерти. Выживаемость для пациентов, подверженных риску смерти такого рода, довольно низка (от 10% до 20%) [8]. Пациенты зачастую умирают из-за того, что вовремя не получают лечения. Появление автоматических внешних дефибрибриляторов позволяет своевременно провести реанимационные действия, восстановив сердечный ритм посредством нанесения удара.


Основой работы автоматических дефибрилляторов является анализ электрокардиограмм и принятие решения на его основе. В последнее время широко распространены исследования, направленные на повышение точности алгоритмов анализа сердечного ритма. В работе [10] для выделения характеристик ритма при его анализе авторы используют вариационную модовую декомпозицию (англ. Variational Mode Decomposition) с последующей классификацией на основе метода опорных векторов (англ. Support Vector Machine). В работе [19] предложен композитный алгоритм, объединяющий анализатор динамики изменения наклонов ритма с цифровым фильтром, для разделения ритма на две группы — с возможностью нанесения удара дефибриллятором и без нее соответственно. В [12] авторами предложено использование статистических методов для классификации ритма трех типов (нормальный синусовый, фибрилляция желудочков, желудочковая тахикардия) с предварительным выделением признаков на основе временной и частотной областей, а также изменений наклонов ритма. Работа [13] направлена на выявление наиболее информативных признаков для процедуры классификации на основе метода адаптивного порога для определения различных пиков ритма. Классификация ритмов на основе использования нейронной сети рассматривалась в [9]. В работе [4] авторы исследуют применимость сверточных нейронных сетей для выявления желудочковой тахикардии, отмечая, что фиксированный набор признаков может быть неприменим в классификации реальных случаев из-за высокой вариабельности ритма между различными пациентами.

Большинство работ основывается на анализе небольшого числа открытых баз данных электрокардиограмм, позволяя сделать вывод о том, что получение данных, особенно значительного для процедуры классификации размера, для этой задачи весьма затруднителено. Тем не менее, на сегодняшний день получили свое развитие методы, применимые к выборкам малого размера [6]. Преимуществом этих методов также является устойчивость к внешним помехам в наблюдениях [1,2,14], которые зачастую присутствуют в электрокардиограммах. В работах [15,16] рассматриваемые методы успешно апробированы на задаче в области механики.

Работа построена следующим образом: В разделе 2 приводится общая постановка задачи с описанием особенностей решаемой проблемы. В разделе 3 отмечены существующие открытые базы данных электрокардиограмм, описаны их недостатки, а также приведено описание собственной базы данных, собранной с дефибрилляторов обычного типа (неавтоматизированных). В разделе 4 рассматривается сравнительный анализ распространенных методов машинного обучения на предмет их применимости в задаче автоматизации дефибриллятора, а также возможная архитектуру взаимодействия с дефибриллятором. В разделе 5 приведено описание программного обеспечения. В разделе 6 даются заключительные выводы по работе и планы на будущее.

       2.        Постановка задачи

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

Начало сердечного цикла в здоровом сердце происходит в синоатриальным узле, расположенном в правом предсердии. Действуя подобно естественному кардиостимулятору, синоатриальный узел инициирует импульс с регулярными интервалами от 60 до 100 раз в минуту. Электрический импульс распространяется через междольные пути, активируя (деполяризуя) предсердия, что заставляет их сокращаться и перекачивать кровь в желудочки. Атриовентрику-

Рис. 1: Проводящая система сердца.

лярный узел собирает и задерживает импульс, позволяя закончить фазу сокращения желудочков заполнением кровью. Затем импульс пересекает стенку между желудочками и разделяется на правую и левую ветви, переходя далее в сеть проводящих волокон, называемых волокнами Пуркинье. Импульс быстро распространяется по этой сети, деполяризуя желудочки и производя единое сокращение. Затем клетки сердца возвращаются в исходное состояние (реполяризуются) с переходом в рефрактерный период, в течение которого они не могут быть деполяризованы снова. Рефрактерный период препятствует возврату импульса в предсердия.

Электрическая активность сердца, регистрируемого электродами, расположенными на поверхности тела, называется электрокардиограммой или ЭКГ. На рисунке 2 показана запись ЭКГ нормального ритма сердца, называемого нормальным синусовым ритмом. Он состоит из Р-волны, QRS-комплекса и Т-волны, вызванной деполяризацией предсердий, деполяризацией желудочков и реполяризацией желудочков соответственно. Реполяризация предсердий отмечается комплексом QRS.

Внезапное прекращение механической активности сердца, под-

Рис. 2: ЭКГ синусового ритма в норме.

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

Наиболее частой причиной внезапной сердечной смерти является проявление фатальных желудочковых аритмий: фибрилляции желудочков (ФЖ) и желудочковой тахикардии (ЖТ), представленных на рисунке 3. В период фибрилляции желудочки быстро деполяризуются и реполяризуются, сердце нарушает свою скоординированную работу и возможность эффективно прокачивать кровь. Единственный действенный способ прекратить фибрилляцию желудочков и восстановить сердечный ритм — дефибрилляция, полученная через передачу электрического удара в сердце. Фибрилляция желудочков обусловлена быстрым повторным возбуждением миокардиальных волокон с неэффективным сокращением желудочка. Условие фибрилляции идентифицируется отсутствием комплексов QRS на ЭКГ. Дефибрилляция деполяризует миокард и заканчивает нерегулярные сокращения, возвращая работу сердца к нормальному регулярному ритму в случае успеха.

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

Рис. 3: ЭКГ синусового ритма в норме.

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

Требуется по набору тестовых данных построить классификатор, относящий сформированный до момента времени t ритм работы сердца человека к одному из классов — ударный/неударный (shockable/non-shockable), максимизируя при этом вероятность положительного исхода применения процедуры дефибрилляции.

       3.        Описание данных

В большинстве работ, посвященных рассматриваемой тематике, используются две открытые базы данных [5]:

    Creighton University Ventricular Tachyarrhythmia Database (CUDB) содержит 35 одноканальных записей, каждая из которых составляет около 8 минут. Путем сегментации каждой записи на множество коротких эпизодов по 10 секунд каждый была создана база данных, содержащая группы электрокардиограмм с ударными ритмами (фибрилляция желудочков и желудочковая тахикардия) и неударными (синусовый ритм, суправентрикулярная тахикардия, асистолия и другие) [11].

    MIT-BIH Malignant Ventricular Arrhythmia Database (VFDB) включает в себя 22 двухканальные записи длительностью 35 минут. Сигналы аналогично разделены на ударные (трепетание и фибрилляция желудочков, желудочковая тахикардия) и неударные группы [7].

Проблема указанных баз данных состоит в том, что на их основе можно построить классификацию типа ритма, но при этом нет никаких сведений об исходе применения процедуры дефибрилляции. Для решения этой проблемы была собрана собственная база данных, содержащая 170 записей по 9 секунд каждая. Каждая запись была отнесена к одному из двух классов — ROAE и NoROAE (дефибрилляция помогла и не помогла соответственно). На основе полученных записей было сформировано 19 признаков, перечисленных в таблице 1.

Таблица 1: Описание признаков.

Признак

Единица измерения

Расшифровка

 

та

MA

mV

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

WA

mV

Амплитуда волны: среднее значение различий между пиком и следующим минимальным

AmpMax

mV

Максимальное          значение сигнала

AmpMin

mV

Минимальное значение сигнала

 

PTT

mV

Peak-To-Trough: разница между максимумом и

минимумом

PPA

 

Peak-Peak Amplitude: 4-х секундная трассировка ЭКГ разделяется на четыре сегмента по одной секунде каждый. Для каждого сегмента находится разница между максимальным и минимальным значениями. Вычисляется среднее четырех значений, полученных на предыдущем шаге.

MS

mV/s

Средний наклон

MedS

mV/s

Медиана наклона

AMSA

mV Hz

Amplitude Spectrum Area: сумма абсолютных значений произведений между амплитудой спектральной плотности и соответствующей частотой

absAMSA

mV Hz

abs Amplitude Spectrum Area: абсолютное значение суммы прозведений между амплитудой спектральной плотности и соответствующей частотой

PSA

mV 2 Hz

Power Spectral Analysis: сумма абсолютных значений произведений между удельной мощностью спектра и соответствующей

частотой

ENRG

mV 2

Energy: интеграл от удельной мощности спектра

CF

Hz

Centroid Frequency: частота “центра масс” удельной мощности спектра

 

частоты F такое, что 95% энергии сигнала ниже F

SMF

dB

Spectral Flatness Measure: отношение геометрического и среднего арифметического

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

4. Сравнительный анализ методов машинного обучения для задачи автоматизации дефибриллятора

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

Accuracy score. Применительно к многоклассовой классификации, метрика отражает точность классификации для каждого отдельного класса или для всех классов вместе взятых. Если все предсказанные системой значения класса соответствуют истинным, то точность равна единице, в ином случае нулю. Пусть yˆi — предсказанное значение класса для i-го набора данных и yi соответствующее истинное значение, тогда доля корректных прогнозов от общего размера выборки nsamples определяется как:

accuracy,

samples i=0

где 1(x) — функция-индикатор события.

AUC score. Агрегированная характеристика качества классификации, вычисляемая как площадь под кривой ошибок (ROCкривая). Кривая ошибок, в свою очередь, отражает зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила.

Confusion matrix. Матрица неточностей (англ. Confusion Matrix) строится на основе подсчета количества раз, когда система приняла верное и неверное решение относительно истинного значения класса принадлежности (true positives (tp) — истино-положительное решение; true negatives (tn) — истино-отрицательное решение; false positives (fp) — ложно-положительное решение; false negatives (fn) — ложно-отрицательное решение), а именно: Оценка системы

 

Class 0

Class 1

Class 0

True negatives (tn)

False positives (fp)

Class 1

False negatives (fn)

True positives (tp)

В бинарной классификации под терминами “положительное решение” и “отрицательное решение” понимается оценка принадлежности входных данных к определенному классу на основе решения классификатора, а под “истинным решением” — класс, заданный человеком. В этом контексте, можно определить характеристики точности (precision), полноты (recall) и F-меры (F-measure) следующим образом:

precision ,

recall ,

Fβ = (1 + β2)β2 · precision×+ recall. precision              recall

В анализе методов машинного обучения применительно к задаче автоматизации дефибриллятора в работе использовались следующие методы: метод ближайших соседей (Nearest Neighbors) [20], дерево принятия решений (Decision Tree) [21], метод случайного леса (Random Forest) [3], нейронные сети (Neural Net) [22], AdaBoostSAMME [17], наивный байесовский классификатор (Naive Bayes) [18], метод опорных векторов (RBF SVM) [23]. При проведении процедуры обучения использовался скользящий контроль (англ. CrossValidation) с разбивкой на четыре блока.

4.1. Метод ближайших соседей (Nearest Neighbors) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.931.000.96310

ROAE0.830.170.2830 avg / total0.920.920.90340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.90690.93020.91660.9404 AUC score0.74430.81730.73190.8265


Рис. 4: Матрица неточностей для метода ближайших соседей.

4.2. Дерево принятия решений (Decision Tree) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.950.950.95310

ROAE0.530.530.5330 avg / total0.920.920.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.90690.87200.91660.8809 AUC score0.72430.73070.68830.8766 Рис. 5: Матрица неточностей для дерева принятия решений.

4.3. Метод случайного леса (Random Forest) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.940.990.96310


ROAE0.820.300.4430 avg / total0.930.930.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.94180.96510.92850.9523 AUC score0.86050.92060.79030.9397 Рис. 6: Матрица неточностей для метода случайного леса.

        4.4.             Нейронная сеть (Neural Net)

Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support


No ROAE0.920.990.96310

ROAE0.670.130.2230 avg / total0.900.920.89340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

                                                  0.9069     0.9418    0.9166      0.9285

                                                    0.7676     0.7708     0.6289     0.5510


Рис. 7: Матрица неточностей для нейронной сети.

                               4.5.          AdaBoost-SAMME

Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.950.970.96310

ROAE0.600.500.5530 avg / total0.920.930.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

                                                                          0.9186    0.9302    0.9285      0.9285

                                                                            0.7820     0.7884     0.7012     0.8571

Рис. 8: Матрица неточностей для метода AdaBoost-SAMME.

4.6. Наивный байесовский классификатор (Naive Bayes) Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.970.910.94310

ROAE0.430.670.5230 avg / total0.920.890.90340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

                                                                          0.9186    0.8837    0.8928      0.8690

                                                                            0.7812     0.9038     0.8218     0.9053

Рис. 9: Матрица неточностей для наивного байесовского классификатора.

                               4.7.               Метод опорных векторов (RBF SVM)

Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.911.000.96310

ROAE1.000.030.0630 avg / total0.920.910.88340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

Accuracy score         0.9069   0.9069   0.9285   0.9166 AUC score0.8525 0.8669  0.7235 0.9721


Рис. 10: Матрица неточностей для метода опорных векторов.

            4.8.            Анализ полученных результатов

Результаты применения методов машинного обучения к задаче классификации электрокардиограмм показывают, что на их основе возможно провести автоматизацию работы дефибриллятора. Тем не менее, выбор конкретного метода классификации затруднителен из-за низких показателей точности по классу ROAE вследствие довольно малой выборки относительно второго класса. В рассматриваемом случае наиболее перспективным представляется использование методов машинного обучения, способных к обучению на выборках малого размера. В дальнейшем также возможна интеграция системы классификация с основной работой дефибриллятора. Приведем одну из возможных архитектур на примере дефибриллятора Physio Control LIFEPAK 12 (см. Рис. 11). Для синхронизации данных в этом случае можно использовать программу от производителя устройства — CODE-STAT. Для соединения дефибриллятора с компьютером следует использовать кабель LIFEPAK Monitor to PC (версия для USB).

Рис. 11: Схема взаимодействия классификатора с дефибриллятором.

            5.         Программное обеспечение

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

Для решения проблемы разнообразия реализаций алгоритмов, автоматизации процесса решения задач машинного обучения и повышения воспроизводимости результатов было разработано специальное программное приложение для решения задач машинного обучения общего назначения. Это программное обеспечение имеет следующие особенности:

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

2.    Добавление алгоритмов. Реализована возможность загружать алгоритмы, написанные на языке Python в виде скрипта в определҷнном виде.

3.    Библиотека алгоритмов. Помимо загрузки своих алгоритмов система обладает уже предзагруженными алгоритмами, которые пользователь может переиспользовать.

4.    Нахождение наилучший алгоритм из представленных. Реализован поиск наилучшего алгоритма для представленных данных.

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

            5.1.          Архитектура системы

Основные элементами архитектуры системы являются:

    cтруктура базы данных;

    взаимодействие клиента и сервера;

    способ хранения моделей/данныx/результатов;

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

Структура базы данных

Разработана структура базы данных, представленная на Рис. 12.

Рис. 12: Структура базы данных.

Клиент-серверное взаимодействие

Взаимодействие клиента и сервера построена на использовании JSON (специализированный текстовый формат) для передачи данных. Необходимо было согласовать какие поля отвечают за каждый тип передаваемых значений. В итоге получилось простое и надҷжное API (интерфейс приложения), позволяющее пользователю гарантированно получить требуемый результат.

Хранение моделей

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

Анализ и результаты классификации

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

            5.2.           Программная реализация

При написании кода использовался паттерн MVC (Model-ViewController). Код хорошо продокументирован, в некоторых местах даны необходимые пояснения в виде комментариев.

Клиентская сторона

Основной клиентский код был написан на JavaScript и Angular JS (первая версия).

Серверная сторона

Для реализации серверной части были использованы:

    язык программирования Python;

    микрофреймворк Flask;

    библиотека машинного обучения и анализа данных scikit-learn;

    библиотеки scipy, numpy, matplotlib для языка Python;

    база данных SQLite;

    библиотека для языка Python Keras.

Программный интерфейс

Примеры реализациии программного интерфейса представлены на рисунках 13, 14, 15, 16, 17, 18.

Рис. 13: Главная страница.

Рис. 14: Создание нового проекта.

Рис. 15: Загрузка данных.

Рис. 16: Добавление алгоритма.

Рис. 17: Выбор алгоритма.

Рис. 18: Результаты анализа данных.

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

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

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

Список литературы

[1]      Граничин О.Н. Введение в методы стохастической оптимизации и оценивания. Учебное пособие. - СПб.: Изд-во С.-Петерб. университета, 2003, 131с.

[2]      Сенов А.А., Граничин О.Н. Идентификация параметров линейной регрессии при произвольных внешних помехах в наблюдениях // В сб. трудов XII Всероссийское совещание по проблемам управления (ВСПУ-2014), Россия, Москва, ИПУ РАН, 16-19 июня 2014. 2014. С. 2708–2719.

[3]      Breiman L. Random Forests // Machine Learning. 2001. Vol. 45. No. 1. P. 5–32.

[4]      Chandra B. S., Sastry C. S., Jana S. Subject-specific detection of ventricular tachycardia using convolutional neural networks // Computing in Cardiology Conference (CinC). 2016. P. 53 – 56.

[5]      Goldberger A.L., Amaral L.A.N., Glass L., Hausdorff J.M., Ivanov

P.Ch., Mark R.G., Mietus J.E., Moody G.B,. Peng C.-K., Stanley H.E. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. 2000. Vol. 101. Issue 23. P. 215–220.

[6]      Car´e A., Csaji B.C., Campi M.C., Weyer. E. Finite-Sample System Identification: An overview and a new correltation method // IEEE Control Systems Letters. 2017. Vol. 2. Issue 1. P. 61–66.

[7]      Greenwald S.D. Development and analysis of a ventricular fibrillation detector // M.S. thesis, MIT Dept. of Electrical Engineering and Computer Science. 1986.

[8]      Mattioni T., Kanaan N., Riggio O., et al. Performance of an automatic external cardioverter-de brillator algorithm in the discrimination of supraventricular from ventricular tachycardia // The American journal of cardiology. 2003. Vol. 91. Issue 11. P. 1323–1326.

[9]      Ming Y., Guang Z., Taihu W., Biao G., Liangzhe L., Chunchen W., Dan W., Feng C. Detection of shockable rhythm using multiparameter fusion identification and BP neural network // 2nd IEEE International Conference on Computer and Communications (ICCC). 2016. P. 798 – 802.

[10]   Nguyen M.N., Nguyen B.V., Kim K. Shockable Rhythm Diagnosis for Automated External Defibrillators Using a Modified Variational Mode Decomposition Technique // IEEE Transactions on Industrial Informatics. 2017. Vol. PP. No. 99.

[11]   Nolle F.M., Badura F.K., Catlett J.M., Bowser R.W., Sketch M.H. CREI-GARD, a new concept in computerized arrhythmia monitoring systems // Computers in Cardiology. 1986. Vol. 13. P. 515–518.

[12]   Ramakrishnan S., Akshaya V., Kishor S., Thyagarajan T. Real Time Implementation of Arrhythmia Classification Algorithm using Statistical Methods // Trends in Industrial Measurement and Automation (TIMA). 2017. P. 1–4.

[13]   Ramakrishnan S., Yogeswaran R. Design and Analysis of Feature Extraction Algorithm for ECG signals using Adaptive Threshold Method // Trends in Industrial Measurement and Automation (TIMA). 2017. P. 1–8.

[14]   Senov A., Amelin K., Amelina N., Granichin O. Exact confidence regions for linear regression parameter under external arbitrary noise // In: Proc. of the 2014 American Control Conference (ACC), 4-6 June, 2014, Portland, USA.

[15]   Volkova M.V., Granichin, Petrov Y.V., Volkov G.A. Dynamic fracture tests data treatment based on the randomized approach // Advances in Systems Science and Applications (ASSA), 2017, no. 3, pp. 35-43.

[16]   Volkova M., Granichin O., Petrov Yu., Volkov G. Sign-perturbed sums approach for data treatment of dynamic fracture tests // In:

Proc. of the 56th IEEE Conference on Decision and Control, December 12-15, 2017, Melbourne, Australia.

[17]   J. Zhu, H. Zou, S. Rosset, T. Hastie Multi-class AdaBoost // Statistics and Its Interface. 2009. Vol. 2. No. 3. P. 349–360.

[18]   H. Zhang The Optimality of Naive Bayes // Proc 17th International Florida Artificial Intelligence Research Society Conference. 2004.

[19]   Zhang F., Li P., Jiang F., Lai D. A shockable rhythm detection algorithm for automatic external defibrillators by combining a slope variability analyzer with a band-pass digital filter // 2014 IEEE Workshop on Electronics, Computer and Applications. 2014. P. 828 – 831.

[20]   Nearest Neighbors. URL: http://scikit-learn.org/stable/modules/ generated/sklearn.neighbors.KNeighborsClassifier.html

[21]   Decision       Tree.       URL:      http://scikit-

learn.org/stable/modules/generated/ sklearn.tree.DecisionTreeClassifier.html

[22]   Neural          Net.        URL:      http://scikit-learn.org/stable/modules/ generated/sklearn.neural_network.MLPClassifier.html

[23]   Support        Vector    Machines.             URL:      http://scikitlearn.org/stable/modules/svm.html

 

Экспериментальный стенд для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока[3]

Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В.[4]

Санкт-Петербургский государственный университет,

Институт проблем машиноведения РАН

{konstantinamelin, ngranichina, deryugin.denis, ivanskiy.yuriy}@gmail.com

В статье рассматривается функционирование стенда, имитирующего крыло самолета с подвижными элементами («перьями»), в условиях турбулентного воздушного потока. За счет поворота подвижных элементов в двух плоскостях в зависимости от характеристик воздушного потока над элементом крыла снижается эффект болтанки. Путем использования механизма обратной связи между соседними элементами крыла осуществляется переходный процесс от неуравновешенного состояния, при котором разница отклонений давлений от их значений в ламинарном потоке сильно отличается на разных участках крыла, к конечному числу кластеров с одинаковым отклонением давлений, а затем к синхронизации всех элементов крыла и окончательному выравниванию разницы давления. Синхронизация осуществляется за счет применения мультиагентного алгоритма, основанного на методе скоростного градиента. В статье описывается математическая модель крыла с подвижными элементами, излагается постановка задачи синхронизации элементов крыла, приводится алгоритм синхронизации, перечисляется элементная база используемых датчиков, проводится анализ результатов имитационных экспериментов.

Ключевые слова: метод скоростного градиента, мультиагентные технологии, переходный процесс, самолет с «перьями», турбулентность.

            1.      Введение

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

Одним из ключевых недостатков традиционных методов анализа и управления системами является предположение о том, что модель описания окружающей среды является заранее известной и точной. На практике часто приходится сталкиваться с различными сложностями. Например, в ряде случаев приходится иметь дело с приближенными моделями (в отсутствие точной модели или по причине неудобства модели для вычислений) и искаженными входными данными (для большинства измерений характерно наличие помех и “выбросов”). Более того, существует возможность технических сбоев, частично или полностью выводящих из строя различные компоненты системы. К тому же, в ряде случаев может меняться и структура пространства состояний.

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

Как было показано в [1,2,3,4], ряд природных явлений имеет смысл рассматривать как процессы с переменной структурой пространства состояний. Изменение структуры пространства состояний приводит к изменению внутренней структуры системы, а взаимодействие элементов системы, в свою очередь, приводит к изменению системы в целом [5]. При рассмотрении турбулентности в жидкостях, газах, мультифазовых и пластических потоках окружение может рассматриваться в качестве подобной системы [6,7]. Примером таких систем может служить практически любая биологическая система. О динамическом формировании структур можно говорить и в рамках социологии, психологии и экономики [8].

Из-за изменения числа степеней свободы даже фиксированный набор переменных для построения математической модели неравновесного процесса, как строго доказано в неравновесной статистической механике [9], никогда не будет полным. Следовательно, неравновесные системы в природе не могут быть описаны в полной мере с помощью традиционных дифференциальных моделей для динамических систем. Для описания таких переходных процессов следует использовать более гибкие математические модели. Эти модели должны уметь приспосабливаться к изменению внешней среды, например, с помощью механизма внутренней обратной связи.

Мультиагентные системы могут быть использованы для эффективного решения широкого спектра проблем, связанных с возмущениями и нестационарными системами [10]. Эффективность решения достигается заменой большой и сложной модели набором простых локальных моделей. Согласованное поведение некоторой подгруппы агентов приводит к уменьшению размерности пространства состояний [11,12]. Возмущения внешней среды могут приводить к нарушению согласованности в поведении некоторых групп агентов, что будет соответствовать увеличению размерности пространства состояний.

В последнее десятилетие проблемы взаимодействия в распределенных системах управления все больше привлекает внимание исследователей [13,14,15,16]. Этот интерес обусловлен растущим количеством прикладных областей, связанных с управлением в распределенных электрических сетях, межпроцессорным взаимодействием, беспроводными, транспортными и промышленными сетями, сетями датчиков, БПЛА, координацией мобильных роботов и

т. п.

В [17] предлагалось использовать мультиагентную систему для решения проблем, связанных с движением в турбулентном потоке. Эта задача не имеет аналитического решения, и в настоящее время используются различные упрощенные модели, а значит, использование мультиагентного подхода может оказаться эффективным.

В этой статье рассматривается математическая модель и устройство экспериментального стенда для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока.

            2.          Синхронизация перьев самолета

В турбулентном потоке ветра на разные “перья” действуют разные силы, их результирующая приводит к изменению траектории полета и быстрым вращениям вокруг центра тяжести, что вызывает эффект болтанки. Согласно результатам неравновесной статистической механики большие градиенты макроскопических полей посредством взаимодействия между элементами системы сглаживаются за счет пространственно-временных корреляций. Этот процесс описывает переход от турбулентного режима обтекания самолета к ламинарному. Например, если рассмотреть только тангенциальную компоненту импульса турбулентного потока, действующего на обтекаемую поверхность самолета, то пойдет процесс формирования кластеров, а когда все возмущающие силы становятся равными 1, то турбулентный режим сменяется ламинарным диссипативным обтеканием. В результате такого перехода энергия турбулентного потока преобразуется в кинетическую энергию поступательного движения самолета E1 с диссипативными потерями, которая приводит к изменению траектории полета. Проблема заключается в том, что естественный процесс сглаживания медленный, тогда как турбулентный ветровой поток изменяется очень быстро. Использование электромагнитных полей для передачи сигналов между элементами системы приводит к ускорению процесса выравнивания силовых полей, индуцированных турбулентными потоками ветра и действующими на поверхность самолета, что будет препятствовать возникновению резких и разнонаправленных ускорений движения самолета.

            2.1.             Формализация постановки задачи

Будем считать, что самолет движется прямолинейно в горизонтальной плоскости и поверхность его крыла состоит из n конечных элементов (“перьев”) a1,a2,...,ai,...,an. Здесь и далее верхний индекс i,i N = {1,2,...,n} обозначает номер “пера” i, а не степень. “Перья” могут изменять свои углы наклона αi к поверхности крыла в определенных границах от значения αдо α+ и поворачиваться в плоскости крыла на угол βi в диапазоне от βдо β+. Эти наклоны и повороты позволяют изменять вертикальную и продольную составляющие возмущающих сил, действующих на “перо”.

Для каждого i = 1,2,...,n будем использовать следующие обозначения: f0i — интегральная сила

f,

действующая на i-е перо в ламинарном потоке ветра до момента времени t1, приложенная к центру пера и направленная перпендикулярно его поверхности,

— величина силы f0i,

 — угол наклона пера i до момента времени t1, i0 — угол поворота пера i до момента времени t1,

 — вертикальная проекция силы, действующей на i-е перо:

,

 — продольная проекция силы, действующей на i-е перо:

, fi — интегральная возмущающая сила

fi(t) = ∫ f(r,t)dr,

ai

действующая на i-е перо в момент времени t t1, приложенная к центру пера и направленная перпендикулярно его поверхности, fi — величина силы fi, αi(t) — угол наклона пера i в момент времени t, βi(t) — угол поворота пера i в момент времени t, zi — вертикальная проекция силы fi, xi — продольная проекция силы fi,

r — интегральное отклонение воз-

мущающей силы fi от стационарного значения f0i при ламинарном обтекании.

Заметим, что при изменении углов αi(t) и βi(t) естественно изменяются векторы fi, а также величины zi и xi, которые равны соответственно zi = ficos(αi) и xi = fisin(αi)cos(βi). Кроме того, в силу введенных обозначений имеем

(1)

                                                                                                                              .        (2)

О п р е д е л е н и е 1. Будем говорить, что “перья” синхронизированы в момент времени t, если совпадают все отклонения  для всех i,j N.

В ламинарном потоке при сохранении углов

все “перья” синхронизированы, так как 0 ∀i,j N.

Л е м м а 1. Если начиная с некоторого момента времени t1 + τ все “перья” самолета синхронизированы, то суммарные вращательные моменты вокруг оси движения (продольной оси) и вертикальной оси равны нулю.

Будем считать, что “перья” являются некоторыми интеллектуальными агентами, которые стремятся выровнять с остальными свои отклонения моментов . Для каждого пера i обозначим через Ni множество его соседей, от которых перо i может получать информацию для принятия решения об изменении своей ориентации и которым оно может передавать информацию о своем состоянии. Для варьирования значимости информации от пера i для пера j и наоборот введем нормированные весовые ко-

эффициентывсех остальных парbi,j = (bi,jj,i), у которых нет связи между собой, опре-: ∑jNi bi,j = 1. Полагая bi,j = 0 для

делим симметричную матрицу смежности B = [bi,j]. В дальнейшем потребуются следующие понятия из теории графов и обозначения: 1n n-мерный вектор из единиц, GB — неориентированный граф связей с матрицей смежности B; взвешенная степень узла iграфа GB — сумма элементов i-й строки матрицы B : di(B) = n=1 i,j;diag{di(B)} — диагональная матрица из взвешенных стеb j

пеней узлов; dmax(B) — максимальная взвешенная степень узла графа GB; L(B) = (diag{di(B)} − B) — Лапласиан графа GB; ·T — операция транспонирования вектора или матрицы; B— Евкли-

дова норма: B∥ = √∑i j(bi,j)2; Tr(B) — след матрицы B (сумма диагональных элементов); λ2(B) — вещественная часть второго по абсолютной величине собственного числа матрицы B; λmax(B) — вещественная часть максимального по абсолютной величине собственного числа матрицы B. Граф GBsg называется подграфом графа GB, если bi,jsg bi,j для всех i,j N. Говорят, что граф GB содержит остовное дерево, если существует дерево Gtr, являющееся подграфом GB. Так как L(B)c1n = 0 при любом c, то любой вектор из одинаковых констант является собственным вектором матрицы Лапласиана L(B), соответствующим нулевому собственному значению. Если граф GB содержит остовное дерево, то кратность нулевого собственного значения матрицы Лапласиана L(B) равна единице (см. [13] или [14]) и, следовательно, |λ2(B)| > 0. Вектор из всех первых двух проекций отклонений моментов ,

обозначим D , и опреде-

лим качество выравнивания отклонений с помощью функционала Лапласа [19]

                                .                      (3)

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

Приведенные выше рассуждения обосновывают следующую формализованную постановку задачи: Требуется при переходе самолета на некотором интервале времени [t1,t2] от равномерного прямолинейного полета в условиях ламинарного обтекания потоком воздуха к полету в зоне турбулентности в условиях возмущений выбрать для каждого “пера” i N такие законы изменения углов наклона αi и поворота βi

                                                α˙i(t) = uiα(t), β˙i(t) = uiβ(t),                                      (4)

которые обеспечили бы для функционала качества Q(D(t)), начиная с некоторого момента времени t1 + τ, выполнение целевого условия

                                                             |Q(D(t))| ≤ ε                                                   (5)

для задаваемого достаточно малого параметра ϵ > 0 при достаточно большом значении t2 > t1 + τ.

2.2.      Использование метода скоростного градиента и оценка времени переходного процесса

Для описания процесса выравнивания сил воспользуемся принципом скоростного градиента (Speed-Gradient Principle, SG) [20,21]. Согласно этому принципу все физические системы эволюционируют по наискорейшему пути в направлении термодинамического равновесия, которому соответствует максимальное значение энтропии. В рамках алгоритма скоростного градиента максимальному приращению энтропии отвечает минимальное значение функционала качества Q. Следуя общей схеме алгоритма скоростного градиента [21], выведем формулы для оптимального закона управления (4). Для Q˙ имеем

                        .               (6)

Из вида (3) функционала Q и свойств Лапласиана графа GB выводим

            ,         (7)

а из (1)-(2) получаем

(8)

(9)

(10)

В соответствии с принципом скоростного градиента надо выбрать такие законы изменения для α˙i и β˙i, чтобы все слагаемые в суммах в (6), умноженные на , были отрицательными. Для этого при условии fi = 0̸ можно взять

(11)

(12)

с некоторым параметром (коэффициентом усиления) γ > 0.

Последние соотношения (11), (12) вместе с (7)–(10) позволяют выписать закон управления.

Если fi = 0, то α˙i = β˙i = 0, иначе

(13)

Т е о р е м а 1. Пусть ε > 0 и для k = 1,2 обозначим через Dk(t1+) предел Dk(t) при t t1 справа. Если граф GB содержит остовное дерево и выполнены сделанные выше предположения, тогда закон управления (13)–(14) обеспечивает достижение цели управления (5) за время не более, чем

где

.

З а м е ч а н и е 1. Важно подчеркнуть мультиагентную природу протокола управления (13)–(14), в котором управляющие сигналы для наклона и поворота “перьев” генерируются только на основании данных о своем состоянии и о состоянии соседних “перьев”.

З а м е ч а н и е 2. Характерное время процесса определяется обратной величиной коэффициента усиления 1и может быть сделано сколь угодно малым. Но в реальной физической системе параметр γ не может быть выбран произвольно большим, так как его выбор будет зависеть от скорости срабатывания датчиков давления и реализации соответствующих команд управления поворотами и наклонами “перьев”.

З а м е ч а н и е 3. Еще одной важной особенностью протокола управления (13)–(14) является то, что в нем нет явной “привязки” к моменту времени t1, при котором изменяется структура набегающего потока. Этот факт “снимает” необходимость решения традиционно сложной задачи “о разладке” (см., например, [22]). Углы наклона “перьев” начинают автоматически изменяться по обратной связи при нарушении согласованности моментов возмущающих сил. Это позволяет легко распространить полученные результаты, используя тот же протокол управления (13)–(14), на случай многократного изменения структуры турбулентного потока в моменты времени t1,t2,...,tm,... при выполнении дополнительного условия: maxm>0{tm+1 tm} >> τ.

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

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

3.1.      Упрощенная математическая модель турбулентного потока

Турбулентный поток действует не постоянно, а возникает в некоторый момент времени. Таким образом, давление воздуха на различные участки поверхности описывается следующим образом. До момента времени t1 на поверхность воздействует ламинарный поток, т. к. pk = wk, где wk — центрированные помехи, соответствующие неточному измерению давления. В момент времени t1 возникает возмущение, которое действует до момента времени t2, после которого может либо вернуться ламинарный поток воздуха, либо появиться турбулентный поток с новыми параметрами. Можно предположить, что турбулентный поток формирует конечное число возмущений, каждое из которых может быть представлено как нормально распределенное с некоторыми коэффициентами.

Таким образом, давление в точке x в момент времени t может быть выражено как

 (16)

3.2. Программная реализация фреймворка для работы с МАС

При аппаратной реализации каждое из роботизированных устройств взаимодействует только со своими соседями (Рис. 1).

Рис. 1: Роботизированные элементы и связь между ними.

Для проведения экспериментов был разработан фреймворк (см. Рис. 2) на языке Python, позволяющий обрабатывать данные о работе системы, строить графики и визуализировать состояние системы в реальном времени.

Фреймворк состоит из двух основных модулей.


Рис. 2: Фрейморк для работы с мультиагентными системами.

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

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

    Упрощенная модель турбулентного потока (16).

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

    Протокол локального голосования из [23].

    Алгоритм для выравнивания давления, предложенный в [2].

    Алгоритм (1), (13), который после дискретизации принимает вид

 ,

где Pr[α+](·) — проектор в интервал [α+], γ — размер шага,  — начальные условия, −1), ¯ im = ri(fmi −1 sin(αmi −1) −  и отправляют сигнал на исполнительный механизм, исполнительный механизм его принимает и устанавливает постоянный угол наклонана весь следующий интервал времени [tm,tm+1].

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

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

                3.3.          Стенд для испытаний

Для проверки обоснованности рассматриваемой новой постановки задачи и работоспособности нового алгоритма разработан экспериментальный стенд, позволяющий проводить реальные физические эксперименты [24].

Экспериментальный стенд выполнен в виде крыла самолета с двояковыпуклым профилем Eppler, на который могут воздействовать разнообразные потоки ветра. Размах крыла 1 m при хорде 0,5 m. Почти вся поверхность крыла покрыта пластинами (“перьями”) с датчиками давления. Количество пластин — n = 100 шт. Размер одной пластины 60 mm × 60 mm.

Пластины равномерно размещены по поверхности со смещением каждого ряда относительно друг друга на 30 mm. Таким образом у каждой пластины имеется максимум шесть соседей. Для измерения давления используется чувствительный аналоговый датчик давления (барометр), который показывает как увеличение давления, так и разряжение на поверхности пластины. Угол наклона пластин αi

Рис. 3: Фрагмент стенда моделирования.

может меняться с помощью приводов (см. Рис. 3) с целью изменения давления воздуха на них. Сбор данных и генерирование сигнала управления ШИМ выполняются с помощью отладочных плат STM32F3DISCOVERY. Задачу управления каждой пластиной, сбор данных с датчиков и взаимодействие с соседями осуществляет микрокомпьютер Arduino Micro, с возможной скоростью обновления данных каждые 0,001 сек. Для управления сервоприводом используется ШИМ с постоянным уровнем напряжения 5 В, постоянной частотой импульсов в 50 Гц и переменной длительностью рабочей части импульса от 0,9 мс до 2 мс, где 1,5 мс является средним положением сервопривода, а отработка из крайнего в крайнее положение занимает 0,1 сек и представляет собой поворот движущейся части на 60 град. Поворот пластин пока не реализован. Сбор данных со всех плат Arduino Micro происходит на отладочных платах Arduino Mega 2560 R3. Одна плата Arduino 2560 обеспечивает взаимодействие с 14 платами Arduino Micro. В стенде используется 7 плат Mega. В экспериментах исследуется топология связи, при которой каждый элемент связан с шестью соседями. В дополнение на пластинах установлены светодиоды для индикации статуса достижения синхронизации. Для обеспечения разнообразных потоков ветра используется шесть вентиляторов общей мощностью в 500 Вт.

Такт работы микроконтроллера выбран h = 0,03 сек. За это время все микрокомпьютеры собирают данные с датчиков f¯mi = fi(tm)

Рис. 4: Соединение платы с сервоприводом.

(здесь и далее моменты времени tm = t1+h(m−1),m = 1,2,...), отправляют и принимают данные от соседей, обрабатывают данные по алгоритму.

Передача данных между микрокомпьютерами формируется посредством цифровых портов. В один и тот же момент каждый микрокомпьютер, после расчетов, отправляет информацию на шесть соседей с одного порта и принимает шесть сигналов с шести других портов. Для передачи информации был разработан протокол, основанный на двоичной системе, в котором давление на датчик имеет градацию от 0 до 10, а начало сообщения содержит три нуля. В связи с этим пластинка перемещается на угол от 0 до 30 град. с шагом в 3 град., что соответствует вращению сервопривода на угол от 0 до 45 град. с шагом в 4,5 град. Задержка отработки сигнала на исполнительных механизмах: поворот подвижной части механизма (качалки) на 60 град. происходит за 0,1 сек., на 4,5 град. за 0,0075 сек.

Вся информация от плат Arduino дублируется в главном компьютере для профилировки и визуализации результатов. На теку-

Рис. 5: Отладочная плата STM32F3DISCOVERY.

щем этапе проекта исследуются работоспособность алгоритма (17) при различных выбираемых пользователем параметрах γ и bi,j. Проведенные эксперименты показывают достаточно высокую скорость протекания переходных процессов, обеспечивающих синхронизацию отклонений моментов возмущающих сил относительно оси по направлению движения самолета. На данный момент выявлена достаточно сильная дискретизация работы исполнительных механизмов, что сказывается на перераспределении. Протокол дорабатывается для увеличения числа ступеней в 3 раза.

                4.          Моделирование работы алгоритма

Для управления поведением системы, функционирующей по алгоритму (17), можно изменять следующие параметры.

Рис. 6: Движение в ламинарном потоке (математическая модель) (t < t0).

    Размер шага γ.

    Отрезок [αk;αk+], в пределах которого изменяется α.

    Топологию системы (т.е. матрицу связей B).

    Соотношение сил ламинарного и турбулентного потоков.

На Рис. 9, 10, 11, 12 изображены графики изменения функционала качества (3) с течением времени.

При меньших γ значение функционала убывает медленнее, испытывая при этом меньшие колебания.

На Рис. 9, 10, 11, 12 наблюдается колебание значений функционала качества при управлении системой элементов крыла по алгоритму (17). Этот эффект наблюдается даже при неизменных внешних условиях. Роботизированные устройства продолжают периодически менять свое положение, и не наблюдается сходимость к близким значениям отклонения давления от давления в ламинарном потоке на элементах крыла. При уменьшении шага колебания

Рис. 7: Воздействие турбулентного потока (математическая модель) (t = t0).

уменьшаются, но время сходимости алгоритма вырастает пропорционально. Было сделано предположение, что это происходит изза центральных элементов на крыле: из-за малого значения плеча возрастает управление (так как длина плеча rk находится в знаменателе). Изменение структуры крыла с полностью покрытого “перьями” на два региона с элементами по краям крыла (при использовании половина от общего числа датчиков) привело к стабилизации (см. Рис. 13, 14).

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

В статье рассматривается устройство и функционирование стенда, имитирующего крыло самолета с подвижными элементами («перьями»), в условиях турбулентного воздушного потока. Эффект

Рис. 8: Балансировка нагрузки (математическая модель) (t0 < t < t1).

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

Список литературы

[1]      Granichin   O.,           Khantuleva          T. Hybrid systems and randomized

Рис. 9: Изменение значений функционала качества с течением времени при.

measuring in nonequilibrium processes // Differential Equations and Control Processes. 2004. Vol. 3. P. 35–43.

[2]      Granichin O., Khantuleva T., Amelina N. Adaptation of aircraft’s wings elements in turbulent flows by local voting protocol // IFACPapersOnLine. 2017. Vol. 50. No. 1. P. 1904–1909.

[3]      Граничин О.Н. Как действительно устроены сложные информационно-управляющие системы? // Стохастическая оптимизация в информатике. 2016. Т. 12. Вып. 1. С. 3–19.

[4]      Граничин О.Н., Хантулева Т.А Адаптация элементов крыла (“перьев”) самолета в турбулентном потоке с помощью мультиагентного протокола // Автоматика и телемеханика. 2017. № 10. С. 168–

188.

Рис. 10: Изменение значений функционала качества с течением времени при.

[5]      Синай Я.Г. Построение кластерной динамики для динамических систем статистической механики // Вестник Московского университета. Серия 1. Математика. Механика. 1974. Т. 29. № 1. С. 152–

158.

[6]      Khantuleva T.A., Meshcheryakov Yu.I. Nonequilibrium processes in condensed media. Part 2. Structural instability induced by shock loading // Physical Mesomechanics. 2016. Vol. 19. No. 1. P. 69–76.

[7]      Meshcheryakov Yu.I., Khantuleva T.A. Nonequilibrium processes in condensed media: Part 1. Experimental studies in light of nonlocal transport theory // Physical Mesomechanics. 2015. Vol. 18. No. 3. P. 228–243.

[8]      Boccaletti S. et al. Complex networks: Structure and dynamics // Physics reports. 2006. Vol. 424. No. 4. P. 175–308.

Рис. 11: Изменение значений функционала качества с течением времени при.

[9]      Зубарев Д.Н. Неравновесная статистическая термодинамика. — М.: Наука. 1971. 416 с.

[10]   Yong-Zheng S., Jiong R. Leader-follower consensus problems of multiagent systems with noise perturbation and time delays // Chinese Physics Letters. 2008. Vol. 25. No. 9. P. 3493.

[11]   Utkin V.I. Sliding Modes in Control and Optimization — SpringerVerlag Berlin, Heidelberg. 1992. 286 p.

[12]   Емельянов С.В. Системы автоматического управления с переменной структурой. — Москва: Наука. 1967. 335 с.

[13]   Chebotarev P.Yu., Agaev R.P. Coordination in multiagent systems and Laplacian spectra of digraphs // Automation and Remote Control. 2009. Vol. 70. No. 3. P. 469–483.

Рис. 12: Изменение значений функционала качества с течением времени при.

[14]   Lewis F.L. et al. Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches (Communications and Control Engineering). — London: Springer. 2014. 307 p.

[15]   Olfati-Saber R., Murray R.M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. 2004. Vol. 49. No. 9. P. 1520–1533.

[16]   Ren W., Beard R.W., Atkins E.M. Information consensus in multivehicle cooperative control // IEEE Control Systems. 2007. Vol. 27. No. 2. P. 71–82.

[17]   Granichin O., Khantuleva T. Local voting protocol for the adaptation of airplane’s “feathers” in a turbulence flow // Proc. of the 2017 American Control Conference. 2017. P. 5684–5689.

Рис. 13: Изменение значений функционала качества с течением времени при использовании всей поверхности крыла.

[18]   Хантулева Т.А. Нелокальная теория неравновесных процессов переноса. — СПб.: Изд-во СПбГУ. 2013.

[19]   Olfati-Saber R., Fax J., Murray R. Consensus and cooperation in networked multi-agent systems // Proceedings of the IEEE. 2007. Vol. 95. No. 1. P. 215–233.

[20]   Khantuleva T.A., Shalymov D.S. Modelling non-equilibrium thermodynamic systems from the speed-gradient principle // Philos. Trans. R. Soc. A. 2017. Vol. 375. Is. 2088. P. 2016220.

[21]   Фрадков А.Л. Исследование физических систем при помощи обратных связей // Автоматика и телемеханика. 1999. №. 3. C. 213–

230.

[22]   Kalmuk A., Granichin O., Granichina O., et al. Detection of abrupt changes in autonomous system fault analysis using spatial adaptive

Рис. 14: Изменение значений функционала качества с течением времени при использовании половины элементов по краям крыла.

estimation of nonparametric regression // Proc. of the 2016 American Control Conference. 2016. P. 6839–6844.

[23]   Granichin O., Khantuleva T., Granichina O. Local voting protocol for the adaptation of airplane’s “feathers” in a turbulence flow // Proc.

of the 2017 American Control Conference. 2017. P. 5684–5689.

[24]   Граничин О.Н., Амелин К.С., Амелина Н.О. Заявка на изобретение “Аэродинамическое крыло летательного аппарата с адаптивно изменяющейся поверхностью”. №2016147133/20(075649) от

30.11.2016.

 

 

 

Реализация менеджера памяти в work-stealing балансировщике[5]

Е. А. Барковский[6]

barkevgen@gmail.com

В работе описывается менеджер памяти, реализованный в экспериментальном work-stealing балансировщике задач. Менеджер разработан на основе математических моделей оптимального управления work-stealing деками. В менеджере реализованы и проанализированы следующие методы управления памятью: оптимальное деление; деление пополам. Также, работа экспериментального менеджера сравнивается с работой стандартного менеджера памяти.

Ключевыеслова: оптимальное управление, work-stealing деки, менеджеры памяти.

                1.      Введение

Стратегии балансировки параллельных вычислений на многоядерной архитектуре разделяют на статические и динамические. Статическая балансировка используются когда известно практически все про выполняемые задачи. В этом случае можно заранее определить оптимальное расписание задач (например, минимизировать среднее время решения), но такие задачи считаются NPполными и встречаются достаточно редко. При динамической балансировке балансировщик во время работы использует некую относительно простую стратегию, которая дает результат близкий к оптимальному. Одна из таких стратегий балансировки называется “work-stealing” – процессоры, ставшие пустыми, пытаются перехватить часть работы у других процессоров. Этот метод реализован в большом числе систем, например: Cilk [1]; TBB [2]; TPL [3]; X10 [4] и другие.

В этом методе балансировки нагрузки каждый процессор решает ряд задач, указатели на которые хранятся в деке этого процессора. Когда процессор создает новую задачу, он добавляет указатель на нее в свой дек; когда процессору нужна задача, он берет указатель из вершины дека. Если процессор узнает, что его дек пуст, он перехватывает указатели на задачи у другого процессора. Первые две операции выполняются как в LIFO-стеке, а перехват происходит из основания дека – как в FIFO-очереди. Т.е. мы работаем (в терминологии Д. Кнута) с деком с ограниченным входом [5]. В [6] рассматривался перехват одного элемента, в [7] – половины элементов.

В предыдущих работах мы предлагали математические модели последовательного циклического представления work-stealing деков, где каждый дек расположен в отдельном участке памяти и на каждом шаге дискретного времени с ними происходят операции с заданными вероятностями [8,9]. В этой статье будет описана и проанализирована одна из реализаций вышеупомянутых моделей и методов, как менеджера памяти встроенного в work-stealing балансировщик задач.

На практике, для работы с деками в виде циклических массивов часто используются классические методы работы с кучей в трансляторах C/C++. Для каждого дека из кучи запрашивается массив. Когда он становится достаточно большой, то запрашивается новый массив, например, в два раза больший – туда копируются элементы дека, а старый массив отдается в список свободных блоков кучи. Если же наоборот, дек стал достаточно мал, то те же действия производятся с массивом, меньшим старого в два раза. Мы же в этой статье рассматриваем задачу поиска оптимальных альтернативных методов управления памятью для деков, в предположении, что известны некоторые их вероятностные характеристики.

                2.         Математическая модель

Приведем постановку задачи математической модели [9], на основе которой был разработан менеджер памяти.

Пусть в памяти размера m мы работаем с двумя последовательными циклическими деками, где все элементы имеют фиксированный размер в одну структурную единицу. Для последовательного представления деков выделим каждому некоторое количество единиц памяти из общего объема m. Пусть s – количество единиц па-