48277 (588532), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

– вектор параметров объекта моделирования;

X – множество допустимых значений входных параметров.

Таким образом, совокупность алгоритмических и программных средств, обеспечивающая процесс автоматизированного моделирования, образует систему автоматизации имитационного моделирования (САИМ) [36]. Поскольку пользователь при этом не вводит каждый набор начальных данных для очередного прогона имитационной модели и только указывает цель или критерий и область варьирования параметров, в то время как поиск допустимых решений задач моделирования выполняется при помощи САИМ автоматически, к последней можно применить определение интеллектуальной системы моделирования. Например, функции САИМ, в контуре управления гибкой производственной системы, в целом, заключаются в анализе альтернативных вариантов поведения роботов после принятия того или иного возможного решения относительно диспетчеризации и оперативного планирования информационно-двигательных действий и т.п.

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

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

На первом этапе автоматизации управления экспериментами решаются две задачи: исполняется структурно-алгоритмическое построение собственно модуля управления; формируются содержательные основы и формальные требования к организации информационного обмена с имитационной моделью.

Задача структурно-алгоритмического построения модуля управления экспериментами и синтеза системы знаний решается в следующей последовательности: определяются состав и структура модуля (разрабатываются условия взаимодействия его компонент и положение в общей структуре САИМ).

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

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

(2.2)

где S – входное слово алгоритма имитационного моделирования;

Q – множество допустимых наборов значений параметров робота;

С – область определения алгоритма имитационного моделирования.

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

Таким образом, выражения (2.2) соответственно определяют условия согласования S с имитационной моделью и с алгоритмом. Задача состоит в разработке аппарата формального анализа непротиворечивости изменений семантически взаимосвязанных параметров для обеспечения варьирования, что не нарушает условия (2.2) и не приводит к изменениям фиксированных параметров.

На втором этапе производится автоматизация управления экспериментами и построения системы знаний решаются следующие этапы:

– разработка принципов, взаимодействия системы логического вывода и численных оптимизационных процедур;

– выбор (разработка) аппарата реализации логического вывода в комбинированных алгоритмов управления экспериментами;

– разработка на основе предложенного аппарата эффективных алгоритмов вывода с учетом специфики взаимодействия с численными процедурами оптимизации.

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

– автоматизации управления экспериментами в условиях лингвистической неопределенности параметров, например, «степень подобия / отличия…» не имеет естественного численного измерения;

– организации экстремальных экспериментов в задачах однопараметрической оптимизации при существенно неравномерном расположении точек в середине интервала, например, унимодальная функция отклика, и фиксирования соответствующих состояний в модели системы знаний;

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

62.3 Алгоритмы планирования

Метод потенциалов в задаче выбора пути для мобильного робота был предложен А.К. Платоновым в 1970 году.

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

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

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

За рубежом основные ссылки делаются на работы Брукса и Хатиба, которые вышли в свет в 1985 году [6, 7]. Следует отметить, что в Японии подобные разработки были выполнены сотрудниками фирмы Hitachi, Ltd. в 1984 году [9]. Подобные же алгоритмы использовались и при трассировке печатных плат в 1967 году (см. [8], в которой дана ссылка на более раннюю работу 1948 года). Для того, чтобы проследить эволюцию архетипа основной идеи метода, ниже приводится историческая справка о разработках, имеющих отношение к методу потенциалов в задачи выбора пути.

В данной работе исследованы модификации алгоритма, изложенного в [1]. При этом рассмотрены следующие направления модификации исходного алгоритма:

1. Исследованы степенная и показательная функции отталкивания от препятствий и влияние их на результирующий путь мобильного робота (МР). Для оценки эффективности пути использовалась функция отклонения вектора направления движения от вектора направления на цель.

1. Проанализированы возможности использования метода потенциалов для управления распределенной мобильной системой (РМС). Исследовано пять способов организации такого движения:

1. движение по схеме «цепь». В этом случае сила притяжения цели действует на «лидера», и каждый МР «притягивается» к впереди идущему;

2. движение типа «гонка за лидером». В этом случае все элементы РМС «притягиваются» к «лидеру», который, в свою очередь, «притягивается» к целевой точке;

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

4. движение типа «схождение». В этом случае «лидер» собирает все элементы РМС в компактную группу;

5. организация движения типа «свободный поиск». В этом случае сила притяжения к цели отсутствует, и каждый элемент РМС движется в свободном от препятствий направлении.

Первые два режима используются для организации передвижения РМС, последние три – для информационного исследования среды.

Основное отличие нового алгоритма от изложенного в [1] состоит в том, что в [1] непосредственно вычислялось расстояние до каждого из препятствий _i непосредственно, а в новом алгоритме используется имитатор дальномерной системы. Полученный массив дальностей в некотором секторе в дальнейшем подвергается логической фильтрации для построения оценок величин _i.

Наряду с указанным названием – метод потенциалов (Potential Field Approach), он имеет следующие названия: способа «искусственных потенциальных полей» (artificial potential fields), «полей виртуальных сил» (virtual force field – VFF), «гистограммы векторных сил» (vector field histogram-VFH) и др. Суть этого метода, напомним, заключается в том, что путь строится на основе решения специального «уравнения движения», в которое входят «сила притяжения к цели», «силы отталкивания от препятствий» и, возможно, некоторые другие «силы». При ссылке на этот метод в качестве пионерских упоминаются работы 1985–1986 гг. [6,7]. Вместе с тем работа фирмы Хитачи по управлению МР, в которой использованы идеи «силового поля», выпущена в 1984 г. [9]. В [1] опубликовали результаты подобного исследования в ИПМ АН СССР в 1974 г. Вместе с тем использование подобных физических аналогий при трассировке электронных плат уходит корнями вглубь 50‑х годов [8]. Правда, вычислительные аспекты при этом имеют свою специфику.

Сам архетип идеи движения в поле «информационных» (виртуальных) сил восходит к работам 30-40-х годов одного из виднейших представителей гештальтпсихологии Курта Левина. Он выступил с идеей применения в психологии концепции физического поля для описания поведения и конфликтных ситуаций при взаимодействии индивида с окружающим миром [3]. Современные психологи критикуют К. Левина за физикализм концепции, акцент на динамический аспект в ущерб содержательному и многое другое. Вместе с тем в указанных работах К. Левина можно почерпнуть немало интересного. Экспериментальный материал, подтверждающий разработанную концепцию, был получен в основном при наблюдении за детьми разного возраста и документирован посредством киносъемок.

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

На начальном этапе исследований в ИПМ рассматривались препятствия в виде окружностей. Подобное представление после результатов работ Koditschek с соавторами [4, 5] можно считать основным. Сила притяжения к цели полагалась постоянной по модулю и направленной к точке цели. Сила отталкивания от i‑ого препятствия f_i зависела от аргумента R_i /r_i, где R_i – радиус i‑ой окружности, r_i -расстояние от центра i‑ой окружности до движущейся точки. f_i считалась направленной от центра окружности. Траектория («локомоция») получалась в результате интегрирования уравнений движения второго порядка, так как ускорение, действующее на движущуюся точку, определялось суммой указанных сил. В ходе исследований выяснилось, что инерционность, заложенная в указанную модель, приводит к тому, что траектория движения становится малоприемлемой (препятствие «отбрасывает» движущуюся точку очень сильно и траектория получается чересчур «изрезанной». Для того, чтобы избавиться от этого недостатка и сделать метод годным для случая аппроксимации контуров препятствий другими способами, было предпринято следующее. Во-первых, стали использоваться уравнения движения первого порядка (т.е. действующие силы определяют скорость, по сути дела речь идет об аналоге простого градиентного спуска). Во-вторых, сила отталкивания стала определяться аргументом, равным расстоянию до препятствия. При этом форма контура препятствия произвольна, а для приведенного выше примера это разность r_i – R_i. Направлена эта сила в сторону от ближайшей точки препятствия. В ходе исследований было признано рациональным в случае наличия нескольких препятствий использовать функции от указанного аргумента x типа x^-k или e^-cx, которые быстро убывают с расстоянием. При этом коэффициенты k и c могут быть варьируемыми параметрами.

Следует особо подчеркнуть, что, варьируя параметры k и c при определении сил отталкивания, можно получать траектории для движения нескольких МР. Если ввести в этом процессе запаздывание, то можно получить режим «следования друг за другом».

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

Таким образом, метод потенциалов позволяет строить «размытые» модели среды и получать решение без учета ненужных подробностей.

Анализируя разнообразие зарубежных работ по методу потенциалов, можно выделить два интересных направления.

Характеристики

Список файлов ВКР