УПРАВЛЕНИЕ РОЕМ РОБОТОВ ПРИ ИССЛЕДОВАНИИ НЕКОТОРОЙ ТЕРРИТОРИИ МЕТОДОМ СИЛОВОЙ РЕЛАКСАЦИИ

Аннотация

Работа посвящена разработке алгоритмов поведения группы роботов, базирующихся на использовании биоинспирированных подходов, основанных на использовании аналогий поведения живых существ, в частности метода роя частиц. Целью работы роя роботов является исследование некоторой территории с целью обнаружения участка с экстре-мальным значением заданного вещества. Основополагающей идеей роевого управления яв-ляется «роевой интеллект». В основу управления гомогенным роем роботов положен прин-цип силовой релаксации. Поиск решения производится в аффинном пространстве, элемен-тами которого являются n-мерные точки (позиции). Обозначим R  {ri |i=1,2,..s } рассмат-риваемый рой роботов, где s – число роботов в рое; Xi(t)(xi (t), yi(t)) – текущее положение робота ri. Пусть начальные положения роботов роя определяет набор векторов Xi(0), i[1:s]. Каждый робот ri вычисляет целевую функцию f(Xi(t)) – значение искомого вещест-ва в точке Xi(t). На каждой итерации выполняются следующие действия. Введем обозначе-ния W(t) – множество координат ячеек (точек) над которыми расположены роботы в момент t. Определяется точка X*i(t)W(t) с лучшим значением функции f(Xi(t)), которая рассматривается в качестве аттрактора. В соответствии с алгоритмом силовой релак-сации положение робота ri в следующий момент времени t1 определяется по формуле: Xi t1)Xi(t) Vi(t). Принципы перемещения робота производится по аналогии с методом роя частиц. В отличие от канонического метода роя частиц в работе предусматривается использование вещественных значений параметров в многомерных, вещественных, метри-ческих пространствах. Также, в отличие от канонического метода роя частиц, в нашем случае скорость Vi(t) и координаты точки Xi(t1) не могут быть представлены в виде ана-литического выражения с вещественными значениями переменных. Если в качестве пози-ции используется двумерный вектор Vi(t) в декартовой системе координат 0xy, то число параметров, определяющих положение частицы в пространстве решений (позицию) долж-но быть равно двум. Значение каждой координаты откладывается на соответствующей оси пространства решений. В этом случае возникают некоторые требования к значениям координат. Значения координат должны быть дискретными и независимыми друг от дру-га. В качестве аналога скорости Vi(t) выступает оператор направленной мутации (ОНМ), суть которого заключается в изменения целочисленных значений координат. Перемещение робота ri в новую позицию означает переход от Vi(t) к новой – Vi(t+1) c новыми целочислен-ными значениями генов координат, полученными после применения оператора направлен-ной мутации. Вектор перемещения Vi(t), которое робот ri совершает при переходе из те-кущего положения Xi(t) в положение Xi(t1) имеет вид: Vi(t)= VIi(t-1)+VCi(t-1)+VSi(t-1). Вре-менная сложность алгоритма лежит в пределах О(n2)-О(n3), где n –число роботов.