title: Алгоритм разрешения коллизий при планировании движения группы роботов в условиях пространственно-ситуационной неопределённости
title: An Algorithm for Collision Avoidance in Path Planning   for a Group of Robots in a Spatio-Situational Indeterminacy
Creators: name: Моторин, Дмитрий Евгеньевич
name: Попов, Сергей Геннадьевич
name: Курочкин, Леонид Михайлович
Publisher: name: Санкт-Петербургский политехнический университет Петра Великого
Year: 2017
Subjects: управление
группа роботов
коллизия
динамическая карта
планирование движения
пространственно-ситуационная неопределённость
control
group of robots
collision
dynamic environment
path planning
spatiosituational indeterminacy

description: Рассмотрен алгоритм разрешения коллизий при планировании действий группы роботов в условиях изменяющейся среды. Во время движения группы к цели возникают пересечения траекторий, приводящие к коллизиям − столкновениям. Проведено сравнение трех подходов к разрешению коллизий: игнорирование коллизий, разрешение всех коллизий последовательно для пар роботов и разрешение коллизий последовательным расширением группы роботов. Эффективность алгоритма оценена исходя из полноты решения задачи и скорости разрешения коллизий, при условии минимизации проходимого каждым роботом пути. Разрешение коллизий произведено удлинением траектории робота в область свободного пространства вокруг места коллизии. Алгоритм состоит из трех частей: поиск свободных от препятствий областей вокруг коллизии для каждого робота, исключение из полученной области областей возможных коллизий и минимизация удлинения пути в полученной области. Исследование алгоритма выполнено средствами имитационного моделирования, в котором реализована модель среды и группы роботов, движущихся в ней. Определены границы применимости и даны рекомендации по выбору режимов работы алгоритма разрешения коллизий при планировании движения. Предложенный алгоритм разрешения коллизий может использоваться при планировании движения групп роботов в условиях пространственно-ситуационной неопределённости.
description: The paper considers a collision avoidance path-planning algorithm for a group of robots in a spatio-situational indeterminacy. When moving a group of robots to the target paths, crossing is the cause of collision. The authors compared three approaches to collision avoidance: ignoring collisions, resolution of all collisions for pairs of robots, resolution of collisions by expanding the group of robots. The effectiveness of the algorithm is evaluated based on the completeness of the solution of the problem and the collision resolution rate while minimizing each robot path. Collision avoidance is achieved by extension of the trajectory of the robots in the free space around the collision area. The algorithm consists of three parts: searching for the space free of obstacles around the collision area for each robot, exclusion from the resulting field areas of possible conflicts and minimizing the elongation paths in the obtained field. The algorithm was studied by simulation modeling, which implemented a model of the environment and the group of robots. The result of this work was to determine the limits of applicability and recommendations for the choice of the operating modes of the collision avoidance path-planning algorithm. The proposed algorithm can be used in case of path planning for a group of robots in a spatio-situational indeterminacy.