Содержание к диссертации
Введение
1 Математические модели колесных роботов 10
1.1 Кинематические схемы колесных роботов. Модельные предложения 12
1.2 Формирование систем координат и геометрия робота 17
1.3 Кинематические характеристики колес 20
1.4 Механические системы с кинематическими ограничениями. Классификация неголономных систем 28
1.5 Кинематическая модель движения платформы колесного робота 32
1.6 Динамическая модель колесного робота 41
1.7 Динамическая модель двухприводного колесного робота 46
1.8 Уравнения Маджи для электромеханических систем с неголономными связями 50
1.9 Электромеханическая модель двухприводного колесного робота 56
2 Анализ математических моделей колесных роботов 61
2.1 Управляемость 61
2.2 Канонические формы и дифференциально плоские системы 64
2.3 Статическая и динамическая линеаризация моделей колесных роботов ..68
2.4 Стабилизация неголономных систем относительно положения равновесия 78
3 Постановка задачи и обобщенная структура системы управления 85
3.1 Описание задач 85
3.2 Описание мобильного робота «Невская стрела» 90
3.3 Сенсорная система 93
3.4 Структурная схема системы управления 99
3.4.1 Анализатор 101
3.4.2 Регулятор 102
4 Алгоритмы ориентации робота на полигоне 104
4.1 Конечные автоматы 105
4.1.1 Решение задачи «Куча» 107
4.1.2 Решение задачи «Маяки-ворота» 112
4.1.3 Решение задачи «Маяки-ворота-восьмерки» 114
4.1.4 Решение задачи «Змейка» 117
4.2 Алгоритм корректировки траектории движения 120
5. Разработка алгоритмов управления 132
5.1 Управление ориентацией робота 134
5.2 Управление продольным перемещением робота 136
Заключение 140
Список использованных источников 142
- Механические системы с кинематическими ограничениями. Классификация неголономных систем
- Статическая и динамическая линеаризация моделей колесных роботов
- Структурная схема системы управления
- Решение задачи «Маяки-ворота-восьмерки»
Введение к работе
Современные мобильные роботы являются сложными программно- техническими комплексами, предназначенными для решения задач различной сложности. Новейшие модификации подобных роботов имеют развитую конструкцию ходовой части, бортовое устройство вычислительной техники, навигационную систему маршрутослежения и средства очувствления. Они характеризуются развитым взаимодействием с внешними объектами, расширенными возможностями приспособления к сложной, неопределенной и подвижной внешней среде, высокой функциональной гибкостью и маневренностью. Эти качества необходимы для выполнения нетривиальных транспортных задач, таких как обход препятствий, проникновение в труднодоступные области рабочего пространства, прецизионное выполнение движений вдоль сложных криволинейных контуров [31]. Построение системы управления движением автономного колесного робота предусматривает разработку алгоритмов моделирования среды, планирования маршрута, контурного управления, обнаружения и обхода статических и подвижных препятствий и т.д.
Колесный робот относится к классу неголономных систем. В таких системах кроме геометрических присутствуют кинематические связи, т.е. связи налагающие ограничения на величины скоростей точек и тел системы и не сводящиеся к геометрическим. В результате для описания положения колесного робота используются переменные, которые не все являются независимыми. Это вызывает основные сложности анализа и синтеза колесных робототехнических систем и затрудняет использование стандартных методов управления. С точки зрения теории управления наличие неголономных связей препятствует использованию стандартных алгоритмов планирования и управления, разработанных, например, для манипуляционных роботов. Задача стабилизации для таких систем является нетривиальной, неголономные системы не могут быть стабилизированы относительно положения равновесия стационарной обратной связью по состоянию [51, 55, 80]. Решение задачи стабилизации колесного робота требует применения других видов обратной связи: нестационарных, кусочно- непрерывных и т.д. Однако, несмотря на это, оказывается возможным использование стационарной обратной связи при решении задачи движения, т. к. она формулируется только по части переменных, описывающих положение робота.
Один из наиболее известных подходов к решению задачи управления движением робота основывается на классических принципах построения следящих систем [39]. Данный метод предполагает включение в систему управления специального задающего устройства (интерполятора), которое генерирует желаемую траекторию в параметрической форме. Однако, точностные требования, предъявляемые к интерполяторам, необходимость перестройки программы эталонного движения при изменении характера движения мобильного робота, а также низкий уровень совместимости с сенсорной информацией определяют основные недостатки данного подхода и ограничивают возможности применения следящих систем управления.
Метод траекторного управления [30, 64, 77] предполагает использование текущих значений отклонений от заранее заданной траектории и исключает необходимость привлечения генераторов эталонной модели. Здесь желаемая траектория движения представляется отрезками гладкой кривой, заданной в неявной форме. Задача контурного управления заключается в стабилизации робота относительно заданной траектории и поддержании требуемой скорости перемещения вдоль нее.
Однако существует ряд транспортных задач, в которых отсутствует или сведена к минимуму априорная информация о существенных для выполнения задачи характеристиках и параметрах окружающей среды, аналитическое описание эталонной траектории движения неизвестно. Задачи такого рода характеризуются неопределенностью цели (целевого условия) [31]. Для решения таких нетривиальных транспортных задач недостающую информацию робот должен получать в ходе выполнения задачи за счет использования различных по исполнению и назначению измерительных устройств, размещенных на нем и составляющих его сенсорную систему. Особая роль в этих условия отводится вычислительной системе робота, на которую возлагается обработка сигналов, поступающих от сенсорной системы, распознавание состояния окружающей среды, определение желаемого поведения робота, вычисление отклонений текущей конфигурации и скоростей робота от желаемых значений и пересчет отклонений в управляющие воздействия. Для решения задач такого рода становится проблематичным использование традиционных методов управления, возникает необходимость использования специальных стратегий управления траекторным движением с использованием принципов адаптации и самообучения.
Таким альтернативным методом решения нетривиальных транспортных задач может служить ситуационный подход. Данный метод основан на обнаружении ситуаций из заранее определенного множества и принятия управленческих решений, ассоциированных с ситуациями. Для описания переходов ситуаций используются дискретно-событийные модели различных видов, в частности, конечные автоматы [42 - 43, 63]. Конечные автоматы в настоящее время все шире применяются в различных областях программирования. Их основными достоинствами являются простота и наглядность. Наиболее разработанным вопросом применения конечных автоматов является синтаксический анализ в различного рода трансляторах алгоритмических языков, также они применяются в области логического управления и в объектно-ориентированном программировании, используются при программировании протоколов, игр и схем программируемой логики. При использовании данного подхода мобильный робот рассматривается как «реактивная» система. Такие системы реагируют на поток событий изменением состояний и выполнением действий при переходах из состояния в состояние или действий в состояниях. Основным источником, "генератором" потоков событий, является окружающая (по отношению к вычислителю, исполняющему программу реактивной системы) среда.
Целью диссертационной работы является разработка методов и алгоритмов управления и ориентации мобильных роботов.
Для достижения поставленной цели были решены следующие задачи.
1. Построение и анализ математических моделей мобильного колесного робота в задачно-ориентированных координатах, исследование их структурных свойств.
2. Анализ оптических схем системы технического зрения мобильного робота.
3. Построение структуры системы управления и ориентации мобильного робота.
4. Синтез и исследование алгоритмов ориентации робота в рабочем пространстве.
5. Синтез и исследование алгоритмов управления движением мобильного робота.
6. Синтез и исследование алгоритма корректировки траектории движения робота.
Методы исследования. Для получения теоретических результатов использовались методы дифференциальной геометрической теории нелинейных систем, нейросетевые технологии, теория графов и конечных автоматов. Для обучения нейронной сети и тестирования полученных результатов был разработан пакет программ с использованием программной среды Matlab.
Новизна научных результатов.
1. Разработана иерархическая структура системы управления движением мобильного робота, которая позволяет решать нетривиальные задачи управления в условиях неопределенности в задании траектории движения.
2. Разработаны алгоритмы ориентации мобильного робота, функционирующего в среде с программируемыми световыми маяками, предложена их реализация с использованием конечно автоматного подхода.
3. Предложен метод синтеза нечеткого нейросетевого алгоритма корректировки траектории движения робота с целью предотвращения столкновения с маяком.
4. предложены алгоритмы управления движением двухприводного мобильного робота при отсутствии явнозаданной траектории движения.
Практическая ценность. Результаты диссертационной работы могут быть использованы для построения систем управления автономными мобильными роботами, функционирующими в условиях неопределенности в задании траектории движения. В ходе работы был разработан пакет прикладных программ, реализующих построенные конечные автоматы, программы для обучения нечеткой нейронной сети и для тестирования полученных результатов.
Практическая значимость представленных алгоритмов управления подтверждается дипломами, полученными на соревнованиях мобильных роботов, проводимых в Москве в Институте механики МГУ им. Ломоносова.
Апробация работы. Работа выполнена на кафедре компьютерных образовательных технологий Санкт-Петербургского государственного университета информационных технологий, механики и оптики в рамках темы «Центр коллективного пользования «Мехатронные и мобильные комплексы» (проект № 226) по направлению «Поддержка интеграции науки и высшей школы», поддержана персональными грантами № М04-3.11К-327 «Разработка алгоритмов управления и ориентации мобильных робототехнических комплексов», № М05-3.11К-314 «Синтез алгоритмов управления движением двухприводного мобильного робота на основе нечеткой логики» и №М06-3.11К-173 «Синтез нечетких алгоритмов управления мобильным роботом» для студентов и аспирантов Конкурсного центра фундаментального естествознания Минобразования РФ. Основные положения диссертации докладывались и обсуждались на I, II, III межвузовских конференциях молодых ученых СПбГУ ИТМО (2004 - 2006 гг.), а также на 11-й Международной студенческой олимпиаде по автоматическому управлению ВОАС 2006 (Санкт-Петербург, 2006 г.).
Публикации работы. Основные результаты диссертации опубликованы в семи печатных работах [1 - 4, 23, 24, 75].
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы, насчитывающего 95 наименований, и приложения. Основная часть работы изложена на 150 страницах машинописного текста. 1 МАТЕМАТИЧЕСКИЕ МОДЕЛИ КОЛЕСНЫХ РОБОТОВ
\ Решение задачи проектирования современной системы управления
колесного робота предполагает наличие адекватной математической модели, которая, с одной стороны, достаточно полно описывает поведение робота в процессе его передвижения в рабочем пространстве, с другой стороны, пригодна для осуществления процедуры синтеза алгоритмов управления. В этом отношении одинаково неприемлемы как примитивные модели, так и излишне сложные, применение которых для синтеза системы связано с непреодолимыми аналитическими сложностями.
Как объект управления колесный робот является многоканальной существенно нелинейной динамической системой. Его математическое описание (модель движения) может быть получено с использованием уравнений Лагранжа или Ньютона-Эйлера, в которых силомоментные воздействия F, М производятся колесной системой. Последняя и определяет основные особенности моделей рассматриваемого класса роботов и их отличия от моделей движения твердого тела. Углы поворотов колес и векторы их линейных скоростей оказываются взаимосвязанными, т.е. подчиняются неголономным ограничениям, что и вызывает основные сложности анализа и синтеза колесных робототехнических систем.
Состояние любой механической системы описывается определенным минимальным набором координат. Введение дополнительных связей между координатами системы уменьшает число ее степеней свободы. Связь, налагающая ограничения на скорости точек и тел системы, то есть устанавливающая между этими скоростями определённые соотношения, называется кинематической. Кинематические связи, не сводящиеся к геометрическим, называются неголономными, а механические системы с такими связями - неголономными системами [32]. Если все связи являются геометрическими (голономными), то есть налагающими ограничения только на положения (или перемещения за время движения) точек и тел системы, но не на величины их скоростей, то это обстоятельство учитывается путем введения координат, непосредственно соответствующих реальному числу степеней свободы. Однако при наличии в уравнениях связей неголономных ограничений такой выбор координат невозможен. Уравнения неголономных связей нельзя использовать для уменьшения числа координат, поэтому при наличии таких связей неизбежно приходится пользоваться координатами, которые не все являются независимыми. Примером неголономной системы является шар, катящийся без проскальзывания по шероховатой плоскости. При этом налагается ограничение не только на положение центра шара (геометрическая связь), но и на скорость точки его касания с плоскостью, которая в любой момент времени должна быть равна нулю (кинематическая связь, не сводящаяся к геометрической). Другой пример дают связи, налагаемые на управляемое движение. Например, если на движение точки налагается условие, что ее скорость в любой момент времени должна быть направлена в другую движущуюся точку, то это условие к какой-нибудь зависимости между координатами не сводится, и связь является неголономной. В робототехнике наиболее широко распространенными примерами неголономных систем являются мобильные роботы [56].
С точки зрения теории управления, наличие неголономных связей препятствует использованию стандартных алгоритмов моделирования, планирования и управления, разработанных, в частности, для манипуляционных роботов [39, 84, 86]. Поэтому проблема планирования и управления движением мобильных колесных роботов по-прежнему остаются актуальной.
Механические системы с кинематическими ограничениями. Классификация неголономных систем
Рассмотрим класс механических систем с кинематическими ограничениями, линейными по скоростям Gj (q\q =0,j = \,...,n-m, (1.22) где q = co\(q],...,qn) - локальные координаты гладкого «-мерного многообразия М, играющего роль конфигурационного пространства, и гладкие локально независимые ковекторные поля (дифференциальные 1- формы), заданные на подмножестве V конфигурационного многообразия М Если левые стороны равенств (1.22) не являются полными производными по времени каких-либо функций координат f\{q),-,fn_m{q), то эти уравнения не могут быть проинтегрированы. Это означает, что их невозможно свести к соотношениям между одними только координатами, которыми можно было бы воспользоваться для выражения положения системы через меньшее число координат в соответствии с реальным числом степеней свободы. В частном случае вопрос об интегрируемости выражения оШ = 0, (1-23) dqt oqk которое эквивалентно условию da(q) = 0. Кроме того, условие (1.25) является достаточным для локального существования функции j{q), удовлетворяющей соотношению (1.24) [77]. Гладкая дифференциальная 1- форма ст( 7) называется замкнутой, если ее внешний дифференциал равен нулю (da=0), и точной (интегрируемой), если существует дифференциальная функция ), для которой df = g [18].
Формально кораспределение Р = span{a,(g),...,an_ni(g)} с Т М задает Пфаффовую систему размерности п-т [89]. Ковектора a\{q),—,G n_m(q) называются генераторами кораспределения Р. Любые т локально независимых дифференциальных 1-форм сn_m+]{q),—,on(q) таких, что
dim(span{P,G„_m+i(q),...,Gn(q)}) = п формируют дополнение кораспределения Р, число т называется коразмерностью Р. есть гладкие векторные поля на конфигурационном многообразии М. Если кораспределение Р локально генерируется точными дифференциальными 1- формами, т.е. P = spm{df](q),...,dfn_m(q)}, то D = kerP инволютивно и, наоборот, если D инволютивно, то кораспределение Р = апп генерируется точными ковекторными полями [77]. Таким образом, инволютивность распределения D означает интегрируемость кораспределения P = annZ). Кораспределение Р называют инволютивным, если инволютивно распределение D.
Для кораспределения P = span{o,(g),...,an_m(g)} сразмерности п-т определим гладкое регулярное распределение D = span{gl(q),...,gm(q)} с ТМ размерности m таким образом, что кораспределение Р служит его аннигилятором Р = апп D (D = кегР), где
Определение. Механическую систему, на траектории которой наложены ограничения (1.22), связывающие координаты системы и ее скорости, называют неголономной, если кораспределение Р = span{o{(q),..., 5n_m(q)} с Т М неинволютивно.
Допустимые траектории q(t)eV системы, т.е. те траектории, которые удовлетворяют в каждый момент времени t кинематическим ограничениям (1.22), удовлетворяют также и дифференциальному уравнению
q = G{q)v, q eV z M, (1.26)
где G = [gx{q),...,gm{q)], v = col(vI,...,vm):/cK- /cR " - т-функция времени. Переменные q, v полностью описывают состояние рассматриваемой механической системы. В принятых предположениях для любого начального состояния q0 = q(t0),tQeI,q0eV существует единственное решение дифференциального уравнения (1.26) q(t) = q(t,t0,q0,v). Уравнения (1.26) является кинематической моделью механической системы с ограничениями (1.22).
Системы вида (1.26) носят название аффинных систем. В общем случае уравнение аффинной системы имеет вид где q = co\(ql,...,qn) - локальные координаты многообразия М и f gi( l) — gm(y) гладкие векторные поля на М. Векторное поле / называется векторным полем неконтролируемого сноса системы, векторные поля gh i - 1, ..., m - векторными полями входов системы, распределение D = span{gi(q),—,gm{q)} - управляемым распределением.
Таким образом, кинематика механической системы с кинематическими ограничениями (1.22) описывается уравнениями (1.27). Рассматриваемая система будет неголономной, если управляемое распределение = кегР неинволютивно.
Принята следующая классификация неголономных систем [22].
Статическая и динамическая линеаризация моделей колесных роботов
Рассмотрим систему, заданную парой if, D), где / е ТМ - гладкое векторное поле на «-мерном гладком многообразии М, DczTM- гладкое распределение на М, dim D = m. При данных условиях существуют такие гладкие векторные поля g,(x),...,gm(x), что D = span{g,(x),...,gm(x)}. Система (f, D) определяет векторное поле на многообразии М и ее траекториями является решение дифференциального уравнения где х = col(x,,...,xn) - локальные координаты гладкого многообразия М\ fig\(x\— gm(x)- гладкие векторные поля на М; veU - w-функция времени. Для того чтобы сформулировать условия достижимости и управляемости, определим для системы (2.1) последовательность гладких распределений А0 с А, с:... с Ада и D0 с Ц с... с Dm следующим образом где Z) = span{g,(x),...,g/n(x)} - управляемое распределение, Df={f + X:Х ЕD). Отметим, что для системы без неконтролируемого сноса (f= 0) справедливо АДх) = А,.(х),/ = 1,2,... для любого xeFv (см. п. 1.4).
Наименьшая подалгебра Ли Со над R векторных полей на М, содержащая Dназывается распределением строгой достижимости Cq=IAQ(Dx) [77]. Распределение C = span{/,C0} называется распределением достижимости.
Известно, что:
-аналитическая система (2.1) обладает свойством строгой достижимости из точки х (множество точек, достижимых из х за достаточно малое время Т О, содержит непустое открытое множество R"), тогда и только тогда, когда rankC0(x) = п\ (2.2)
-аналитическая система (2.1) обладает свойством достижимости из точки х (множество точек, достижимых из х за произвольное время Т О, содержит непустое открытое множество R"), тогда и только тогда, когда rank С(х) = п.
Система (2.1) называется управляемой, если для каждой пары точек x0,x,ei?" существует конечное время 0 Г оо и допустимое управление v:[0,T]- UczRm такие, что соответствующая траектория системы х(/) обладает свойством х(Г,0,х0,У) = х,. Пусть f ED И множество F = {f(x) + gi(x)vi:(vl,...,vm)eU} /=i
симметрично (т.е. из X е F следует -X е F), то для того чтобы система (2.1) была управляемой, достаточно, чтобы она была строго достижимой, т.е. необходимо выполнение условия (2.2). В случае, когда управляемое распределение D является аналитическим, это условие является также и необходимым [77].
Все кинематические модели движения платформы робота, рассмотренные в п. 1.6, являются полностью управляемыми. Для платформы с кинематической схемой, состоящей только из поворотных асимметричных модулей (пример 1.1), управляемость следует из того факта, что управляемое распределение Dx имеет размерность, равную размерности вектора состояния х. В остальных случаях (примеры 1.2 - 1.5) управляемость является прямым следствием полной неголономности кинематических моделей (rankС0(х) = та(х) = п, где п = dim(x)).
Отметим, что линейная система т /=1 представляющая линеаризованную систему (2.1), / = 0 относительно ее решения х = v = 0, полностью управляема только в случае, если т = п. Следовательно, применительно к кинематическим моделям колесных роботов получаем, что линейная аппроксимация кинематической модели движения платформы, оснащенной асимметричными колесными модулями, управляема, в то время как для всех остальных моделей - неуправляема. Таким образом, при переходе от кинематической модели движения платформы, оснащенной не только асимметричными колесными модулями, к ее линейной аппроксимации происходит потеря информации.
Во многих случаях синтез алгоритма управления может быть упрощен за счет предварительной замены координат системы, в результате чего уравнения модели робота принимают более простую каноническую форму. Проблема преобразования нелинейных систем вида (2.1) состоит в том, чтобы найти такую неособую нелинейную замену координат и обратную связь, что в новых координатах трансформированная система принимает вид линейной управляемой системы
ё = Ае + Ви, (2.3)
где А - (пхп) и В- (пхт) - постоянные матрицы и пара (А, В) управляема.
Особый интерес представляет приведение к канонической форме Бруновского [77], которая характеризуется тем, что матрицы А и В имеют следующую блочно-диагональную структуру
Структурная схема системы управления
Использование активных, включаемых по определенной программе маяков, позволяет ставить перед роботом разнообразные задачи, сложность которых может варьироваться в широких пределах от простого наведения на маяк до маневрирования между группой активных маяков, причем в первом случае упражнение считается выполненным при возникновении механического контакта между роботом и маяком, а во втором случае недопустимо любое касание роботом маяка. Кроме того, сложность выполнения маршрута определяется расположением и порядком включения маяков, задающих маршрут, шириной "ворот". Как показал анализ, наиболее простыми в реализации являются упражнения «маяки-ворота» и «куча», несмотря на то, что робот в данном случае робот работает с группой маяков. Наиболее сложные задачи - задачи с маневрированием между группой маяков («восьмерка» и «змейка»), причем сложность увеличивается с увеличением числа активных маков.
Роботы, участвующие в соревнованиях, представляют собой автономную тележку, несущую необходимые датчики и систему управления движением. Это типичные мехатронные устройства, с развитыми сенсорными системами, сложными связями между отдельными их частями, содержательными компьютерными алгоритмами обработки информации и формирования управляющих сигналов.
Организаторы выдвигают некоторые обязательные требования к машинам:
1. Робот с исходной позиции начинает работать автономно по команде "старт" (нажатие кнопки на борту), и до "финиша" никакого вмешательства в его работу не допускается, кроме снятия робота с маршрута аварийным выключением.
2. Для фиксации контакта робота и маяка робот должен быть снабжен "фиксатором" - горизонтальным диском диаметром не более 300 мм, который находится на высоте 1100 мм над полигоном, чтобы обеспечивалось нужное взаимодействие робота с контактным датчиком маяка. Рекомендуется установить "фиксатор" над локатором робота; при таком расположении фиксатор сможет выполнить также функции страховочной устройства, отводящего качающийся подвесной маяк и исключающий его удар о локатор.
3. Робот может иметь любую ходовую часть (кол-во колес, тянущих и рулевых двигателей), любое устройство датчика маяка, системы управления. Вес робота ограничен 50 кг, его ширина не должна превышать 700 мм, его высота над полигоном (без локатора и фиксатора) не должна превышать 900 мм.
Для участия в соревнованиях, проводимых в Институте механики МГУ, в СПбГУ ИТМО был разработан мобильный робот «Невская стрела». На соревнованиях, проходивших в МГУ в 2002-ом году, «Невская стрела» получила два диплома за второе место в упражнениях «Куча» и «Маяки- ворота», а также была отмечена дипломом «За прогресс и стабильно высокие результаты». Копии дипломом представлены в приложении.
Динамическая модель робота без учета влияния электроприводов представлена в разделе 1.7, электромеханическая - в 1.9.
Конструкция робота представлена на рисунке 3.4. Основу корпуса составляет каркас из дюралюминиевых трубок диаметром 10 мм. Снаружи каркас покрыт съемными панелями, что обеспечивает доступ к приводам и электронике. Конструкция рамы имеет клиновидную форму. На расстоянии 650 мм от носовой части робота установлена мачта высотой 1100 мм.
Приводы правого и левого колес включают в себя двигатель постоянного тока с независимым возбуждением и двухступенчатый редуктор с общим передаточным числом равным 11.4. Непосредственно на выходном валу редуктора установлено обрезиненное колесо диаметром 160 мм. На двигателе также установлены датчики пройденного пути, аналогичные датчикам компьютерной мыши. В носовой части машины стоит самоориентирующееся колесо.
Решение задачи «Маяки-ворота-восьмерки»
Данный раздел посвящен разработке алгоритмов ориентации робота в рабочем пространстве - полигоне со специальными световыми маяками. Данная задача относится к верхнему уровню системы управления. В диссертационной работе решение задачи поиска ориентиров движения реализовано программно с помощью аппарата конечных автоматов. Конечный автомат представляет собой хотя и абстрактную, но с функциональной точки зрения довольно точную модель дискретного (цифрового) вычислительного или управляющего процесса [19]. Одной из основных областей применения конечных автоматов является моделирование так называемых реактивных систем. Реактивные или реагирующие - это системы, реагирующие на поток событий изменением состояний и выполнением действий при переходах из состояния в состояние или действий и деятельностей в состояниях [36, 42]. Основным источником, "генератором" потоков событий, является окружающая (по отношению к вычислителю, исполняющему программу реактивной системы) среда. В настоящее время возобновляется интерес к использованию конечных автоматов в программировании, например, в области логического управления и в объектно-ориентированном программировании. Они широко используются при программировании протоколов, игр и схем программируемой логики, при создании компиляторов [38, 41 - 44, 63]. В [44] показано, что автоматы являются не просто одной из математических моделей дискретной математики, а могут применяться при реализации любых программ, обладающих сложным поведением. Достоинством конечных автоматов является возможность декомпозиции сложной задачи на более простые подзадачи. Использование аппарата конечных автоматов обеспечивает в значительной мере формализацию построения и проверки правильности программ, их однотипность, наглядность, структурированность, наблюдаемость и управляемость [42]. Под управляемостью в данном случае понимаются свойства алгоритмов и программ, обеспечивающие упрощение внесения корректных изменений в них [44]. Также необходимо отметить наличие программного обеспечения, позволяющего конструировать конечные автоматы, например, Stateflow - это специальный инструмент Matlab для синтеза, анализа и моделирования сложных активных систем на основе конечных автоматов.
Основным понятием предлагаемой технологии является понятие "внутреннее состояние" (в дальнейшем - "состояние"). Состояния рассматриваются как некоторые абстракции, вводимые в начале процесса алгоритмизации, например, путем однозначного сопоставления каждого из них с одним из физических состояний управляемого объекта, так как обычно функционирование производственных систем проявляется через изменение их состояний. При этом каждое состояние в алгоритме поддерживает объект в соответствующем состоянии, а переход в новое состояние в алгоритме приводит к переходу объекта в новое соответствующее состояние, что и обеспечивает процесс логического управления объектом. Состояния системы играют роль некоторой памяти о ее предыстории.
Определение 4.1 [19] Конечным автоматом называется система S = {U,X,Y,b,X), где U, X, Y - конечные лшожества (алфавиты): U = {их,...,ит) - алфавит входа, X = {х,,..., „} - алфавит состояний, Y =:{у\,...,уг) - алфавит выхода, а 8:Х xU — X, Х:Х xU - Y - функции, определенные на этих множествах: 8 - правило перехода, X - правило выхода. Если, кроме того, в автомате S выделено одно состояние, называемое начальным, то полученный автомат называется инициальным.
Поскольку функции 5 и X определены на конечных множествах, то их удобно задавать таблицами. Обычно две таблицы сводятся в одну таблицу bxX .XxU - XxV, называемую таблицей переходов автомата или просто автоматной таблицей. Другой распространенный и наглядный способ задания автомата - ориентированный мультиграф, называемый графом переходов или диаграммой переходов. Вершины графа соответствуют состояниям; если 8(х;,Uj) = хк и X(xpUj) = у,, то из х,- в хк ведет ребро, на котором написаны uj и
. Для любого графа переходов в каждой вершине х,- выполнены следующие условия, называемые условиями автоматности или корректности [19, 43]:
1. для любой входной буквы Uj имеется ребро, выходящее из х„ на котором написано Uj (условие полноты);
2. любая буква uj встречается только на одном ребре, выходящем из х, (условие непротиворечивости или детерминированности).
Автомат S называется частичным или неполностью определенным, если хотя бы одна из его функций не полностью определена, т.е. для некоторых пар «состояние - вход» значения функций 8 и А, не определены. В автоматной таблице неполная определенность автомата выражается в том, что некоторые ее клетки не заполнены - в них стоят прочерки. В графе частичного автомата в вершинах, где 5 не определена, нарушено условие полноты.
На практике обычно рассматривают два типа автоматов - автомат Мили и Мура. Выход автомата Мура является функцией только текущего состояния в то время, как выход автомата Мили является функцией как текущего состояния, так и начального внешнего воздействия X:XxU- Y. Функцию выходов автомата Мура естественно считать одноаргументной функцией, которую называют функцией отметок (т.к. она каждому состоянию однозначно ставит в соответствие отметку - выход), и обозначают ц. В графе автомата Мура выход пишется не на ребрах, а при вершине.
Похожие диссертации на Разработка алгоритмов управления и ориентации мобильных роботов
