Стохастические методы оптимизации в информатике

Рандомизированные алгоритмы

Новые рандомизированные алгоритмы в управлении и обработке данных

К. С. Амелин, аспирант,

О. Н. Граничин, д. ф.-м. н.

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

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

Oleg_granichin@mail.ru, konstantinamelin@mail.ru

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

Рандомизированный алгоритм не что иное, как процедура, при которой один или несколько шагов основаны на случайном выборе правила, т. е. при использовании рандомизированных алгоритмов на каком-то этапе вместо того, чтобы самим принять решение, мы призываем "судьбу" (случай) выбирать за нас. Но тогда естественно возникает вопрос: зачем прибегать к "судьбе" мудрому человеку? "Судьба" не является специалистом ни в чем, выбор делается случайно. Итак, почему от рандомизированных алгоритмов мооюет быть польза? Сознательное использование рандомизированных методов требует ответов себе на этот вопрос, часть из которых обсуждается в статье.

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

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

86 наименований

Campi M.C. Why is resorting to fate wise? A critical look at randomized algorithms in systems and control // European Journal of Control. 2010. Vol. 5. P. 419-430.

Граничин О.Н., Хантулева Т.А. Гибридные системы и рандомизированные измерения в неравновесных процессах // Дифференциальные уравнения и процессы управления, электронный журнал, per. №Р23275 от 07.03.97. №3. 2004.

Деревицкий Д.П., Фрадков Ф.Л. Две модели для анализа динамики алгритмов адаптации // Автоматика и телемеханика. 1974. № 1. С. 67-75.

Деревицкий Д.П., Фрадков А.Л. Прикладная теория дискретных адаптивных систем управления. М.: Наука, 1981.

Лъюнг Л., Сёдерстрём Т. Идентификация систем: теория для пользователя. — М.: Наука. 1991. 431 с.

Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag. 2002. 415 p.

Ширяев А.Н. Вероятность. — M.: Наука. 1980. 574 с.

Граничин О.Н. Неасимптотическое доверительное множество для параметров линейного объекта управления при почти произвольных помехах // Автоматика и телемеханика. 2011.

Nemirovski A. Several NP-hard problems arising in robust stability analysis // J. Matrix Anal. Appl. 1993. Vol. 6. P. 99-105.

Braatz R.P., Young P.M., Doyle J.C., Morari M. Computational complexity of /л calculation // IEEE Trans. Autom. Control. 1994. Vol. 39. P. 1000-1002.

Blondel V.D., Tsitsiklis J.N. A survey of computational complexity results in systems and control // Automatica. 2000. Vol. 36. P. 1249-1274.

Hoeffding W. Probability inequalities for sums of bounded random variables // J. Am. Stat. Assoc. 1963. Vol. 58. P. 13-30.

Metropolis N., Ulam S. The Monte Carlo Method // J. Amer. statistical assoc. 1949. Vol. 44. No. 247. P. 3354341.

Ермаков СМ. Метод Монте-Карло и смежные вопросы. Сер. "Теория вероятностей и математическая статистика". — М.: Изд-во Наука. 1971. 471 с.

Fisher R.A. The Design of Experiments. — Edinburgh: Oliver and Boyd, 1935.

Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. — М.: Наука. 1977. 223 с.

Цыпкин Я.З. Информационная теория идентификации. — М.: Наука. 1995. 336 с.

Young P.С. Recursive Estimation and Time-Series Analysis. An Introduction. — Berlin-Heidelberg: Springer. 1984.

Граничин О.Н. Алгоритм стохастической аппроксимации с возмущением на входе для идентификации статического нестационарного дискретного объекта // Вестник Ленингр. ун-та. Сер. 1. 1988. Вып. 3. С. 92-93.

Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Проблемы передачи информации. 1992. №2. С. 16-20.

Goldenshluger A.V., Polyak В. Т. Estimation of regression parameters with arbitrary noise // Mathematical Methods of Statistics. 1993. Vol. 2. No. 1. P. 18-29.

Граничин О.Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. — М.: Наука. 2003. 291 с.

Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. №1(4). С. 19-21.

Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 2. С. 126-133.

Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

Spall J.C. Multivariate Stochastic Aproximation Using a Simultaneous Perturbation Gradient Aproximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332-341.

Chen H.-F., Duncan Т.Е., Pasik-Duncan B.A. Kiefer-Wolfowitz algorithm with randomized differences // IEEE Trans. Automat. Contr. 1999. Vol. 44. No. 3. P. 442-453.

Растригин Л.А. Статистические методы поиска. М.: Наука. 1968. 376 с.

Сушков Ю.А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. Изд-во Ленингр. гос. ун-та. 1972. Т. 1. С. 180-185.

Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. — М.: Наука. 1991.

Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. Н., and Teller E. Equation of State Calculations by Fast Computer Machines // J. Chemical Physics. 21. 6. June 1953. P. 1087-1092.

Kirkpatrick S., Gelatt Jr. C. D., and Vecchi M. P. Optimization by Simulated Annealing // Science. 220. 1983. P. 671-680.

Лопатин А.С. Метод отжига // Стохастическая оптимизация в информатике. 2005. Вып. 1. С. 133-149.

Тихомиров А.С. О быстрых вариантах алгоритма отжига (simulated annealing) // Стохастическая оптимизация в информатике. 2009. Вып. 5. С. 65-90.

Holland J.H. Adaptation in natural and artificial systems. — University of Michigan Press. Ann Arbor. 1975.

Вапник В.Н., Червоненкис А.Я. Теория равномерной сходимости частот появления событий к их вероятностям и задача поиска оптимального решения по эмпирическим данным // Автоматика и телемеханика. №2. 1971.

Вапник В.Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука. 1974.

Фомин В.Н. Математическая теория обучаемых опознающих систем. — Л.: Изд-во Ленингр. ун-та. 1976. 236 с.

Vidyasagar M. A Theory of Learning and Generalization. — New York: Springer. 1997.

Vidyasagar M. Statistical learning theory and randomized algorithms for control // IEEE Control Systems. 1998. No 12. P. 69-85.

Calafiore G.C., Campi M.C. The scenario approach to robust control design // IEEE Trans. Automat. Control. Vol. 51. No. 5. 2006. P. 742-753.

Tempo R., Calafiore C, Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems. — New York: Springer-Verlag. 2005.

Calafiore C, Dabbene F., Tempo R. Research on probabilistic methods for control system design // Automatica. Vol. 47. 2011. P. 1279-1293

Stengel R.F., Ray L.R. Stochastic robustness of linear time-invariant control systems // IEEE Trans. Autom. Control. 1991. Vol. 36. P. 82-87.

Khargonekar P.P., Tikku A. Randomized algorithms for robust control analysis have polynomial time complexity // Proc. of Conf. on Decision and Control. 1996. P. 3470-3475.

Barmish B.R., Lagoa CM. The uniform distribution: A rigorous justification for its use in robustness analysis // Math. Control, Signals, Syst. Vol. 10. 1997. P. 203-222.

Oishi Y., Kimura H. Randomized algorithms to solve parameter-dependent linear matrix inequalities and their computational complexity // Proc. of Conf. on Decision and Control. Orlando. USA. 2001. P. 2025-2030.

Calafiore G, Polyak B.T. Stochastic algorithms for exact and approximate feasibility of robust LMIs // IEEE Trans. Autom. Control. Vol. 46. 2001. P. 1755-1759.

Fujisaki Y., Dabbene F., Tempo R. Probabilistic robust design of LPV control systems // Automatica. Vol. 39. 2001. P. 1323-1337.

Polyak B.T., Tempo R. Probabilistic robust design with linear quadratic regulators // Syst. Control Lett. Vol. 43. 2001. P. 343-353.

Поляк Б. Т., Щербаков П.С. Робастная устойчивость и управление. — М.: Наука. 2002. 303 с.

Kanev S., De Schutter В., Verhaegen M. The ellipsoid algorithm for probabilistic robust controller design // Proc. of Conf. on Decision and Control. Las Vegas. USA. 2002. P. 2248-2253.

Ishii H., Basar Т., Tempo R. Randomized algorithms for quadratic stability of quantized sampled-data systems // Automatica. Vol. 40. 2004. P. 839-846.

Щербаков П. С. Генерирование устойчивых полиномов // Стохастическая оптимизация в информатике. 2009. Вып. 5. С. 65-90.

Граничин О.Н., Халидов В.И. Рандомизированный подход к обнаружению разрывов функции // Стохастическая оптимизация в информатике. Т. 1. 2005. С. 73-80.

Граничин О.Н., Шалимов Д.С, Аврос Р., Волкович 3. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. №4. С. 86-98.

Avros R., Granichin О., Shalymov D., Volkovich Z., Weber G.-W. Randomized algorithm of finding the true number of clusters based on Chebychev polynomial approximation (Chapter 6) // Data Mining: Found, and Intell. Paradigms, D.E. Holmes, L.C. Jain (Eds.). — Berlin Heidelberg: Springer-Verlag, ISRL 23. Vol. 1. 2011. P. 131-155.

Granichin O., Morozkov M., Volkovich Z. Necessary conditions for the confidence level of the randomized algorithm of finding the true number of clusters // Proc. of IEEE Int. Symposium on Intelligent Control (MSC-2011). Denver. USA. 2011. P. 1002-1007.

Морозков М.А. Быстрый рандомизированный алгоритм нахождения точного количества кластеров в большом множестве данных // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 69-82.

Фелъдбаум А.А. О проблемах дуального управления // В кн.: Методы оптимизации автоматических систем. — М.: Наука. 1972. С. 89-108.

Граничин О.Н., Фомин В.Н. Адаптивное управление с использованием пробных сигналов // Автоматика и телемеханика. 1986. № 2. С. 100-112.

Chen H.-F., Guo L. Convergence rate of least-squares stochastic systems // Int. J. of Control. 1986. Vol. 44. No. 5. P. 1459-1477.

Campi M.C., Weyer E. Non-asymptotic confidence sets for the parameters of linear transfer functions // IEEE Trans. Automat. Control. Vol. 55. No. 12. 2010. P. 2708-2720.

Calafiore G.C., Fagiano L. Robust model predictive control: the random convex programming approach // Proc. of IEEE Int. Symposium on Intel. Control. Denver. USA. 2011. P. 222-227.

Граничин О.Н. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // Автоматика и телемеханика. 2002. № 9. С. 125-133.

Granichin O.N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automat. Contr. Vol. 49. Oct. 2004. No. 10. P. 1830-1835.

Baxumoe А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. № 11. С. 70-79.

Vakhitov A., Granichin O., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. 2010. Baltimore. USA. P. 4004-4009.

Амелин К.С, Граничин О.П. Возможности рандомизации в алгоритмах предсказания калмановского типа при произвольных внешних помехах в наблюдении // Гироскопия и навигация. №2 (73). 2011. С. 38-50.

Амелин К. С. Возможности рандомизации в алгоритме предсказания отклонения от курса легкого беспилотного летательного аппарата при произвольных внешних помехах в наблюдении // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 93-115.

Кривоконъ Д.С., Вахитов А.Т. Нестационарная оптимизация с шагом предсказания в задаче отслеживания объекта при помощи двух камер // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 116-127.

Candes E., Romberg J., Тао Т. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information // IEEE Trans. Inform. Theory. Feb. 2006. Vol. 52. No. 2. P. 489-509.

Donoho D. Compressed sensing // IEEE Trans. Inform. Theory. Apr. 2006. Vol. 52. No. 4. P. 1289-1306.

Граничин О.Н. Рандомизация измерений и l1-оптимизация // Стохастическая оптимизация в информатике. Вып. 5. 2009. С. 3-23.

Граничин О.Н., Павленко Д-В. Рандомизация данных и 11-оптимизация // Компьютерные инструменты в образовании. 2010. №1. С. 5-13.

Граничин О.Н., Павленко Д-В. Рандомизация получения данных и l1-оптимизация (опознание со сжатием) (Обзор) // Автоматика и телемеханика. 2010. № 11. С. 3-28.

Вахитов А.Т., Граничин О.Н., Сысоев С.С. Точность оценивания рандомизированного алгоритма стохастической оптимизации // Автоматика и телемеханика. 2006. № 4. С. 86-96.

Tang Q-Y., Chen H.F., Han Z-J. Convergence rates of Perturbation-Analysis-Robbins-Monro-Single-Run algorithms for single server queues // IEEE Trans, on Automatic Control. 1997. Vol. 42. No. 10. P. 1442-1447.

Волкович Я.В., Граничин О.Н. Адаптивная оптимизация сервера, обрабатывающего очередь заданий // Стохастическая оптимизация в информатике. Т. 1. 2005. С. 17-28.

Вахитов А.Т., Граничин О.Н., Панъшенсков М.А. Методы оценивания пропускной способности в распределенных системах // Нейрокомпьютеры: разработка, применение. 2009. № 11. С. 45-53.

Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. № 8. С. 52-63.

Александров А.Г., Орлов Ю.Ф. Конечно-частотная идентификация: динамический алгоритм // Проблемы управления. 2009.

№ 4. С. 2-8.

Bai E.W., Nagpal K.M., Tempo R. Bounded-error parameter estimation: Noise models and recursive algorithms // Automatica. Vol. 32. 1996. P. 985-999.

Garulli A., Giarre L., Zappa G. Identification of approximated Hammerstein models in a worst-case setting // IEEE Trans. Autom. Control. Vol. 47. No. 7. Dec. 2002. P. 2046-2050.

Соколов В. Ф. Оценка качества робастной системы управления при неизвестных верхних границах возмущений и помехи измерений // Автоматика и телемеханика. Ж 9. 2010. С. 3-18.

Фомин В.Н. Методы управления линейными дискретными объектами. — Л.: Изд-во Ленингр. ун-та. 1985. 336 с.

Быстрый рандомизированный

алгоритм нахождения точного количества

кластеров в большом множестве данных

М. А. Морозков

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

mmorozkov@gmail.com

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

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

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

[1] Boyd S., Mattingley J., Grant M., Wang Y. Real-Time Embedded Convex Optimization. — Plenary Speech on IEEE MSC-2011. 2011. Denver. USA. 2011.

[2] Граничин О.Н. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике. Т. 6. 2010. С. 3-44.

[3] Амелин К.С, Граничин О.Н. Новые рандомизированные алгоритмы в управлении и обработке данных // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 3-68.

[4] Calafiore G.C., Campi M.C. The scenario approach to robust control design // IEEE Trans. Automat. Control. Vol. 51. No. 5. May 2006. P. 742-753.

[5] Calafiore G.C., Fagiano L. Robust model predictive control: the random convex programming approach // Proc. of 2011 IEEE Int. Symposium on Intelligent Control. Denver. USA. 2011. P. 222-227.

[6] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. № 8. С. 52-63.

[7] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

[8] Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. Ж 2. С. 44-55.

[9] Hartigan J. Statistical theory in clustering // J. Classification. Vol. 2. 1985.

[10] Sugar C, James G. Finding the number of clusters in a data set: An information theoretic approach // J. of the American Statistical Association. Vol. 98. 2003. P. 750-763.

[11] Граничин О.Н., Шалимов Д.С, Аврос Г., Волкович 3. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. №4. С. 86-98.

[12] Avros R., Granichin О., Shalymov D., Volkovich Z., Weber G.-W. Randomized algorithm of finding the true number of clusters based on Chebychev polynomial approximation (Chapter 6) // Data Mining: Found, and Intell. Paradigms, D.E. Holmes, L.C. Jain (Eds.) - Berlin Heidelberg: Springer-Verlag , ISRL 23. Vol. 1. 2011. P. 131-155.

[13] Granichin O., Morozkov M., Volkovich Z. Necessary conditions for the confidence level of the randomized algorithm of finding the true number of clusters // Proc. of 2011 IEEE Int. Symposium on Intelligent Control. (MSC-2011). Denver. USA. 2011. P. 1002-1007.

[14] Levine E., Domany E. Resampling method for unsupervised estimation of cluster validity // Neural Computation. Vol. 13. 2001. P. 2573-2593.

[15] Jain А.К., Moreau J. V. Bootstrap technique in cluster analysis // Pattern Recognition. Vol. 20. 1987. P. 547-568.

[16] Cuevas A., Febrero M., Fraiman R. Estimating the number of clusters // Canadian J. of Statistics. Vol. 28(2). 2000. P. 367-382.

[17] Cuevas A., Febrero M., Fraiman R. Cluster analysis: a further approach based on density estimation // Computational Statistics and Data Analysis. Vol. 28. 2001. P. 441-459.

[18] Volkovich Z., Barzily Z., Morozensky L. A statistical model of cluster stability // Pattern Recognition. Vol. 41. 2008. P. 2174-2188.

[19] Граничин О.Н., Халидов В.И. Рандомизированный подход к обнаружению разрывов функции // Стохастическая оптимизация в информатике. Т. 1. 2005. С. 73-80.

[20] Sharma P., Salapaka S., Beck С. A scalable approach to combinatorial library design for drug discovery // J. of Chemical Information and Modeling. Vol. 48. No. 1. 2008. P. 27-41.

[21] Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of euclidean sum-of-squares clustering // Mach. Learn. Vol. 7. No. 2. 2009. P. 245-248.

[22] Cortes J., Martinez S., Karatas Т., Bullo F. Coverage control for mobile sensing networks: variations on a theme // Proc. of Mediterranean Conf. on Control and Automation. 2002.

[23] Sheu J.B. A fuzzy clustering-based approach to automatic freeway incident detection and characterization // Fuzzy Sets Syst. Vol. 128. No. 3. 2002. P. 377-388.

[24] Sharma P., Salapaka S., Beck C. Entropy based algorithm for combinatorial optimization problems with mobile sites and resources // Proc. of American Control Conf. 2008. P. 1255-1260.

[25] Xu Y., Salapaka S., Beck CL. Dynamic maximum entropy algorithms for clustering and coverage control // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. P. 1836-1841.

Квазирандомизированный метод решения систем линейных уравнений

С И. Смирнов, аспирант

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

q4ality@gmail.com

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

Большой прикладной интерес представляет случай, когда упомянутые значения вычисляются с помощью методов Монте-Карло. В частности, если требуется решить большую систему линейных алгебраических уравнений, то вычислительную работу можно уменьшить за счет рандомизации или конструирования несмещенных оценок суммы квадратов невязок (случайный выбор к уравнений из п, где к <С п). В обоих случаях моделируется случайный процесс, решающий поставленную задачу. Представляет большой интерес использовать технику Квази-Монте-Карло метода (КМК) при моделировании.

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

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

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

[1] Sabelfeld К., Mozartova N. Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method // Monte Carlo Methods Appl. 2009. Vol. 15. No. 3. P. 257-284.

[2] Drineas P., Kannan R. Fast Monte Carlo algorithms for approximate matrix multiplication // Proc. of 42nd IEEE Symposium of Foundations of Computer Science. 2001. P. 452-459.

[3] Drineas P., Drinea E., Huggins P.S. An experimental evalution of Monte Carlo algorithms for singular value decompositions // Lecture notes in computer science. 2003. Vol. 2563. P. 279-296.

[4] Bockek LA. Calculation of the Ritz and Galerkin coefficients by the Monte-Carlo method // USSR Computational Mathematics and Mathematical Physics. 1967. Vol. 7. No. 1. P. 231-239.

[5] Ермаков С. М. Параметрически разделимые алгоритмы // Вестник СПбГУ. 2010. Сер. 1. Вып. 4. С. 25-32.

[6] Chen X., White H. Asymptotic properties of some projection-based Robbins-Monro procedures in a Hilbert space // Studies in Nonlinear Dynamics and Econometrics. 2002. Vol. 6. P. 1-53.

[7] Golub G.H., van Loan C.F. Matrix computations. — JHU. 1996. 3rd edition.

[8] Gyorfi L. Stochastic approximation from ergodic sample for linear regression // Z.Wahrscheinlichkeitstheorie verw. Gebiete. 1980. Vol. 54. P. 47-55.

Фильтрация

Технология программирования легкого БПЛА для мобильной группы

К. С. Амелин, аспирант

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

konstantinamelin@gmail.com

Рассматривается технология создания программ для автопилота легкого беспилотного летательного аппарата (БПЛА). Описывается трехуровневая архитектура легкого БПЛА, который оснащен стандартными исполнительными механизмами, автопилотом, бортовым микрокомпьютером, и в котором основным датчиком ориентирования в геодезической системе координат является навигационная система с модулями ГЛОНАС/GPS. Анализируются возможности создания адаптивного управления группой БПЛА за счет применения мультиагентных технологий, а также исследуются методики создания программы автопилота легкого БПЛА и построения алгоритмов оптимизации полета. В упрощенной математической модели предполагается, что на динамику полета БПЛА оказывает неконтролируемое влияние ветер, а наблюдения производятся с неизвестными, но ограниченными ошибками в системе навигации. Предлагается рандомизированный алгоритм, отфильтровывающий такие почти произвольные ошибки в наблюдении. Работоспособность нового алгоритма при нерегулярных помехах в наблюдениях иллюстрируется примерами имитационного моделирования в сравнении с традиционными подходами.

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

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

[1] Виттих В.А., Скобелев П.О. Метод сопряженных взаимодействий для управления распределением ресурсов в реальном масштабе времени // Автометрия. 2009. Т. 45. № 2. С. 84-86.

[2] Сайт по беспилотным летательным аппаратам /bpla.ru/

[3] Сечин А.Ю., Дракин М.А., Киселева А.С. Беспилотный летательный аппарат: применение в целях аэрофотосъемки для картографирования. — М.:"Ракурс". 2011.

[4] Калман Р.Е., Бъюси Р. С. Новые результаты в линейной фильтрации и теории предсказания // Труды американского общества инженеров-механиков. Техническая механика. 1961. Т. 83. Сер. Д. № 1. С. 123-141.

[5] Фомин В.Н Рекуррентное оценивание и адаптивная фильтрация. — М.: Наука. 1984. 288 с.

[6] Kibzun A.I., Кап Yu.S Stochastic Programming Problems with Probability and Quantile Functions. — Chichester: Wiley. 1996.

[7] Панков А.Р., Семенихин К.В. Минимаксная идентификация обобщенной неопределенно-стохастической линейной модели // Автоматика и телемеханика. 1998. № 11. С. 158-171.

[8] Поляк Б. Т., Щербаков П.С. Робастная устойчивость и управление — М.: Наука. 2002. 303 с.

[9] Степанов О.А., Осипов А.В., Васильев В.Н. Открытые муль-тиагентные системы для оперативной обработки информации в процессах принятия решений // Автометрия. 2002. №6. С. 45-61.

[10] Амелин К. С. Легкий беспилотный летательный аппарат для автономной группы // Стохастическая оптимизация в информатике. Т. 6. 2010. С. 117-126.

[11] Амелин К.С, Антал Е.И., Васильев В.И., Граничина И.О. Адаптивное управление автономной группой беспилотных летательных аппаратов // Стохастическая оптимизация в информатике. Вып. 5. 2009. С. 157-166.

[12] Амелин К.С, Граничин О.И. Мультиагентное сетевое управление группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № 6. С. 64-72.

[13] Интернет ресурс проекта Paparazzi /paparazzi.enac.fr/.

[14] Punin Y.O., Shtukenberg A.G., Smetannikova O.G., Amelin K.S. Plagioclase twin associations from the basic volcanic rocks of the Kamchatka, Russia: growth conditions and formation mechanisms // European Journal of Mineralogy. 2010. No. 1. P. 139-145.

[15] Allen M.J. Autonomous soaring for improved endurance of a small uninhabited air vehicle // 43rd AIAA Aerospace Sciences Meeting and Exhibit (AIAA 2005). Reno. Nevada. 2005. P. 1025.

[16] Reichmann H. Cross-Country Soaring. — Minnesota: Soaring Society of America. 1978.

[17] Edwards D.J. Implementation Details and Flight Test Results of an Autonomous Soaring Controller. — NC State Univ.

[18] Antal G, Granichin O., Levi S. Adaptive autonomous soaring of multiple UAVs using simultaneous perturbation stochastic approximation // IEEE Conf. on Decision and Control (CDC-49). Atlanta. USA. 2010. P. 3656-3661.

[19] Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. №1(4). С. 19-21.

[20] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

[21] Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. № 2. С. 44-55.

[22] Граничин О.Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. — М.: Наука. 2003. 293 с.

[23] Граничин О.И. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике. Т. 6. 2010. С. 3-44.

[24] Вахитов А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. № 11. С. 70-79.

[25] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of IEEE Conf. on Decision and Control (CDC-48). 2009. Shanghai. P.R. China. P. 5763-5767.

[26] Granichin O., Vakhitov A., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. (ACC-2010) 2010. Baltimore. MD. USA. P. 4004-4009.

[27] Granichin O.N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automat. Contr. Vol. 49. Oct. 2004. No. 10. P. 1830-1835.

[28] Граничин О.И. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. 2002. №1. С. 30-41.

[29] Граничин О.И. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // Автоматика и телемеханика. 2002. № 9. С. 125-133.

[30] Амелин К.С., Граничин О.И. Возможности рандомизации в алгоритмах предсказания калмановского типа при произвольных внешних помехах в наблюдении // Гироскопия и навигация. № 2(73). 2011. С. 38-50.

[31] Levy L.J. Применение фильтра Калмана в навигационной аппаратуре // GPS World. USA. Сентябрь 1997.

Нестационарная оптимизация с шагом предсказания в задаче отслеживания объекта при помощи двух камер

Д. С. Кривоконъ,

А. Т. Вахитов, к. ф.-м. н.

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

dmitry00@gmail.com, alexander.vakhitov@gmail.com

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

Ключевые слова: нестационарная оптимизация, отслеживание объекта, стерео-камера.

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

[1] Поляк Б. Т. Введение в оптимизацию. — М.: Наука. 1983.

[2] Robbins H., Monro S. A stochastic approximation method // Annals of Mathematical Statistics. 1951. Vol. 22. No. 3. P. 400-407.

[3] Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function. // Annals of Mathematical Statistics. 1952. Vol. 23. No. 3. P. 462-466.

[4] Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. Вып.1(4). С. 19-21.

[5] Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 2. С. 45-53.

[6] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

[7] Spall J.C. Multivariate stochastic aproximation using a simultaneous perturbation gradient aproximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332-341.

[8] Граничин О.П. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике. Т. 6. 2010. С. 3-44.

[9] Попков А. Ю. Градиентные методы для нестационарных задач безусловной оптимизации // Автоматика и телемеханика. 2005. № 6. С. 883-891.

[10] Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag. 2002.

[11] Granichin O., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of the Combined 48th IEEE Conf. on Decision and Control and 28th Chinese Control Conf. Shanghai. P.R. China. 2009. P. 5763-5767.

[12] Gurevich L., Vakhitov A. SPSA Algorithm for Tracking. // Proc. 12th Int. Student Olympiad on Automatic Control. 2008. P. 52-57.

[13] Фомин B.H. Методы управления линейными дискретными объектами. — Л.: Изд-во Ленингр. ун-та. 1985.

[14] Матвеев А.С, Якубович В.А. Абстрактная теория оптимального управления. — СПбГУ. 1994.

[15] Zisserman A., Hartley R. Multiple View Geometry in Computer Vision. — Cambridge University Press. 2004.

[16] Mikic I., Santini S., Jain R. Video processing and integration from multiple cameras. // Proc. of the Image Understanding Workshop. Morgan-Kaufman. 1998. P. 183-187.

[17] She S. Navigation System for Autonomous Mobile Robot — a Simultaneous Localization and Mapping Approach, [online] www.ietymec.org/papers/U16.pdf

[18] Sibley G., Sukhatme G., Matthies L. The iterated sigma point kalman filter with applications to long range stereo // Proc. of Robotics: Science and Systems. 2006.

[19] Kahl F., Hartley R. Multiple-view geometry under the Ll-Norm. // IEEE Trans, on Pattern Analysis and Machine Intelligence. 2008. Vol. 30. No. 9.

Идентификация нестационарного динамического объекта методом инвариантного погружения на закрепленном интервале

В. М. Понятский, к. т. н., доцент

ГУП "Конструкторское бюро приборостроения", Тула

kbkedr@tula.net, pwmru@rambler.ru

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

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

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

[1] Сейдж Э.П., Мелса Дж.Л. Теория оценивания и ее применение в связи и управлении. - М.: Связь, 1976.

[2] Медич Дж. Статистически оптимальные линейные оценки и управление. - М., Энергия. 1973.

[3] Понятский В.М., Замотаев И.В., Киселев В.Б. Идентификация нестационарного динамического объекта с использованием метода инвариантного погружения // Материалы VII Международной конференции "Идентификация систем и задачи управления"(28-31 января, 2008) - М.: ИПУ, 2008.

[4] Понятский В.М. Оценка экспериментальных характеристик летательного аппарата методом инвариантного погружения // Первая Всероссийская научно-техническая конференция кФундаментальные основы баллистического проектированиян>.23-26 июня 2008 г.: Сборник материалов — Санкт-Петербург. БГТУ. 2008. Т. 1 С. 29-33

[5] Понятский В.М., Оберман М.С. Программа для идентификации методом фильтрации Калмана параметров линейной нестационарной модели динамического объекта // Труды международной конференции "Третьи Окуневские чтения". Ч.З. — СПб.:БГТУ, 2003.

Синтез интервального фильтра Калмана на основе минимаксного подхода

В. М. Понятский, к. т. н., доцент

ГУП "Конструкторское бюро приборостроения", Тула

kbkedr@tula.net, pwmru@rambler.ru

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

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

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

[1] Сейдж Э.П., Мелса Дж.Л. Теория оценивания и ее применение в связи и управлении. - М.: Связь, 1976.

[2] Толпегин О.В. Дифференциально-игровые методы управления движением беспилотных летательных аппаратов. - СПб. БГ-ТУ. 2009. - 244 с.

[3] Кумков СИ. Разработка совместного Российского - ISO стандарта (методики) обработки измерительной информации в условиях неопределенности ошибок измерений и малого числа наблюдений (на основе методов интервального анализа) // Доклады Всероссийского Совещания по интервальному анализу и его приложениям "ИНТЕРВАЛ-06", 1 - С.-Пб, Санкт-Петербургский государственный университет. 2006. С. 63-67, http://www.ict.nac.ru/interval/Conferences/Interval-06.

Мулътиагентные системы

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

Н. О. Амелина, аспирант

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

leishe@mail.ru

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

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

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

[1] Shoham Y., Leyton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations — London: Cambridge University Press. 2009. 513 p.

[2] Официальный сайт НПК "Генезис знаний" http://www.kg.ru/.

[3] Лада А., Майоров И., Скобелев П., Царев А., Амелина Н. Исследование моделей организации грузовых перевозок с применением мультиагентной системы адаптивного планирования грузовиков в реальном времени // Проблемы управления. 2011. № 6.

[4] Murray R.M., Astrom K.J., Boyd S.P., Brockett R.W., Stein G. Future directions in control in an information-rich world // IEEE Control Systems. 2003. Vol. 23. No. 2. P. 20-33.

[5] Городецкий В.И., Грушинский М.С., Хабалов А.В. Многоагент-ные системы (обзор) // Новости искусственного интеллекта. 1998. №2. С. 64-116.

[6] Скобелев П. О. Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений // Автометрия. 2002. № 6. С. 45-61.

[7] Maes P. Agent that reduce work and information overload // Communication of the ACM. July 1994. Vol. 37. No. 7. P. 30-40.

[8] Cohen P.R., Morgan J.L., Pollack M. Intentions in Communication - Bradford Books. MIT Press. 1990. 508 p.

[9] Тарасов В.Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте // Новости искусственного интеллекта. 1998. № 2. С. 5-63.

[10] Граничина И.О. Мультиагентная система для распределения заказов // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". 2010. С. 549-566.

[11] Виттих В.А., Скобелев П.О. Метод сопряженных взаимодействий для управления распределением ресурсов в реальном масштабе времени // Автометрия. 2009. Т. 45. № 2. С. 84-86.

[12] Каляев И.А., Гайдук А.Р., Капустян С.Г. Распределенные системы планирования действий коллективов роботов. — М.: Янус-К. 2002. 292 с.

[13] Амелин К.С, Антал Е.И., Васильев В.И., Граничина И.О. Адаптивное управление автономной группой беспилотных летательных аппаратов // Стохастическая оптимизация в информатике. Вып. 5. 2009. С. 157-166.

[14] Antal С, Granichin О., Levi S. Adaptive autonomous soaring of multiple UAVs using SPSA // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. Atlanta. USA. P. 3656-3661.

[15] Амелин К. С, Граничин О.И. Мультиагентное сетевое управление группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № 6. С. 64-72.

[16] Фрадков А.Л. Кибернетическая физика: принципы и примеры - СПб.: Наука. 2003. 208 с.

[17] Olfati-Saber R., Murray R.M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Trans. Automatic Control. Sept. 2004. Vol. 49. P. 1520-1533.

[18] Ren W., Beard R.W. Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications — Communication and Control Engineering Series. — Springer Verlag. New York. 2007. 319 p.

[19] Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов) // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". 2010. С. 470-505.

[20] Fax A., Murray R.M. Information flow and cooperative control of vehicle formations // IEEE Trans. Automat. Contr. Sept. 2004. Vol. 49. P. 1465-1476.

[21] Tanner H.G., Jadbabaie A., Pappas G. J. Flocking in fixed and switching networks // IEEE Trans. Autom. Contr. 2007. Vol. 52. No. 5. P. 863-868.

[22] Li W. Stability analysis of swarms with general topology // IEEE Trans. Syst. Man. Cybern. B. 2008. Vol. 38. No. 4. P. 1084-1097.

[23] Гершгорин С.A. Uber die abgrenzung der eigenwerte einer matrix // Изв. АН СССР, отд. физ.-мат. наук. 1931. С. 749-754.

[24] Деревицкий Д.П., Фрадков А.Л. Две модели для анализа динамики алгоритмов адаптации // Автоматика и телемеханика. 1974. № 1. С. 67-75.

[25] Ljung L. Analysis of recursive stochastic algorithms // IEEE Trans. Aut. Control. 1977. No. 4. P. 551-575.

[26] Деревицкий Д.П., Фрадков А.Л. Прикладная теория дискретных адаптивных систем управления. — М.: Наука. 1981. 216 с.

[27] Fradkov A.L. Continuous-time averaged models of discrete-time stochastic systems: survey and open problems // Proc. of IEEE Conf. on Decision and Control (CDC-50). Orlando. USA. 2011.

[28] Гелиг А.Х., Леонов Г.А., Якубович В.А. Устойчивость нелинейных систем с неединственным состоянием равновесия. — М.: Наука. 1978. 400 с.

[29] Huang M. Stochastic Approximation for Consensus with General Time-Varying Weight Matrices // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. Atlanta. USA. P. 7449-7454.

[30] Armbruster D., Mikhailov A.S., Kaneko K. (eds.) Networks of Interacting Machines: Production Organization in Complex Industrial Systems and Biological Cells — World Scientific. Singapore. 2005. 267 p.

[31] Glashenko A., Inozemtzev S., Grachev I., Skobelev P. Magenta Technology: case studies of Magenta i-scheduler for road transportation // Proc. of Int. Conf. on Autonomous Agents and Multi Agent Systems (AAMAS-6). Hawaii. 2007. P. 1385-1392.

[32] Граничин О.Н. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике. 2010. Т. 6. С. 3-44.

[33] Вахитов А.Т., Граничин О.Н., Панъшенсков М.А. Методы оценивания скорости передачи данных в грид // Нейрокомпьютеры: разработка, применение. 2009. № 11. С. 45-52.

[34] Friedrich Т.A., Sauerwald Т.В., Vilenchik D.C. Smoothed analysis of balancing networks // Random Structures and Algorithms. Aug. 2011. Vol. 39. No. 1. P. 115-138.

[35] Li H. Load balancing algorithm for heterogeneous P2P systems based on Mobile Agent // Proc. of ICEICE 2011. 2011. P. 1446-1449.

[36] Kechadi M.-T., Savvas I.K. Dynamic task scheduling for irregular network topologies // Parallel Computing. 2005. Vol. 31. No. 7. P. 757-776.

[37] Катуева Я.В. Балансировка загрузки несимметричного вычислительного комплекса при решении задачи статистического оценивания // Информатика и системы управления. 2006. № 2(12). С. 88-93.

[38] Костенецкий П. С, Лепихов А.В., Соколинский Л.Б. Технологии параллельных систем баз данных для иерархических многопроцессорных сред // Автоматика и телемеханика. 2007. № 5. С. 112-125.

[39] Gilly К., Juiz С, Puigjaner R. An up-to-date survey in web load balancing // World Wide Web. 2011. Vol. 14. No. 2. P. 105-131.

[40] Granichin O., Vakhitov A., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. (ACC-2010). 2010. Baltimore. USA. P. 4004-4009.

[41] Вахитов А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. №11. С. 70-79.

[42] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of IEEE Conf. on Decision and Control (CDC-48). 2009. Shanghai. P.R. China. P. 5763-5767.

Обобщенные линейные алгоритмы управления формациями

С. Э. Парсегов, аспирант

Институт проблем управления РАН, Москва

parsegov@ipu.ru

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

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

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

[1] Ren W., Beard R. W., Atkins E.M. A survey of consensus problems

in multi-agent coordination // Proc. American Control Conf. 2005. Vol. 3. P. 1859-1864.

[2] Pavone M., Frazzoli E. Decentralized policies for geometric pattern formation and path coverage // ASME Journal on Dynamic Systems, Measurement, and Control. 2007. Vol. 129. No. 5. P. 633-643.

[3] Ramirez J.L.,Pavone M., Frazzoli E. and Miller D. W. Distributed Control of Spacecraft Formations via Cyclic Pursuit: Theory and Experiments // AIAA Journal of Guidance, Control, and Dynamics. 2010. Vol. 33. No. 5. P. 1655-1669.

[4] Петрикевич Я.И. Линейные алгоритмы управления геометрическим расположением объектов в многоагентной системе // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". — М.: ИПУ РАН. 2010. С. 665-680.

[5] Щербаков П. С. Управление формациями: схема Ван Лоуна и другие алгоритмы // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". — М.: ИПУ РАН. 2010. С. 681-696.

[6] Поляк Б. Т., Цыпкин Я.З. Устойчивость и робастная устойчивость однотипных систем // Автоматика и телемеханика. 1996. № 11. С. 91-104.

[7] Нага S., Hayakawa Т., Sugata H. Stability analysis of linear systems with generalized frequency variables and its applications to formation control // Proc. Decision and Control Conf. 2007. P. 1459-1466.

[8] Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. — М.: Наука. 1984. 320 с.

Дискретные стохастические системы

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

В. Н. Трубников,

М. К. Чирков, д. ф.-м. н.

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

vakh08@mail.ru

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

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

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

[1] Чирков М.К., Пономарева А.Ю. Стационарные детерминированные и вероятностные автоматы (Теория автоматных моделей) - СПб.: Изд. СПбГУ. 2008. 248 с.

[2] Трубников В.Н., Чирков М.К. Об эквивалентном преобразовании R-нечетких автоматов в стохастические // Стохастическая оптимизация в информатике. Том 6 (Выи 1). — СПб.: Изд. СПбГУ. 2010. С. 184-202.

[3] Чирков М.К., Наср Я. О стохастических и нестохастических минимальных формах стохастических автоматов // Теория и приложения дискретных систем. — СПб.: Изд. СПбГУ. 1995. С. 37-67.

[4] Masakazu N., Namio H. Fuzzy events realized by probabilistic automata // Inform, and Control. Vol. 12. No. 15. 1968. P. 284-303.

[5] Шестаков А.А., Чирков М.К. Обобщенные конечные автоматы: Поведенческая эквивалентность и проблемы оптимизации.

- Апатиты: Изд. КНЦ РАН. 1992. 160 с.

[6] Чирков М.К., Кабаве М. Абстрактный анализ обобщенных конечных автоматов // Теория и приложения дискретных систем.

- СПб.: Изд. СПбГУ. 1995. С. 3-36.

[7] Чирков М.К., Кабаве М. Абстрактный синтез обобщенных конечных автоматов // Математическое моделирование дискретных систем. - СПб.: Изд. СПбГУ. 1995. С. 3-37.

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

Н. К. Кривулин, д. ф.-м. н.

О. А. Нев

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

nkk@math.spbu.ru, nevolga@gmail.com

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

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

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

[1] Heidergott В., Olsder G.J., van der Woude J. Max-Plus at work. — Princeton: Princeton University Press, 2006.

[2] Маслов В.П., Колокольцев В.Н. Идемпотентный анализ и его применение в оптимальном управлении.—М.:Физматлит. 1994.

[3] Кривулин Н.К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. — СПб.: Изд-во С-Петерб. ун-та. 2009.

[4] Olsder G.J., Resing J.A.C., De Vries R.E., Keane M.S., Hooghiemstra G. Discrete event systems with stochastic processing times // IEEE Trans. Automat. Contr. 1990. Vol. 35. No. 3. P. 299-302.

[5] Jean-Marie A. Analytical computation of Lyapunov exponents in stochastic event graphs // Performance Evaluation of Parallel and Distributed Systems. Solution Methods: Proc. 3rd QMIPS Workshop. Amsterdam: CWI Tracts. Vol. 106. 1994. P. 309-341.

[6] Кривулин Н.К. Скорость роста вектора состояний обобщенной линейной стохастической системы с симметричной матрицей // Зап. науч. семин. ПОМИ. 2007. Т. 341. С. 134-141.

[7] Кривулин Н.К. О вычислении скорости роста вектора состояний обобщенной линейной стохастической системы второго порядка // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 1. С. 38-48.

[8] Кривулин Н.К. Вычисление показателя Ляпунова обобщенных линейных систем с показательным распределением элементов переходной матрицы // Вестн. С.-Петерб. ун-та. Сер. 1. 2009. Вып. 2. С. 37-47.

[9] Кривулин Н.К. Вычисление показателя Ляпунова для одной модели стохастической системы с синхронизацией // Стохастическая оптимизация в информатике. 2010. Т. 6. С. 171-183.

[10] Кривулин Н.К. Вычисление средней скорости роста вектора состояний стохастической системы с синхронизацией событий // Вестн. С.-Петерб. ун-та. Сер. 1. 2011. Вып. 1. С. 109-116.

Информационные системы

Сопоставление синтаксических элементов в системах контроля версий

Павленко Д. В., аспирант

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

dmit10@gmail.com

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

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

[1] http://en.wikipedia.org/wiki/Subversion.

[2] http://en.wikipedia.org/wiki/Git.

[3] http://en.wikipedia.org/wiki/Mercurial.

[4] Лап S., Heung-Yeung S., Nan-Ning Zh. Stereo matching using belief propagation // IEEE Trans, on Pattern Analysis and Machine Intelligence. 2003. Vol. 25. P. 787-800.

[5] Boykov Y., Veksler O., Zabih R. Markov random fields with efficient approximations // In IEEE conf. on Computer Vision and Pattern Recognition (CVPR). 1998. P. 648-655.

[6] Samson Ch. Proof of Hammersley-Clifford Theorem. 2008.

[7] Yedidia J.S., Freeman W.T., Weiss Y. Understanding belief propagation and its generalizations // Exploring Artificial Intelligence in the New Millennium. Science & Technology Books. 2003. Chap. 8. P. 239-236.

[8] Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. № 2. С. 44-55.

[9] Граничин О.Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 88-99.

Стохастический метод решения задач классификации и обучения

В. Н. Шац, д. т. н.

Санкт-Петербург

vlnash@mail.ru

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

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

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

[1] Браверман Э. М., Мучник И. Б. Структурные методы обработки эмпирических данных. — М.: Наука. 1983. 496 с.

[2] Граничин О.Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания при почти произвольных помехах. — М.: Наука. 2003. 291 с.

[3] Прикладная статистика: Классификация и снижение размерности: Справ, изд. / Под ред. С.А. Айвазяна. — М.: Финансы и статистика. 1989. 607 с.

[4] Материалы "круглого стола". Информационный подход в междисциплинарной перспективе // Вопросы философии. 2010. №2. С. 84-112.

[5] Величковский Б.М. Когнитивнвая наука: Основы психологии познания: в 2 т. — Т.1. — М.: Смысл. 2006. 448 с.

[6] Шац В.Н. О модели воздействия информации на группу // Социология: методология, методы, математическое моделирование. 2010. №30. С. 181-194.

[7] Шац В.Н. Вычислительная модель модуля нервной системы // Сборник научных трудов научно-технической конференции "Нейроинформатика-2011" . Ч. 2. 2011. С. 229-238.

[8] Шац В.Н. Непрерывно ветвящаяся цепь как модель биологической цепи нейронов // Труды одиннадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2008. Т. 1. - М.: ЛЕНАНД. 2008. С. 164-170.

[9] Asuncion A., Newman D.J. UCI Machine Learning Repository. — Irvine CA: University of California, School of Information and Computer Science. 2007.

[10] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). — М.: Наука. 1974. 416 с.

ABSTRACTS

Randomized Algorithms

New Randomized Algorithms in Control and Data Processing

K. S Amelin, O. N. Granichin

Saint Petersburg State University

Oleg_granichin@mail.ru, konstantinamelin@mail.ru

Key words: randomized algorithms, optimization and estimation, control.

Randomization allows one to enrich the observation data and design speedy algorithms significantly reducing the number of operations and annihilating systematic errors (the bias effect of an arbitrary noise). Their accuracy usually weakly depends on the data dimension.

A randomized algorithm is nothing but a procedure where one or more steps are based on a random rule, that is, when using a randomized algorithm, at some stage instead of making a decision ourselves we call on fate to choose for us. But then, a question arises naturally: why should resorting to fate be any wise? Fate is not an expert of anything, all it does is choosing by chance. So, why should randomized be any good? A conscious use of randomized methods demands to question ourselves about this issue, and this paper contains some answers on this question. An exposition of randomized algorithms and their application are given.

Bibliogr.: 86 refs.

Fast Algorithm for Finding True Number of Clusters in a Large Data Set

M. A. Morozkov

Saint Petersburg State University

mmorozkov@gmail.com

Key words: clustering, randomized algorithms, adaptive control, optimization, machine learning.

One of the most difficult problems in cluster analysis is the identification of the number of groups in a given data set. In this paper we propose a randomized approach in the rate distortion framework and devise the corresponding randomized algorithm. The fundamental ideas of novel scenario approach are used in order to significantly reduce the computational cost. Having the ability to determine the true number of groups in a data set and perform clustering online, we outline several applications to control systems and decision-making problems that can essentially benefit from the considered algorithm. Simulation results show considerable improvement of the rate of convergence under the guaranteed level of probability.

Bibliogr.: 25 refs.

Quasirandomized Method for Solving of Linear Equation Systems

S. I. Smirnov

Saint Petersburg State University

q4ality@gmail.com

Key words: system of linear algebraic equations, Monte Carlo method, Quasi-Monte Carlo method, stochastic approximation.

As it is known, finding a root of the equation F (x) = 0 or extrema of the function G (x) from the measurements of F and G corrupted by random noise can be implemented via use of stochastic approximation methods.

Of the great applied interest is the case where the above-mentioned values are calculated by the Monte-Carlo method. In particular, if it is required to solve a large system of the linear algebraic equations, it is possible to reduce computational burden by using randomization or designing unbiased estimates for the sum of squares of the adjustments (we choose к random equations from n, where к <С n). Specifically, Quasi-Monte Carlo (QMC) methods might be very useful in simulations.

In this paper we present stochastic approximation algorithms for solving large systems of linear algebraic equations and discuss the advantages of using QMC for these problems.

Bibliogr.: 9 refs.

Filtering

Software Engineering of Unmanned Aerial Vehicle for Mobil Autonomous Group

K. S Amelin

Saint Petersburg State University

konstantinamelin@mail.ru

Key words: unmanned aerial vehicles, UAV, navigation system, autopilot, actuators, autonomous group of UAV, software engineering.

The control system architecture for an unmanned aerial vehicle (UAV) is considered which guarantees its proper functioning in an autonomous UAV group. The prototype of this newly created UAV is described. Flight optimization approaches are described.

Bibliogr.: 31 refs.

Non-stationary Optimization with Prediction Step for Object Tracking with Two Cameras

D. S. Krivokon, A. T Vakhitov

Saint Petersburg State University

dmitry00@gmail.com, alexander.vakhitov@gmail.com

Key words: non-stationary optimization, object tracking, stereo-camera.

The paper presents an application of a non-stationary randomized optimization method with prediction step to the problem of tracking an object from noisy readings of the two calibrated perspective cameras. Over the examples, the algorithm outperforms previously proposed non-stationary randomized optimization. The paper contains both theoretical justification and simulation.

Bibliogr.: 19 refs.

Identification of Non-stationary Dynamic Plant by a Method of Invariant Immersing on the Fixed Interval

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: identification, dynamic plant, parameters, discrepancy, signal, noise, model, reverse time.

A nonlinear method of invariant embedding is used in this paper for identification of non-stationary dynamic plants. With the proposed approach, the initial conditions for the estimated parameters can be refined via use of identification algorithms in reverse time. An inverse time estimation algorithm for the non-stationary parameters of a dynamic plant is designed and analyzed.

Bibliogr.: 5 refs.

Synthesis of the Interval Kalman Filter on the Basis of the Minimax Approach

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: dynamic plant, filtering, signal, noise, estimation.

An approach is proposed to interval Kalman filter both in continuous and discrete time. The interval Kalman filter is designed and compared to the conventional Kalman filter. The analysis of the results shows that the minimax filter provides a better accuracy of estimation while retaining the properties of the cojventional Kalman filter.

Bibliogr.: 3 refs.

Multi-Agent Systems

Multi-agent Technology, Adaptation, Self-organization, Consensus

N. O. Amelina

Saint Petersburg State University

leishe@mail.ru

Key words: multi-agent systems, multi-agent control, self-organization, adaptation, consensus, workload balancing network.

The paper presents a brief introduction to the multi-agent technology which focuses on the two important fields, namely, multi-agent systems in computer science and multi-agent control in a new control theory. Multi-agent technology is also deeply connected with decentralized and parallel computation, network communications and other related areas. The considerations are supplied by examples of self-organization and adaptation in a logistic problem and network workload balancing algorithm.

Bibliogr.: 42 refs.

Generalized Linear Algorithms for Formation Control

S. E. Parsegov

Institute of Control Sciences of RAS, Moscow

parsegov@ipu.ru

Key words: multi-agent systems, formation control.

In recent years, a new framework for systems to be handled appeared which is based on decentralized cooperative control using simple, identical, cooperating subsystems named agents. Such systems are referred to as multi-agent systems. In this paper, some linear algorithms that extend and generalize the known results for formation control are proposed. As the first step, the algorithms of allocation of a group of agents on a segment are considered, stability criteria and convergence analysis results are presented.

Bibliogr.: 8 refs.

Discrete Stochastic Systems

Representing Conditions

of Generalized Regular Languages

by Stochastic Automata

V. N. Trubnikov,

M. K. Tchirkov

Saint Petersburg State University

vakh08@mail.ru

Key words: stochastic finite automata, generalized regular languages, representation of generalized languages by automata, synthesis of automata in accordance with a regular expression of language.

The paper presents analysis and substantiation of necessary and sufficient conditions for the representation of generalized regular languages defined over the field of real numbers by stochastic finite automata. A stochastic automaton satisfying these conditions is designed from a regular expression of the generalized language. An example is given.

Bibliogr.: 7 refs.

Asymptotic Properties of State Vector

in a Generalized Linear Stochastic Dynamical

System with Symmetric Matrix

N. K. Krivulin, O. A. Nev

Saint Petersburg State University

nkk@math.spbu.ru, nevolga@gmail.com

Key words: stochastic dynamical system, Lyapunov exponent, idempotent semiring, convergence in distributions.

The paper examines stochastic dynamical systems described by a linear vector equation with second-order symmetric matrix in an idempotent semi-ring with operations of maximum and addition. It is assumed that the diagonal of the matrix consists of a nonnegative random variable and zero, whereas both off-diagonal elements are equal to a nonnegative constant. A problem of calculating the mean asymptotic growth rate of system state vector (the Lyapunov exponent) is considered. The solution includes change of variables resulting in new random variables that appear to be more suitable for analysis than the random coordinates of the state vector. Furthermore, for the new random variables, corresponding sequences of one-dimensional probability distributions are constructed and their convergence is examined. The Lyapunov exponent is calculated as the mean value of the limiting distribution for one of the sequences.

Bibliogr.: 10 refs.

Information Systems

Syntax Elements Matching in Version Control Systems

D. V. Pavlenko

Saint Petersburg State University

dmit10@gmail.com

The paper presents a formulation of the matching problem for file syntax elements. Solution of this problem facilitates better description of the modifications performed over the stored file contents and efficient solution of the conflict problem.

Bibliogr.: 9 refs.

Stochastic Method of Solving Problems of Classification and Training

V. N. Shats

St. Petersburg vlnash@mail.ru

Key words: information environment, classification problem, expansion of initial information, stochastic algorithm.

A stochastic method is proposed for the solution of classification and training problems. A continuous mapping of the set of points represented by objects with noisy data is considered, which generates a matrix that, under certain conditions, retains the properties of the objects in the original matrix. This mapping is implemented as a continuous multivariable function obtained in the information environment theory developed by the author. By varying random parameters of this function, an ensemble of matrices can be obtained. These enrich the initial information and reduce the corresponding problem to statistical evaluation of the deterministic solutions for individual matrices computed through a uniform algorithm.

Bibliogr.: 10 refs.

Содержание

Рандомизированные алгоритмы

Амелин К.С, Граничин О.Н. (СПбГУ) Новые рандомизированные
алгоритмы в управлении и обработке данных ............................................. 3

Морозков М.А. (СПбГУ) Быстрый рандомизированный алгоритм
нахождения точного количества кластеров в большом множестве дан
ных ................................................................................................................. 69

Смирнов С.И. (СПбГУ) Квазирандомизированный метод решения
систем линейных уравнений .........................................................................

Фильтрация

Амелин К.С. (СПбГУ) Технология программирования легкого БПЛА
для мобильной автономной группы................................................................ 93

Кривоконь Д.С, Вахитов А.Т. (СПбГУ) Нестационарная оптимиза
ция с шагом предсказания в задаче отслеживания объекта при по
мощи двух камер ........................................................................................... 116

Понятский В.М. (ГУП "КБП", Тула) Идентификация нестационар
ного динамического объекта методом инвариантного погружения на
закрепленном интервале................................................................................... 128

Понятский В.М. (ГУП "КБП", Тула) Синтез интервального фильтра
Калмана на основе минимаксного подхода .................................................. 142

Мультиагентные системы

Амелина Н.О. (СПбГУ) Мультиагентные технологии, адаптация, са
моорганизация, достижение консенсуса ...................................................... 149

Парсегов С.Э. (ИПУ, Москва) Обобщенные линейные алгоритмы
управления формациями ............................................................................... 186

Дискретные стохастические системы

Трубников В.Н., Чирков М.К. (СПбГУ) Условия представимости
обобщенных регулярных языков стохастическими автоматами..................... 204

Кривулин Н. К., Нев О.А. (СПбГУ) Асимптотические свойства век
тора состояний обобщенной линейной стохастической системы с сим
метричной матрицей......................................................................................... 232

Информационные системы

Павленко Д.В. (СПбГУ) Сопоставление синтаксических элементов в системах
контроля версий ............................................................................................ 240

Шац В.Н. (СПб) Стохастический метод решения задач классифи
кации и обучения ........................................................................................... 257

Abstracts ............................................................................................................. 269