Generalized algorithm for processing weakly formalized information and applications of such algorithm

Full Text

Введение В последнее время много работ посвящено обработке слабо формализованной информации [3-22]. Под слабо формализованной понимается информация, которая не может быть загружена на компьютер и/или не может обрабатываться на компьютере без предварительной обработки, которая и называется формализацией информации [2]. Поступающие с датчиков данные часто являются слабо формализованной информацией. Требования, предъявляемые к системам обработки подобной информации, следующие: системы обработки слабо формализованной информации должны из слабо формализованной информации, путем ее переработки, получать формализованную информацию, которую можно обрабатывать на компьютере. Для обработки слабо формализованной информации предложен обобщенный алгоритм [4; 6; 7; 10], который может быть использован для обработки информации в различных технических системах. Одним из таких приложений может быть безопасное движение автотранспорта. Безопасное движение автотранспорта Предполагается, что на автомобилях установлены датчики в различных диапазонах (например, видеодатчики, звуковые и ультразвуковые датчики). Если погода хорошая, то видеодатчики позволяют хорошо наблюдать обстановку в окружении автомобиля. Если же погода плохая (туман, снег, дождь и т.д.), то видеодатчики с этой задачей могут не справиться, а совместная работа видео- и аудиодатчиков может привести к желаемому результату. С этих датчиков поступает информация о препятствиях, которые находятся на пути движения автомобиля (постройках, деревьях, других транспортных средствах, людях, животных и т.д.). Недостаток информации может проявляться в том, что одно препятствие может заслонять другое, например, человек может находиться за машиной вне зоны видимости. Задача состоит в том, чтобы не произошло столкновения машины с каким-нибудь препятствием (другая машина, здание, человек, животное и др.). Для этого существуют два параметра: скорость и направление движения автомобиля. В случае уменьшения расстояния между одним автомобилем и другим автомобилем или каким-либо препятствием автомобиль может изменить либо направление движения, либо скорость. Изменяя скорость и направление движения, можно достичь безопасного движения автомобиля. Приложения обобщенного алгоритма Применим обобщенный алгоритм обработки слабо формализованной информации [4; 6; 7; 10]. Этап 1. Информация, которая собирается с различных датчиков, поступает в модуль «Сбор информации». В нашем случае это могут быть видео-, аудио-, ультразвуковые и другие датчики, которые установлены на машинах. Этап 2. Информация из модуля «Сбор информации» поступает в модуль «Распознавание информации». В нашем случае машины распознаются по видео-, аудио- и ультразвуковым датчикам. Этап 3. Из модуля «Распознавание информации» информация поступает в модуль «Классификация информации», где осуществляется ее классификация по классам (n - количество классов). В нашем случае имеем видеоинформацию (первый класс), аудиоинформацию (второй класс), ультразвуковую информацию (третий класс), а также их сочетания: видео-аудиоинформацию (четвертый класс), видео-ультразвуковую информацию (пятый класс), аудио-ультразвуковую информацию (шестой класс) и видео-аудио-ультразвуковую информацию (седьмой класс), т.е. n = 7. Этап 4. В каждом из n = 7 модулей «Свертка информации» информация проходит свою, характерную для данного класса, обработку по определенному алгоритму [1; 23; 24]. В нашем случае (например, когда рассматриваем две машины) считаем, что свертка - среднее расстояние между двумя машинами за некоторый промежуток времени. В итоге получаем для каждых двух машин среднее расстояние между ними за некоторый промежуток времени. Этап 5. Оценивание достоверности информации в модулях «Оценивание достоверности информации». Предполагается, что ранее была проведена серия экспериментов (например, при пересечении машинами перекрестка), в результате которых было выявлено, что среднее расстояние Hсрi между каждыми двумя машинами Нmin Hср i Hmax, где i - номер пары машин, N - всего пар машин, Нmin, Hmax - минимальное и максимальное значение (определяется на основании предыдущих экспериментов). Если НminHноваяiHmax для всех i, то информация достоверная. Если это верно для N1 пар машин, то достоверность равна N1/N. Этап 6. Оценивание безопасности информации в каждом из n классов происходит в модулях «Оценивание безопасности информации». Проверяем N-N1 пар машин, где Нmini>Hноваяi и/или Hноваяi>Hmaxi. Возможны варианты: это либо неисправность системы, или так и должно быть. Прогоняем старый тестовый вариант. Если он дает правильные результаты, то Нmini и/или Hmaxi корректируются. Если же нет, то эта конкретная пара машин работает неправильно (например, водитель пьяный). Выявляем число неправильно работающих пар машин N2, и тогда безопасность равна (N-N2)/N. Этап 7. Установление связей между недавно полученной информацией в каждом из n классов и прежде полученной информацией происходит в модулях «Установление связей». Новая информация - набор усредненных расстояний между парами машин в какой-то момент (промежуток) времени. Сравниваем этот набор с наборами, хранящимися в памяти, и ищем наиболее близкий (минимизируем среднее квадратичное отклонение). Если задать некоторый интервал ∆, то в него может попасть несколько старых вариантов. Число таких вариантов (связей) пусть будет равно М. Этап 8. В модулях «Оценивание вероятности» происходит оценивание вероятности, с которой можно доверять поступившей информации в каждом из n классов. В нашем случае: если МM*, где М* задано, то Р = 1. В противном случае переходим на этап «Распознавание информации». Пусть, например, М* = 1, и М = 2. Тогда МM* и, следовательно, Р=1. Этап 9. В модулях «Поддержка принятия решений» происходит поддержка принятия решений в каждом из n классов. Это происходит следующим образом. Если выполнены следующие условия: § достоверность поступающей слабо формализованной информации IДПИ> IДПИ* для некоторого IДПИ*; § безопасность поступающей слабо формализованной информации IБПИ > IБПИ* для некоторого IБПИ *; § число связей М>M* для некоторого М* ; § вероятность, с которой можно доверять вновь полученной слабо формализованной информации Р>P* для некоторого Р*, то эта новая поступающая информация включается в хранилище для данного класса. Нормируем число связей М следующим образом , где M N - нормированное значение М, Mmax - максимальное значение М. Таким образом, достоверность поступающей информации IДПИ, безопасность поступающей информации IБПИ, нормированное число связей M N, вероятность, с которой можно доверять вновь полученной информации Р, находятся в промежутке от 0 до 1, т.е. 0IДПИ 1, 0IБПИ1, 0 M N1, 0 Р1 . Для того, чтобы новую поступающую информацию включить в модуль «Хранилище» для данного класса, нужно, чтобы выполнялись неравенства § IДПИ> IДПИ* для некоторого IДПИ*, § IБПИ > IБПИ* для некоторого IБПИ *, § M N > M N * для некоторого нормированного M N *, § Р>P* для некоторого Р*. В нашем случае информацию (набор средних расстояний между парами машин в некоторый момент (промежуток) времени) включаем в модуль «Хранилище», поскольку все 4 условия выполнены. Этап 10. В модуле «Обобщенная поддержка принятия решений» проводится сбор сгенерированных решений из n классов и после этого на их основе осуществляется генерация новой совокупности решений. В нашем случае имеем видеодатчики, аудиодатчики и ультразвуковые датчики (т.е. датчики трех видов). То есть нашу новую информацию (набор средних расстояний между парами машин в некоторый момент (промежуток) времени) включаем в модуль «Хранилище». Этап 11. Сравнение недавно принятого решения с ранее принятыми решениями происходит в модуле «Определение числа связей». Определение числа связей, подтверждающих правильность принятого решения, осуществляется следующим образом. При поступлении новой информации в модуль «Хранилище» осуществляется ее свертка CN и сравнение со свертками (C1, C2, …, Ck) ранее полученной информации, хранящимися в модуле «Хранилище», следующим образом. Если i= |CN -Ci| < для некоторого i {1, 2, …, k} и некоторого > 0 , то считаем, что новая информация с номером N и старая информация с номером i между собой связаны. После установления связей считаем число этих связей ММ. Если ММ>ММ * для некоторого ММ *, то считаем, что вероятность правильности принятого решения Р = 1. В противном случае Р<1. В нашем случае (на основе предыдущего) Р = 1. Этап 12. В модуле «Выработка устойчивой реакции» происходит выработка устойчивой реакции на неоднократно поступающую информацию и ее запоминание. Если для некоторого >0 среднее квадратичное отклонение между новым вариантом и несколькими старыми вариантами меньше , то считается, что эти фрагменты информации (набор средних расстояний между парами машин в некоторый момент (интервал) времени) образуют устойчивую информацию, и их записываем в хранилище с индексом «устойчивая» IУИ. Этап 13. В модуле «Генерация решений» генерируются решения. Собираем в модуле «Хранилище» все фрагменты информации с индексом «устойчивая». Рассмотрим сеть связей в модуле «Хранилище» для набора устойчивой информации IУИi , i=1, … , n. Если между фрагментами информации с номерами i и j имеется Сij связей и Сij > C* , где C* - некоторое число, то считаем, что фрагменты информации с номерами i и j связаны непосредственно (уровень связности Сij). Этап 14. В модуле «Хранилище» на основе информации, которая записана последней, и ранее записанной информации генерируется новая информация. Сведения о том, что фрагменты информации с номерами Ii и Ij связаны, могут рассматриваться, как новая информация с номером Ik, и ее можно направить на этап «Сбор информации» с целью распознавания, классификации информации и т.д. Это означает, что если фрагмент информации с номером Ii определяется показателями i1, i2, …, ii1, а фрагмент информации с номером Ij - показателями j1, j2, …, jj1 , то фрагмент информации с номером определяется показателями i1, i2, …, ii1, j1, j2, …, jj1 , представляющими собой объединение показателей, которыми определяются фрагменты информации с номерами Ii и Ij. Это означает, что свертка в дальнейшем делается по показателям i1, i2, …, ii1, j1, j2, …, jj1. В нашем случае объединяем две совокупности двух экспериментов и вычисляем в каждом случае средние значения, т.е. это означает, что такой вариант средних значений тоже возможен. Это новая информация, которую можно переслать на вход в систему (в модуль «Сбор информации») и прогнать аналогично. В итоге можно вычислить среднее значение по всем парам машин, дисперсию и среднее квадратичное отклонение. Таким образом, если среднее значение достаточно мало, а дисперсия велика, то нужно изменять режим движения (например, изменять скорость при пересечении перекрестка (установить соответствующие знаки)). Через некоторый интервал времени (когда часть машин пересечет перекресток) снова вычисляем среднее значение (математическое ожидание). Снова изменяем режим движения (например, через перекресток), и т.д. Движение через Т-образный перекресток. Рассмотрим, например, Т-образный перекресток (рис. 1). Рис. 1. Перекресток трех дорог АВ, АС, AD в системе координат (X, Y) Если рассмотреть две машины, которые движутся из пунктов B и D через перекресток А, то возможны варианты: первая машина - маршруты BAC и BAD, вторая машина - маршруты DAB и DAC. Причем, если интервал времени между прохождениями перекрестка больше некоторого ∆, то они пройдут его, не изменяя скорости. Если же нет, то возможны варианты: маршруты BAD и DAC (машины разойдутся), маршруты BAD и DAB (машины разойдутся), маршруты BAC и DAC (машины не разойдутся, если не изменят скорость), маршруты BAC и DAB (машины не разойдутся, если не изменят скорость). Проводим несколько экспериментов с различными вариантами движения и запоминаем условия и результаты экспериментов (скорости и направления движения, успешно ли пересекли перекресток и т.д.). В итоге, на основе запомненной информации формируются интервалы скоростей, при которых возможны аварийные ситуации на дороге и при которых невозможны. Если в следующий раз возникает похожая ситуация (например, к перекрестку приближаются две машины со скоростями V1 , V2), то рассматриваются интервалы, выбирается наиболее близкий вариант и генерируются рекомендации об изменении (или не изменении) скорости. В случае необходимости интервалы корректируются. Однако, хотя и генерируются рекомендации об изменении скорости, машины могут: изменить скорость на ту величину, которая рекомендуется; изменить скорость на другую величину; не изменять скорость. В любом случае в память записывается полная информация о результатах пересечения перекрестка машинами. В качестве примера рассмотрим вариант, когда скорость первой машины V1 = = 10 м/с (36 км/ч) и она движется по маршруту BAC, а вторая машина со скоростью V2 движется по маршруту DAB. Предполагается, что AB = AC = AD = 100 м. В этом случае первая машина пересечет перекресток через 10 с. Тогда, проводя эксперименты, т.е. запуская вторую машину с различными скоростями, получим следующие экспериментальные данные (табл. 1). Например, пусть первая машина движется по маршруту ВАС со скоростью 10 м/с, а вторая - по маршруту DAB со скоростью 20 м/с. Тогда координаты машин и расстояние между ними будут следующие (табл. 2, рис. 2). Таблица 1 Скорости и время прохождения перекрестка № Скорость второй машины V2 (м/с) Время прохождения перекрестка А (с) Возможность столкновения 1 2 50,00 2 4 25,00 3 6 16,67 4 8 12,50 5 10 10,00 Возможно столкновение 6 12 8,33 7 14 7,14 8 16 6,25 9 18 5,55 10 20 5,00 Поскольку машины представляют собой не материальные точки, а имеют размеры, и в целях безопасности можно взять, например, интервал для времени (t0-t* , t0+t*), в течение которого может сложиться опасная ситуация на дороге, где t0 - время пересечения курсов машин, например, t*=3 с. Тогда интервалы опасных скоростей (при которых возможна аварийная ситуация на дороге) будут для перекрестка А следующие: t € (10-3 c ; 10+3 c ) = (7 c; 13 c), V1 = 10 м/с, V2 € (8 м/с; 14 м/с). Это означает, что если скорость V2 принадлежит этому интервалу, то при приближении к перекрестку рекомендуется ее изменить в целях обеспечения безопасности движения. Таблица 2 Координаты машин и расстояние между ними Время (с) Координаты первой машины (м) Координаты второй машины (м) Расстояние между машинами (м) Комментарии 0,00 (0,0; 200,0) (0,0; 0,0) 200,00 5,00 (0,0; 150,0) (0,0; 100,0) 50,00 6,67 (0,0; 133,34) (0,0; 133,34) 0,0 Машины встречаются 10,00 (0,0; 100,0) (0,0; 200,0) 100,00 15,00 (50,0; 100,0) (0,0; 300,0) 206,16 20,00 (100,0; 100,0) (0,0; 400,0) 316.,23 25,00 (150,0; 100,0) (0,0; 500,0) 427,20 t L Рис. 2. Изменение расстояния (L, м) между двумя машинами с течением времени (t, с) Рассматриваем различные варианты (проводим эксперименты) и запоминаем их. Запомненные варианты обрабатываем, т.е. получаем некоторые интервалы скоростей, при которых возможна аварийная ситуация на дороге. Если возможна аварийная ситуация, то одна из машин должна изменить скорость на некоторую величину, чтобы избежать аварии. Эту информацию можно рассматривать, как новую информацию. В случае проведения нового эксперимента, например, V1 = 12 м/с, V2= 11 м/с, определяем, принадлежит ли скорость V2 опасному интервалу (8 м/с; 14 м/с). Поскольку V2=11 м/с принадлежит опасному интервалу, то не рекомендуется с такой скоростью ехать через перекресток А. То есть одна из машин должна изменить скорость при подъезде к перекрестку, чтобы избежать аварийной ситуации. Аналогично, проводя следующие эксперименты, о каждом эксперименте информацию сохраняем в памяти. В случае необходимости границы опасных интервалов корректируются. Заключение Предложено применение обобщенного алгоритма обработки слабо формализованной информации к задаче безопасного движения автотранспорта, в частности, через Т-образные перекрестки. Для более сложных ситуаций, например, когда к перекрестку приближается несколько машин с различными скоростями, все делается аналогично: - Вся информация о пересечении перекрестка сохраняется и накапливается (например, можно определять скорость машин за 100, 200, 300 и т.д. метров от перекрестка); - На основе накопленной информации генерируются безопасные и опасные интервалы скоростей для каждой машины; - В случае рассмотрения нового варианта пересечения перекрестка определяются интервалы скоростей, в которые попадают скорости машин, приближающихся к перекрестку; - Если интервалы не опасные, то изменение скоростей не происходит; - Если интервалы опасные, то в памяти осуществляется поиск ближайшего неопасного варианта, т.е. такого варианта, чтобы изменение скоростей было минимальным; - Новый сценарий пересечения перекрестка записывается в память; - Если необходимо, то происходит коррекция интервалов скоростей; - Далее происходит ожидание следующего пересечения машинами перекрестка и т.д. Таким образом, применяя обобщенный алгоритм, можно получить на выходе некоторые рекомендации по поддержке принятия решений, в частности, определить, кому, по какому маршруту и с какой скоростью перемещаться. Аналогичная ситуация наблюдается в железнодорожном, речном и морском транспорте, где также можно применять обобщенный алгоритм.

About the authors

A. A Kopyltsov

Saint-Petersburg State Electrotechnical University «LETI»

Email: kopyl2001@mail.ru
Senior Lecturer at the Department of Automated Information Processing Systems, Saint-Petersburg State Electrotechnical University «LETI».

References

Supplementary files