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

Abstract


This paper offers applications of the generalized algorithm for processing weakly formalized information from sensors to ensure safe road traffic. Weakly formalized information is information that cannot be loaded on the computer and/or cannot be processed on the computer without preliminary processing, namely, information formalization. The data arriving from sensors are often weakly formalized information, which means that in order to upload the data they have to be processed. There are special requirements imposed on the systems of processing such data, particularly, the systems have to process weakly formalized information and obtain formalized information which can be further processed on the computer. We have proposed a generalized algorithm for processing weakly formalized data that can be used for information processing in various technical systems, particularly, to ensure safe road traffic. Vehicles are thought to be equipped with various sensors (video, sound, ultrasonic sensors, etc.) providing data on obstacles on the road (buildings, constructions, trees, other vehicles, people, animals, etc.). The data may be insufficient due to such cases when one obstacle covers another, for example, a person can be behind car in the blind spot. The point is in avoiding collision of the car with any obstacle (other car, building, person, animal, etc.). There are two parameters to be considered: driving speed and direction. If the distance between one car and other car or any obstacle gets smaller, a vehicle can change either driving speed or direction, thus ensuring safe road traffic. This paper considers vehicle movement through a T-junction as an example and shows that applying the considered generalized algorithm allows ensuing safe road traffic.

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

  1. Воробьев В.И., Копыльцов А.В., Пальчун Б.П., Юсупов Р.М. Методы и модели оценивания качества программного обеспечения. - СПб., 1992.
  2. Воройский Ф.С. Информатика. Энциклопедический словарь-справочник: введение в современные информационные и телекоммуникационные технологии в терминах и фактах. - М., 2011.
  3. Копыльцов А.А. Алгоритм коррекции связей между фрагментами слабо формализованной информации и генерация новой информации // Вестник Нижневартовского гос. ун-та. - 2014. - № 3. - С. 28-34.
  4. Копыльцов А.А., Копыльцов А.В. Алгоритм обработки слабо формализованной информации, поступающей от технических систем // Известия СПбГЭТУ «ЛЭТИ» (известия государственного электротехнического университета). Серия «Информатика, управление и компьютерные технологии». - 2012. - № 8. - С. 30-36.
  5. Копыльцов А.А., Копыльцов А.В. Качественная и количественная слабо формализованная информация и ее обработка // Материалы ХIV Санкт-Петербургской международной конференции «Региональная информатика - 2014» (29-31 октября 2014 г.). - СПб., 2014. - С. 557.
  6. Копыльцов А.А., Копыльцов А.В. Обобщенный алгоритм обработки слабо формализованной информации и его применение // Вестник Нижневартовского гос. ун-та. - 2014. - № 35. - С. 35-44.
  7. Копыльцов А.А., Копыльцов А.В. Обработка слабо формализованной информации, поступающей от технических систем // Вестник Нижневартовского гос. гуманит. ун-та. - 2013. - № 1. - С. 32-36.
  8. Копыльцов А.А., Копыльцов А.В. Технические системы и слабо формализованная информация // Материалы ХIII Санкт-Петербургской международной конференции «Региональная информатика - 2012» (24-26 октября 2012 г.). - СПб., 2012. - С. 375.
  9. Копыльцов А.А., Копыльцов А.В. Цифровой образовательный ресурс «Краткая история моделирования» и его применение в учебном процессе // Материалы сетевой международной научно-практической конференции «Электронное обучение в вузе и школе» (16-19 апреля 2014 г.). - СПб., 2014. - С. 153-155.
  10. Копыльцов А.А. Модель классификации информации и алгоритм ее предварительной обработки для статических и динамических объектов // Известия СПбГЭТУ «ЛЭТИ» (известия государственного электротехнического университета). Серия «Информатика, управление и компьютерные технологии». - 2013. - № 6. - С. 134-139.
  11. Копыльцов А.А. Обработка информации в живых и технических системах // Материалы ХIII Санкт-Петербургской международной конференции «Региональная информатика - 2012» (24-26 октября 2012 г.). - СПб., 2012. - С. 373-374.
  12. Копыльцов А.А. Обработка слабо формализованной информации в живых и технических системах // Материалы Всероссийской научно-практической конференции студентов, магистров, аспирантов «Современное программирование» (16-17 апреля 2014 г.). - Нижневартовск, 2014. - С. 117-121.
  13. Копыльцов А.А. Обработка слабо формализованной информации при недостатке информации // Материалы ХIII Санкт-Петербургской международной конференции «Региональная информатика - 2012» (24-26 октября 2012 г.). - СПб., 2012. - С. 374.
  14. Копыльцов А.А. Особенности обработки слабо формализованной информации // Материалы ХIV Санкт-Петербургской международной конференции «Региональная информатика - 2014» (29-31 октября 2014 г.). - СПб., 2014. - С. 555-556.
  15. Копыльцов А.А. Понятие слабо формализованной информации и особенности ее обработки // Материалы сетевой международной научно-практической конференции «Электронное обучение в вузе и школе» (20-24 апреля 2015 г.). - СПб., 2015. - С. 140-144.
  16. Копыльцов А.А. Применение обобщенного алгоритма обработки слабо формализованной информации для управления неравновесной химической реакцией // Инженерный вестник Дона. - 2015. - № 1. - Ч. 2. - URL: ivdon.ru/ru/magazine/archive/n1p2y2015/2812.
  17. Копыльцов А.А. Программа для обработки слабо формализованной информации, поступающей от технических систем // Свидетельство о государственной регистрации программы для ЭВМ № 2013617310. Правообладатель: ФГБОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им В.И. Ульянова (Ленина)» (СПб ГЭТУ «ЛЭТИ»). Заявка № 2013615041. Дата поступления 19 июня 2013 г. Дата государственной регистрации в Реестре программ для ЭВМ 08 августа 2013 г.
  18. Копыльцов А.А. Слабо формализованная информация и алгоритмы ее обработки // Материалы ХIV Санкт-Петербургской международной конференции «Региональная информатика - 2014» (29-31 октября 2014 г.). - СПб., 2014. - С. 556-557.
  19. Копыльцов А.А. Сохранение конфиденциальности данных при поддержке принятия решений, на основе извлекаемой специальным образом информации // Материалы VIII Санкт- Петербургской межрегиональной конференции «Информационная безопасность регионов России» (23-25 октября 2013 г.). - СПб., 2013. - С. 104.
  20. Копыльцов А.А. Цифровой образовательный ресурс «Обработка слабо формализованной информации в живых и технических системах» // Материалы сетевой международной научно-практической конференции «Электронное обучение в вузе и школе» (16-19 апреля 2014 г.). - СПб., 2014. - С. 151-153.
  21. Копыльцов А.А., Нечитайленко Р.А. Кластерное атрибутирование объектов информационной обработки по понятийным частным и интегральным признакам // Материалы ХII Санкт-Петербургской международной конференции «Региональная информатика - 2010» (20-22 октября 2010 г.). - СПб., 2010. - С. 49-50.
  22. Копыльцов А.А., Нечитайленко Р.А. Обеспечение пороговой безопасности обработки слабо формализованной информации при распределенном управлении с целью принятия решений // Труды VII Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России» (26-28 октября 2011 г.). - СПб., 2011. - С. 154-155.
  23. Копыльцов А.В. Об оценке качества программных продуктов // Проблемы информатизации (теоретический и научно-практический журнал). - 1994. - Вып. 3-4. - С. 46-48.
  24. Хованов Н.В. Статистические модели теории квалиметрических шкал. - Л., 1986.

Statistics

Views

Abstract - 0

PDF (Russian) - 0

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies