Материал: 2426

ти) присутствуют как в ряде традиционных универсальных САПР мирового уровня, так и в некоторых специализированных САПР.

Анализ современного состояния вопроса в предметной области позволил сделать вывод, что все программные продукты и системы с функциями САПР, в которых в том или ином виде присутствуют функции автоматизированного планирования и оптимизации траектории движения объектов (планирования и оптимизации пути), могут быть разделены на 5 групп:

1)специализированные САПР – трассировщики печатных плат;

2)универсальные САПР различного уровня, в которых (либо в их приложениях/расширениях) в качестве одной из дополнительных частных специфических функций присутствует функция планирования

иоптимизации пути в определенной предметной области;

3)специализированные ГИС-системы пространственного анализа данных рельефа поверхности Земли;

4)игровые «движки» (middleware-программы, специализированные вычислительные ядра, или библиотеки подпрограмм), предназначенные для быстрого поиска некоторых неоптимальных в общем случае гладких траекторий движения игровых персонажей при условии непересечения с препятствиями;

5)специализированные научные и инженерные САПР, предназначенные для автоматизированного планирования и оптимизации траектории движения объектов.

Рассмотрим примеры наиболее эффективных и распространенных представителей САПР перечисленных пяти групп.

1. К специализированным САПР, предназначенным для автоматической топологической трассировки печатных плат, относятся продукты: TopoR компании Эремекс (РФ), OrCAD компании Cadence Design Systems (США), PROTEUS VSM компании Labcenter Electronics (Великобритания), Altium Designer компании Altium Limited (Австралия) и многие другие [167, 180, 185].

Ввиду специфики решаемой задачи (двухмерное пространство, возможность многослойных перекрытий) данные специализированные САПР не могут быть применены для планирования и оптимизации траектории движения объемных объектов в трехмерном пространстве с произвольными препятствиями.

2. Проектирование кабельных и/или трубопроводных систем с функцией автоматического прокладывания (трассировки) электропроводов (трубопроводов) в трехмерном пространстве с препятствиями присутствует в ряде приложений/расширений универсальных

20

САПР: AutoCAD Plant 3D компании Autodesk (США), Autodesk Inventor Routed Systems Suite, Bentley AutoPLANT компании Bentley Systems (США), SolidWorks Routing компании Dassault Systemes (Франция), Model Studio CS Трубопроводы – расширение САПР AutoCAD, разработанное компанией CSoft (Россия), КОМПАС-3D Трубопроводы 3D компании Аскон (Россия) и др. При этом минимизируется длина пути электропровода (трубопровода), в ряде продуктов дополнительно возможно задание определенного минимального расстояния до препятствий [139, 143, 152, 185].

Однако данный функционал также имеет свою специфику и не может быть использован даже для поиска оптимальной по геометрической длине пути траектории движения точки в трехмерном пространстве, поскольку электропроводы/трубопроводы прокладываются только в определенных направлениях (как правило, параллельных трем координатным осям пространства, иногда добавляются поворо-

ты на 45°).

3.К третьей группе относятся ГИС-системы: AutoCAD Map 3D компании Autodesk, Гис Zulu компании Политерм (Россия), ArcGIS компании ESRI (США), свободная кроссплатформенная система

Quantum GIS на площадке SourceForge, системы GRASS, gvSIG с от-

крытым исходным кодом, 2ГИС и многие другие [10, 67, 68, 130]. Среди заявленных возможностей большинства ГИС-систем – оп-

ределение пути с минимальной стоимостью от начальной до конечной точки на карте.

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

4.Отдельную группу программных продуктов, которые могут быть классифицированы как специализированные САПР с функциями планирования и оптимизации траектории объектов, составляют т.н. игровые middleware-«движки» с функциями поиска свободных от столкновения путей: SpirOps AI французской компании SpirOps,

Kynapse AI компании Autodesk, NavPower AI компании BabelFlux (США), PathEngine одноименной французской компании и др. [207, 236, 240, 248]. Необходимо отметить, что функции игровых «движков» не ограничиваются планированием траекторий отдельных игро-

21

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

Планируемая траектория

Игровой персонаж

Препятствия

Рис. 1.5. Пример планирования траектории отдельного игрового персонажа в игровом уровне с препятствиями при помощи Autodesk Kynapse

Наиболее известный и распространенный игровой middleware- «движок» Kynapse компании Autodesk, предназначенный для реализации искусственного интеллекта (AI) в играх, позволяет осуществлять поиск пути юнитов (игровых персонажей) на карте и на сложном трехмерном ландшафте с препятствиями (рис. 1.5) [207].

Другой распространенный «движок» для поиска гладких траекторий движения юнитов в различных играх, NavPower, позволяет автоматически генерировать полигональные навигационные сетки над всеми проходимыми для юнита поверхностями уровня, используя геометрию уровня в качестве исходных данных [236].

По утверждениям разработчиков NavPower, автоматическая генерация сеток NavGraph позволяет легко обрабатывать для последующего поиска пути юнитом, сложные поверхности уровня, например, путепроводы, эстакады, изогнутые тоннели, винтовые лестницы, а также многоуровневые здания с использованием собственных методик вокселизации и техники генерации поверхностей. Кроме того, обеспечивается поддержка изменения пути юнита при меняющихся условиях, т.е. динамическом изменении расположения препятствий [236].

Расширение «движка» NavPower FlightPak позволяет планировать движение летающих и плавающих в игре объемных объектов-

22

юнитов в трехмерном пространстве со множеством выпуклых объемных тел препятствий [236].

PathEngine – еще одна компьютерная программа, подпрограммное обеспечение (англ. middleware), предназначенное для реализации поиска пути в трехмерном пространстве. PathEngine поставляется в виде SDK и используется как составной компонент других программных продуктов [240].

В основном перечисленные возможности middleware-«движков» используются в играх для поиска гладких путей движения юнитов, описываемых математически как отдельные точки, в двухмерном пространстве с препятствиями (на карте) либо в псевдотрехмерном пространстве, сводимом к двухмерному (полигональные навигационные сетки накладываются на проходимые поверхности рельефа местности).

Ограничениями и недостатками перечисленных игровых «движков» с позиции рассматриваемой в настоящей монографии проблематики являются: неоптимальный характер планируемых траекторий по геометрической длине пути, невозможность учета угловых координат перемещающегося объекта-юнита при оптимизации траектории, ограниченность учета объемных тел препятствий только выпуклыми формами (NavPower FlightPak), невозможность задания пользовательских целевых функций на основе линейных и угловых координат юнита, невозможность планирования и оптимизации траектории в пространстве конфигураций многозвенного объекта (механизма) с большим количеством степеней свободы.

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

5. Представители пятой группы САПР с функциями автоматизированного планирования и оптимизации траектории движения объектов, которые довольно малочисленны, обладают наиболее широким диапазоном возможностей и эффективностью в решении собственных задач.

Однако среди них также преобладают специализированные САПР, предназначенные для решения специфических задач. К подобным САПР относятся, например, программные комплексы планирования движений большегрузных грузовых автомобилей больших размеров по городским магистралям AutoTURN канадской фирмы

Transoft Solutions [208], PathPlanner R4 шведской фирмы SIMTRA [247], а также планирования траекторий движения самолетов по тер-

23

ритории аэродрома и взлетно-посадочным полосам PathPlanner A5 уже упомянутой фирмы SIMTRA [247].

Данные программные продукты фактически рассматривают частные расчетные случаи задачи оптимизации траекторий движения объектов в неоднородном организованном пространстве, сводя пространственную расчетную схему к плоской (рис. 1.6). Они не могут быть использованы для планирования траекторий объемных тел произвольной формы в пространстве.

И наконец, среди пятой группы САПР существует несколько программных продуктов, предназначенных собственно для

планирования траекторий объемных тел произвольной формы в пространстве.

Необходимо отметить специализированный САПР VIZMO, разра-

ботанный в Parasol Laboratory, Department of Computer Science Texas A&M University (США) [206].

Данный продукт позволяет планировать движение объемных объектов произвольной формы в трехмерном пространстве с произвольно расположенными препятствиями.

Используются подходы и методики на основе рандомизации пространства: вероятностной дорожной карты (PRM, Probabilistic Road Map), быстро развертываемых случайным образом деревьев пути

(RRT, Rapidly-Exploring Random Tree), поиска на графах, локальной оптимизации [206].

По данным переписки с разработчиками, VIZMO является «закрытым», некоммерческим САПР, допускается его использование лишь сотрудниками университета Texas A&M University, вследствие чего ограничена возможность его практического использования. По указанной причине невозможно провести оценку эффективности используемых в VIZMO алгоритмов и методик, а также использовать данный продукт для решения поставленных задач.

САПР eM-Workplace PC (старое название ROBCAD), входящий в пакет решений для трехмерного моделирования, анализа и автомати-

24