Программное обеспечение системы принятия решений адаптивного робота
Порядок и назначение разработки подсистемы планирования действий интеллектуального робота. Задачи, решаемые данной подсистемой и функциональные требования к ней. Информационное моделирование функционирования интеллектуального робота и управление им.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 10.06.2010 |
| Размер файла | 864,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Константа b управляет величиной поворота и определяется эмпирически, поскольку математическое решение нетривиально и зависит от многих факторов. Кроме того, при практической реализации алгоритма, выбор c может быть неоднозначен. В рассматриваемых примерах для трехколесного МР в качестве c бралась середина оси между двумя задними колесами.
В работе [12] представлен метод обхода препятствий мобильным роботом (МР), получивший название метода «гистограмм векторных полей» (VHF_метод). Он позволяет обнаруживать препятствия и обходить их во время движения. МР, управляемый данным алгоритмом, маневрирует быстро и без остановок даже среди большого количества неупорядоченных препятствий.
VHF_метод для представления препятствий использует сетку на двумерной декартовой плоскости. Каждой ячейке сетки ставится в соответствие характерное значение, представляющее уровень «уверенности» алгоритма в присутствии препятствия в данной ячейке. Метод использует двухуровневую систему представления данных:
– на первом уровне - детальное описание среды, окружающей робота, с помощью декартовой сетки C;
– на втором уровне - полярная гистограмма H, которая строится по данным, содержащимся в C, вокруг центра масс МР как набор значений из C, соответствующий некоторым фиксированным секторам шириной каждый. Каждому сектору k ставится в соответствие величина hk, называемая полярной плотностью препятствий в направлении k.
Выходными данными алгоритма являются сигналы управления МР.
Пусть C*, называемая активной областью, есть область сетки C размером wsws, построенная вокруг МР; ее элементами являются активные ячейки cij. Тогда C преобразуется в H следующим образом: строятся векторы препятствий, направление которых относительно точки текущего положения МР определяется как:
(2.6)
а модуль вектора
(2.7)
где a, b = const > 0;
dij - расстояние между активной ячейкой и МР;
c*ij - среднее значение в активной ячейке (i, j);
x0, y0 - текущие координаты МР;
xi, yi - координаты активной ячейки (i, j).
Каждому из k секторов ставится в соответствие угол из ряда 0, , 2,…, 360-. Тогда между k и c*ij существует следующее отношение:
(2.8)
Для каждого сектора k hk вычисляется
(2.9)
Таким образом, каждая из активных ячеек находится в одном из секторов. Однако, из-за дискретности сетки, в результате такого распределения ячеек могут возникать «ступеньки» в секторах, что может привести к ошибкам в выборе направления. Для того чтобы избежать искажения результата, используется сглаживающая функция:
(2.10)
Далее вычисляется направление движения в полярных координатах, free, и соответствующий ему сектор kfree в H. Алгоритм выбирает более «проходимое» направление и, вместе с тем, как можно более приближенное к текущему направлению на цель targ.
Скорость движения МР в начальной точке устанавливается максимальной (Smax), а затем определяется на каждом шаге в соответствии с формулой:
(2.11)
где h``c = min (h`c, hm);
h`c - сглаженная полярная плотность препятствий в выбранном направлении движения;
hm - эмпирически установленная константа.
При этом отношение (*) гарантирует S` 0 при h``c hm.
Статья [13] посвящена методу построения гладких трасс движения мобильного робота (МР), основанному на физической аналогии. Основными достоинствами метода являются устойчивое решение и работа не только с двоичными (препятствие или свободное пространство), но и с разнородными средами, поверхность которых может иметь неравные коэффициенты трения или углы наклона на различных участках.
В основе метода лежат физические принципы гидродинамики. Если предположить, что вся среда заполнена жидкостью, то потоки жидкости позволяют добраться из начальной точки в целевую. В этом случае оптимальным путем будет поток, направленный вдоль градиента давления, в котором достигается стационарное движение жидкости; локальный минимум не может быть достигнут, поскольку во всех точках потока удовлетворяется уравнение Лапласа. Для учета неоднородностей среды вводится внешняя сила, учитывающая силу трения и влияние проходимых препятствий, поэтому рассматриваются потоки вязкой жидкости. Основным уравнением движения вязкой несжимаемой жидкости является уравнение Навье-Стокса:
(2.12)
где - плотность жидкости;
v - вектор скорости движения жидкости;
t - время;
f - внешняя сила;
p - давление;
- коэффициент вязкости жидкости.
Упрощенное уравнение выглядит следующим образом:
(2.13)
Здесь неизвестными являются вектор скорости v и абсолютная координата x.
Граничные условия:
(2.14)
где - границы препятствий, n - внешняя нормаль к границе препятствия.
Начальные условия:
(2.15)
где xS - начальная точка, xG - целевая точка.
Для решения уравнения в двумерном пространстве методом конечных разностей уравнение представляется следующим образом:
(2.16)
где
(2.17)
Если число точек сетки N, то необходимо решить разреженную систему из 3N линейных уравнений.
Результатом работы рассматриваемого алгоритма является множество так называемых «коридоров». Каждый коридор начинается в окрестности стартовой точки и заканчивается в окрестности целевой. Следование МР по осевой линии коридора гарантирует его безопасность.
Далее рассматривается случай, когда внешняя сила не равна нулю, что позволяет учитывать разнородность среды.
Полная потенциальная энергия частицы в потоке:
(2.18)
где S - начальная точка, G - целевая точка, T - вектор, касательный к траектории, pG - pS - разность давлений в xS и xG.
В случае присутствия силы трения F:
(2.19)
Механическая работа силы трения LF зависит от длины траектории L. В случае достаточно большой величины F:
(2.20)
Все траектории имеют ограниченную длину
(2.21)
Практически, установка очень большой величины F на границах препятствий эквивалентна условию v = 0. При использовании F = const длина потоков может быть ограничена, поэтому, увеличивая величину F, можно добиться отсеивания путей большей длины, оставляя лишь пути, длины которых близки к оптимальным.
Для тестов данного метода использовался 4-х колесный МР на полигоне 60 м 100 м с препятствиями [13]. Внешняя сила f задавалась в виде:
(2.22)
где m - масса МР, - угол наклона участка поверхности в направлении движения, Kf - коэффициент трения между колесами и поверхностью.
Следует отметить также направление, связанное с достаточно сложным по своей структуре заданием потенциальной функции, которая не имеет локальных минимумов [4, 5]. Однако при этом задание подобной потенциальной функции может оказаться очень сложным.
3. Управление мобильным роботом на основе конечно-автоматного подхода
3.1 Предпосылки создания алгоритма
Распределенные системы, в том числе робототехнические, в последнее время привлекают все большее внимание исследователей. Одна из причин этого состоит в том, что системы такого класса все чаще используются как для промышленных, так и непромышленных приложений: действительно, объединение параллельно функционирующих подсистем позволяет выполнять такие задания, которые не под силу каждой из компонент сложной системы. На рис. 3.1 приведен пример такой многокомпонентной системы, включающей мобильные роботы разного назначения: погрузчики, исследователи и т.д. С другой стороны, управление системами такого класса представляет собой нетривиальную задачу: если управление каждой из подсистем, составляющих сложную систему, задача, вообще говоря, решенная (например, перевод манипулятора из точки в точку по заданной траектории), то управление согласованным поведением группы роботов, объединенных общей целью, является сложной проблемой. Заметим, что задача управления существенно усложняется, если часть подсистем преследует конфликтующие цели.
Рис. 3.1 - Многокомпонентная робототехническая система
В статье предлагается подход к решению задачи координации взаимодействия подсистем, составляющих сложную систему, базирующийся на описании всех подсистем как конечных автоматов и использующий сеть специальным образом построенных автоматов для координации работы подсистем в процессе выполнения предварительно сформированного задания. Кроме того, предложены способы планирования поведения сложной системы, использующие методы искусственного интеллекта.
3.2 Многокомпонентность интеллектуального робота
Многокомпонентная система это система, включающая в свой состав множество подсистем, объединенных общим заданием.
Можно дать ее более точное определение.
Пусть задание T может быть представлено как множество подзаданий ti:
T = {t1, t2,…, tm} (3.1)
Введем отношение следования F на T, так что tiFtj означает, что задание ti может быть выполнено только, если выполнено tj. Если такая структуризация задания T проведена, тогда можно построить описывающий T ориентированный граф:
G = (T, A), (3.2)
где T = {ti} - множество вершин графа G, A = {ai} T T - множество направленных дуг, при этом дуга a A соединяет ti с tj тогда и только тогда, когда tiFtj.
Пусть система S состоит из подсистем si (далее называемых локальными системами или терминалами):
S = {s1, s2,…, sN}, (3.3)
при этом Ti T - задание, выполняемое системой si.
Тогда систему:
CS = (S, T), (3.4)
будем называть T_сложной системой (далее - сложной системой), если выполнены следующие условия:
(3.5)
Условия C1, C2 можно интерпретировать следующим образом:
C1: Сложная система представляет собой набор подсистем, которые в состоянии выполнить задание T.
С2: Действия всех подсистем, входящих в состав сложной системы, должны координироваться в процессе выполнения задания. Под координацией здесь мы понимаем обмен данными (или командами) между подсистемами.
Если одна из подсистем si S является роботом, то такую сложную систему будем называть многокомпонентной робототехнической системой (МРС).
3.3 Выбор способа организации управления робототехнической системой
Обсудим сначала следующий вопрос: «Что мы понимаем под управлением МРС?» В действительности, каждая из подсистем Si, входящая в состав МРС, обладает собственной системой управления, способной обеспечить выполнение всех функций, свойственных этой подсистеме. Однако, возникающая для рассматриваемого класса систем необходимость взаимодействовать в процессе исполнения задания, ставит задачу формирования для подсистемы именно того задания, выполнение которого диктуется сложившейся обстановкой. Таким образом, задача управления распределенными системами состоит в планировании действий подсистем до начала исполнения и последующей координации в процессе исполнения.
Организация процедуры планирования и координации является чрезвычайно важной: она оказывает существенное влияние на используемые методы управления.
3.3.1 Централизованное управление
Этот метод организации предполагает наличие центральной системы управления, которая планирует действия всех подсистем и затем координирует их взаимодействие в процессе исполнения (рис. 3.2) в соответствии с предварительно разработанным планом. Центральная система управления (ЦСУ) передает подсистеме задание, исполнение которого не требует какой-либо координации между подсистемами. Результат исполнения возвращается в ЦСУ. В зависимости от присланного результата ЦСУ посылает подсистеме следующее задание, и далее процесс повторяется. Заметим, что физически ЦСУ может быть реализована либо как отдельное устройство, либо на базе системы управления одной из компонент МРС.
3.3.2 Распределенное управление
При таком способе организации управления отсутствует центральная система, и процессы планирования заданий и координация в процессе исполнения реализуются путем обмена сообщениями между подсистемами (рис. 3.3). На этапе планирования осуществляется переговорный процесс, результатом которого является согласованный план исполнения задания. Реализация этого плана происходит на этапе исполнения и состоит в выполнении подзаданий и обмене результатами их исполнения. Строго говоря, при такой организации нельзя говорить об управлении распределенной системой, поскольку, в отличие от централизованной организации, отсутствует явно выраженный носитель управления, обеспечивающий требуемое поведение системы: все подсистемы являются равноправными как на этапе планирования, так на этапе исполнения.
Таким образом, централизованное управление реализует иерархический способ организации системы, состоящий в частности в том, что управление является многоуровневым с явным подчинением нижних уровней (локальных систем управления) верхним (центральной системе управления). Все обмены сообщениями между подсистемами происходит не напрямую, а через верхний уровень. Распределенное управление реализует гетерархический способ организации, когда все компоненты системы равноправны и процесс планирования осуществляется параллельно всеми подсистемами.
3.3.3 Выбор архитектуры подсистем интеллектуального робота
Архитектура каждой компоненты МРС обусловлена тем набором функций, которые она должна выполнять, а именно:
F1 - иметь возможность обмениваться данными либо с центральной системой управления (для централизованного способа управления), либо с локальными подсистемами (для распределенного способа).
F2 - обеспечивать процесс принятия решения или планирования (для децентрализованного управления).
F3 - обеспечить координацию с другими подсистемами на этапе исполнения спланированного задания,
F4 - исполнять соответствующие подзадания, сформированные на этапе планирования.
Функция F1 является, вообще говоря, чисто технической и ее реализация состоит в поддержке соответствующих сетевых протоколов. Обеспечение функции F2 состоит в требовании иметь в составе подсистемы базу знаний для принятия решений. Функция F3 требует наличия механизма, приводящего в действие исполнение системой соответствующих подзаданий по сигналам, поступающим от других подсистем. При этом эти сигналы не должны требовать перепланирования задания в целом (например, неуспех при выполнении подзадания одной из подсистем). Выполнение функции F4 обеспечивается нижним уровнем локальной системы управления и аппаратными средствами подсистем.
Заметим, что если локальная система является сложной в смысле введенного в п. 2 определения, то процесс исполнения подзадания также может включать в себя этапы планирования и координации исполнения. Например, для мобильного робота, включающего в свой состав шасси, манипулятор и систему технического зрения, подзадание в форме «переместить объект А в позицию В» может быть распланировано следующим образом: t1 - манипулятор, убрать; t2 - TV, найти А; t3 - манипулятор, сменить схват; t4 - манипулятор, взять А; t5 - манипулятор, положить в В; с соответствующей координацией между подсистемами «манипулятор» и «TV» в процессе исполнения.
Таким образом, подсистема должна включать по крайней мере следующие 4 функционально различные компоненты (рис. 3.4):
- коммуникатор (F1);
- планировщик (F2);
- координатор (F3);
- исполнитель (F4).
4. Метод координации и планирования
4.1 Координация исполнения
Воспользуемся подходом, состоящим в представлении этого уровня системы управления как сети специальным образом построенных конечных автоматов.
4.1.1 Сетевой автомат
Назовем сетевым автоматом NA с p входами и q выходами следующий кортеж:
NA = <I, O, U, X, Z, f, h> (4.1)
где I = {i1, i2,…, ip} - множество входов;
O = {o1, o2,…, oq} - множество выходов;
U = {u1, u2,…, um} - входной алфавит;
X = {x1, x2,…, xn} - множество состояний;
Z = {z1, z2,…, zk} - выходной алфавит;
f: XVX - одношаговая переходная функция, где VUI;
h: XVW - выходная функция, где WZO.
Элементы множеств V и W будем называть обобщенными входными и выходными алфавитами соответственно.
Введем дополнительно специальный символ , который является элементом и входного и выходного алфавитов. Этот символ мы будем интерпретировать как пустой символ, который всегда присутствует на выделенном входе автомата, так что если в описании перехода из некоторого состояния присутствует входной символ , тогда осуществляется соответствующий переход. Появление символа в выходном канале означает, что на выход ничего не поступает. Здесь надо заметить, что полученный в результате автомат не является автоматом Мили, поскольку он не сохраняет длину отображения.
Далее при изображении графа сетевого автомата мы будем использовать следующую нотацию: через i.u будем обозначать символ входного алфавита uU, пришедший по входному каналу i I; через z.o будем обозначать символ выходного алфавита zZ, поступивший в выходной канал oO.
Введем теперь понятие сети автоматов как набора автоматов, объединенных своими входами и выходами и взаимодействующих путем передачи / приема символов своих выходных / входных алфавитов.
Назовем сетью автоматов L связный мультиграф:
L = (E, C), (4.2)
где E = {e1, e2,…, en} - множество вершин графа;
C = {c1, c2,…, cm} - множество направленных дуг, ci = (ej, ek).
Вершина графа интерпретируется как сетевой автомат, а дуга - как канал связи между автоматами, используемый для обмена элементами входных / выходных алфавитов.
Работа сети заключается в параллельном функционировании всех составляющих ее автоматов, поведение каждого из которых, в свою очередь, определяется его текущим состоянием, а также состоянием входных каналов.
Пусть теперь L = (E, C) - сеть автоматов, и пусть распределенная система состоит из подсистем, каждая из которых описывается конечным автоматом, так что M = {Mi} - множество моделей подсистем.
Тогда, если M E, то
Lc = {Ec, Cc}, (4.3)
где Ec = E \ M, будем называть управляющей структурой для распределенной системы, представленной моделями {Mi}.
Ясно, что будучи соединенной с реальными подсистемами, управляющая структура обеспечит некоторое поведение подсистем, зависящее от топологии управляющей структуры и атрибутов сетевых автоматов, входящих в ее состав.
4.1.2 Управляющая структура как средство координации
Рассмотрим простой пример. Пусть два робота Rb1 и Rb2 перекладывают детали из накопителя S на два конвейера С1 и С2 (рис. 4.1).
В соответствии с изложенным выше, роботы Rb1, Rb2 будем описывать как конечные автоматы
Rbi = (Ii, Oi, Ui, Xi, Zi, fi, hi), i=1,2 (4.4)
со следующими атрибутами:
Ii ={i0}; Oi ={i0}; Ui ={g}; xi ={0, 1, 2}; Zi ={y, Y}, i = 1,2 (4.5)
Функции fi и hi задаются диаграммой, представленной на рис. 4.2. Каждый из роботов Rbi воспринимает только одну команду «g», в результате которой он перемещается к накопителю S, захватывает деталь, переносит и устанавливает ее на конвейер Сi. Сигналы «y» и «Y» на выходе робота появляются тогда, когда он освобождает опасную зону и завершает выполнение одного цикла соответственно. Будем строить управляющую структуру в виде трех автоматов, два из которых (Reg1 и Reg2) являются логическими регуляторами роботов, а третий (Res) обеспечивает слежение за ресурсом.
На рис. 4.2 представлена топология управляющей структуры, а также диаграммы всех входящих в ее состав автоматов. Структура функционирует следующим образом. Регулятор каждого робота посылает запрос на занятие опасной зоны автомату-ресурсу. Если зона свободна, то этот запрос удовлетворяется, опасная зона переходит в состояние «занято» и регулятор посылает команду роботу начать транспортную операцию. После того, как робот выйдет из опасной зоны, он информирует об этом регулятор, который в свою очередь переводит опасную зону в состояние «свободно» и ждет окончания выполнения операции. Далее цикл повторяется.
4.1.3 Анализ функционирования планировщика
Приведенный выше способ координации является весьма эффективным средством для построения только централизованных систем управления. Действительно, если нижний уровень управляющей структуры представляет собой по сути дела логические регуляторы и может быть без труда ассоциирован с локальными системами управления, то верхние уровни обмениваются данными со всеми подсистемами, участвующими в выполнении задания, и потому являются фрагментом центральной системы управления.
Естественный способ преодоления этой трудности состоит в формировании одноуровневой управляющей структуры, т.е. такой, у которой число автоматов совпадает с числом подсистем, разрешив этим автоматам обмениваться данными непосредственно между собой, а не с верхним уровнем. Это, с одной стороны, приводит к усложнению довольно простого логического регулятора, а с другой стороны позволяет обойтись без центральной системы управления. На рис. 4.3 показана соответствующая архитектура системы управления (модули, не связанные с координацией, не показаны).
4.2 Планирование исполнения информационно-двигательных действий
Рассмотрим сначала метод планирования задания для централизованной системы. Суть подхода состоит в выполнении двухшаговой процедуры:
Шаг 1. На основе методов искусственного интеллекта найти последовательность подзаданий, выполняемых каждой из подсистем и сформированных в терминах входных алфавитов подсистем.
Шаг 2. Преобразовать эти последовательности в управляющую структуру, которая обеспечит координацию исполнения сформированного задания.
Обсудим более детально эту процедуру. В качестве метода решения задачи планирования будем использовать исчисление предикатов первого порядка. Входная информация, необходимая для решения задачи планирования, состоит из следующих компонент, содержащих описание:
К1 - возможностей каждой из подсистем,
К2 - начального состояния,
К3 - задания,
К4 - универсальных свойств.
Компонента К1 включает набор предложений (правил), отражающих возможности каждой подсистемы изменять состояние внешней среды (перемещение объектов, получение информации об объектах и т.д.). Отличительной особенностью этой компоненты является наличие сколемовской функции, относящейся к одной из подсистем. Множество К2 включает факты, описывающие начальное состояние системы. Компонента К3 представляет собой формулировку задания. Множество К4 описывает универсальные свойства, не зависящие от подсистем, входящих в состав МРС (это множество может быть пусто). Элементы всех множеств представляют собой правильно построенные формулы (ППФ) в исчислении предикатов 1_го порядка.
Задача планирования состоит в получении последовательности операторов, обеспечивающих выполнение цели. При этом для обеспечения максимально возможного распараллеливания процесса исполнения представим множество К1 в виде:
(4.6)
где N - множество подсистем.
Таким образом, каждое подмножество К1i содержит только ППФ, отражающие возможности i_ой подсистемы. После осуществления такого разбиения будем строить резолюции rij, и не-цели с элементами К1i настолько долго, насколько это возможно. Если этот процесс невозможно продолжить, оставаясь в К1i (это означает, что на этом этапе исполнения необходимо взаимодействие между подсистемами), строим резолюции с соседними подмножествами. Такой процесс обеспечит (в случае успеха) получение последовательности операторов, относящихся к каждой из подсистем, а также точек координации их взаимодействия. Далее полученные результаты используются для преобразования в управляющую структуру, обеспечивающую исполнение сформированного плана (рис. 4.4).
Подобные документы
Прямая и обратная задача кинематики и позиционирования захвата манипуляционного робота. Разработка алгоритмов и решений, позволяющих организовать процесс нанесения рисунков на поверхность изделия при помощи робота-манипулятора FS03N фирмы Kawasaki.
дипломная работа [4,1 M], добавлен 17.09.2013Назначение, технические характеристики промышленного робота МП20. Режимы работы робота и кинематическая схема. Приводные электродвигатели. Элементы электроавтоматики. Алгоритм управления следящим цифроаналоговым приводом. Интерфейс станочной магистрали.
курсовая работа [1,7 M], добавлен 15.04.2013Основные понятия компьютерного моделирования. Функциональная схема робота. Системы компьютерной математики. Исследование поведения одного звена робота с использованием системы MathCAD. Влияние значений изменяемого параметра на амплитуду угла поворота.
курсовая работа [1,2 M], добавлен 26.03.2013Использование в микропроцессорных системах цифрового способа представления информации. Помехоустойчивость устройств. Принципиальная схема на микроконтроллере для управления роботом. Устройство и принцип действия робота. Области действия фотодатчиков.
курсовая работа [693,7 K], добавлен 31.01.2015Знайомство з інтерфейсом ОС Linux, робота з довідковою системою Linux. Робота з утилітами командного рядка. Символічні посилання та архівація даних. Пошук файлів за критеріями. Робота з програмою Midnight Commander. Використання офісних додатків.
методичка [396,5 K], добавлен 17.05.2011Концепция систем поддержки принятия решений. Диапазон применения Analytica 2.0. Программное обеспечение количественного моделирования. Графический интерфейс для разработки модели. Основные способы моделирования. Диаграмма влияния и дерево решений.
контрольная работа [1,1 M], добавлен 08.09.2011Техническое задание для разработки программного обеспечения "Больница". Обоснования для проведения разработки. Цель, назначение подсистемы. Требования ко всем видам обеспечения программы. Общесистемное программное обеспечение. Применение языка Delphi 6.0.
курсовая работа [832,9 K], добавлен 18.01.2010Составление программы для построения траектории движения захвата манипулятора робота: запись системы линейных алгебраических уравнений, получение коэффициентов. Анимация движения манипулятора. Схема направления движения точки соединения звеньев робота.
лабораторная работа [274,4 K], добавлен 01.12.2013Середовище програмування Visual Studio 2010. Функції стандартного введення-виведення. Робота з побітовими операціями. Робота з функцією заміни у рядку символів. Робота з масивами. Тестування алгоритму роботи програми. Представлення двовимірного масиву.
курсовая работа [652,2 K], добавлен 15.01.2014Обзор схемы конструкции автоматизированного мобильного робота. Выбор компонентов конструкции. Общая классификация роботов; виды двигателей. Выбор типа микроконтроллера. Осуществление программирования на основе расчётов по математической модели робота.
курсовая работа [1,2 M], добавлен 20.05.2015
