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

 

 

                                        

 

при этом b пересчитывается каждый раз при нахождении нового вектора скорости.

 

Пример №2:

Пусть рабочая область пространства W, в которой действует МР, является подмножеством Ân. Пусть  O Ì W представляет собой множество препятствий в рабочей области, тогда свободным пространством в W будет являться множество F = W \ O; задача построения пути МР в таком случае есть задача нахождения набора точек в F, определяющих траекторию движения МР из начальной точки  в  точку целевую.          

Сначала рассматривается простой алгоритм, в котором многоугольный объект M, имеющий две степени свободы, перемещается в рабочем пространствеW, в котором присутствует конечное множество препятствий O. Текущее положение объекта M задается вектором x, начальное положение – вектором xs, а целевая точка – вектором xg. Тогда трасса строится по следующему алгоритму: 

 

 

            x ¬ xs          

repeat                   

Dmin ¬ min (D(M,o)) "o Î O                   

Frepulse ¬ Dmin × 1 / |D|2                   

Fattract ¬ xg – x                   

Fres ¬ Fattract + a × Frepulse                   

x ¬ x + Fres          

until ( x = xg ) or ( |Fres| = 0 ) 

 

 

            Здесь D - вектор, доставляющий минимальное расстояние между M и препятствием o Î O. Константа a управляет влиянием препятствия на M в зависимости от расстояния. При использовании подобной потенциальной функции столкновений с препятствиями не происходит, однако, алгоритм может зацикливаться в случае достижения МР локального минимума в потенциальном поле. Для борьбы с этим явлением могут применяться различный методы, например, «барьер» из точек высокого потенциала вокруг точки локального минимума или метод Монте-Карло.          

Далее для объекта M вводится дополнительная степень свободы  - угол поворота q, начальная конфигурация объекта в данном случае –

( xs , qs ). Предполагается, что движется в коридоре минимального потенциала (КМП). Если он ориентирован так, что момент вращения МР в потенциальном поле минимален, то движение происходит таким образом, что главная ось направлена по касательной к КМП.          

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

x ¬ xs            

q ¬ qs          

repeat       

Frepulse ¬ ( 0 , 0 )                   

moment ¬ 0                   

for each p Î P                             

Dmin ¬ min (D( c + p , o)) "o Î O                             

Frepulse ¬ Frepulse + Dmin × 1 / |D|2                             

moment ¬ moment + ( p ´ Dmin ) × k

endfor

Fattract ¬ xg – x                    

Fres ¬ Fattract + a × Frepulse                   

x ¬ x + Fres                        

q ¬ q + b ´ moment          

until ( x = xg ) or ( |Fres| = 0 ) 

 

 

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

 

Пример №3:

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

·        на первом уровне – детальное описание среды, окружающей робота, с помощью декартовой сетки C;

·        на втором уровне – полярная гистограмма H, которая строится по данным, содержащимся в C, вокруг центра масс МР как набор значений из C, соответствующий некоторым фиксированным секторам шириной a каждый. Каждому сектору k ставится в соответствие величина hk, называемая полярной плотностью препятствий в направлении k.

Выходными данными алгоритма являются сигналы управления МР.          

Пусть C*, называемая активной областью, есть область сетки C размером ws´ws, построенная вокруг МР; ее элементами являются активные ячейки cij. Тогда C преобразуется в H следующим образом: строятся векторы препятствий, направление которых относительно точки текущего положения МР определяется как                                      

а модуль вектора                                      

где a,b = const > 0;

dij – расстояние между активной ячейкой и МР;

c*ij – среднее значение в активной ячейке (i,j);

x0, y0 – текущие координаты МР;

xi, yi – координаты активной ячейки (i,j).           

Каждому из k секторов ставится в соответствие угол из ряда 0, a, 2a,…, 360°-a. Тогда между k и c*ij существует следующее отношение: 

 

 

                                        

 

Для каждого сектора k hk вычисляется  

 

 

                                       

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

Далее вычисляется направление движения в полярных координатах, qfree, и соответствующий ему сектор kfree в H. Алгоритм выбирает более «проходимое» направление и, вместе с тем, как можно более приближенное к текущему направлению на цель qtarg.           

Скорость движения МР в начальной точке устанавливается максимальной (Smax), а затем определяется на каждом шаге в соответствии с формулой                                      

где

h``c = min(h`c , hm);

h`c – сглаженная полярная плотность препятствий в выбранном направлении движения;

hm – эмпирически установленная константа.

При этом отношение (*) гарантирует S` ³ 0 при h``c £ hm.

 

 

 

 

 

 

 

 

 

 

 

 

 2.3 Метод точек видимости

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

 

ВЫВОДЫ

В результате научно-исследовательской работы были рассмотрены и изучены такие методы алгоритма поиска пути как:

• Астар
• Метод потенциальных полей
• Метод точек видимости

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

 

Список литературы

1)	Принцип работы алгоритма поиска пути Астар (A*) http://www.gamedev.ru/articles/?id=70121
2)	The long and short of steering in computer games Simon L. Tomlinson 2 Campden Way, Handforth, Cheshire. SK9 3JA, United Kingdom e-mail: DrSimonT@iclway.co.uk
3)	ISSN 1009 - 3095 Journal of Zhejiang University SCIENCE V. 4, No. 3,P. 264-269, May- June, 2003 http://www. zju.edu.cn/jzus; http: //www. periodicals, com. en;
4)	Applying an Enhanced Path Finding Avatar for a Virtual Environment Jui-Fa Chen, Wei-Chuan Lin*, Li-Hao Yang Department of Computer Science and Information Engineering, TamKang University, Danshui, Taiwan 25137