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

Анотація наукової статті за медичними технологіями, автор наукової роботи - Моторин Дмитро Євгенович, Попов Сергій Геннадійович


Multi-Criteria Path Planning Algorithm for a Robot on a Multilayer Map

Introduction: A complex environment is characterized by the possibility to decompose the factors affecting the robot into independent layers. As the robot is moving in a complex environment, it is exposed to negative factors which affect its ability to achieve the goal. The problem arises how to choose the motion trajectory while minimizing the negative effects on the robot and the distance covered. Purpose: Developing and analyzing an algorithm for two-criteria optimization of robot motion trajectory, taking into account the desired criteria about the interaction with the environment and the trajectory length. Results: We have developed and implemented an algorithm for shortest path search on a map each layer of which displays a property of the space and allows you to take into account the interaction between the robot and the environment, as well as the distance covered. The algorithm implementation is incorporated into the robot group control model. To analyze the algorithm, test multilayer maps were used, with the addition of Gaussian noise. The simulation results are a set of trajectories reflecting the coefficients with which the space properties affect the robot when the initial and final positions on the map are given. A space of the robot motion states demonstrates how the influence of the environment properties on the robot depends on the trajectory length and on the failure risk throughout the path. Practical relevance: The developed algorithm can be applied in planning systems of individual or group motion of robots. The resulting state space reflects the ranges of effective characteristics of the robot when performing tasks in a given environment. As the next step, the developed algorithm will be applied to plan paths on multiscale maps, and sets of trajectories will be built in the state space of a group of robots.


Область наук:

  • Медичні технології

  • Рік видавництва: 2018


    Журнал: Інформаційно-керуючі системи


    Наукова стаття на тему 'Алгоритм многокритериального пошуку траєкторій руху робота на багатошарової карті'

    Текст наукової роботи на тему «Алгоритм многокритериального пошуку траєкторій руху робота на багатошарової карті»

    ?УДК 519.876.5, 519.873, 004.023: 896 М: 10.1521 7 / 1ЗБП1 684-8853.2018.3.45

    АЛГОРИТМ Багатокритеріальний ПОШУКУ траєкторії руху РОБОТА НА багатошарових КАРТІ

    Д. Є. Моторина, аспірант, Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    С. Г. Попова, канд. техн. наук, доцент, Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    аСанкт-Петербурзький політехнічний університет Петра Великого, Політехнічна вул., 29, Санкт-Петербург, 195251, РФ

    Постановка проблеми: складне середовище характеризується можливістю декомпозиції впливають на робота чинників на незалежні шари. У процесі руху робота в складному середовищі на нього впливають негативні фактори, що впливають на можливість досягнення мети. У зв'язку з цим виникає проблема вибору траєкторії руху при одночасній мінімізації небажаних впливів на робота і довжини пройденого шляху. Мета: розробка і аналіз результатів роботи алгоритму двухкрітеріальной оптимізації траєкторії руху робота з урахуванням бажаних критеріїв взаємодії з середовищем і довжини траєкторії. Результати: розроблено та реалізовано алгоритм пошуку найкоротшого шляху на карті, кожен шар якої відображає властивість простору і дозволяє враховувати взаємодію робота і середовища з урахуванням довжини пройденої траєкторії. Реалізація алгоритму вбудована в модель управління групою роботів. Для аналізу алгоритму розглянуті тестові багатошарові карти з додаванням гауссова шуму. В результаті симуляції побудовано безліч траєкторій руху з урахуванням коефіцієнтів впливу властивостей простору на об'єкт управління при заданих початковому і кінцевому положенні на карті. Побудовано простір станів руху робота, представлене у вигляді залежностей впливу властивостей середовища на робота від довжини траєкторії і ризику відмов протягом усього шляху. Практична значимість: розроблений алгоритм може бути застосований в системах планування індивідуального або групового руху роботів. Отримане простір станів відображає діапазони ефективних характеристик робота при виконанні поставлених завдань в заданій середовищі. Продовженням роботи стане застосування розробленого алгоритму при пошуку шляху на різномасштабних картах і побудова сімейств траєкторій в просторі станів групи роботів.

    Ключові слова - пошук траєкторій, багатошарові карти, управління, робот, простір станів, евристичний алгоритм, реалістична середу.

    Цитування: Моторин Д. Є., Попов С. Г. Алгоритм многокритериального пошуку траєкторій руху робота на багатошарової мапі // Інформаційно-керуючі системи. 2018. № 3. С. 45-53. doi: 10.15217 / issn1684-8853.2018.3.45

    Citation: Motorin D. E., Popov S. G. Multi-Criteria Path Planning Algorithm for a Robot on a Multilayer Map. Informatsionno-upravliaiushchie sistemy [Information and Control Systems], 2018, no. 3, pp. 45-53 (In Russian). doi: 10.15217 / issn1684-8853.2018.3.45

    Вступ

    Управління роботами і їх групами включає в себе ряд складних завдань, починаючи з механічних принципів руху і закінчуючи інтелектуальними алгоритмами прийняття рішень про вибір глобальних цілей для виконання. На даний момент центральною проблемою управління і планування руху є пошук траєкторій. Побудова шляху на плоскій карті з дискретними перешкодами є добре вивченою завданням як в теоретичному, так і в практичному плані. Для її вирішення, як правило, використовуються класичні алгоритми пошуку на графах, такі як, наприклад, алгоритми Дейкстри, А *, хвильової, Флойда - Уоршелла [1, 2]. Вони широко і успішно застосовуються при наявності одного шару карти. При цьому складно поширити їх на багатошарові карти, що враховують кілька властивостей середовища.

    Порівняння стандартних алгоритмів пошуку траєкторій розглядається в роботах [2-4]. Автори оптимізують алгоритми А *, Дейкстри

    і власний алгоритм Істмен для систем з низькими обчислювальними ресурсами. Аналіз показав, що алгоритм А * найбільш ефективний за критерієм мінімізації довжини траєкторії. Зі стандартних пошукових алгоритмів найбільш поширений для дослідження і модифікації також алгоритм А *. Наприклад, його модифікація [5] дозволяє мінімізувати число перспективних вершин в процесі пошуку, а евристика, яка оцінює перспективність переходу на основі змінної довжини кроку пошуку [6], скорочує час отримання результату більш ніж в два рази. Критерій пошукового алгоритму [7] враховує не тільки час отримання результату, але і динаміку середовища, що складається в переміщенні перешкод, що дозволяє уникати колізій в процесі руху. Модифіковані способи застосування пошукових алгоритмів дають можливість вирішувати складні завдання планування гібридних траєкторій в двох наближеннях [8] або дозволяти колізії траєкторій [9] з використанням алгоритмів пошуку проміжних цільових точок.

    Крім класичних алгоритмічних підходів використовуються еволюційні алгоритми [10], зокрема генетичні [11]. В роботі [12] розглядається модифікація алгоритму зі змінною довжиною хромосом з апробацією в натурному експерименті по руху робота. Скорочення обчислювальних витрат [13] забезпечується реалізацією ієрархічного генетичного алгоритму з редукцією області пошуку траєкторій. Генетичні алгоритми використовуються при побудові траєкторії для завдання максимального покриття, в роботі [14] запропоновано критерій мінімізації витрачається роботом енергії.

    Порівняно новим підходом при пошуку траєкторій є мурашиний алгоритм [1517]. Модифікація цього методу [18], що складається в редукції складності завдання комівояжера, зазначенням обов'язкового відвідування бажаних вузлів застосована для вирішення завдання побудови індивідуальних туристичних маршрутів. Оптимізація мурашиного алгоритму для статичних карт різного розміру з типовим і випадковим розподілом перешкод представлена ​​в роботі [19], де досліджено залежність довжини шляху від розміру популяції. алгоритм

    [20] надає рішення задачі пошуку траєкторії руху транспортного засобу в реальному часі в міських умовах при наявному прогнозі дорожньої обстановки.

    Зазначені вище методи і алгоритми розглядають двовимірні плоскі карти з дискретними перешкодами, що не завжди об'єктивно відображає ситуацію в навколишньому середовищі. Для більш точного опису обстановки використовуються об'ємні тривимірні карти. Наприклад, в статті

    [21] розглядається оптимізація траєкторії руху літаків щодо спільної мінімізації критеріїв відстані і часу польоту із завданням початкових параметрів оптимізації. Для пошуку траєкторії літаючих роботів з обертовим крилом [22] застосовується комбінація алгоритму А * і евристичної функції оцінки перспективності наступного вузла, в якій використовується значення потенційного поля, що дозволяє будувати плавні траєкторії.

    У розглянутих раніше алгоритмах і методах застосовуються одношарові карти, що істотно знижує можливості управління, ефективність побудованих шляхів і збільшує невизначеність і ймовірність відмови роботів під час руху. Пошук траєкторій в складних середовищах, як в роботі [23], передбачає обчислення траєкторії руху надводного робота об'єднанням векторного поля і маски заборонених до руху областей. Запропонований підхід [24] дозволяє будувати траєкторії в умовах динамічної карти, що складається з обсяг-

    ного шару поверхні ландшафту і шару з областями ймовірних відмов.

    Якщо розглядати навколишній світ як набір окремих шарів, що містять вимірювані значення властивостей середовища, то задача може бути вирішена методами багатокритеріальної оптимізації. У даній статті авторами запропонований евристичний алгоритм пошуку траєкторій на багатошарових картах.

    Постановка завдання багатокритеріального пошуку на багатошарової мапі

    Розглядається карта Е, розмічена регулярною сіткою, що складається з т шарів. Кожен шар відображає властивість простору, наприклад висоту ландшафту місцевості над рівнем моря, радіаційний фон, температуру. Кожен вузол сітки приймає значення в діапазоні певним обраним властивістю шару від мінімального до максимального значення [шт; ... шах;].

    У початковий момент часу робот Я розташований в початковій точці сітки АЯ і повинен переміститися в цільову точку ZR. Потрібно побудувати траєкторію Ь = {АЯ,? 1, ..., 1 та, ..., ZR} е! : 1 та е Е, що представляє собою набір точок сітки, в які послідовно проходить робот під час руху.

    При цьому робот будує траєкторію руху з урахуванням вектора G = ..., gm}, що відображає емпіричні коефіцієнти схильності робота властивостями середовища.

    Планування траєкторії руху здійснюється на безлічі Е - навколишнього робота середовищі:

    Е = Е, ..., Е, ^ [вху1? у, ...}, I = 1, ..., т,

    де Е; - окремий шар, що характеризує властивість, що впливає на робота, кожен елемент еху; якоговідображає значення властивості з можливих значень й, е [шт ..., шах;] в координатах сітки (х, у). Пошук тректоріі здійснюється за допомогою евристичного правила

    Р (еху1) = нт

    хуг> 8 I

    е'ху) р) ^ ^ (1)

    де еху; - значення властивості в 1-м шарі простору на траєкторії руху робота; gi - коефіцієнт впливу шару на ймовірність відмови об'єкта управління; р - відстань від поточного положення до цільового; до - функція перетворення значень шарів в ймовірність відмови; f - функція, що задає відношення шарів:

    ^ • 1еху1 + ^ еху2 + ^ еху3.

    (2)

    Представлене правило використовується при формуванні критерію

    ZF (L) ^ min, (3)

    де L - траєкторія руху робота.

    В основі алгоритму лежить мінімізація ймовірності відмови робота при переходах з однієї дискретної точки в іншу і мінімізація геометричного відстані, пройденого роботом.

    Алгоритм пошуку траєкторії на багатошарової мапі

    Для вирішення поставленого завдання розроблений алгоритм пошуку траєкторій на багатошарової карті (рис. 1). Представлений алгоритм виконується в два етапи: на першому формується карта ймовірностей, на другому будується траєкторія руху.

    Формування карти починається з поточного положення об'єкта управління A (k) в просторі карти Е, розміченій регулярною сіткою на кожному шарі, яке записується в вектор переглядаються значень leftP. Далі аналізуються сусідні осередки сітки nearP, якщо вони ще не були переглянуті (вектор madeP). У знайдених точках nearP розраховуються ймовірності відмови устаткування, після чого точки додаються в загальну карту ймовірностей mapP. Точки nearP і leftP об'єднуються в один список і сортуються за величиною суми ймовірності відмови. Для наступних ітерацій береться точка з мінімальною сумою?. Ітерації закінчуються в момент досягнення кінцевої точки Z (k), так як сума ймовірностей відмов в ній буде мінімальною, а перехід з іншого положення збільшить ймовірність відмови.

    Формована карта ймовірності mapP на початковому етапі складається з заборонених для про-

    ( Вхід )

    Вхідні дані: карта, функції, бажані параметри, початкові і кінцеві координати

    Поточне положення - єдина координата в списку не переглянутих

    <г-- Досягнуто цільова точка?

    append [mapP; F (nearP)]

    sort (append [nearP; leftP])

    Пошук сусідніх точок

    Видалення переглянутої точки

    Сусідні точки проглядалися?

    Формування карти ймовірностей

    Додавання сусідніх точок в список

    для перегляду і сортування по ймовірності

    Г

    Відновлення шляху по побудованій карті mapP

    Відновлення шляху градієнтним методом, мінімізація ймовірності відмови і відстані до цілі

    вихід

    Мал. 1. Алгоритм формування карти ймовірностей відмови і пошуку траєкторій Fig. 1. The algorithm for generating failure probability maps and path planning

    ходу значень, замінних в процесі виконання першого етапу пошуків на обчислені за допомогою виразу (1) значення, при цьому підсумкова карта Тарра не є багатошаровою.

    На другому кроці використовується стандартний метод градієнтного спуску для пошуку траєкторій по мінімальних значень ймовірності відмов, починаючи з кінцевої точки.

    Реалізація алгоритму

    Алгоритм реалізований в пакеті MatLab і вбудований в модель системи планування руху групи роботів як програмна функція пошуку траєкторій руху робота з поточного положення в цільову точку robot_search_ multilayer_path.

    Вхідними даними є координати початкової і кінцевої точок руху, бажані параметри оптимізації у вигляді вектор-стовпці і простір дії.

    Вихідними даними є траєкторія як послідовність точок переміщення робота.

    Основний цикл функції працює до тих пір, поки не знайдена кінцева точка або поки не закінчаться НЕ переглянуті точки на карті. В ході його реалізації з впорядкованої черзі leftP береться координата з мінімальною сумарною ймовірністю відмови і відстанню до кінцевої точки leftP '. Вона має групу точок-сусідів четирехсвязной області nearP. Кожна точка з nearP перевіряється на вихід за межі фізичних кордонів карти і приналежність до стека переглянутих точок madeP. Якщо точка проходить перевірку, то викликається подфункция розрахунку сумарного ризику по верствам карти robot_risk_ fun.

    Ризик розраховується відповідно до формули (1). Коефіцієнти gi задаються користувачем і є вхідними даними для функції розрахунку ризику. Реалізація функції відстані до мети Р = sqrt ((exy т - exy ц) 2 + (exy т - exy ц) 2)

    використовує оцінку по прямій, де (exy т, exy т) - координати поточного положення; (Exy ц, exy ц) - координати цілі; sqrt - операція взяття квадратного кореня. Функція f реалізована сумою добутку значень властивостей шарів і коефіцієнтів g впливу на робота; h визначає функцію перекладу фізичних характеристик шару в функцію ризику.

    Сума обчисленої функції robotriskfun для координат nearP і значення leftP 'поточної точки додаються в список leftP відповідно до сортуванням по зростанню. Перевірена точка leftP 'додається до списку madeP.

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

    Модель руху робота

    Для тестування алгоритму використовується модель в системі Ма ^ ав, що дозволяє симулювати рух групи роботів в просторі з декількома шарами. Модель містить модулі: відображення простору руху об'єктів управління; генерації випадкових і завантаження призначених для користувача карт; вибору постановок виконуваних завдань; визначення параметрів і реалізації взаємодії середовища і роботів; планування операцій роботів; вирішення колізій траєкторій; реалізації динамічних змін середовища.

    На зображенні інтерфейсу моделі (рис. 2, а) зазначені: шари властивостей простору руху групи роботів, положення роботів, вантажів, цілей і траєкторії руху з початкової точки в кінцеву при транспортуванні вантажу для гомогенних і гетерогенних груп роботів. Додатково можуть бути візуалізовані шари карти, траєкторії, простір станів.

    Побудова траєкторій здійснюється відповідно до алгоритму (див. Рис. 1).

    На рис. 2, а представлено рішення транспортної задачі доставки вантажів в цільові точки групою гетерогенних роботів, транспортерів і навантажувачів; на карті показано перетин трьох шарів простору. На рис. 2, б і в продемонстровані індивідуальні траєкторії роботів на картах ймовірностей відмов, що генеруються в процесі пошуку траєкторії.

    моделювання

    Для перевірки працездатності алгоритму реалізована тришарова карта (рис. 3, а-в). Кожен шар зберігає характеристики середовища, використовувані для розрахунку коефіцієнтів ризику за формулою (1).

    Кожен шар карти являє собою функцію з єдиним максимумом, підсумовану з функцією гауссова шуму і відображає значення властивості простору руху. Шари зміщують траєкторію об'єкта управління з урахуванням коефіцієнтів впливу G.

    б)

    10

    20

    30

    40

    50

    в)

    10

    20

    30

    40

    50

    5 10 15 20 25 30 35 40 45 50

    5 10 15 20 25 30 35 40 45 50

    | Рис. 2. Подання середовища в моделі (а) і приклади відображення шару ймовірності відмови і побудованої на ньому траєкторії (б, в)

    | Fig. 2. Representation of the environment in the model (а) and examples of the failure probability layer and planned trajectory on it (б, в)

    а)

    25 50 75

    б)

    25 50 75

    1001-1-1-1-1 100

    25 50 75 100

    IF 1

    25 50 75 100

    в)

    25 50 75

    100

    25 50 75 100

    | Рис. 3. Значення рівня властивостей шарів. При побудові траєкторій шар зміщує траєкторію вправо (а); відштовхує від центру карти (б); зміщує вліво (в)

    | Fig. 3. Layer property level values. When constructing trajectories, the layer shifts the trajectory to the right (a); pushes away from the center of the map (б); shifts to the left (в)

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

    Коефіцієнти G, крім впливу шарів на відхилення траєкторії, також впливають на пріоритетність критеріїв; наприклад, на рис. 4 принагідно [0; 0; 0] траєкторія перетворюється в пряму. Якщо вказати для моделі дискретний шар, ймовірність відмови на якому буде або нульовою, або нескінченної, то ал-

    горітм буде працювати за аналогією з алгоритмом А *.

    Безліч побудованих траєкторій може бути відображено у вигляді простору станів. Простір станів для робота, траєкторії якого показані на рис. 4 (в центрі), представлені на рис. 5, де прийняті наступні колірні позначення: червоний колір - високі значення параметрів (ймовірності або довжини), зелений - середні, синій - малі. Варто відзначити, що зміни величин відбуваються плавно, а не стрибкоподібно, і кордони областей є умовними.

    На рис. 5, а відображена залежність довжини траєкторії від коефіцієнтів впливу властивості шару на шлях руху робота; великий вплив всіх верств простору очевидно збільшує ймовірність відмови (область, обмежена крас-

    100

    75 50 25 0

    [1/3; 1/3; 1/3]

    [1; 0; 0]

    [0; 1; 0]

    100

    75 50 25 0

    75 100 - [0; 0; 1]

    75 100

    [0; 3/4; 1/4]

    [3/4; 1/4; 0] ............ [1/4; 3/4; 0]

    [3/4; 0; 1/4] ............ [1/4; 0; 3/4]

    Мал. 4. Траєкторії руху робота при різних значеннях G Fig. 4. Robot 'motion trajectories for different values ​​of G

    100

    75 50 25 0

    f E iH P, h ' "1. hU.

    г

    Г "1 'i i

    Г /

    [1/2; 1/2; 0] [0; 1/2; 1/2]

    0 25 50 75 100 [0; 1/4; 3/4]

    [1/2; 0; 1/2] [0; 0; 0]

    а)

    1

    3 0,75

    про

    в

    I 0,5

    про в

    ° 0,25

    0,75

    0,5

    0,25

    властивість 2

    0 0 0,25

    0,5

    0,75

    властивість 1

    властивість 2

    00

    0,25

    1

    0,5 Властивість 1

    Мал. 5. Простір станів: а - ймовірність; б - довжина траєкторії Fig. 5. State space: а - probability; б - trajectory length

    1

    вим кольором), але при зниженні впливу хоча б одного з шарів менш ніж на 50% (при 100% -м вплив інших) створюються умови, що дозволяють будувати траєкторії із середніми і низькими можливостями відмов. На рис. 5, б представлена ​​ймовірність досягнення мети роботом. Можна помітити, що навіть при максимальному впливі властивостей 1 і 3 траєкторії мінімальні, як і ймовірності; більш того, довжина траєкторії залежить в основному від якості 2, що логічно випливає з рис. 3, б.

    висновок

    У статті розроблено та досліджено алгоритм планування траєкторії руху робота на багатошарових картах. Вбудований в модель алгоритм може бути використаний для планування групового руху роботів.

    1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 3rd. - MIT Press, 2009. - 1313 p.

    2. Eraghi N. O., Lopez-Colino F., de Castro A., Garrido J.

    Path Length Comparison in Grid Maps of Planning Algorithms: HCTNav, A * and Dijkstra // Design of Circuits and Integrated Systems, Madrid, 2014. P. 1-6. doi: 10.1109 / DCIS.2014.7035557

    3. Столяров А. А., Санніков Е. В. Вибір ефективного алгоритму планування для формування інформаційної підсистеми руху мобільного робота // Universum: Технічні науки: електрон. науч. журн. 2015. № 8-9 (20). http: // 7universum. com / ru / tech / archive / item / 2586 (дата звернення: 28.04.2018).

    4. Нейдорф Р. А., Полях В. В., Черногоров І. В., Ярахмедов О. Т. Дослідження евристичних алгоритмів в задачах прокладки і оптимізація маршрутів в середовищі з перешкодами // Изв. ПФУ. Технічні науки. 2016. № 3 (176). С. 127-143.

    5. Lin M., Yuan K., Shi C., Wang Y. Path Planning of Mobile Robot based on Improved A * Algorithm // 2017 29th Chinese Control and Decision Conf. (CCDC), Chongqing, 2017. P. 3570-3576. doi: 10.1109 / CCDC. 2017.7979125

    6. Da K., Xiaoyu L., Bi Z. Variable-Step-Length A * Algorithm for Path Planning of Mobile Robot // 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, 2017. P. 7129-7133. doi: 10.1109 / CCDC.2017.7978469

    7. Cherni F., Boutereaa Y., Rekik C., Derbel N. Autonomous Mobile Robot Navigation Algorithm for Planning Collision-Free Path Designed in Dynamic Environments // 2015 9th Jordanian International Electri-

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

    Побудоване простір станів дозволяє планувати рух робота при заданих умовах середовища. Надані рекомендації щодо модифікації параметрів об'єкта управління для оптимізації часу виконання завдання або ймовірності виконання поставлених перед системою завдань.

    У продовження цієї роботи планується модифікація алгоритму для роботи з простором станів і побудови в ньому траєкторій з метою оптимізації параметрів ймовірності відмов і довжин траєкторій в динамічно змінюваних середовищах.

    Робота виконана за фінансової підтримки РФФД, проект № 16-29-04319.

    cal and Electronics Engineering Conf. (JIEEEC), Amman, 2015. P. 1-6. doi: 10.1109 / JIEEEC.2015.7470747

    8. Дарінцев О. В., Мігранов А. Б. Синтез гібридних інтелектуальних алгоритмів планування траєкторії // Фундаментальні дослідження. 2015. № 12. Ч. 4. С. 676-681. http://www.fundamental-research.ru/ru/article/view?id = 39603 (дата звернення: 28.04.2018).

    9. Моторин Д. Є., Попов С. Г., Курочкін Л. М. Алгоритм розв'язання колізій при плануванні руху групи роботів в умовах просторово-ситуаційної невизначеності // Науково-технічні відомості СПбДПУ. Інформатика. Телекомунікації. Управління. 2017. Т. 10. № 2. С. 32-44. doi: 10.18721 / JCSTCS.10203

    10. Дівєєв А. І., Шмалько Е. Ю. Еволюційні методи обчислень для синтезу управління групою роботів і пошуку оптимальних траєкторій їх руху // Cloud of Science. 2017. T. 4. № 3. С. 395 414.

    11. Федоренко К. В., Оловянніков А. Л. Дослідження основних параметрів генетичного алгоритму стосовно до задачі пошуку оптимального маршруту // Вісник Державного університету морського і річкового флоту імені адмірала С. О. Макарова. 2017. Т. 9. № 4. С. 714-723. doi: 10. 21821 / 2309-5180-2017-9-4-714-723

    12. Ni J., Wang K., Huang H., Wu L., Luo C. 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. P. 145-149. doi: 10.1109 / FSKD.2016.7603165

    13. Li J., Huang Y., Xu Z., Wang J., Chen M. Path Planning of UAV based on Hierarchical Genetic Algo-

    rithm with Optimized Search Region // 2017 13th IEEE Intern. Conf. on Control & Automation (ICCA), Ohrid, 2017. P. 1033-1038. doi: 10.1109 / ICCA.2017. 800320323

    14. Schafle T. R., Mohamed S., Uchiyama N., Sawodny O.

    Coverage Path Planning for Mobile Robots using Genetic Algorithm with Energy Optimization // 2016 International Electronics Symposium (IES), Den-pasar, 2016. P. 99-104. doi: 10.1109 / ELECSYM.2016. 7860983

    15. Ming K. Solving Path Planning Problem based on Ant Colony Algorithm // 2017 29th Chinese Control and Decision Conference (CCDC), Chongqing, 2017. P. 5391-5395. doi: 10.1109 / CCDC.2017.7979455

    16. Ватутін Е.І., Титов В. С. Аналіз результатів застосування алгоритму мурашиної колонії в задачі пошуку шляху в графі при наявності обмежень // Изв. ПФУ. Технічні науки. 2014. № 12 (161). С. 111-120.

    17. Мартинов А. В., Курейчик В. М. Гібридний алгоритм вирішення задачі комівояжера // Изв. ПФУ. Технічні науки. 2015. № 4 (165). С. 36-44.

    18. Zhang W., Gong X., Han G., Zhao Y. An Improved Ant Colony Algorithm for Path Planning in One Scenic Area With Many Spots // IEEE Access. 2017. Vol. 5. P. 13260-13269. doi: 10.1109 / ACCESS.2017.2723892

    19. Uriol R., Moran A. Mobile Robot Path Planning in Complex Environments using Ant Colony Optimization Algorithm // 2017 3rd Intern. Conf. on Control, Automation and Robotics (ICCAR), Nagoya, 2017. P. 15-21. doi: 10.1109 / ICCAR.2017.7942653

    20. Xiao S. Optimal Travel Path Planning and Real Time Forecast System based on Ant Colony Algorithm // 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conf. (IAEAC), Chongqing, 2017. P. 2223-2226. doi: 10.1109 / IAE-AC.2017.8054413

    21. Lin T., Zhang K., Cui N., Tu Z., Zhang H. Path Planning of Aircraft based on Adaptive Multiobjective Estimation of Distribution Algorithm // 2016 IEEE Symp. Series on Computational Intelligence (SSCI), Athens, 2016. P. 1-8. doi: 10.1109 / SSCI.2016. 7850199

    22. Tan J., Zhao L., Wang Y., Zhang Y., Li L. The 3D Path Planning based on A * Algorithm and Artificial Potential Field for the Rotary-Wing Flying Robot // 2016 8th Intern. Conf. on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2016. P. 551-556. doi: 10.1109 / IHMSC.2016.155

    23. Song R., Liu W., Liu Y., Bucknall R. A Two-Layered Fast Marching Path Planning Algorithm for an Unmanned Surface Vehicle Operating in a Dynamic Environment // OCEANS 2015 року, Genova, Genoa, 2015. P. 1 -8. doi: 10.1109 / 0CEANS-Genova. 2015.7271405

    24. Chen H., Wang H., Jiang L. Path Planning of UAV based on Cultural Algorithm in Dynamic Environments // 2016 6th Intern. Conf. on Electronics Information and Emergency Communication (ICEIEC), Beijing, 2016. P. 130-134. doi: 10.1109 / ICEIEC.2016. 7589704

    UDC 519.876.5, 519.873, 004.023: 896 doi: 10.15217 / issn1684-8853.2018.3.45

    Multi-Criteria Path Planning Algorithm for a Robot on a Multilayer Map

    Motorin D. E.a, Post-Graduate Student, Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її. Popov S. G.a, PhD, Tech., Associate Professor, Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    aPeter the Great St. Petersburg Polytechnic University, 29, Politekhnicheskaia St., 195251, Saint-Petersburg, Russian Federation

    Introduction: A complex environment is characterized by the possibility to decompose the factors affecting the robot into independent layers. As the robot is moving in a complex environment, it is exposed to negative factors which affect its ability to achieve the goal. The problem arises how to choose the motion trajectory while minimizing the negative effects on the robot and the distance covered. Purpose: Developing and analyzing an algorithm for two-criteria optimization of robot motion trajectory, taking into account the desired criteria about the interaction with the environment and the trajectory length. Results: We have developed and implemented an algorithm for shortest path search on a map each layer of which displays a property of the space and allows you to take into account the interaction between the robot and the environment, as well as the distance covered. The algorithm implementation is incorporated into the robot group control model. To analyze the algorithm, test multilayer maps were used, with the addition of Gaussian noise. The simulation results are a set of trajectories reflecting the coefficients with which the space properties affect the robot when the initial and final positions on the map are given. A space of the robot motion states demonstrates how the influence of the environment properties on the robot depends on the trajectory length and on the failure risk throughout the path. Practical relevance: The developed algorithm can be applied in planning systems of individual or group motion of robots. The resulting state space reflects the ranges of effective characteristics of the robot when performing tasks in a given environment. As the next step, the developed algorithm will be applied to plan paths on multiscale maps, and sets of trajectories will be built in the state space of a group of robots.

    Keywords - Trajectory Planning, Multilayer Maps, Control, Robot, State Space, Heuristic Algorithm, Realistic Environment.

    Citation: Motorin D. E., Popov S. G. Multi-Criteria Path Planning Algorithm for a Robot on a Multilayer Map. Informatsionno-upravliaiushchie sistemy [Information and Control Systems], 2018, no. 3, pp. 45-53 (In Russian). doi: 10.15217 / issn1684-8853.2018.3.45

    References

    1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 3rd. MIT Press, 2009. 1313 p.

    2. Eraghi N. O., Lopez-Colino F., de Castro A., Garrido J. 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

    3. Stolyarov A. A., Sannikov E. V. Choice of Effective Planning Algorithm for Formation of Informative Subsystem of Mobile Robot Motion. Universum: Tekhnicheskie nauki, 2015-го, no. 8-9 (20). Available at: http://7universum.com/ru/tech/ archive / item / 2586 (acces sed 28 April 2018) (In Russian).

    4. Neydorf R. A., Polyakh V. V., Chernogorov I. V., Yarakhme-dov O. T. The Study of Heuristic Algorithms in the Tasks Strip, and Optimization of Routes in an Environment with Obstacles. Izvestiia YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, no. 3 (176), pp. 127143 (In Russian).

    5. Lin M., Yuan K., Shi C., Wang Y. Path Planning of Mobile Robot based on Improved A * Algorithm. 2017 29th Chinese Control and Decision Conf. (CCDC), Chongqing 2017, pp. 3570-3576. doi: 10.1109 / CCDC.2017.7979125

    6. Da K., Xiaoyu L., Bi Z. Variable-Step-Length A * Algorithm for Path Planning of Mobile Robot. 2017 29th Chinese Control and Decision Conf. (CCDC), Chongqing 2017, pp. 7129-7133. doi: 10.1109 / CCDC.2017.7978469

    7. Cherni F., Boutereaa Y., Rekik C., Derbel N. Autonomous Mobile Robot Navigation Algorithm for Planning Collision-Free Path Designed in Dynamic Environments. 2015 9th Jordanian Intern. Electrical and Electronics Engineering Conf. (JIEEEC), Amman, 2015-го, pp. 1-6. doi: 10. 1109 / JIEEEC.2015.7470747

    8. Darintsev O. V., Migranov A. B. Synthesis of the Hybrid Intelligent Algorithm of Planning Path. Fundamental'nye issledovaniya [Fundamental Research], 2015-го, no. 12, part

    4, pp. 676-681. Available at: http://www.fundamental-re-search.ru/ru/article/view?id = 39603 (accessed 28 April 2018) (In Russian).

    9. Motorin D. Ye., Popov S. G., Kurochkin L. M. An Algorithm for Collision Avoidance in Path Planning for a Group of Robots in a Spatio-Situational Indeterminacy. Nauchno-tekh-nicheskie vedomosti SPbGPU. Informatika. Telekommunika-cii. Upravlenie [St. Petersburg Polytechnic University Journal of Engineering Science and Technology] 2017, vol. 10, no. 2, pp. 32-44 (In Russian). doi: 10.18721 / JCSTCS.10203

    10. Diveev A. I., Shmal'ko E. Yu. Evolutionary Computing Methods for Control Synthesis a Group of Robots and the Search for Optimal Trajectories of their Movement. Cloud of Science 2017, vol. 4, no. 3, pp. 395-414 (In Russian).

    11. Fedorenko K. V., Olovyannikov A. L. Research of the Main Parameters of the Genetic Algorithm for the Problem of Searching the Optimal Route. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala

    5. O. Makarova 2017, vol. 9, no. 4, pp. 714-723 (In Russian). dio: 10.21821 / 2309-5180-2017-9-4-714-723.

    12. Ni J., Wang K., Huang H., Wu L., Luo C. Robot Path Planning based on an Improved Genetic Algorithm with Variable Length Chromosome. 2016 12th Intern. Conf. on Natural Computation, Fuzzy Systems and Knowledge Discovery

    (ICNC-FSKD), Changsha, 2016, pp. 145-149. doi: 10.1109 / FSKD.2016.7603165

    13. Li J., Huang Y., Xu Z., Wang J., Chen M. Path Planning of UAV based on Hierarchical Genetic Algorithm with Optimized Search Region. 2017 13th IEEE Intern. Conf. on Control & Automation (ICCA), Ohrid 2017, pp. 1033-1038. doi: 10.1109 / ICCA.2017.800320323

    14. Schafle T. R., Mohamed S., Uchiyama N., Sawodny O. 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

    15. Ming K. Solving Path Planning Problem based on Ant Colony Algorithm. 2017 29th Chinese Control And Decision Conf. (CCDC), Chongqing 2017, pp. 5391-5395. doi: 10. 1109 / CCDC.2017.7979455

    16. Vatutin Je. I., Titov V. S. Analysis of the Results of Applying the Ant Colony Optimization Algorithm to the Shortest Path Problem in the Graphs with Constraints. Izvestiia YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014 року, no. 12 (161), pp. 111-120 (In Russian).

    17. Martinov A. V., Kureichik V. M. Hybrid Approach for Travelling Salesman Problem. Izvestiia YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015-го, no. 4 (165), pp. 36-44 (In Russian).

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

    19. Uriol R., Moran A. Mobile Robot Path Planning in Complex Environments using Ant Colony Optimization Algorithm. 2017 3rd Intern. Conf. on Control, Automation and Robotics (ICCAR), Nagoya 2017, pp. 15-21. doi: 10.1109 / IC-CAR.2017.7942653

    20. Xiao S. Optimal Travel Path Planning and Real Time Forecast System based on Ant Colony Algorithm. 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conf. (IAEAC), Chongqing 2017, pp. 2223-2226. doi: 10.1109 / IAEAC.2017.8054413

    21. Lin T., Zhang K., Cui N., Tu Z., Zhang H. Path Planning of Aircraft based on Adaptive Multiobjective Estimation of Distribution Algorithm. 2016 IEEE Symp. Series on Computational Intelligence (SSCI), Athens, 2016, pp. 1-8. doi: 10.1109 / SSCI.2016.7850199

    22. Tan J., Zhao L., Wang Y., Zhang Y., Li L. The 3D Path Planning based on A * Algorithm and Artificial Potential Field for the Rotary-Wing Flying Robot. 2016 8th Intern. Conf. on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2016, pp. 551-556. doi: 10.1109 / IHM-SC.2016.155

    23. Song R., Liu W., Liu Y., Bucknall R. 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

    24. Chen H., Wang H., Jiang L. Path Planning of UAV based on Cultural Algorithm in Dynamic Environments. 2016 6th Intern. Conf. on Electronics Information and Emergency Communication (ICEIEC), Beijing, 2016, pp. 130-134. doi: 10.1109 / ICEIEC.2016.7589704


    Ключові слова: ПОШУК траєкторії /БАГАТОШАРОВІ КАРТИ /MULTILAYER MAPS /УПРАВЛІННЯ /CONTROL /РОБОТ /ROBOT /ПРОСТІР СТАНІВ /STATE SPACE /ЕВРИСТИЧНИЙ АЛГОРИТМ /HEURISTIC ALGORITHM /реалістичність середу /REALISTIC ENVIRONMENT /TRAJECTORY PLANNING

    Завантажити оригінал статті:

    Завантажити