Методы и алгоритмы планирования транспортных операций гетерогенной группы автономных роботов в условиях пространственно-ситуационной неопределенности тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Моторин Дмитрий Евгеньевич

• Моторин Дмитрий Евгеньевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Моторин Дмитрий Евгеньевич

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

§ 1.1. Общие методы управления роботами

§ 1.2. Анализ методов и алгоритмов картографирования и моделирования среды движения роботов

§ 1.3. Управление группой роботов в условиях пространственно-ситуационной неопределенности

§ 1.4. Постановка задачи планирования транспортных операций гетерогенной группы автономных роботов в условиях пространственно-ситуационной неопределенности

ГЛАВА 2. МЕТОДЫ УПРАВЛЕНИЯ ГРУППОЙ РОБОТОВ УСЛОВИЯХ ПРОСТРАНСТВЕННО-СИТУАЦИОННОЙ НЕОПРЕДЕЛЕННОСТИ

§ 2.1. Метод синтеза траектории движения робота в периодически изменяющейся среде

§ 2.2. Метод согласования глобальных и локальных траекторий движения робота на разномасштабных картах

§ 2.3. Метод адаптивного разрешения коллизий траекторий роботов в условиях пространственно-ситуационной неопределенности

ГЛАВА 3. АЛГОРИТМЫ УПРАВЛЕНИЯ ГРУППОЙ РОБОТОВ В УСЛОВИЯХ ПРОСТРАНСТВЕННО-СИТУАЦИОННОЙ НЕОПРЕДЕЛЕННОСТИ

§ 3.1. Задача планирования траекторий судов северного морского пути в условиях сложной ледовой обстановки

§ 3.2. Алгоритм синтеза траекторий движения робота в условиях пространственно-ситуационной неопределенности

§ 3.3. Алгоритм согласования глобальных и локальных траекторий движения робота на разномасштабных картах

§ 3.4. Алгоритм многокритериального поиска траекторий на многослойной карте

§ 3.5. Адаптивный алгоритм разрешения коллизий группы роботов в условиях пространственно-ситуационной неопределенности

Глава 4. ИССЛЕДОВАНИЯ АЛГОРИТМОВ УПРАВЛЕНИЯ

§ 4.1. Исследование метода синтеза траекторий движения робота в условиях пространственно-ситуационной неопределенности

§ 4.2. Исследование метода согласования глобальных и локальных траекторий движения робота на разномасштабных картах

§ 4.3. Исследование алгоритма многокритериального поиска траекторий на многослойной карте

§ 4.4. Исследование адаптивного метода разрешения коллизий группы роботов в условиях пространственно-ситуационной неопределенности

ВЫВОДЫ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы планирования транспортных операций гетерогенной группы автономных роботов в условиях пространственно-ситуационной неопределенности»

ВВЕДЕНИЕ

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

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

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

Степень разработанности темы исследования. Для управления робототехническими системами разработан ряд методов, методик и алгоритмов.

Фундаментальные вопросы управления роботами рассматриваются в работах Е.И. Юревича. Обобщение задачи распределения целей в группах роботов разной численности представлено в работах И.А. Каляева, С.Г. Капустяна, А.Р. Гайдука и В.Х. Пшихопова. Ярким примером исследования в области управления подвижными объектами в условиях высокой неопределенности среды являются работы А.В. Инзарцева.

Наиболее примечательными работами зарубежными исследованиями в этой области стоит отметить работы M. C. Hoy, в которых рассмотрены современные методы решения задач группового и индивидуального движения роботов. Задачи построения траекторий для оптимального выполнения глобальных целей рассматриваются в работах E. Gacleran и M. Carreras, а также L. E. Parker. Исследования, проводимые командой проекта «Martha» Rachid Alami, Sara Fleury, Matthieu Herrb, François Felix Ingrand, Farkas Robert, представляют задачу топологического и геометрического представления среды.

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

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

- разработке метода синтеза траекторий движения робота при решении циклических задач в периодически изменяющейся среде;

- разработке метода согласования локальных и глобальных траекторий на разномасштабных картах;

- разработке метода адаптивного разрешения числа коллизий траекторий роботов в динамических средах;

- разработке алгоритма поиска путей на многослойных реалистичных картах, учитывающих несколько заданных свойств среды;

- оценке реализованных методов и алгоритмов в системе управления на примере реалистичных динамических сред.

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

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

Научная новизна результатов исследования:

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

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

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

динамической оценке числа разрешаемых коллизий. Предложенный метод позволяет корректировать траектории движения на заданное число коллизий в зависимости от динамики среды.

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

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

Методология и методы диссертационного исследования. При

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

Научные результаты, выносимые на защиту:

1. метод синтеза траекторий движения робота при решении циклической транспортной задачи в периодически изменяющейся среде;

2. метод согласования глобальных и локальных траекторий на разномасштабных картах;

3. метод адаптивного разрешения коллизий при планировании движения группы роботов в условиях пространственно-ситуационной неопределенности;

4. алгоритм многокритериального поиска траекторий движения на многослойной карте.

Соответствие научного доклада паспорту научной специальности.

Отраженные в диссертации научные положения соответствуют области исследования пунктам 3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем» и

9 «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных» области исследования паспорта специальности 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей по номенклатуре специальностей научных работников «Технические науки».

Апробация и реализация результатов диссертации. Научные результаты и основные положения работы докладывались и обсуждались на конференциях: XXIII Международна научно-техническа конференция "Автоматизация на дискретното производство АДП - 2014", 19-22 июня, 2014, София, Болгария; Неделя науки СПБПУ, 14-19 ноября, 2016, Санкт-Петербург, Россия; 2017 XX IEEE International Conference on Soft Computing and Measurements (SCM), May 24 - 26, 2017 , St. Petersburg, Russia; 21rd IEEE Open Innovations Association Finnish-Russian University Cooperation in Telecommunications, November 6-10, 2017, Helsinki, Finland; 2018 XXI Международная конференция по мягким вычислениям и измерениям (SCM), 23 - 25 мая, 2018, Санкт-Петербург, Россия; VI Международная научно-практическая конференция «Прогресс транспортных средств и систем - 2018», 9-11 октября 2018, Волгоград, Россия.

Результаты работы поддержаны грантом правительства Санкт-Петербурга в конкурсе для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2017.

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

функционирования» № АААА-А17-117041110088-6 (17-01-00118 А); «Методы робастного синтеза интеллектуальных транспортных систем для коалиции киберфизических объектов на основе байесовской концепции вероятности и аппарата модальных логик» № АААА-А18-118071290029-0 (18-29-03250 мк).

Получены свидетельства о регистрации ЭВМ: «Программа для управления беспроводными соединениями транспортных средств с облачными информационными сервисами», номер регистрации (свидетельства): 2018612656, дата регистрации: 21.02.2018; «Программа моделирования решения транспортной задачи для группы роботов в условиях пространственно-ситуационной неопределенности», номер регистрации (свидетельства): 2018612745, дата регистрации: 26.02.2018.

Результаты научной работы внедрены в учебный процесс подготовки бакалавров и магистров по направлениям 02.03.01, 02.04.01 «Математика и компьютерные науки» в СПбПУ.

Личный вклад. Все результаты, представленные в диссертационной работе, получены лично автором в процессе выполнения научно -исследовательской деятельности.

Публикации. Основные результаты по теме научного исследования изложены в 11 печатных изданиях, 4 из которых изданы в журналах, рекомендованных ВАК, 3 - в издании индексируемом в Scopus, Web of Science и Springer.

Структура и объем работы. Диссертационное исследование состоит из: введения, четырех глав и заключения. Список использованной литературы содержит 156 наименований. Основной текст научной работы содержит 147 страницу машинописного текста, включая 37 рисунков и 3 таблицы.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ РЕШЕНИЯ

ТРАНСПОРТНЫХ ЗАДАЧ

§ 1.1. Общие методы управления роботами

Управление роботами включает в себя задачи из различных областей человеческих знаний, от механики, геометрии шасси и актуаторов [1, 2, 3], заканчивая глобальным планированием кооперативных действий группы гетерогенных роботов [4, 5, 6]. Робототехнические системы имеют широкий спектр возможного применения, например, в ходе спасательных операций [7, 8], в сельскохозяйственной промышленности [9], бытовом использовании [10] или исследовательских работах [11]. Многие их этих задач уже решены методами классической теории управления.

В настоящее время производятся исследования кооперации в статичных [12] и динамичных [13] средах, что позволит решать задачи управления и планирования на верхнем уровне. Сложности могут возникать при решении задачи планирования в общем виде [14] в следствии специфики среды [15, 16], динамики окружения [17], поставленной задачи [18, 19] или геометрии габаритов и сложности шасси робота [20]. Углубленно исследуются узкоспециализированные задачи, например, анализ роботом окружающего локального и глобального пространства [21], автоматическая корректировка маршрута [22], распределение функций роботов в группе [23], ситуационное моделирование [24], сетевое взаимодействие и передача данных [25].

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

Алгоритмы поиска траекторий зависят от математического представления среды в системе управления роботом. В следствии простоты хранения и анализа широкое распространение получили поисковые алгоритмы на графах. В [26] произведен сравнительный анализ классических алгоритмов Дейкстры, А* и

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

Классические алгоритмы на графах и их сочетания могут быть применены для планирования траекторий в объемном пространстве, например, в статье [28] предлагается объединение алгоритма А* и потенциального поля в трехмерном статичном пространстве. Для предварительного планирования используется А*, затем производится оптимизация использования ключевых узлов на пути движения. Последним этапом производится сглаживание траектории алгоритмом потенциального поля.

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

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

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

Исследования муравьиного алгоритма заключается в настройке алгоритма для эффективного поиска траекторий в конкретных условиях. Для этого корректируют количество феромонов, скорость испарения, жадность или стадность алгоритма [31]. Помимо близости найденного пути к оптимальному исследуется скорость его нахождения [32].

Еще один заимствованный из природы метод поиска - генетический алгоритм, основанный на итеративном процессе мутации генов отражающих целевую функцию задачи. Процесс поиска состоит из этапа генерации начальной популяции и цикла: размножение ^ мутация ^ вычисление целевой функции ^ селекция. Цикл заканчивается если выполняется условие останова, например, время, количество поколений, нахождение оптимума. Исследования основных параметров генетических алгоритмов рассматривается в [33], рассматривается влияние коэффициентов скрещивания, коэффициентов мутации и количество поколений на оптимальность найденной траектории. Исследование влияния относительного расположения запрещенных зон, ограничивающих область поиска, на оптимизацию поиска кратчайших путей предложен в [34]. Генетические алгоритмы могут быть использованы для решения задачи покрытия [35], для этого предложена функция оценки для фундаментальных действий выполняемых роботов при достижении цели. Генетический алгоритм с переменной длиной хромосом, представленный в [36] реализует поиск в пространстве размеченном регулярной сеткой и встроен в реального робота.

Сравнение природных подходов и классических алгоритмов на графах рассматриваемое в [37] показывает, что наиболее близким к оптимальному маршруту получается при использовании алгоритма А*. Системы, основанные на нейронных сетях, могут быть использованы при планировании траекторий и

позволяют учитывать, как статические, так и реагировать на динамические препятствия [38].

Планирование маршрутов, основанное на правилах нечеткого вывода предложено в [39]. Перед непосредственным поиском производится обработка кластеров для сокращения групп препятствий и времени вычислений. Построение траектории движения осуществляется в два этапа, на первом осуществляется поиск «грубого» пути, а на втором сглаживание.

Гибридные системы планирования использующая генетические алгоритмы и методы нечеткого вывода синтезируют оптимальные пути на глобальном и локальном уровне. На первом этапе формируется модель окружающей среды, как входных данных для генетического алгоритма. Полученное решение является приближенным, а его уточнение производится на втором этапе локального поиска нечетких методов. Этот подход предлагает возможность применения в задачах с жесткими требованиями к вычислительным ресурсам и энергопотреблению аппаратной части оборудования, реализующего гибридный подход. Так же алгоритмы могут быть применены в условиях с высокой степенью изменчивости и неопределенности пространства движения и выполнения операций роботов. [40] Реализация и расширение аналогичного подхода представлена в [41]. Помимо двухэтапного построения траектории предлагается способ типизация и назначения приоритетов препятствиям, что позволяет алгоритму работать в динамических средах.

Метод Монте-Карло, основанный на случайных процессах, может быть использован для поиска путей [42]. Тестирование поисковых алгоритмов производилось в игре Рас-Мап, что усложняло задачу ограничением времени принятия решения и наличием агрессивной среды действия. Алгоритм исследовался на четырех уровнях сложности, основанных на поведении призраков, и рассматривал модификации: дерева переменной глубины, учет командных стратегий, долгосрочное целевой планирование, повторное использование дерева с заданным распадом.

Модификацией метода Монте-Карло является алгоритм быстрого обхода случайных деревьев RRT (Rapidly-exploring random tree). В [43] исследуется оптимизация поиска путей для скоординированной группы роботов. Разработанный алгоритм минимизирует пройденное расстояние используя функцию стоимости и максимизировать время желаемого взаиморасположения роботов в группе.

Алгоритмы на основе случайных деревьев используются в случае представления роботов как неголономных систем [44] для планирования гладких траекторий. Модификация алгоритма случайных деревьев и алгоритма А* представленная в [45] разрешает проблему оптимизации вычислений сокращая объем обрабатываемой информации. Исследуются метрики критериев: евклидова и Манхэттенское расстояние для классического и модифицированного алгоритма, на картах с препятствиями разной плотности. Алгоритм случайных деревьев с эвристической оценкой А* Манхэттенским расстоянием оказался оптимальным по всем параметрам, тем не менее при поиске на картах с тупиковыми препятствиями возникает проблема локальных минимумов, не решаемая предложенными методами.

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

Основными модификациями алгоритма случайных деревьев являются RRT* и T-RRT. Алгоритм RRT* обеспечивает конвергенцию к оптимальному пути в отношении заданного критерия качества пути, то есть асимптотически устойчив, но может медленно сходится в сложных пространствах. Модификация T-RRT позволяет эффективно исследовать пространство движения благодаря фильтрам, с другой стороны, он не является асимптотически устойчивым. В [47] рассматривается возможность использования комбинации этих двух подходов, для этого разработаны T-RRT* и AT-RRT предполагающие те же границы

оптимальности что и ЯЯТ*. Предложенные алгоритмы Т-ЯЯТ* и АТ-ЯКГ являются асимптотически устойчивыми и оценены в нескольких задачах планирования маршрутов с комплексными непрерывными функциями затрат. В условиях сложной топологии и/или размерности пространства поиска алгоритмы сходятся быстрее чем ЯЯТ* на порядок.

Планирование траекторий в неизвестных средах нетривиальная задача, классические подходы к которой исследованы в [48]. Рассматриваются различные модификации жадного алгоритма в контексте задачи коммивояжера, что не дает существенных выигрышей в ходе поисков и оценивает только пройденное расстояние. Существует более сложный подход, основанный на методах экстраполяции и обучения, позволяющий использовать банк знаний, обновляемый во время предыдущих прогонов робота, что позволило улучшить средний результат на 15% по расстоянию [49].

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

Методы постобработки спланированных траекторий используются для реализации в натурных моделях, например, это сглаживание острых и прямых углов кривыми Безъе [52]. Планирование движения для неголономных объектов помимо плавности траектории движения требует наличия пространства движения, соответствующего габаритным размерам робота. Для реализации поиска пространства может использоваться сферический алгоритм. В работе [53] представлен алгоритм построения гиперсферического пути для построения гомотопических кривых. Предложены и реализованы эффективные стратегии поворота, разворота и движения робота. Также проведены исследования

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

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

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

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

Уровнем выше стоят системы планирования траекторий рассматривающие алгоритмы поиска путей движения. Широко рассматриваемыми можно считать такие алгоритмы как А*, Дейкстры, Флойда—Уоршелла и их модификации

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

Список литературы диссертационного исследования кандидат наук Моторин Дмитрий Евгеньевич, 2021 год

СПИСОК ЛИТЕРАТУРЫ

[1] Z. Wang, D. Huang, N. Li and S. Li, "Quadruped robot gait planning with stair environment constraints," Proceedings of the 33rd Chinese Control Conference, Nanjing, 2014, pp. 8583-8588. doi: 10.1109/ChiCC.2014.6896441

[2] G. S. Dordevic, M. Rasic, D. Kostic and V. Potkonjak, "Representation of robot motion control skill," in IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 30, no. 2, pp. 219-238, May 2000. doi: 10.1109/5326.868444

[3] E. Jung, B. Yi and W. Kim, "Kinematic Analysis and Motion Planning for a Planar Multiarticulated Omnidirectional Mobile Robot," in IEEE/ASME Transactions on Mechatronics, vol. 20, no. 6, pp. 2983-2995, Dec. 2015. doi: 10.1109/TMECH.2015.2416153

[4] P. Svestka and M. Overmars, "Coordinated path planning for multiple robots," Robotics and Autonomous Systems, vol. 23, no. 3, pp. 125-152, 1998

[5] Каляев И. А. Модели и алгоритмы коллективного управления в группах роботов / И. А. Каляев, А. Р. Гайдук, С. Г. Капустян. - М. : Физматлит, 2009.

[6] V. Vonásek, M. Saska, K. Kosnar and L. Preucil, "Global motion planning for modular robots with local motion primitives," 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, 2013, pp. 2465-2470. doi: 10.1109/ICRA.2013.6630912

[7] N. Sato, K. Kon, H. Fukushima and F. Matsuno, "Map-based Navigation Interface for Multiple Rescue Robots," 2008 IEEE International Workshop on Safety, Security and Rescue Robotics, Sendai, 2008, pp. 152-157. doi: 10.1109/SSRR.2008.4745893

[8] А.И. Мотиенко, О.О. Басов, М.М. Бизин, «Система поддержки принятия решений о спасении пораженных в результате аварий на опасных производственных объектах», Научный вестник НГТУ, том 67, № 2, 2017, с. 6582, DOI: 10.17212/1814-1196-2017-2-65-82

[9] T. Blender, T. Buchner, B. Fernandez, B. Pichlmaier and C. Schlegel, "Managing a Mobile Agricultural Robot Swarm for a seeding task," IECON 2016 -42nd Annual Conference of the IEEE Industrial Electronics Society, Florence, 2016, pp. 6879-6886. doi: 10.1109/IECON.2016.7793638

[10] I. Jeong, W. Ko, G. Park, D. Kim, Y. Yoo and J. Kim, "Task Intelligence of Robots: Neural Model-Based Mechanism of Thought and Online Motion Planning," in IEEE Transactions on Emerging Topics in Computational Intelligence, vol. 1, no. 1, pp. 41-50, Feb. 2017. doi: 10.1109/TETCI.2016.2645720

[11] T. Howard, M. Pivtoraiko, R. A. Knepper and A. Kelly, "Model-Predictive Motion Planning: Several Key Developments for Autonomous Mobile Robots," in IEEE Robotics & Automation Magazine, vol. 21, no. 1, pp. 64-73, March 2014. doi: 10.1109/MRA.2013.2294914

[12] R. Alami, S. Fleury, M. Herrb, F. Ingrand and F. Robert, "Multi-robot cooperation in the MARTHA project," in IEEE Robotics & Automation Magazine, vol. 5, no. 1, pp. 36-47, March 1998. doi: 10.1109/100.667325

[13] H. Fujii and K. Yoshida, "Action control method for mobile robot considering uncertainty of information," 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, Alta., 2005, pp. 3915-3920. doi: 10.1109/IR0S.2005.1545098

[14] Galceran, Enric & Carreras, Marc. "A survey on coverage path planning for robotics." Robotics and Autonomous Systems. 2013. 61. 1258-1276. 10.1016/j.robot.2013.09.004.

[15] D. Sidoti et al., "A Multiobjective Path-Planning Algorithm With Time Windows for Asset Routing in a Dynamic Weather-Impacted Environment," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 12, pp. 32563271, Dec. 2017. doi: 10.1109/TSMC.2016.2573271

[16] Tao Lin, Ke Zhang, Naigang Cui, Zhenbiao Tu and Hu Zhang, "Path planning of aircraft based on adaptive multiobjective estimation of distribution algorithm," 2016 IEEE Symposium Series on Computational Intelligence (SSCI), Athens, 2016, pp. 1-8. doi: 10.1109/SSCI.2016.7850199

[17] J. P. Fentanes, B. Lacerda, T. Krajnik, N. Hawes and M. Hanheide, "Now or later? Predicting and maximising success of navigation actions from long-term experience," 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, 2015, pp. 1112-1117. doi: 10.1109/ICRA.2015.7139315

[18] M. Mishra et al., "Context-Aware Decision Support for Anti-Submarine Warfare Mission Planning Within a Dynamic Environment," in IEEE Transactions on Systems, Man, and Cybernetics: Systems. doi: 10.1109/TSMC.2017.2731957

[19] M. M. Kurdi, A. K. Dadykin and I. Elzein, "Navigation of mobile robot with cooperation of quadcopter," 2017 Ninth International Conference on Advanced Computational Intelligence (ICACI), Doha, 2017, pp. 30-36. doi: 10.1109/ICACI.2017.7974481

[20] T. A. V. Teatro, J. M. Eklund and R. Milman, "Nonlinear Model Predictive Control for Omnidirectional Robot Motion Planning and Tracking With Avoidance of Moving Obstacles," in Canadian Journal of Electrical and Computer Engineering, vol. 37, no. 3, pp. 151-156, Summer 2014. doi: 10.1109/CJECE.2014.2328973

[21] P. Stepan, M. Kulich and L. Preucil, "Robust data fusion with occupancy grid," in IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 35, no. 1, pp. 106-115, Feb. 2005. doi: 10.1109/TSMCC.2004.840048

[22] J. Israelsen, M. Beall, D. Bareiss, D. Stuart, E. Keeney and J. van den Berg, "Automatic collision avoidance for manually tele-operated unmanned aerial vehicles," 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014, pp. 6638-6643. doi: 10.1109/ICRA.2014.6907839

[23] B. Madhevan and M. Sreekumar, "A systematic implementation of role assignment in multi robots using leader follower approach: Analytical and experimental evaluation," 2014 13th International Conference on Control Automation Robotics & Vision (ICARCV), Singapore, 2014, pp. 1792-1798. doi: 10.1109/ICARCV.2014.7064588

[24] D. Dietrich, W. Kastner, T. Maly, C. Roesener, G. Russ and H. Schweinzer, "Situation modeling," IEEE International Workshop on Factory Communication

Systems, 2004. Proceedings., Vienna, 2004, pp. 93-102. doi: 10.1109/WFCS.2004.1377687

[25] K. Kim, M. Park, S. Lee and S. Ji, "Development of a dependable network using collective robots with restricted communication range," 2012 9th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), Daejeon, 2012, pp. 408-412. doi: 10.1109/URAI.2012.6463027

[26] N. O. Eraghi, F. Lopez-Colino, A. de Castro and J. Garrido, "Path length comparison in grid maps of planning algorithms: HCTNav, A* and Dijkstra," Design of Circuits and Integrated Systems, Madrid, 2014, pp. 1-6. doi: 10.1109/DCIS.2014.7035557

[27] M. Lin, K. Yuan, C. Shi and Y. Wang, "Path planning of mobile robot based on improved A* algorithm," 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, 2017, pp. 3570-3576. doi: 10.1109/CCDC.2017.7979125

[28] J. Tan, L. Zhao, Y. Wang, Y. Zhang and L. Li, "The 3D Path Planning Based on A* Algorithm and Artificial Potential Field for the Rotary-Wing Flying Robot,"

2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2016, pp. 551-556. doi: 10.1109/IHMSC.2016.155

[29] Э.И. Ватутин, В.С. Титов, «Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений», Известия ЮФУ. Технические науки, 12, 2014, с. 111-120.

[30] W. Zhang, X. Gong, G. Han and Y. Zhao, "An Improved Ant Colony Algorithm for Path Planning in One Scenic Area With Many Spots," in IEEE Access, vol. 5, pp. 13260-13269, 2017. doi: 10.1109/ACCESS.2017.2723892

[31] J. Cheng, Z. Miao, B. Li and W. Xu, "An improved ACO algorithm for mobile robot path planning," 2016 IEEE International Conference on Information and Automation (ICIA), Ningbo, 2016, pp. 963-968. doi: 10.1109/ICInfA.2016.7831958

[32] K. Ming, "Solving path planning problem based on ant colony algorithm,"

2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, 2017, pp. 5391-5395. doi: 10.1109/CCDC.2017.7979455

[33] Федоренко К. В. Исследование основных параметров генетического алгоритма применительно к задаче поиска оптимального маршрута / К. В. Федоренко, А. Л. Оловянников // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2017. — Т. 9. — № 4. — С. 714-723. DOI: 10.21821/2309-5180-2017-9-4-714-723.

[34] J. Li, Y. Huang, Z. Xu, J. Wang and M. Chen, "Path planning of UAV based on hierarchical genetic algorithm with optimized search region," 2017 13th IEEE International Conference on Control & Automation (ICCA), Ohrid, 2017, pp. 10331038. doi: 10.1109/ICCA.2017.8003203

[35] T. R. Schafle, S. Mohamed, N. Uchiyama and O. Sawodny, "Coverage path planning for mobile robots using genetic algorithm with energy optimization," 2016 International Electronics Symposium (IES), Denpasar, 2016, pp. 99-104. doi: 10.1109/ELECSYM.2016.7860983

[36] J. Ni, K. Wang, H. Huang, L. Wu and C. Luo, "Robot path planning based on an improved genetic algorithm with variable length chromosome," 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), Changsha, 2016, pp. 145-149. doi: 10.1109/FSKD.2016.7603165

[37] Р.А. Нейдорф, В.В. Полях, И.В. Черногоров, О.Т. Ярахмедов, «Исследование эвристических алгоритмов в задачах прокладки и оптимизация маршрутов в среде с препятствиями», ИЗВЕСТИЯ ЮФУ. ТЕХНИЧЕСКИЕ НАУКИ, 2 (176), 2016, с. 127-143.

[38] Y. Chen and W. Chiu, "Optimal robot path planning system by using a neural network-based approach," 2015 International Automatic Control Conference (CACS), Yilan, 2015, pp. 85-90. doi: 10.1109/CACS.2015.7378370

[39] Kuo-Ho Su and Tan-Phat Phan, "Robot path planning and smoothing based on fuzzy inference," 2014 IEEE International Conference on System Science and Engineering (ICSSE), Shanghai, 2014, pp. 64-68. doi: 10.1109/ICSSE.2014.6887906

[40] Даринцев О.В., Мигранов А.Б., «Синтез гибридных интеллектуальных алгоритмов планирования траектории», Фундаментальные исследования. - 2015. - № 12 (часть 4) - С. 676-681

[41] M. A. A. Hemmat, Z. Liu and Y. Zhang, "Real-time path planning and following for nonholonomic unmanned ground vehicles," 2017 International Conference on Advanced Mechatronic Systems (ICAMechS), Xiamen, 2017, pp. 202207. doi: 10.1109/ICAMechS.2017.8316535

[42] T. Pepels, M. H. M. Winands and M. Lanctot, "Real-Time Monte Carlo Tree Search in Ms Pac-Man," in IEEE Transactions on Computational Intelligence and AI in Games, vol. 6, no. 3, pp. 245-257, Sept. 2014. doi: 10.1109/TCIAIG.2013.2291577

[43] J. Rosell and R. Suarez, "cRRT*: Planning loosely-coupled motions for multiple mobile robots," Proceedings of the 2014 IEEE Emerging Technology and Factory Automation (ETFA), Barcelona, 2014, pp. 1-7. doi: 10.1109/ETFA.2014.7005133

[44] J. J. Park and B. Kuipers, "Feedback motion planning via non-holonomic RRT* for mobile robots," 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, 2015, pp. 4035-4040. doi: 10.1109/IR0S.2015.7353946

[45] J. Li, S. Liu, B. Zhang and X. Zhao, "RRT-A* Motion planning algorithm for non-holonomic mobile robot," 2014 Proceedings of the SICE Annual Conference (SICE), Sapporo, 2014, pp. 1833-1838. doi: 10.1109/SICE.2014.6935304

[46] J. Bruce and M. Veloso, "Real-time randomized path planning for robot navigation," IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland, 2002, pp. 2383-2388 vol.3. doi: 10.1109/IRDS.2002.1041624

[47] D. Devaurs, T. Siméon and J. Cortés, "Optimal Path Planning in Complex Cost Spaces With Sampling-Based Algorithms," in IEEE Transactions on Automation Science and Engineering, vol. 13, no. 2, pp. 415-424, April 2016. doi: 10.1109/TASE.2015.2487881

[48] M. Kulich, L. Preucil and J. J. M. Bront, "Single robot search for a stationary object in an unknown environment," 2014 IEEE International Conference on Robotics

and Automation (ICRA), Hong Kong, 2014, pp. 5830-5835. doi: 10.1109/ICRA.2014.6907716

[49] V. Nagarajan and P. Raja, "Path planning for space robots: Based on knowledge extrapolation and risk factors," 2010 IEEE International Conference on Automation and Logistics, Hong Kong and Macau, 2010, pp. 373-378. doi: 10.1109/ICAL.2010.5585312

[50] A. Kumar and A. Ojha, "An evader-centric strategy against fast pursuer in an unknown environment with static obstacles," 2013 International Conference on Control, Automation, Robotics and Embedded Systems (CARE), Jabalpur, 2013, pp. 1-6. doi: 10.1109/CARE.2013.6733717

[51] T. Bretl and S. Hutchinson, "Robust coverage by a mobile robot of a planar workspace," 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, 2013, pp. 4582-4587. doi: 10.1109/ICRA.2013.6631228

[52] A. Khan, I. Noreen and Z. Habib, "Coverage Path Planning of Mobile Robots Using Rational Quadratic Bézier Spline," 2016 International Conference on Frontiers of Information Technology (FIT), Islamabad, 2016, pp. 319-323. doi: 10.1109/FIT.2016.065

[53] G. Diaz-Arango, H. Vázquez-Leal, L. Hernandez-Martinez, M. T. S. Pascual and M. Sandoval-Hernandez, "Homotopy Path Planning for Terrestrial Robots Using Spherical Algorithm," in IEEE Transactions on Automation Science and Engineering, vol. 15, no. 2, pp. 567-585, April 2018. doi: 10.1109/TASE.2016.2638208

[54] S. Matsunaga, Y. Kobayashi, K. Matsumaura and C. H. Kim, "Motion planning of mobile robot considering velocity-dependent cost and time," 2016 IEEE International Conference on Robotics and Biomimetics (ROBIO), Qingdao, 2016, pp. 619-624. doi: 10.1109/R0BI0.2016.7866391

[55] M. G. Ocando, N. Certad, S. Alvarado and Á. Terrones, "Autonomous 2D SLAM and 3D mapping of an environment using a single 2D LIDAR and ROS," 2017 Latin American Robotics Symposium (LARS) and 2017 Brazilian Symposium on Robotics (SBR), Curitiba, 2017, pp. 1-6. doi: 10.1109/SBR-LARS-R.2017.8215333

[56] L. Zhao, Z. Fan, W. Li, H. Xie and Y. Xiao, "3D Indoor Map Building with Monte Carlo Localization in 2D Map," 2016 International Conference on Industrial Informatics - Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII), Wuhan, 2016, pp. 236-240. doi: 10.1109/ICIICII.2016.0064

[57] L. D'Alfonso, A. Griffo, P. Muraca and P. Pugliese, "A SLAM algorithm for indoor mobile robot localization using an Extended Kalman filter and a segment based environment mapping," 2013 16th International Conference on Advanced Robotics (ICAR), Montevideo, 2013, pp. 1-6. doi: 10.1109/ICAR.2013.6766461

[58] B. Ristic, D. Angley, D. Selvaratnam, B. Moran and J. L. Palmer, "A random finite set approach to occupancy-grid SLAM," 2016 19th International Conference on Information Fusion (FUSION), Heidelberg, 2016, pp. 935-941.

[59] H. Wang, C. Zhang, Y. Song and B. Pang, "Mobile robot SLAM methods improved for adapting to search and rescue environments," 2017 Chinese Automation Congress (CAC), Jinan, 2017, pp. 988-993. doi: 10.1109/CAC.2017.8242910

[60] F. Cao, Y. Zhuang, H. Zhang and W. Wang, "Robust Place Recognition and Loop Closing in Laser-Based SLAM for UGVs in Urban Environments," in IEEE Sensors Journal, vol. 18, no. 10, pp. 4242-4252, 15 May15, 2018. doi: 10.1109/JSEN.2018.2815956

[61] H. Kim, J. Kim and C. Kim, "Hybrid representation and rendering of indoor environments using meshes and point clouds," 2014 11th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), Kuala Lumpur, 2014, pp. 289291. doi: 10.1109/URAI.2014.7057436

[62] D. Kanoulas and M. Vona, "Sparse surface modeling with curved patches," 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, 2013, pp. 4209-4215. doi: 10.1109/ICRA.2013.6631172

[63] C. Farabet, C. Couprie, L. Najman and Y. LeCun, "Learning Hierarchical Features for Scene Labeling," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 8, pp. 1915-1929, Aug. 2013. doi: 10.1109/TPAMI.2012.231

[64] S. Sato, M. Hashimoto, M. Takita, K. Takagi and T. Ogawa, "Multilayer lidar-based pedestrian tracking in urban environments," 2010 IEEE Intelligent Vehicles Symposium, San Diego, CA, 2010, pp. 849-854. doi: 10.1109/IVS.2010.5548135

[65] Z. Pan and M. Wang, "Motion object detection method based on real-time background update under complex environment," 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, 2017, pp. 2163-2166. doi: 10.1109/IAEAC.2017.8054400

[66] G. Q. Huang, A. B. Rad and Y. K. Wong, "Online SLAM in dynamic environments," ICAR '05. Proceedings., 12th International Conference on Advanced Robotics, 2005., Seattle, WA, 2005, pp. 262-267. doi: 10.1109/ICAR.2005.1507422

[67] J. Jung, S. Lee and H. Myung, "Indoor Mobile Robot Localization and Mapping Based on Ambient Magnetic Fields and Aiding Radio Sources," in IEEE Transactions on Instrumentation and Measurement, vol. 64, no. 7, pp. 1922-1934, July 2015. doi: 10.1109/TIM.2014.2366273

[68] G. Tanzmeister, J. Thomas, D. Wollherr and M. Buss, "Grid-based mapping and tracking in dynamic environments using a uniform evidential environment representation," 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014, pp. 6090-6095. doi: 10.1109/ICRA.2014.6907756

[69] R. Drouilly, P. Papadakis, P. Rives and B. Morisset, "Local map extrapolation in dynamic environments," 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), San Diego, CA, 2014, pp. 3109-3114. doi: 10.1109/SMC.2014.6974405

[70] K. K. D. K. U. Weerasinghe et al., "Mapping and path planning for long distance autonomous navigation using multisensory data," 2016 Electrical Engineering Conference (EECon), Colombo, 2016, pp. 1-6. doi: 10.1109/EECon.2016.7830926

[71] T. Lowe, S. Kim and M. Cox, "Complementary Perception for Handheld SLAM," in IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 1104-1111, April 2018. doi: 10.1109/LRA.2018.2795651

[72] J. Delmerico, E. Mueggler, J. Nitsch and D. Scaramuzza, "Active Autonomous Aerial Exploration for Ground Robot Path Planning," in IEEE Robotics

and Automation Letters, vol. 2, no. 2, pp. 664-671, April 2017. doi: 10.1109/LRA.2017.2651163

[73] M. Nitsche, P. de Cristóforis, M. Kulich and K. Kosnar, "Hybrid mapping for autonomous mobile robot exploration," Proceedings of the 6th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems, Prague, 2011, pp. 299-304. doi: 10.1109/IDAACS.2011.6072761

[74] S. A. Fadzli, S. I. Abdulkadir, M. Makhtar and A. A. Jamal, "Robotic Indoor Path Planning Using Dijkstra's Algorithm with Multi-Layer Dictionaries," 2015 2nd International Conference on Information Science and Security (ICISS), Seoul, 2015, pp. 1-4. doi: 10.1109/ICISSEC.2015.7371031

[75] V. Hoang, D. C. Hernández, J. Hariyono and Kang-Hyun Jo, "Global path planning for unmanned ground vehicle based on road map images," 2014 7th International Conference on Human System Interactions (HSI), Costa da Caparica, 2014, pp. 82-87. doi: 10.1109/HSI.2014.6860453

[76] Y. Chen, X. Wang, S. Hong, X. Zhong and C. Zou, "Motion planning implemented in ROS for mobile robot," 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, 2017, pp. 7149-7154. doi: 10.1109/CCDC.2017.7978473

[77] Z. Lv, L. Yang, Y. He, Z. Liu and Z. Han, "3D environment modeling with height dimension reduction and path planning for UAV," 2017 9th International Conference on Modelling, Identification and Control (ICMIC), Kunming, 2017, pp. 734-739. doi: 10.1109/ICMIC.2017.8321551

[78] P. Ertle, H. Voos and D. Soffker, "Utilizing dynamic hazard knowledge for risk sensitive action planning of autonomous robots," 2012 IEEE International Symposium on Robotic and Sensors Environments Proceedings, Magdeburg, 2012, pp. 162-167. doi: 10.1109/R0SE.2012.6402608

[79] Z. Meng, H. Sun, H. Qin, Z. Chen, C. Zhou and M. H. Ang, "Intelligent robotic system for autonomous exploration and active SLAM in unknown environments," 2017 IEEE/SICE International Symposium on System Integration (SII), Taipei, 2017, pp. 651-656. doi: 10.1109/SII.2017.8279295

[80] C. Zhong, S. Liu, Q. Lu, B. Zhang and S. X. Yang, "An Efficient Fine-to-Coarse Wayfinding Strategy for Robot Navigation in Regionalized Environments," in IEEE Transactions on Cybernetics, vol. 46, no. 12, pp. 3157-3170, Dec. 2016. doi: 10.1109/TCYB.2015.2498760

[81] S. Edelkamp, M. Pomarlan and E. Plaku, "Multiregion Inspection by Combining Clustered Traveling Salesman Tours With Sampling-Based Motion Planning," in IEEE Robotics and Automation Letters, vol. 2, no. 2, pp. 428-435, April 2017. doi: 10.1109/LRA.2016.2635107

[82] Y. Awashima, H. Fujii, Y. Tamura, K. Nagatani, A. Yamashita and H. Asama, "Safeness visualization of terrain for teleoperation of mobile robot using 3D environment map and dynamic simulator," 2017 IEEE/SICE International Symposium on System Integration (SII), Taipei, 2017, pp. 194-200. doi: 10.1109/SII.2017.8279211

[83] A. Kaplan, N. Kingry, P. Uhing and R. Dai, "Time-Optimal Path Planning With Power Schedules for a Solar-Powered Ground Robot," in IEEE Transactions on Automation Science and Engineering, vol. 14, no. 2, pp. 1235-1244, April 2017. doi: 10.1109/TASE.2016.2533418

[84] V. H. Bennetts, T. P. Kucner, E. Schaffernicht, P. P. Neumann, H. Fan and A. J. Lilienthal, "Probabilistic Air Flow Modelling Using Turbulent and Laminar Characteristics for Ground and Aerial Robots," in IEEE Robotics and Automation Letters, vol. 2, no. 2, pp. 1117-1123, April 2017. doi: 10.1109/LRA.2017.2661803

[85] Mandelbrot, Benoit B. The fractal geometry of nature. Update and augmented. New York: W.H. Freeman, 1983. 468 p. ISBN 0-7167-1186-9.

[86] R. Harba, G. Jacquet, C. Wilches, M. Zequera and L. Vilcahuaman, "Whittle maximum likelihood estimator for isotropic fractional Brownian images," 2014 IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), Noida, 2014, pp. 000422-000427. doi: 10.1109/ISSPIT.2014.7300626

[87] J. Chen, F. Yang, K. Luo, Y. Wu, C. Niu and M. Rong, "Study on contact spots of fractal rough surfaces based on three-dimensional Weierstrass-Mandelbrot function," 2016 IEEE 62nd Holm Conference on Electrical Contacts (Holm), Clearwater Beach, FL, 2016, pp. 198-204. doi: 10.1109/H0LM.2016.7780032

[88] Z. Islam and G. Metternicht, "Fractal dimension of multiscale and multisource remote sensing data for characterising spatial complexity of urban landscapes," IGARSS 2003. 2003 IEEE International Geoscience and Remote Sensing Symposium. Proceedings (IEEE Cat. No.03CH37477), Toulouse, 2003, pp. 1715-1717. doi: 10.1109/IGARSS.2003.1294227

[89] D. Riccio and G. Ruello, "Synthesis of Fractal Surfaces for Remote-Sensing Applications," in IEEE Transactions on Geoscience and Remote Sensing, vol. 53, no. 7, pp. 3803-3814, July 2015. doi: 10.1109/TGRS.2014.2384595

[90] H. Wang, W. Chen, X. Liu and B. Dong, "An improving algorithm for generating real sense terrain and parameter analysis based on fractal," 2010 International Conference on Machine Learning and Cybernetics, Qingdao, 2010, pp. 686-691. doi: 10.1109/ICMLC.2010.5580560

[91] P. Walsh and P. Gade, "The use of an aesthetic measure for the evolution of fractal landscapes," 2011 IEEE Congress of Evolutionary Computation (CEC), New Orleans, LA, 2011, pp. 1613-1619. doi: 10.1109/CEC.2011.5949808

[92] Y. Fu, Z. Zheng, D. Fu and Y. Tong, "Comparison of two fractal surface modeling methods," 2016 12th World Congress on Intelligent Control and Automation (WCICA), Guilin, 2016, pp. 417-421. doi: 10.1109/WCICA.2016.7578280

[93] D. Li, D. Hu, X. Tan and Y. Ding, "Dynamic Simulation of Large-Scale Forest Scene for Wind Field," 2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2016, pp. 429-432. doi: 10.1109/IHMSC.2016.48

[94] T. Sun, F. Xu, J. Lu, M. Yin and X. Liu, "A novel and practical algorithm for generating 3D volumetric clouds," 2015 International Conference on Wireless Communications & Signal Processing (WCSP), Nanjing, 2015, pp. 1-5. doi: 10.1109/WCSP.2015.7341322

[95] C. Beckham, C. Pal, A step towards procedural terrain generation with GANs, 2017. arXiv:1707.03383

[96] L. Cucu, M. Rubenstein and R. Nagpal, "Towards self-assembled structures with mobile climbing robots," 2015 IEEE International Conference on Robotics and

Automation (ICRA), Seattle, WA, 2015, pp. 1955-1961. doi: 10.1109/ICRA.2015.7139454

[97] S. Zein-Sabatto and R. Ramakrishnan, "Multiple path planning for a group of mobile robots in a 3D environment using genetic algorithms," Proceedings IEEE SoutheastCon 2002 (Cat. No.02CH37283), Columbia, SC, USA, 2002, pp. 359-363. doi: 10.1109/SEC0N.2002.995620

[98] T. Regev and V. Indelman, "Multi-robot decentralized belief space planning in unknown environments via efficient re-evaluation of impacted paths," 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, 2016, pp. 5591-5598. doi: 10.1109/IR0S.2016.7759822

[99] G. Best, J. Faigl and R. Fitch, "Multi-robot path planning for budgeted active perception with self-organising maps," 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, 2016, pp. 3164-3171. doi: 10.1109/IR0S.2016.7759489

[100] A. Zhu and S. X. Yang, "A Neural Network Approach to Dynamic Task Assignment of Multirobots," in IEEE Transactions on Neural Networks, vol. 17, no. 5, pp. 1278-1287, Sept. 2006. doi: 10.1109/TNN.2006.875994

[101] А. И. Дивеев, Е. Ю. Шмалько, «Эволюционные методы вычислений для синтеза управления группой роботов и поиска оптимальных траекторий их движения», Cloud of Science. 2017. T. 4. № 3, с. 395-414

[102] D. Sakai, H. Fukushima and F. Matsuno, "Leader-Follower Navigation in Obstacle Environments While Preserving Connectivity Without Data Transmission," in IEEE Transactions on Control Systems Technology, vol. 26, no. 4, pp. 1233-1248, July 2018. doi: 10.1109/TCST.2017.2705121

[103] S. Seghour and M. Tadjine, "Consensus-based approach and reactive fuzzy navigation for multiple no-holonomic mobile robots," 2017 6th International Conference on Systems and Control (ICSC), Batna, 2017, pp. 492-497. doi: 10.1109/ICoSC.2017.7958658

[104] S. Liu, D. Sun and C. Zhu, "Coordinated Motion Planning for Multiple Mobile Robots Along Designed Paths With Formation Requirement," in IEEE/ASME

Transactions on Mechatronics, vol. 16, no. 6, pp. 1021-1031, Dec. 2011. doi: 10.1109/TMECH.2010.2070843

[105] A. D. Dang, H. M. La and J. Horn, "Distributed formation control for autonomous robots following desired shapes in noisy environment," 2016 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), Baden-Baden, 2016, pp. 285-290. doi: 10.1109/MFI.2016.7849502

[106] D. Zhou and M. Schwager, "Virtual Rigid Bodies for coordinated agile maneuvering of teams of micro aerial vehicles," 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, 2015, pp. 1737-1742. doi: 10.1109/ICRA.2015.7139422

[107] V. Spurny, T. Baca and M. Saska, "Complex manoeuvres of heterogeneous MAV-UGV formations using a model predictive control," 2016 21st International Conference on Methods and Models in Automation and Robotics (MMAR), Miedzyzdroje, 2016, pp. 998-1003. doi: 10.1109/MMAR.2016.7575274

[108] M. Cognetti, G. Oriolo, P. Peliti, L. Rosa and P. Stegagno, "Cooperative control of a heterogeneous multi-robot system based on relative localization," 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, 2014, pp. 350-356. doi: 10.1109/IR0S.2014.6942583

[109] И.А. Каляев, С.Г. Капустян, Л.Ж. Усачев, «Метод решения задачи распределения целей в группе БЛА сетецентрической системой управления», Известия ЮФУ. Технические науки, 12 (185), 2016, с. 55-70, DOI 10.18522/23113103-2016-12-5570

[110] Ватаманюк И. В., Панина Г. Ю., Ронжин А. Л., «Реконфигурация пространственного положения роя роботов», Управление большими системами: Сборник трудов, №58, 2015 г., с. 285-305, ISSN: 1819-2440

[111] J. Chen, M. Gauci, W. Li, A. Kolling and R. Groß, "Occlusion-Based Cooperative Transport with a Swarm of Miniature Mobile Robots," in IEEE Transactions on Robotics, vol. 31, no. 2, pp. 307-321, April 2015. doi: 10.1109/TR0.2015.2400731

[112] M. Pashna, R. Yusof and S. Yazdani, "Analysis of prediction methods for swarm robotic — In the case of oil spill tracking," 2015 10th Asian Control Conference (ASCC), Kota Kinabalu, 2015, pp. 1-6. doi: 10.1109/ASCC.2015.7244697

[113] Christer Ericson, "Real-Time Collision Detection", Elsevier, 2004, 594 pages, ISBN: 1-55860-732-3

[114] L. Wang, A. D. Ames and M. Egerstedt, "Safety Barrier Certificates for Collisions-Free Multirobot Systems," in IEEE Transactions on Robotics, vol. 33, no. 3, pp. 661-674, June 2017. doi: 10.1109/TR0.2017.2659727

[115] J. Jin, Y. Kim, S. Wee and N. Gans, "Decentralized cooperative mean approach to collision avoidance for nonholonomic mobile robots," 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, 2015, pp. 35-41. doi: 10.1109/ICRA.2015.7138977

[116] L. Wang, A. D. Ames and M. Egerstedt, "Multi-objective compositions for collision-free connectivity maintenance in teams of mobile robots," 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, 2016, pp. 2659-2664. doi: 10.1109/CDC.2016.7798663

[117] W. Luo, N. Chakraborty and K. Sycara, "Distributed dynamic priority assignment and motion planning for multiple mobile robots with kinodynamic constraints," 2016 American Control Conference (ACC), Boston, MA, 2016, pp. 148154. doi: 10.1109/ACC.2016.7524907

[118] U. Borrmann, L. Wang, A. D. Ames, M. Egerstedt, "Control Barrier Certificates for Safe Swarm Behavior", IFAC-PapersOnLine, Volume 48, Issue 27, 2015, Pages 68-73

[119] D. Sun, A. Kleiner and B. Nebel, "Behavior-based multi-robot collision avoidance," 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014, pp. 1668-1673. doi: 10.1109/ICRA.2014.6907075

[120] Y. Zhou, H. Hu, Y. Liu and Z. Ding, "Collision and Deadlock Avoidance in Multirobot Systems: A Distributed Approach," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 7, pp. 1712-1726, July 2017. doi: 10.1109/TSMC.2017.2670643

[121] L. E. Parker, "Path Planning and Motion Coordination in Multiple Mobile Robot Teams", in Encyclopedia of Complexity and System Science, R. Meyers, Editorin-Chief, Springer, 2009.

[122] A. Fujimori, M. Teramoto, P. N. Nikiforuk, M. M. Gupta, "Cooperative collision avoidance between multiple mobile robots", Journal of Field Robotics, Volume17, Issue7, July 2000, Pages 347-363, DOI:10.1002/1097-4563(200007)17:7%3C347::AID-ROB1%3E3.0.CO;2-A

[123] X. Wang, M. Kloetzer, C. Mahulea and M. Silva, "Collision avoidance of mobile robots by using initial time delays," 2015 54th IEEE Conference on Decision and Control (CDC), Osaka, 2015, pp. 324-329. doi: 10.1109/CDC.2015.7402221

[124] F. Cherni, Y. Boutereaa, C. Rekik and N. Derbel, "Autonomous mobile robot navigation algorithm for planning collision-free path designed in dynamic environments," 2015 9th Jordanian International Electrical and Electronics Engineering Conference (JIEEEC), Amman, 2015, pp. 1-6. doi: 10.1109/JIEEEC.2015.7470747

[125] S. Xiao, "Optimal travel path planning and real time forecast system based on ant colony algorithm," 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, 2017, pp. 22232226. doi: 10.1109/IAEAC.2017.8054413

[126] S. Chen, Z. Yang, Z. Liu and H. Jin, "An improved artificial potential field based path planning algorithm for unmanned aerial vehicle in dynamic environments," 2017 International Conference on Security, Pattern Analysis, and Cybernetics (SPAC), Shenzhen, 2017, pp. 591-596. doi: 10.1109/SPAC.2017.8304346

[127] A. T. Sadiq and A. H. Hasan, "Robot path planning based on PSO and D * algorithmsin dynamic environment," 2017 International Conference on Current Research in Computer Science and Information Technology (ICCIT), Slemani, 2017, pp. 145-150. doi: 10.1109/CRCSIT.2017.7965550

[128] M. L. Tazir, O. Azouaoui, M. Hazerchi and M. Brahimi, "Mobile robot path planning for complex dynamic environments," 2015 International Conference on Advanced Robotics (ICAR), Istanbul, 2015, pp. 200-206. doi: 10.1109/ICAR.2015.7251456

[129] S. Primatesta, L. O. Russo and B. Bona, "Dynamic trajectory planning for mobile robot navigation in crowded environments," 2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA), Berlin, 2016, pp. 1-8. doi: 10.1109/ETFA.2016.7733510

[130] Y. Singh, S. Sharma, R. Sutton, D. Hatton and A. Khan, "Feasibility study of a constrained Dijkstra approach for optimal path planning of an unmanned surface vehicle in a dynamic maritime environment," 2018 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), Torres Vedras, 2018, pp. 117-122. doi: 10.1109/ICARSC.2018.8374170

[131] Y. Lin, S. Li, S. Liu and Y. Chen, "An efficient approach to mobile robot motion planning in dynamically unknown environments," 2014 13th International Conference on Control Automation Robotics & Vision (ICARCV), Singapore, 2014, pp. 1764-1770. doi: 10.1109/ICARCV.2014.7064583

[132] Xiao Guo-bao and X. Yan, "A new cooperative multi-robot path planning in dynamic environment," International Conference on Automatic Control and Artificial Intelligence (ACAI 2012), Xiamen, 2012, pp. 159-165. doi: 10.1049/cp.2012.0944

[133] A. D. Dang and J. Horn, "Formation adaptation control of autonomous robots in a dynamic environment," 2015 IEEE International Conference on Industrial Technology (ICIT), Seville, 2015, pp. 3190-3195. doi: 10.1109/ICIT.2015.7125569

[134] L. Deng, X. Ma, J. Gu and Y. Li, "Improved poly-clonal artificial immune network for multi-robot dynamic path planning," 2013 IEEE International Conference on Information and Automation (ICIA), Yinchuan, 2013, pp. 128-133. doi: 10.1109/ICInfA.2013.6720283

[135] S. Biswas, S. G. Anavatti and M. A. Garratt, "Nearest neighbour based task allocation with multi-agent path planning in dynamic environments," 2017 International Conference on Advanced Mechatronics, Intelligent Manufacture, and Industrial Automation (ICAMIMIA), Surabaya, 2017, pp. 181-186. doi: 10.1109/ICAMIMIA.2017.8387582

[136] R. Palm, A. Bouguerra, M. Abdullah and A. J. Lilienthal, "Navigation in human-robot and robot-robot interaction using optimization methods," 2016 IEEE

International Conference on Systems, Man, and Cybernetics (SMC), Budapest, 2016, pp. 004489-004494. doi: 10.1109/SMC.2016.7844939

[137] R. Palm and A. J. Lilienthal, "Long distance prediction and short distance control in human-robot systems," 2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Naples, 2017, pp. 1-6. doi: 10.1109/FUZZ-IEEE.2017.8015396

[138] T. Wada et al., "Building human motion map for mobile robot in the indoor dynamic environment," 2010 IEEE International Conference on Robotics and Biomimetics, Tianjin, 2010, pp. 543-548. doi: 10.1109/ROBIO.2010.5723384

[139] L. Iocchi, L. Marchetti and D. Nardi, "Multi-robot patrolling with coordinated behaviours in realistic environments," 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, 2011, pp. 27962801. doi: 10.1109/IROS.2011.6094844

[140] E. Repiso, G. Ferrer and A. Sanfeliu, "On-line adaptive side-by-side human robot companion in dynamic urban environments," 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, 2017, pp. 872877. doi: 10.1109/IROS.2017.8202248

[141] A. Mohri, M. Yamamoto and S. Fukuda, "Collision free trajectory planning for multiple mobile robots in environment with periodic motion obstacle," Proceedings of the 1996 IEEE IECON. 22nd International Conference on Industrial Electronics, Control, and Instrumentation, Taipei, Taiwan, 1996, pp. 1572-1576 vol.3. doi: 10.1109/IECON.1996.570627

[142] A. Q. Nilles, I. Becerra and S. M. LaValle, "Periodic trajectories of mobile robots," 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, 2017, pp. 3020-3026. doi: 10.1109/IROS.2017.8206140

[143] A. Jahn, R. J. Alitappeh, D. Saldana, L. C. A. Pimenta, A. G. Santos and M. F. M. Campos, "Distributed multi-robot coordination for dynamic perimeter surveillance in uncertain environments," 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 2017, pp. 273-278. doi: 10.1109/ICRA.2017.7989035

[144] Y. Toda and N. Kubota, "Self-Localization Based on Multiresolution Map for Remote Control of Multiple Mobile Robots," in IEEE Transactions on Industrial Informatics, vol. 9, no. 3, pp. 1772-1781, Aug. 2013. doi: 10.1109/TII.2013.2261306

[145] T. Ort, L. Paull, D. Rus, "Autonomous Vehicle Navigation in Rural Environments without Detailed Prior Maps", ICRA 2018 - IEEE International Conference on Robotics and Automation, May 2018.

[146] R. Song, W. Liu, Y. Liu and R. Bucknall, "A two-layered fast marching path planning algorithm for an unmanned surface vehicle operating in a dynamic environment," OCEANS 2015 - Genova, Genoa, 2015, pp. 1-8. doi: 10.1109/OCEANS-Genova.2015.7271405

[147] C. Bensaci, Y. Zennir, D. Pomorski and E. Mechhoud, "Complex safety study of intelligent multi-robot navigation in risk's environment," 2017 International Carnahan Conference on Security Technology (ICCST), Madrid, 2017, pp. 1-6. doi: 10.1109/CCST.2017.8167809

[148] K. Hernandez, B. Bacca and B. Posso, "Multi-goal Path Planning Autonomous System for Picking up and Delivery Tasks in Mobile Robotics," in IEEE Latin America Transactions, vol. 15, no. 2, pp. 232-238, Feb. 2017. doi: 10.1109/TLA.2017.7854617

[149] A. Akbari, Muhayyuddin and J. Rosell, "Task planning using physics-based heuristics on manipulation actions," 2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA), Berlin, 2016, pp. 1-8. doi: 10.1109/ETFA.2016.7733599

[150] M. Guo and D. V. Dimarogonas, "Task and Motion Coordination for Heterogeneous Multiagent Systems With Loosely Coupled Local Tasks," in IEEE Transactions on Automation Science and Engineering, vol. 14, no. 2, pp. 797-808, April 2017. doi: 10.1109/TASE.2016.2628389

[151] M. Gassner, T. Cieslewski and D. Scaramuzza, "Dynamic collaboration without communication: Vision-based cable-suspended load transport with two quadrotors," 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 2017, pp. 5196-5202. doi: 10.1109/ICRA.2017.7989609

[152] A. Valero-Gomez, J. Valero-Gomez, A. Castro-Gonzalez and L. Moreno, "Use of genetic algorithms for target distribution and sequencing in multiple robot operations," 2011 IEEE International Conference on Robotics and Biomimetics, Karon Beach, Phuket, 2011, pp. 2718-2724. doi: 10.1109/ROBIO.2011.6181716

[153] Д. Е. Моторин, С. Г. Попов, М. А. Курочкин, А. С. Тучков, Исследование алгоритма согласования глобальных и локальных траекторий движения робота на разномасштабных картах, XXI Международная конференция по мягким вычислениям и измерениям (SCM'2018), Санкт-Петербург, с. 530-533

[154] Моторин Д.Е., Попов С.Г., Курочкин Л.М. Алгоритм разрешения коллизий при планировании движения группы роботов в условиях пространственно-ситуационной неопределённости // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2017. Т. 10. № 2. С. 32-44. DOI: 10.18721/JCSTCS.10203

[155] Dmitrii Motorin, Serge Popov, Vladimir Muliukha, "Collision-Free Path Planning Algorithm for Group of Robots in Spatio-Situational Uncertainty", PROCEEDING OF THE 21ST CONFERENCE OF FRUCT ASSOCIATION, Helsinki, Finland, pp. 456-461, ISSN 2305-7254

[156] Моторин Д. Е., Попов С. Г. Алгоритм многокритериального поиска траекторий движения робота на многослойной карте// Информационно-управляющие системы. 2018. № 3. С. 45-53. doi:10.15217/issn1684-8853.2018.3.45