В статье на основе использования свойств произведения Кронекера (КП) матриц предлагается новый алгоритм для повышения эффективности выполнения операции ум- ножения КП на вектор. Указанная операция широко применяется при решении задач обра- ботки сигналов, изображений, криптографии и т.п., где выполняется формирование мат- риц большого размера с заданными свойствами с помощью КП матриц малого размера. При этом используются матрицы со следующими свойствами: ортогональные (унитар- ные), обращаемые, инволютивные. Умножение квадратной матрицы размера на вектор имеет вычислительную сложность O(n2). Поэтому при росте количества элемен- тарных матриц-сомножителей размер результирующей матрицы КП и сложность умно- жения ее на вектор растут экспоненциально. Это обстоятельство существенно повыша- ет время решения прикладных задач. Целью предлагаемой работы является построение алгоритма, ориентированного на аппаратную реализацию и ускоряющего процессы фор- мирования КП и умножения вектора на него. Предлагается совместить во времени эти процедуры. Таким образом матрица КП в явном виде фактически не рассчитывается. Вме- сто этого матрицы-сомножители КП итеративно умножаются на компоненты вектора за время O(nlog2n) и требуют линейной сложности памяти. Приведена схема вычислений с топологией гиперкуба для возможной аппаратной реализации предлагаемого алгоритма, которая легко поддается конвейеризации. В разделе 1 приведены определения и свойства КП, используемые при синтезе предлагаемого алгоритма. В разделе 2 рассмотрен иллюст- рирующий предлагаемый алгоритм пример с , на основе которого в разделе 3 пред- ложена аппаратурно-ориентированная структура его реализации для произвольного n.
При разработке алгоритмов планирования путей роботов в режиме реального времени возникает проблема ограничения быстродействия соответствующих классических алгоритмов. В настоящей работе рассматривается метод планирования перемещений робота в двумерной сложной конфликтной среде. В отношении планирования в сложных средах предложен гибридный алгоритм планирования, базирующийся на сочетании и синтезе классического алгоритма клеточной декомпозиции и недавно предложенного алгоритма на базе характеристического графа видимости. Этот алгоритм подразумевает предварительный анализ степени сложности сцены с препятствиями, по результатам которого выбирается один из двух указанных частных алгоритмов. Показывается, что таким образом удается в значительной степени преодолеть ограничения обоих этих алгоритмов. В компактном виде описан метод уклонения от источников возмущения, основанный на аппарате характеристических вероятностных функций, и показана его взаимосвязь с методами планирования в сложных средах при решении соответствующих задач глобальной оптимизации вероятности успешного прохождения целевой траектории. В рамках развиваемого подхода рассмотрен вопрос о взаимосвязи вероятности успешного прохождения пути в поле источников и соответствующей функции риска. Для решения задач глобального планирования перемещений роботов в сложной конфликтной среде на первом этапе предлагается использовать указанный гибридный алгоритм - для построения семейства начальных кривых в соответствующих допустимых коридорах движения без учета источников. Затем решается семейство задач локальной оптимизации в пределах допустимых коридоров движения с учетом источников. Далее выбирается траектория с максимальным значением вероятности успешного прохождения либо нормированной функции безопасного движения. Приводятся примеры численной реализации предлагаемого метода, подтверждающие его эффективность
