Управление группой движущихся объектов

САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ПЕТРА ВЕЛИКОГО

ИНСТИТУТ КОМПЬЮТЕРНЫХ НАУК И ТЕХНОЛОГИЙ

Кафедра «Системный анализ и управление»

 

 

 

 

 

 

Научно-исследовательская работа

Тема: Управление группой движущихся объектов

 

 

Направление: 27.03.03 – Системный анализ и управление

 

 

 

 

 

Выполнил студент гр. 53502/1      ________     А.К. Артиков

 

Руководитель, к.т.н., доц.      ________    А.А. Ефремов

 

 

 

 

 

 

Санкт-Петербург

2015 
Оглавление

 

 

ВВЕДЕНИЕ

Групповое управление объектами – это одна из самых актуальных проблем во многих сферах жизни общества. Если с помощью группы каких-либо объектов (роботов, людей) требуется решить общую задачу, возникает проблема взаимодействия внутри этой группы.

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

 

1 Поиск пути и обход препятствий

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

Если мир дискретен найти путь — значит найти последовательность клеток перемещаясь по которым можно перейти из одного положения в другое. Когда-же мир непрерывен, найти путь — значит найти функции линейного и углового ускорения от координат. Таким образом алгоритмы поиска пути делятся на дискретные и непрерывные. В статье [3] также предлагается деление на алгоритмы локального и глобального поиска. При этом, под алгоритмами локального поиска автор понимает поиск пути в непосредственной близости от цели, соответственно, под алгоритмами глобального поиска понимается поиск на некотором протяжённом расстоянии. Однако, такое деление представляется достаточно условным так как в различных ситуациях один и тот — же алгоритм может использоваться как вблизи, так и на большом расстоянии от цели.

 

2 Алгоритмы поиска пути

2.1 Алгоритм Астар

Алгоритмы поиска на дискретной карте сводятся к поиску пути на графе. Существует несколько алгоритмов поиска пути. Среди них чаще всего используется алгоритм А со звездой или A* - поиск по первому наилучшему совпадению. Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). 

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Этот алгоритм был впервые описан в 1968 году Питером Хартом Нильсом Нильсоном и Бертраном Рафаэлем. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.

A* пошагово просматривает  все пути, ведущие от начальной  вершины в конечную, пока не  найдёт минимальный. Как и все  информированные алгоритмы поиска, он просматривает сначала те  маршруты, которые «кажутся» ведущими  к цели. От жадного (который тоже  является алгоритмом поиска по  первому лучшему совпадению) его  отличает то, что при выборе  вершины он учитывает, помимо  прочего, весь пройденный до неё  путь (составляющая g(x) — это стоимость  пути от начальной вершины, а  не f(x), после чего этот узел  раскрывается. На каждом этапе  алгоритм оперирует с множеством  путей из начальной точки до  всех ещё не раскрытых (листовых) вершин графа («множеством частных  решений»), которое размещается в  очереди с приоритетом. Приоритет  пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает  свою работу до тех пор, пока  значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью. от предыдущей, как в жадном алгоритме).

В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение.

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

Алгоритм оперирует двумя списками: сортированным (далее open), в котором хранятся вершины, ребра которых еще не были обработаны (узлы сортируются по оценке расстояния до конечного узла от наиболее близкого), и не сортированный (далее close) с обработанными узлами. Изложим принцип работы данного алгоритма в виде диаграммы деятельности.

Рисунок 1. Диаграмма деятельности алгоритма А*

 

лгоритм A* является полным в том смысле, что он всегда находит решение, если таковое существует. Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути). В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в некотором лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.

Одной из проблем алгоритма является скорость его выполнения: Основная сложность с реализацией A* состоит в увеличении скорости вычислений. Действительно, с ростом количества одновременных поисков и размеров карты вычисления занимают всё больше машинного времени. Как известно, основное время в поиске пути занимает работа с Open и Closed списками. Хорошо продумав алгоритмы поиска и вставки элементов можно существенно увеличить скорость работы А*. К сожалению правильной реализации собственно поиска может оказаться недостаточно в случае очень большой карты или большого количества одновременных поисков. Кроме того, следует учитывать особенности реализации структур данных для выбранной платформы. Поэтому на практике применяют ряд подходов, которые позволяют уменьшить применение А*. Некоторые из них описаны ниже.

Уменьшение точности поиска.

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

Остановимся подробнее на требованиях, которые налагаются на локации. В большинстве случаев путь от точки А к Б ищется для того, чтобы произвести определённые действия, к примеру бот ищет путь к персонажу игрока для того, чтобы атаковать его. Понятно, что для атаки в большинстве случаев необходимо, чтобы игроки были видимы друг другу, или говоря иными словами между ними не должно быть непроходимых областей, или клеток, если речь идёт о двумерной карте. Т.е. между центрами клеток в которых находятся персонажи A и Б можно провести прямую так, чтобы она не пересекала непроходимых клеток. Таким образом мы видим, что локация является частным случаем выпуклого множества [2] и задача разбиения карты на локации сводится к разбиению на выпуклые множества.

Предварительный расчёт пути.

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

Комбинирование различных алгоритмов поиска

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

 

2.2 Метод потенциальных  полей

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

Таким образом, отталкивающая сила будет равна:

 

Где   искомая функция дающее направление движения в данной точке карты,  - сила притяжения к цели, - сумма сил отталкивания от препятствия соответственно.

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

Существует ряд способов её решения. Так например пытаются подобрать ф — ции, которые не имеют локальных минимумов. Другое решение состоит в том, чтобы при попадении в локальный минимум временно изменить цель, по достижении этой временной цели двигаться по направлению к главной. Данный способ выхода из локального минимума называется методом виртуальных локальных целей и изложен в [4].

Вариацией метода потенциальных полей является метод виртуальных отталкивающих клеток изложенный в [5]. Его суть состоит в том, что игровое поле разделяется на клетки (поля) и если клетка содержит препятствие, она обладает отталкивающим потенциалом. Объект, для которого нужно найти путь представляется находящимся в центре квадрата стороны которого параллельны клеткам игрового поля. Если клетка с препятствием попадает внутрь квадрата, она производит отталкивающее действие, иначе нет. Результирующая сила вычисляется как сумма отталкивающих сил от клеток с препятствиями и притягивающей к цели силе. Таким образом устраняется влияние удалённых препятствий и отдалённых частей препятствий большого размера. В следствие этого, траектория движения получается более плавной.

Иллюстрация метода представлена на рисунке.

Рисунок 2. Иллюстрация метода

 

2.2.1 Примеры реализации  метода потенциальных полей

Пример №1:

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

В данной реализации метода потенциалов МР представляется как точкка начала отсчета в полярных координатах, из которой вращающимся сенсором осуществляется непрерывное циклическое сканирование местности с сектором обзора 360° (рис. 4).  

Пусть угол g – угловой шаг сканирования, di - результат i–го (относительно текущего направления движения МР) замера дальности от МР до препятствия. В соответствие каждому di ставится вектор силы fi, вычисляемый с помощью уравнений для искусственного потенциального поля:  

 

 

       

 

где A – фиксированная константа. После обзора всего сектора (360°) определяются новые компоненты вектора скорости Vx и  Vy:

         

 

 

 

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