автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Управление интеллектуальными манипуляционными роботами в среде с неизвестными препятствиями

РГБ ОД

- 8 (КОИ 1998

На правах рукописи

ЛОПАТИН ПАВЕЛ КОНСТАНТИНОВИЧ

УПРАВЛЕНИЕ ИНТЕЛЛЕКТУАЛЬНЫМИ МАНИПУЛЯЦИОННЫМИ РОКОТАМИ В СРЕДЕ С НЕИЗВЕСТНЫМИ ПРЕПЯТСТВИЯМИ

05.13.01 - Управление в технических системах

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск 1998

Работа выполнена в Сибирской аэрокосмической академии им. акад. М.Ф.Рсшетнева

Научный руководитель: доктор технических наук,

профессор Ильин В. А.

Официальные оппоненты: доктор технических наук Лаптенок В.Д.,

кандидат технических наук, доцент Масальский Г.Б.

Ведущая организация: Сибирский научно-исследовательский институт технологии

машиностроения, г.Красноярск

Защита состоится июня 1998 года в час. на заседании диссертационного

совета К 064.46.01 в Сибирской аэрокосмической академии по адресу: 660014, Красноярск, проспект имени газеты "Красноярский рабочий", 31.

С диссертацией можно ознакомиться в библиотеке Сибирской аэрокосмической академии.

Ваш отзыв, заверенный печатью, просьба выслать по адресу:

660014, Красноярск, а/я 486, ученому секретарю диссертационного Совета Ильину В.А.

Автореферат разослан 1998 г.

Ученый секретарь диссертационного совета

д.т.н., профессор Ильин В. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В литература,. по робототехнике рассматриваются следующие основные постановки задач планирования траекторий и управления роботами:

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

Можно указать, следующие основные методы управления манипулятором при исполнении спланированной траектории:

Управление с помощью оптимального регулятора Методика "обратных задач" Децентрализованное управление

Планирование,траекторий и управление роботами в среде с известными препятствиями. .,м„-.-

Основным 1 методом при решении этой задачи является графовый подход. Имеются работы, гарантирующие нахождение траектории, если таковая существует. Даны способы математического описания препятствий в декартовом пространстве и в пространстве обобщенных координат.

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

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

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

На основе информации, полученной от датчиков, робот осуществляет движение по приведенным в диссертации алгоритмам. Обсуждается работоспособность этих алгоритмов.

. Цель настоящей диссертации состоит в следующем.

1. Разработка вопросов теории управления роботами в неизвестной среде.

2.Разработка численных алгоритмов управления манипуляторами в неизвестной среде.

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

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

Научная новизна диссертационной работы состоит в следующем:

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

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

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

На защиту автором выносятся следующие основные положения:

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

2. Итеративные алгоритмы планирования траекторий и управления манипуляционными роботами в условиях неполной информации о внешней среде.

' 3. Результаты исследований разработанного программного обеспечения.

Реализация полученных результатов. Разработанное при работе над диссертацией алгоритмическое и программное обеспечение используется в учебном процессе кафедры информатики и вычислительной техники и кафедры конструирования машин и электронного машиностроения при обучении студентов по курсу "Теория робототехнических систем" в Сибирской аэрокосмической академии. Основные результаты научно-технической работы включены в научно-

технические отчеты по научно-исследовательским работам по темам, выполнявшимся в Сибирской аэрокосмической академии и НИИ систем управления, волновых процессов и технологий по заказ-нарядам Министерства О ПО" РФ "Алгоритмическое и программное обеспечение интеллектуальных манипуляционных роботов в условиях неопределенности" и "Интеллектуальные системы управления манипуляционными роботами в неизвестных экстремальных средах".

Апробация работы и публикации. В полном объеме результаты работы обсуждались на межрегиональных конференциях "Проблемы информатизации региона", проходивших в Красноярске в 1994, 1995 и 1996 годах; на международной конференции "Динамика систем, механизмов и машин" (Омск, ноябрь 1995); на IX международном симпозиуме по непараметрическим методам в кибернетике и информатике "Непараметрика'97" (Красноярск, октябрь 1997); на научных семинарах кафедры ИВТ CAA и кафедры технологии машиностроения Тафтского университета (США).

По теме диссертации опубликовано 8 научных работ, список которых приводится в конце автореферата.

Структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и текстов трех программных пакетов, содержащихся в отдельном Приложении. Общий объем работы - 121 страница и 230 страниц текстов программ, список литературы - 152 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В параграфе 1.1 рассматривается задача описания движения манипулятора.

Манипулятор (робот) будем представлять в виде механической руки, или, другими словами, в виде совокупности твердых тел, связанных друг с другом, но способных двигаться друг относительно друга (рис. 1).

Предполагается, что звенья манипулятора связаны в кинематические пары 5-го класса (практически все манипуляторы, используемые в промышленности, состоят из звеньев, объединенных в кинематические пары 5-го класса). Если пара вращательная, то движение ¡-го звена относительно (М)-го можно описал, некоторой функцией ф,(0, рассказывающей о том, как изменяется угол (р, между 1-м и (М)-м звеньями. Если пара поступательная, то движение 1-го звена относительно (Н)-го можно описать некоторой функцией &(1), рассказывающей о том, как изменяется смещение $ между ¡-м и (¡-))-м звеньями.

Можно ввести обозначение

, V _ | (р (0,е с ли п аравращатетьн ая ЧкО - 1 1

[¡5,(0>е с ли п ара п о с тутга льн а

Совокупность функций (¡=0,1,...,п-1) объединяется в вектор-функцию

'КО = ЫО, 4.(1), ... , Я-нО))т

Вектор описывает движение всех звеньев манипулятора друг относительно друга, то есть описывает движение всего манипулятора.

В параграфе 1.2. рассматриваются способы исполнения спланированной траектории.

Сначала составляется вектор-функция q(t), адекватно описывающая желаемое движение. Затем дается уравнение динамики манипулятора, по которому можно вычислить силы и(0, которые надо приложить к манипулятору, чтобы он исполнил требуемую траекторию. В общем виде уравнение можно представить так:

<0=г,(ч(0) (1)

Силы и(0 прикладывают к звеньям двигатели (точнее - привод). Чтобы привод приложил к звеньям требуемые силы и(0, на привод надо подать токи ¡(0 (электро-, гидро- или пневмотокн, в зависимости от типа привода), вычисляемые согласно формуле, в общем виде которую можно представить так:

1(0=Ь(и(0) (2)

Получаем следующую схему:

Компьютер:

1. Определяет требуемую траекторию

2.По формуле (1) вычисляет и(0

3.Па формуле (2) вычисляет ¡(0

токи

в цифровой

ад

реальные токи

Преобразователь ш Привод и(1) Звенья

4(1)

Рис. 2

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

Задача движения манипулятора в среде с неизвестными препятствиями формулируется следующим образом: даны начальная конфигурация я0 и целевая

конфигурация qт, в рабочей области могут располагаться препятствия, но перед началом движения информация о наличии препятствий, их количестве, расположении и форме отстутствует. Требуется сделать так, чтобы манипулятор передвинулся из (|':| в qт.

Делаются следующие допущения:

1. Положение, форма и размеры препятствий неизменны в течение всего времени движения манипулятора.

2. Заранее известно, что цель достижима (то есть известно, что в пространстве обобщенных координат можно найти линию, соединяющую (¡° и чт и не налегающую ни на какое присутствующее в рабочей зоне препятствие).

3. Обобщенные координаты должны удовлетворять ограничениям

а< < Ч(г) ^ а2, (3)

где

а' - вектор нижних ограничений на обобщенные координаты

а2 - вектор верхних ограничений На обобщенные координаты •4. Манипулятор снабжен сенсорной системой, позволяющей определять, налегает ли манипулятор в текущей конфигурации на препятствия или нет, а также определять, имеются ли препятствия в небольшой окрестности текущей конфигурации. Устройство сенсорной системы в данной работе не рассматривается.

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

.Метод управления манипуляторами в среде с неизвестными препятствиями заключается в следующем:

1. Пусть манипулятор находится в Манипулятор с помощью своей сенсорной системы исследует небольшую г-окрестность в пространстве конфигураций около (рис. 3). Конфигурации, находящиеся в этой окрестности, образуют множество У(я°). Конфигурации, налегающие на препятствия, заносятся в множество запрещенных конфигураций Конфигурации, не налегающие на

препятствия, заносятся в множество разрешенных конфигураций Манипулятор генерирует в пространстве обобщенных координат линию qт), соединяющую q0 с qт, причем эта линия должна быть такой, что каждая точка этой линии удовлетворяет неравенствам (3) и не принадлежит множеству <2(я°).

Рис. 3

Манипулятор начинает движение по этой линии и переходит в точку д'еУ^0). Следующий шаг опишем для общего случая, обозначив конфигурацию, в которой находится робот, через qn (п=1, 2, ...у

2. Находясь в точке ч"еУ(цп>). манипулятор исследует г-окрестность около конфигурации q" и образует множества <3(ц") и 74ц"). При этом возможны

две ситуации:

а) Линия, по которой движется манипулятор, не пересекается с множеством С?(ЧП). В этом случае манипулятор движется и дальше по этой линии;

б) Линия, по которой движется манипулятор, пересекается с множеством (рис. 4)

Рис. 4

Тогда манипулятор передвигается по линии в ту точку следующая за которой уже принадлежит множеству Перейдя в точку я', манипулятор генерирует

новую линию Ь(я!, я7), не пересекающую множеств ¡=0, 1.....пи собирается

—........двигаться уже по новой_лшши . _____________________

3. Манипулятор по намеченной линии переходит в точку чп+1еУ(ц"), а алгоритм переходит на п.2, при этом индекс "п+1" заменяется на "п". На основе этого алгоритма формулируется следующая Теорема. Если манипулятор будет двигаться по вышеописанному алгоритму, то он достигнет цели за конечное число шагов.

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

Пусть манипулятор оказался в точке ц5, в которой надо менять маршрут. Манипулятор может сразу сгенерировать новый маршрут, а может перейти в некоторую конфигурацию по какому-нибудь алгоритму. Оказавшись в

манипулятор вновь может либо сгенерировать новый маршрут, либо перейти в некоторую конфигурацию Число таких переходов в может

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

конечное число шагов. Данное утверждение сформулировано как следствие из теоремы.

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

Шаг 1. Пусть пройдена траектория .....ц™. Если прямолинейный отрезок

соединяющий я" и не проходит через множество СКя"), то алгоритм переходит к шагу 2, если проходит, то к шагу 3.

Шаг 2. Если отрезок не пересекает множеств (3(я')> 1—0, 1, ... , п-1, то робот делает шаг по отрезку в сторону цели, и алгоритм переходит к шагу 1 с

увеличением п. Если отрезок пересекает указанные множества, то алгоритм переходит к шагу 3.

Шаг 3. Робот выбирает точку qnH по алгоритму отталкивания от предыстории (пояснения см. ниже). После выбора qn+1 агоритм переходит к шагу 1 с увеличением п.

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

В Шаге 3 имеется ссылка на алгоритм отталкивания от предыстории (АОП). АОП используется для облегчения выхода из тупика, возникшего в г-окрестности текущей конфигурации.

АОП базируется на следующих эвристических соображениях. Пусть мы имеем множество точек yi (¡=0, 1, ... , п-1), в которых робот сменил маршрут (другими словами, когда робот находился в этих точках, требовался переход к шагу 3). Следовательно, около этих точек были обнаружены препятствия. Сейчас робот также находится в точке (обозначим ее qn), в которой надо менять маршрут и искать какую-то ql,+1eZ(q"). Целесообразно выбрать такую qn+l, которая бы лежала как можно дальше от возможно большего числа точек у' (то есть от точек, около которых были обнаружены препятствия) и которая бы лежала как можно ближе к qT. Другими словами, АОП реализует желание как можно дальше уйти от уже обнаруженных препятствий и как можно сильнее приблизиться к целевой конфигурации.

На рис.5 представлена блок-схема описанного выше алгоритма.

Алгоритм формирования предварительного маршрута

Предварительный маршрут представляет собой конечное множество точек, принадлежащих отрезку прямой линии в пространстве конфигураций. Отрезок исходит из текущей конфигурации qn и приходит в целевую конфигурацию qT. Точки в маршруте идут через определенный интервал delta. Интервал delta рассчитывается следующим образом:

Пусть мы имеем две соседние точки q1 = (qi1, 42', ... , qa')T и q11 = (qin, q2n, ... , q„ir)T в маршруте робота, тогда для каждой обобщенной координаты i (i=l,...,n) будет

q," = q,i + delta, (4)

где deltai - величина дискрета по i-той обобщенной координате.

delta! вычисляется по следующему принципу. Имеем qU - наименьшую допустимую величину для i-той обобщенной координаты и имеем qH, -наибольшую допустимую величину для i-той обобщенной координаты. Пусть number__of_steps - максимальное число шагов, которое может быть в маршруте робота. Тогда

delta; = ji qH'"qb-V (5)

у V number_ of_ steps-1J

Начало

Маршрут формируется следующим образом. Первой точкой маршрута будет текущая конфигурация qn. Следующая точка маршрута образуется по следующему принципу. Если

< I delta, I

q,n-H = qn

в противном случае qin+l = q," + deltai

(6)

(7),

(8)

1=1.....п

Затем переходим к формированию следующей точки маршрута. Процесс прекращается на той конфигурации для каждой координаты 1 которой выполнилось условие (6). Последней точкой маршрута делаем конфигурацию

При отработке маршрута манипулятор перемещается из одной точки маршрута в следующую. Пусть манипулятор находится в конфигурации q0. Вычислим расстояние между qin и для каждого 1 (¡=1.....п):

tripjengthi

(9)

Если для каждого 1

|1пр_1еп§1Ь(| < |с1е11а,|, то считается, что цель достигнута.

Алгоритм формирования множества допустимых конфигураций

Пусть робот занимает конфигурацию 4 = q2, ... , qn). Множество конфигураций, находящихся в окрестности текущей образуется следующим образом. К каждой компоненте q¡ вектора 4 прибавляется (Ая,)*с, где с может быть равно -1, 0 или I. В результате надо образовать множество всевозможных конфигураций вида:

Ч'=Й>+(-1)*ДЯ1,Я2.....q„),

Чг = (Чь I ... ^п),

= + (-1)* Лч,, Ч2 + 1*ДЧ,, ... , + (-1)* Дqa) и т.д. Задача может быть разбита на следующие этапы:

а) Составляем таблицу, в строках которой будут комбинации чисел -I, 0 и 1. Число столбцов в этой таблице будет равно числу компонент вектора а число строк.будет равно числу конфигураций, образованных около текущей.

i \ > 1 2 3 п

1 -I -1 -1 -1

2 0 -1 -1 -1

3 1 -1 -1 -1

4 -1 0 -1 -1

m 1 1 1 1

ТАБЛИЦА 1

б) Для каждой строки таблицы выполняем следующую операцию: число, стоящее в ]'-том столбце (¡=1,...,п), умножаем на с1еИа).

в) Каждую строку таблицы складываем с вектором q.

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

Число строк в таблице 1 равно Зп-1, где п-число степеней свободы манипулятора.

Опишем процедуру заполнены таблицы 1. Таблицу 1 можно представлять как двумерный массив TT[i][j], где i-номер строки, j-номер столбца. В элемент ТТИО] надо вписать либо -1, либо 0, либо 1. Введем в рассмотрение массив muí, у которого

mul[0]=-l, mul[l]=0, mul[2]=l.

Заполнение элементов массива ТТ будет производиться операцией присваивания:

TT[i]tj]=mul[k] (Ю)

-j=0...(n-l), i=0...3-4, k-0...2.

Выведена формула k=í(ij)i по которой, исходя из заданных i и j, вычисляется к. а затем осуществляется операция присваивания (10):

k=4(i/3J)-[U(i/3i+i)*3] (10

Итак, получена возможность, зная i и j, вычислять к, а по к определять, какое число следует подставить в TT[i]|j]. Затем каждый элемент в столбце j следует умножить на deltaj.

Заполнив таблицу 1, из нее следует вычеркнуть строку, в которой стоят только нули.

После этого к каждой строке таблицы 1 прибавляем текущую конфигурацию q = (q1, q2, ... , q"). Если в текущей строке i хотя бы для одного j не выполняется неравенство

qL¡ < TT[i][j] < qH¡ (12)

где TT[i][j] - элемент, стоящий на пересечении i-той строки и j-того столбца; qL¡ - нижнее допустимое значение обобщенной координаты; ■ qH¡ - верхнее допустимое значение обобщенной координаты; то такая строка исключается из таблицы.

В итоге мы получим таблицу, содержащую конфигурации, находящиеся в окрестности текущей, то есть содержащую множество Y(q").

Алгоритм формирования множества допустимых конфигураций и множества запрещенных конфигураций

Множества Z(q") и Q(q") образуются следующим образом. Из множества Y(q") поочередно извлекаются все конфигурации и каждая конфигурация проверяется на предмет того, налегает ли она препятствия или нет. Если хотя бы одна точка манипулятора в данной конфигурации принадлежит внутренней области препятствия, то считается, что и вся конфигурация налегает на препятствия. Препятствия аппроксимируются параллелепипедами, с каждым из которых связана своя система координат. Дана формула, преобразующая координаты точки манипулятора из системы, связанной со звеном манипулятора в систему, связанную с препятствием. Конфигурация, налегающая на препятствия, заносится в множество запрещенных конфигураций Q(q"). Конфигурация, не налегающая на препятствия, заносится в множество разрешенных конфигураций Z(q").

Алгоритм проверки пересечения предварительного маршрута с множествами запрещенных конфигураций

Проверка того, не пересекается ли маршрут с множествами Q(q'), i=0,l,...,n, происходит следующим образом. Пусть q5 - некоторая конфигурация из маршрута, qP - некоторая конфигурация из одного из множеств Q(q'). Для каждой обобщенной координаты вычисляется расстояние между q! и qP :

rasst^ T¡(qsrqp)2 (13)

rflej=l,...,n. n - число обобщенных координат. Если для всех j

rasstj < deltaj (14)

где deltaj - величина дискрета между соседними конфигурациями по j-той обобщенной координате, то считается, что конфигурация qf недопустимо близко лежит к предварительному маршруту (то есть пересекает его). В этом случае делается вывод о том, что маршрут налегает на недопустимые конфигурации.

Если же неравенство (14) не выполняется хотя бы по одному j, то считается, что пересечения нет и происходит проверка следующей конфигурации маршрута.

Итак, ecjrn хотя бы для одной конфигурации qP из uQ(q'), i=0,l.....n

выполняются все n неравенств (14) для какой бы то ни было конфигурации из предварительного маршрута, делается вывод о том, что предварительный маршрут пересекает запрещенные конфигурации.

Сформулирована и доказана модификация теоремы, приведенной на стр.8.

В третьей главе описывается программный пакет, моделирующий движение манипулятора в среде с неизвестным^ препятствиями на геометрическом уровне. Программный пакет написан на язкке Turbo С++ 1.0. В начале работы пакета пользователь в диалоговом режиме вводит необходимые данные, после чего программа начинает изображать движение манипулятора. Во время работы пакета на экране присутствуют: базовая трехмерная система координат; манипулятор в начальной, текущей и конечной конфигурациях; препятствия. Звенья манипулятора изображаются в виде прямолинейных отрезков. Препятствия изображаются в виде параллелепипедов, произвольно расположенных относительно базовой системы координат. По достижении целевой конфигурации на экран выдается сообщение "Цель достигнута". В приложении даны тексты программ. Программный пакет работает в соответствии с блок-схемой, приведенной на рис.5. .

В четвертой главе излагается теория управления динамическими системами в среде с неизвестными препятствиями.

Динамику систем принято описывать с помощью систем дифференциальных уравнений в нормальной форме:

х — f(x, u. t) (15)

где х=(хП|, ... , х|т>) - вектор состояния, xeXc:Rm, X - ограниченное

множество; u=(u(1).....uW) - вектор управлений, ueUcR*; f=(fi.....fm) - вектор-

функция.

Можно показать, что уравнение динамики манипулятора можно привести к виду (15).

Множество X разбито на два подмножества M и XYM, где M - множество состояний, доступных системе, Х\М - множество состояний, недоступных системе.

Разбиение X на доступные и недоступные состояния системе заранее неизвестно. Задано начальное состояние хо и конечное состояние хт. Цель системы заключается в достижении хт, при условии, что нужно двигаться только по доступным состояниям множества М.

Информация о разбиении X на M и Х\М доставляется по мере движения в окрестносш текущего состояния. Система реализует следующий способ движения.

В ri-окрестнорти точки Хо доставляется информация о доступных и недоступных состояниях в виде двух множеств Zm(xo) и Qm(xo), Zm(xo)<-> Qm(xo)=Y(xo), Y(xg) - шар радиуса ri с центром в хо, Zm(xo)^i Qm(xo)=0. Далее с учетом локального ограничения на состояния x0Qm(xo) ищется управление и соответствующая ему траектория, обеспечивающая перемещение системы из точки хо в некоторую точку xi, находящуюся на расстоянии не более чем го от точки хо, го<ги Величину n назовем радиусом сбора информации, го - радиусом перемещения.

Радиус псремещсни. ПрИ фиксированном Г1 определяется динамикой системы и задается ис-одя из условий существования управлений, обеспечивающих непопадань системы в недоступные состояния и обход недоступных состояний. Напр1Мер, для транспортного робота величина п-го представляет общую длину тормозного пути при максимально возможной скорости движения.

После перемещения систем в точку XI аналогично доставляется информация о доступных и недосту1^ых состояниях в п-окрестности точки XI в виде двух множеств У.мЫ) и Qм(xl). Т«оке выбирается точка х2 из го-окрестности Х| такая, что хг£ Qм(xo) и(2м(х0. Находится управление и траектория, переводящие систему из х> в хг с учетом ограничения: хг С2м(хо) иС2м(хО и т.д.

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

где хо, хь ... , х„ - точки пройденной траектории, являющиеся локальными подцелями в го-окрестностях.

Задача состоит в том, чтобы так уметь зыбирать последовательность

локальных подцелей Xi, Хз.....х„..., кавдая из которых находится в го-окрестности

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

x0Qm^(xo, ..., х„), п=0,1,..., где QMji определяете* в виде (16). Пусть для любого хеМ мы умеем решать задачу нахождения управления u(t) и соответствующей ему траектории x(t) системы (15), таких, что x(to)=xo, x(t) gQ, х(Т)=хт, где Q - некоторое произвольное подмножество из Х\М. Данная задача является задачей с полной информацией.

Приведем структуру D алгоритма выбора подцелей xi, X2.....Хо.....

обеспечивающих достижение Х\М цели хт за конечное число локальных перемещений в условиях пополняющейся информации о множестве XVM запретных состояний.

_ Введем несколько понятий и обозначений. Пусть L„(xn, хт, u„(t)) -множёство точек, составляющих траекторию, имеющую началом х„, оканчивающуюся в окрестности хт, с соответствующим ей управлением un(t), te[t„, Т]. Через Rn(xo,... , хп) обозначим множество вида

R,,(xo,..., xn)—Ln(xa, Хт, Un(t))nQMfl(xo,..., х„) (17)

Через р(х, R„) обозначим расстояние от точки х до множества R,, определяемое следующим образом: р(х, Rn) = р(х, V),

где veRn и все точкн от х до v лежат в Zm(x).

Перемещение ИЗ ТОЧКИ Хц В ТОЧКу Xq+i ПО ЛИНИИ Ln(Xn, Хт, un(t)) назовем допустимым, если выполняются три условия:

3) траектория от Хп к х„+1 целиком лежит во множестве 2м(Хл). Описание структуры алгоритмов.

Шаг 1. Для начальной точки хо находится управление ио(0 и траектория хор) системы (15), удовлетворяющие условиям:

п

QMJI(Xo.....Хп) = Ü QM(XI), К=0,1,—

(16)

1) р(Хп, Xn+l) < Го

2)р(хп+1, Rn) ä Г| - Го

(18) (19)

xo(to)=xo, хо(Т)еОхт Xo(t) е QM,o(xo)

(20) (21)

где 0«т-е - окрестность точки хт. Qm,o(xo)=Qm(xo). Траектории xo(t) соответствует множество точек Lo(xo, Хт, uo(t)).

Переход к шагу 2.

Шаг 2. Пусть пройдена последовательность подцелей хо, xi, ... , xn, п=0,1,... и построена линия Ln(xn, хт, Un(t)), начинающаяся в точке Хп. оканчивающаяся в е-окрестности хт, с соответствующим управлением u„(t), te[t„,T]. Подцель Xn+i выбирается на максимальном расстоянии от х„ в пределах допустимого перемещения и система перемещается в xn+i.

Переход к шагу 3.

Шаг 3. Формируются множества Zm(Xo+i), С2м(хп+0, Rn+i- Если хте2м(х„^), то, переместившись по Ln в окрестность хт, робот заканчивает свое движение. В противном случае проверяется условие:

Если Rn+i(xo, ... , x„ti) = 0 . (22)

то Ln+i(xn+i, хт, u„+i(t)) принимается равной Ln(x„+i, хт, u„(t)), te[t„+i, Т] и алгоритм возвращается к шагу 2 с заменой п на п+1.

Если R0+i(xo,..., Xn+i) 0 (23)

то рассматриваются два случая.

Если р(хп+1, Rn+i) > Г| - го, то Ln-n(x„ri, хт, u0+i(t)) принимается равной L„(x„+i, хт, u„(t)), te[t„+i, Т] и алгоритм возвращается к шагу 2 с заменой п на п+1. Если p(Xn+i, Rn+i) = ri - То, то алгоритм переходит к шагу 4.

Шаг 4. В точке Xn+i находится новое управление un+i(t) и траектория xn+i(t) системы (1), удовлетворяющие условиям:

*Xn+i(tn+i) = Xn+i, x„+i(T) е Охт (24)

Xn+i(t) 2Qm*+i(xo, ... , Xn+i) (25)

Найденной траектории соответствует множество точек L„+i(x„+i, хт, u„+i(t)). составляющих линию в пространстве Rm. Алгоритм переходит к шагу 2 с заменой п на п+1.

Алгоритмы структуры D отличаются друг от друга способом выбора управления на шаге 4.

Теорема. Алгоритмы структуры D обеспечивают попадание системы в е-окресгность целевой точки хт за конечное число локальных перемещений для любого заранее неизвестного М с достижимой точкой цели хт.

Дано доказательство данной теоремы.

Дается метод формирования траектории, соединяющей локальные подцели qn и qn+i При расчете траектории, соединяющей q" и qn+l, будем исходить из следующих условий: находясь в точке q°, манипулятор покоится, то есть обобщенные скорости и ускорения равны 0. По прибытии в qn+1 обобщенные скорости и ускорения манипулятора также должны быть равны 0. Будем считать, что манипулятор находится в конфигурации qn в момент времени t„, а в конфигурацию qn+1 манипулятор прибудет в момент времени t„+i. Итак, нам надо найти вектор-функцию q(t), удовлетворяющую следующим условиям:

1) q(t„) = q"

2) q(t„+i) = qn+l

3)q(t„) = 0

4) q (t„+i) = 0

5) q (tn) = 0

6) q(t„+i) = 0,

• причем Цем считать, что t„=0 и t„+i=l.

Очевидно МТо и каждая компонента вектора q(t) должна удовлетворять условиям 1)-б).

Представимсаждую компоненту вектора q(t) в виде полинома: q,(t) = aot" + iti + a2t2 + ... + a,„tra, i=l.....n

Коэффициент 3ji j=o,...,m неизвестны и подлежат определению. Поскольку q,(t) должна удовле'ь0рЯТЬ шести вышеперечисленным условиям, примем т=5. Тогда получим 6 уравкчий с б неизвестными коэффициентами:

1) a0t" + ait1 + a2t2 аз1з + а44 + ajt5 |t=0 = qn

2) aot" + ait1 + a2t2 + ,lt3 + a44 + a5ts |t=, = q,n+i

3) a, + 2a2t' + 3a3t2 + + 5а5^|,=(, = 0

4) a, + 2a2t' + 3a3t2 + 4itJ + 5a5t4|,=i = 0

5) 2a2+ 6a3t' + 12a4t2 + 2List3|l=0 = о

6) 2a2+ ôast1 + I2a4t2 + гОад^., = 0 Или

, 1) a,, = q,"

2) ao+ ai+ a2+ a3+ a4+ as = q,1

3) ai =0

4) ai + 2a2+ 3a3+ 4a4+ 5a5 = 0

5) 2a: = 0

6) 2a2+ 6a3+ 12a4+ 20a3 = 0 Решая эту систему, получим

1) а„ = q,"

2) а, = 0

3) а2 = О

4) а3 = 10(q,n+1 - qi")

5) a4 = -15(q,"+1-q,")

6) а5 = 6(q,"+1 - qin)

Итак, получаем выражение для i-той компоненты вектора q(t):

q,(t) = q," + 10(q1"+1 - q,")t3 - 15(q,"+1 - q,")t4 + 6(q,"+1 - q,n)t5 (26)

И тогда

q ¡(t) = 30(qi"+I - q,")t2 - 60(qr' - q,")t3 + 30(q,n+1 - q,n)t4 (27)

и

q,(t) - 60(q,n+1 - q,n)t - 180(q,n+l - qin)t2 + 120(q,"" - q,")t3 (28)

i=I.....n.

Силы u(t), необходимые для перемещения манипулятора из q" в qn+l вычисляются в соответствии с известной формулой:

A(q(t), с) q (t) + b(q(t), q (t), с) = u(t) (29)

где

q(t) - вектор обобщенных координат размерностью n х 1 q(t) - вектор обобщенных скоростей размерностью n х 1

q (t) - вектор обобщенных ускорений размерностью n х 1 .с - вектор параметров (длины, массы, радиусы звеньев) A(q(t), с) - матрица инерции размером n х n

b(q(t). q (t), t) - вектор размерностью n x 1

u(t) - вектор обобщенных сил размерностью n х 1

п - число степеней свободы манипулятора

Для каждого момента времени t е [0;1] вычисляются q(t), q(t), q(t),A(q(t),

с), b(q(t), q (t). t). Полученные значения подставляются в (29) и получаем u(t) для каждого момента времени.

Описывается программный пакет, построенный на основе этого алгоритма. Программный пакет написан на языке Turbo С++ 1.0. В приложении даны тексты программ.

В пятой главе описывается программный пакет, управляющий реальным манипулятором "Adept" в присутствии неизвестных препятствий. Программный пакет работает в соответствии с алгоритмом, приведенном на рис.5. Вид манипулятора, обходящего препятствия дан на рис.6. Манипулятор имеет две степени подвижности (первое звено вращается вокруг оси, перпендикулярной плоскости стола, второе звено вращается вокруг оси, параллельной первой оси). Препятствия представляли собой три бумажных параллелепипеда, поставленных друг на друга, грани которых были параллельны координатным плоскостям базовой системы координат. Работа датчиков имитировалась в программе.

Программный пакет написан на роботоориентированном языке высокого уровня V+. Обсуждаются результаты экспериментов. В приложении даны тексты программ.

' ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. На основе численных алгоритмов создано три пакета программ.

Программы допускают использование как для исследования алгоритмов

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

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

Практическое использование программного пакета проведено на манипуляционном роботе "Adept".

Итак, в диссертации решена следующая научно-техническая задача: разработано алгоритмическое и программное обеспечение задач планирования траекторий манипуляторов в условиях неполной информации о внешней среде.

По теме диссертации опубликонаны следующие работы

1. Ильин В.Л., Лопатин П.К. Ал! орнтмическое и программное обеспечение задач планирования траекторий манипуляторов в условиях неопределенности;'/ Проблемы информатизации региона: Труды межрегиональной конференции. КГТУ. Красноярск. 1995. с.142.

2. Ильин В.А., Лопатин П.К. Моделирование движения .манипулятора в среде с неизвестными препятствиями с учетом уравнений динамики// Проблемы информатизации региона: Труды межрегиональной конференции. ЗАО "Диалог-Сибирь". Красноярск. 1997, с. 12.

3. Ильин В.А.. Лопатин П.К. Планирование траекторий и управление динамической системой при неполной информации об ограничениях на состояния/ Информатика и процессы управления: Межвуз. Сборник научных статей. Под ред. А.И.Рубана. Красноярск: КГТУ. S996, с.52-60.

4. Ильин В.А., Лопатин П.К. Управление динамической системой с неполной информацией об ограничениях на состояния// "Динамика систем, механизмов и машин''. Международная научно-техническая конференция. Тезисы докладов. Кн.З. Омск. 1995, с.62-64.

5. Ильин В.А., Лопатин П.К. Управление интеллектуальным манипуляционным роботом в условиях неопределенности// Вторая научно-практическая конференция "Проблемы информатизации города". Сб. тезисов. Красноярск. 1995, с.79-81.

6. Ильин В.А., Лопатин П.К. Управление манипуляционным роботом "Adept" в среде с неизвестными препятствиями// Проблемы информатизации региона: Труды межрегиональной конференции. ЗАО "Диалог-Сибирь". Красноярск. 1997. с.129-130.

7. Ильин В.А., Лопатин П.К. Управление механическими системами при неполной информации о структуре внешних ограничений// Проблемы информатизации региона: Труды межрегиональной конференции. КГТУ. Красноярск. 1995. с. 143145.

8. Лопатин П.К. Алгоритм управления манипуляционным роботом "Adept" в среде с неизвестными препятствиями// IX международный симпозиум по непарамегрическим методам в кибернетике и информатике "Непараметрика'97". Красноярск, (в печати).