автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.07, диссертация на тему:Концепция инвариантной системы оперативного управления транспортным модулем в ГПС

ГОСУДШЛВШЫЙ КОМИТЕТ РСФСР Ю НАШ И ВЫСШЕЙ ШКОЛЕ.

МОСКОВСКИЙ ОРДИ1А ТРУДОЫГО КРАСНОГО ШАШНИ СТАНКШИСТРУШ1ТАЛШЫЯ ИНСТИТУТ

На правах рукописи ТОКАРЕВ Алексей Леонидович

УДК 658.бг.0Н.б6.01*.3(043.3)

КОЩ&ЦИЯ ИНВАИШПНОЙ СИСТЕМЫ ОПЕРАТИВНОГО У(1РАЬДШЯ ТРАШЮРШНМ МОДУЛЕМ В ПК

Специальность: 05).13.07 - "Автоматизация технологических

процессов н прстэодста" (гаи-иноетро еино)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата техническик наук

икстъ*«-1290

Т^&бота ©ыаожнеиа в Еосковсзгоа ордера ¡Красного

Знаяени ■станкоинструыентальноа мыстаисуто.

¡Научный руководитель

- доктор теэзии«(ес№шс паук, профессор ■СОООНКИН Ё.Л.

Офкциальные оппоненты

Ведущая организация

доктор технических наук, профессор ШВАРЦБУРГ Л.Е.

кандидат технических наук, старший научный сотрудник ШЕЛЬШОВ Б.В.

Экспериментальна научно-исследоьа-тольский институт ыеталлореку\ци* станков (ЭНИМС)

Завдта состоится

1991 г. о

часов

На заседании специализированного совета К 063.4^.04 Московского станкоинструментального института .по адресу: 10147*;, Москва, Вадковский пер., д.За,

С диссертацией можно ознакомиться >в 'библиотеко Московского станкоинструментального института.

Автореферат разослан 11 к$" 199 г.

Ученый секретарь

специализированного совета .К 063.4^.04 кандидат технических наук

СЛ.. ЕГОРОВ

V&AlV» j - I -

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

яхсяергацу.Д |

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

Неотъемлемой часть» ГПС является транспортная система (ТС), которая реализует транспортные потоки в ГПС и связывает ее со смежными производствами. Суммарные затраты на управление ыатериальныии потоками, складирование, переиецение и упаковку объектов материальных потоков ГПС составляют до 40 X обоях производственных затрат, а доля затрат на транспортные подсистемы (модули) с учетом стоимости системы управления достигает 28 X всей стоимости ГЛС.

Система оперативного управления (СУ) транспортного модуля (ТИ), реализованная как правило на базе ЭВИ, зависит от особенностей ГПС: топологии транспортной сети, количества транспортных средств, расположения технологического и вспомогательного оборудования в система. Поэтому проектирование СУ осуществляют сегодня практически заново для каждой создаваемой ГПС. Это сопряжено с большими трудностями и требует творческого груда специалистов высокой квалификации. Причина состоит в отсутствии СУ, независимых от особенностей конкретиык ГПС. Поэтому разработка концепции инвариантной системы оперативного управления транспортным модулем а ГПС является актуальной задачей.

Целью работы является повышение производительности иыхене-рного труда при создании программного обеспечения (ПО) систем управления ТИ.

Метрды исследования. Работа выполнена с ¡применением методов теории логического проектирования операционных смстеи; теории графов; теории тупиков в вычислительных системах;

Кип?2ЦКСпНйГ0 моделирования.

Научная новизна. Основными научными результатами работы являются:

- структура программного обеспечения СУ ТИ;выделенное независимое ядро;

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

- метод преодоления тупиков в ТС на основе теории тупиков Холта, повышающий эффективность работы алгоритма локальной маршрутизации;

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

по быстродействии от размера транспортного графа и количества робокаров в системе;.

- обнаруженное при моделировании явление динамического тупика для алгоритма локальной маршрутизации;

Практическая ценность. В результате проведенных исследований разработана структура программного обеспечения СУ ТМ, позволяющая применять его для широкого класса структурных и аппаратных решений ТЫ; разработаны новые алгоритмы маршрутизации, пригодные для управления в режиме реального времени; на их базе создана система моделирования совместных перемещений робокаров в общей транспортной сети ГПС, которая может использоваться при проектировании и исследовании ТМ.

Реализация работы. Научные результаты исследований внедрены в учебный процесс Мосстанкина и Пензенского политехнического института, а также использованы на опытном полигоне ГПС кафедры ЧПУ СК Мосстанкина.

Апробация работы^ Результаты диссертационной работы докладывались и были одобрены иа заседаниях кафедры "ЧПУ станками и комплексами* в Московском сганкоинструментальном инсги-туте, на всесоюзной_JшцфaдfШцш^—— кая информатика - 69" (г.Москва, 1989), на международном конкурсе молодых научных работников "Роботика - 89" (г. Созополь, Болгария, 1989).

П^ШШШШ! • теме диссертации опубликовано три печатные работы.

Структура и объем раь^ты. Диссертация состоит из введения, четырех глав, обцих выводов, списка литературы и приложений. Работа изложена на 90 страницах машинописного текста, содержит 39 рисунков, 3 таблицы, список литературы иэ 84 наименований.

Глава I. Проблемы управления транспортным модулем в ГПС

Анализ проблемы начинается с рассмотрения транспортной системы как объекта управления. Дана классификация ТС. В большинстве случаев при проектировании ГПС выбирают между робокарами с произвольным направлением маршрута, робокарами с индуктивный управлением, рельсовыми тележками и конвейерами. Наиболее предпочтительными и перспективными средства»* автоматизации транспортных операций а ГПС считают смстеиы робокаров (АНТОИАТЕО ОЯШ) \ШО£В - АСУ). Кавдый робокар имеет бортовую систему управления, которая обеспечивает перемещение и осуществляет информационный обмен с ЭВН более высокого уровня. Применение робокаров в ГПС позволяет обеспечить: независимость от объемо-планировочного реионяя; возможность быстрой перестройки тречспортной трассы; возможность оптимизации грузопотоков; высокую ритмичность работы ГПС в целом; надежность ТС; высокий козЯФВДвнт использования робокаров.

По данным литературных источников в 90 % суцествуочих систем для управления движение»! робокаров используют электромагнитные кабели. Помимо управления движениеи робокара, кабель иояет использоваться & качестве физической среды для передачи информационных сигналов иеаду бортовой СУ робокара и СУ ТИ. Кроме электромагнитный кабелей используют такие оптические системы с отражающей лентой; магнитные полосы; системы автономной навигации; системы маяков; настенную и напольную маркировку Практически у всех типов робокаров имеются устройства предотвращения столкновений; датчики максимальных расстояний; контактные датчик», првдотврацаоаив наезд ш> препятствие; оптические дальномеры; ультразвуковые локаторы; и др.

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

- ч -

¡гью. Двусторонняя связь между робокараии и СУ ТМ отсутствует. Автоноичч? робокары выполняет свои функции автоматически, не нуждаясь в центральной ЭБМ, управляющей движением. Команды на перемещение к пункту назначения робокары получают от оператора с пульта управления. Комплексные системы представляют собой совокупность робокаров, управляемых универсальной ЭВМ и работающих как автононкые системы. Главная ЭВМ выполняет функции диспетчера. Робокары получают управляющие сигналы через систему связи с упраляющей ЭВМ.

Важной для организации управления особенностью ТС является топология транспортной сети. Различает три типа топологий (простая петлевая; лестничная; сложная). Наиболее перспективными считают комплексные ТС со сложной топологией.

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

Существуют три вида организации управления движение« робокаров без столкновений: зонное, (секционное); сенсорное; комбинированное. При зонной управлении все рабочее пространство транспортной сети разбивается на зоны (секции). В зоне может находиться только один робокар. Движение робокара в другую зону разрешается, если она в данный момент времени полностью свободна. Сенсорное управление применяют в ТС с большим числом прямолинейных участков маршрутной сети. Принцип работы заключается в следующем: как только датчики движущегося робокара обнаружат перед собой другой роОокар, они дают команду на останов своему робокару. Если передний робокар вышел из зоны действия датчиков, следующий за ним робокар возобновляет движение. Достоинства сенсорного управления: возможность соблюдения короткой дистанции между робокараии и отсутствие фиксированных пунктов останова, что позволяет существенно увеличить плотность робокаров в заданном участке пространства. Koм6иниp»IШHцoo-yaeaвлetш^ лучшими качествами зонного и сенсорного управления. При этом виде управления снижается вероятность столкновений робокаров, а следовательно выше безопасность и надежность всей транспортной системы.

Важной задачей управления ТС с несколькими робокараии является планирование маршрутов робокаров (маршрутизация)» движущихся одновременно в общей транспортной сети. Решение этой задачи сопряхено с большими трудностями. Время, потраченное одним робокаром на ожидание, когда другой робокеч освободит перегон, может существенно повлиять на общее время пере* зце-ния, а значит, на производительность работы всей транспортной системы. Для рея-гния этой задачи используют понятие конфигурационного пространства (КП). Конструируется КП, которое отображает все степени свободы всех подвижных объектов. Если для управления применяется зонный метод, то под конфигурационным пространством можно понимать граф состояния транспортной системы. Вершина графа будет соответствовать определенному расположении робокаров в зонах, на которые разделено рабочее пространство транспортной сети; дуга графа - разрешенному переходу (совместный перемещениям робокарэв из одной зоны в соседнюо, при которых исключены столкновения робокаров между собой). Задача ¡после этого сводится к поиску кратчайшего пути в графе конфигурационного пространства из текущей вериьлы в целевую. Достоян ст-во алгоритмов, использухнцих понятие конфигурационного пространства, - оптимальное решение задачи. Недостаток: при Эолызои числе робокаров, развитой обслуживаемом технологическое оборудовании и повышенных размерах и сложности транспортной сети размерность графа КП очень велика, что снижает быстродеЯстаяе алгоритмов или делает невозможным их применение.

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

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

(¡аакцияО?,. вшивавший конфликт. Достоинство этого содкеда заклинается в его простота. Недостаток - кеоптимальность решения, т.е. возможны ситуации, когда маршруты объезда получаются очень длинными, но их можно было бы избежать, если заранее знать о возникающем конфликте.

Производительность ТС сильно зависит не только от результатов решения задачи маршрутизации, но и от определения последовательности выполнения трансь >рткых заданий и назначения для них робокаров (планирования перевозок или диспетчеризации). Для решения этой задачи в настоящее время используется три подхода.

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

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

Третий подход использует аппарат продукционных систем, которые являются одним из способов представления знаний и поиска решений в теории искусственного интелекта. Алгоритмы поиска решений в продукционных системах обладают универсальностью по -QwoujeHw*)—к—сшгтстатпгс Системы в момент принятия решения, критерию качества решения, структуре и свойствам элементов системы (топология транспортной сети, количество мест загрузки-разгрузки, количество робокаров, количество грузов, перевозимых робокарами одновременно). По мнению авторов (£иель-

янов В.В., Ясиновский С.И.) применение данного подход позволяет повысить эффективность работы ТС за счет более оптииального решения задачи планирования перевозок по сравнению с первыми двумя подходами.

Проведенный анализ показал, что сегодня разрг'отан ряд алгоритмов решения задачи управления ТМ (алгоритмы маршрутизации; планирования перевозок), однако не исследованы вопросы, связанные с проектированием инвариантных систем управления ТМ ГПС, и не создано такое программное обеспечение, которое позволило бы без существенных ограничений переносить отдельные его фрагменты из одной СУ в другую; из существующих способов и алгоритмов маршрутизации ни один не обладает преимуществами по всем показателям работы (оптимальность решения, быстродействие, потребляемые ресурсы, независимость показателей от топологии транспортной сети) по сравнению с другими.

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

1. Установление внутренних и внешних информационных связей системы управления ТМ ГПС.

2. Разработка структуры ПО системы уравлвния, выделение в яей инвариантного (независимого от реализация ТМ) ядра.

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

Экспериментальная сравнительная оценка разработанных алгоритмов.

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

1. Информация, поступающая от центральной СУ ГПС или модулей (запросы о выполнении транспортныа задания, о состоянии ТМ; транспортные задания; подтверждения о эагруэке/разгруэке).

2. Информация от оператора - человека (запросы о выполнении заданий, о состоянии ТМ; настройка режима работы СУ; команды).

3. Информация от робокаров (запросы на команды (программы) перемещения; сообщения о наступлении аварийной ситуации; отве-

ты на запросы о состоянии робокара (исправен/неисправен; за-гружен/незагружен; перемещается/стоит и др.). Быкодной информационный поток разделяется на три группы и несколько подгрупп в каждой группе..

- Интерфейс с I СУ ГПС

Л

Многопроцессная среда

Интерфейс с оператором

Диспетчер заданий

Л

V

Л V

V

Информационная модель

транспортного модуля

Л

V

Л

V

Л V

Процесс управления движением 1-го роб-ра

Процесс управления движением 2-го роб-ра

Процесс управления движением П-го роб-ра

V

Интерфейс с робокараш

Рис. I. Структура системы управления ТЫ

1. К СУ ГПС или модулям (ответы на запросы о выполнении транспортных заданий, о состоянии ТМ; сообщения об окончании выполнения транспортного задания; требования (загрузить/разгрузить робокар)).

2. К оператору - человеку (ответы на запросы оператора; отображение работы ТМ на дисплее;

3. К робокарам (команды (програимы) на перемещения; запросы о состоянии робокаров; специальные команды (разгрузиться/загрузиться; перейти в состояние заряда аккумуляторных батарей; команды точного перемещения; и др.).

После анализа внешних информационных потоков была определена структура ПО системы управления. Итак, ПО состоит из четырех основных частей (рис. I).

1. Независимое ядро, состоящее из диспетчера заданий и процесса(ов) управления движением робокаров.

2. Интерфейсные блоки (для СУ ГПС;для оператора; для робокара).

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

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

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

Глава Ъ. Принципы управления дискретным движением группы робокаров в общем рабочем пространстве транспотной системы в ГПС

Рабочее пространство ТС при зонном методе представляют в виде совокупности связанных дискретных местоположений (ДМ), часть ДМ является целевыми (местами загрузки/разгрузки). От диспетчера каждому управляющему процессу (УП) поступают команды

< te целевого ДМ>. Это означает, что робокар должен качать движение в указанное целевое ДМ. Задача УП состоит в трансляции команды диспетчера заданий б последовательность команд робока-РУ Двигаться в соседнее ДМ №■...> до достижения данного целевого £ 1. Такая организация работы УП практически полностью исключает столкновения между робокарами.

В работе предложено зри алгоритма маршрутизации для решения выае изложенной задачи. Первый, условно названный алгоритмом локальной маршрутизации, использует таблицу предпочтительных направлений (ТПН).Определение ТПН;

Пусть Р = СРь р2, • • • рЛ - множество ДМ ТС; Р» - ДМ; Р'с Р - подмножество целевых ДМ (мест погрузки/разгрузки). Пусть I i- упорядоченное множество смежных Pt местоположений, а L = {íj, -12, ... in). Тогда ТПН называется отображение Рхр1— >L ((р., pj) —> ¿i(Poi, Р„2, ...Рвп)).

Смысл этой таблицы (рис. 2(6)) заключается в том, что она предписывает робокару, находящемуся в Pt и движущимуся в pj, сначала испытать местоположение paj (проверить свободно оно или занято, если свободно - переместиться в него), затем реа и т.д. Порядок paj на каждом i t определяет стратегию управления ообокараии, чьи больше <_;., тем хуже окончательная траектория.

Для улучшения показателей работы и повышения надежности ТС в алгоритм включен механизм преодоления тупиков, основанный ' на алгоритмах Ходта для случая повторно используемых ресурсов единичной емкости. Первоначально робокараи разрешается выбирать ДМ из ТПН, стоящие на первое месте в упорядоченном множестве £ (<Х = 1) , если выбранное ДМ оказалось занятым, то ожидать его освобождения. При этом неизбежен тупик (рис. 2). Как следует из теории, лалта необходимым и достаточным условием тупика д.чч повторно используемых ресурсов единичной емкости (для нашего случая ДМ) яв~ ется цикл в графе ресурсов (рис. 2(в)), Программно алгоритм распознавания оформляется в виде процедуры, которая запускается УП всякий раз, когда wvio^ee ДМ. выбранное по Tiiii с а = I, оказалось занятым. Процедура распознай;_

—ния ЕТШТрЩает IRLE и список робокаров, попавших в тупик, в случае обнаружения тупика и FASE в случае отсутствия тупика. Задача после этого сводится к выбору в возвращаемом процедурой распознавания списке робокара, кот юиу разрешается выбирать

I 2

4 5

„Л

7 8

1).

_Р а I 2

I 2 3 I 2 3

I 0 О 0 3 п 0

? 0 О 0 б 0

.5 I 4 6 4 6 0

4 3 7 5 5 7 3

S 4 й О ?. ¿1

6 7 0 7

7 6 4 У 8 о

8 7 5 0 5 7 ■л

со

ч.

X

г

Й7

в)..

0).

Рис. 2. Иллюстрация тупика в ТС ДМ из I с (X > I Это должен быть робокар с наименьшим приоритетом, т.к. при это« у него ухудшается (удлииняется) траектория. Как только этот робокар переместится в любое соседнее ДМ, "разорвется" цикл в графе ресурсов, т.е. произойдет выход из тупика.

Проверка на программной модели (при относительно большом количестве робокаров по отношению к количеству дискоетных местоположений) предложенного способа преодоления тупиков выявила ситуации, когда все робокары, попавшие з тупик, не имеют ни одного свободного соседнего местоположения. Эта ситуация была условно названа - ФАТАЛЬНЫЙ ТУПИК. Для преодоления батальных тупиков достаточно перевести систему на один такт (зрекя, в течение которого все робокары выполнят элементарную команду - <переместиться> или <ждать>) в "беступиковый" режим работы. Это означает, что всем робокарам разрешено один раз переместиться в любое свободное соседнее местоположение. Правильность такого решения была подтверждена проверкой на программной модели.

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

Второй агоритм резервирования направлений также использует ТПН, но в отличии от первого алгоритма в ТИН заносятся только то ДМ, которые соответствуют перекресткам (узловые ДМ). Перед начало« движения УП робокара резервирует направления (рас-

-За-

ставляет строки в транспортной графе) н, всей маршруте до целевого, ДМ. ЛРИ двяжонии робокара УП убирает свои стрелки по мере прохождения соответстаующик участков ТС. При.резервировании направлений разревется зарезервировать направление на участке ; ;:/ПУГ0Й УП ив зарезервировал направление раньше или заре ^ рвированкое ранее направление не противоречит наоеиу Цель резервирования - исключить встречу двух робокаров. движущихся в

протквоаоложны, направлениях, „а линейном учас^е В процессе

ре:ерВ,рйЕания (поиска царшрута) цожет Бозникнугь ^^ £ « Д

° резервирования варианты маршрутов, при кото-

рых возникают циклы, игнорируются.

' Проверка на программной модели предложенного алгоритма подтвердила воз-ожность его использования для топологий, граф

которых является деревом или 1..2 ДМ),

содержит большие участки (больше .на которых необходимо обеспечить движение робокаров В обоих направления.

ХЕрй^щ™ использует граф конфигурационного простра-

"Г" С00"етСГВ^т определенному расположению робоксооа в и. Дуга - разрешенному переходу (совместным перемещениям робокаров из одного ДМ в соседнее, при которых исключены столкновения робокаров между собой). Каждая дуга нагружена совокупным тюнелортнки заданием «= {{„ 1:2 О гле

р Г Н0"С' Ч!ЛеВ0Г0 робокэра, п - количество'робокаров

в системе. После этого получаем управляема таблицу Г « Б х V 1где Ь -.множество всех состояний ТС, V - множество всех совокупных транспортных заданий - комбинаций целевых ДЫ), которая по номеру текущего состояния ( » строки).« номеру текущего совокупного транспортного задания ( » столбца) дает номер следующего состояния, в которое нужно перевести систему на данном шаге. Зная текущее и следующее состояния системы, определяют команды хахдому робокару на ЭП.

Алгоритм управ. шя группой робокаров после этого становится независимый по быстродействию от количества робокаров и количест;_ДМ в ТС,_:_ »»ка^ов и

Ограничением прим, :внм предлагаемого метода является Размер управляющей таблицы, равный - N. • V,.

а 7к""- п}7 : = ♦ 1)П-

П - число робокаров в ТС; К - число ДМ в ТС; Мц«л - число целевых ДМ в ТС.

Глава 4.Экспериментальная оценка алгоритмов маршрутизации

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

Структура обеих программ представляет собой упрощенный вариант предлагаемой структуры системы упраллеггия. В ней отсутствуют интерфейсные блоки с робокарами и с СУ ГПС. Интерфейсный блок с оператором (пользователем) реализован частично в блоке обработки команд пользователя и в управляющих процессах. Информационная модель представляет собой совокупность данных, хранящихся в оперативной памяти ЭВМ.

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

Моделирование проводилось для трех различных топологий. В целом можно констатировать, что при алгоритме резервирования направлений при любом количестве робокаров, кроме максимального, - на всех топологиях повышается производительность транспортной системы в средней на 1,I...37,6%; и снижается средний пробег робокаров в среднем на 12,1...37,8%.

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

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

2. На использование алгоритма резервирования направлений необходимо накладывать ограничение, суть которого в следующем: роб кар может начать движение из начального пункта в целевой в тон и только том случае, если целевой пункт в данный момент времени свободен и никакой другой робокар не имеет задания двигаться в этот пункт. Иначе есть опасность возникновения тупика по прибытии туда нашего робоквра. Поэтому количество робокаров в ТС не может быть большим N - 1 (№ - количество целевых ДМ).

3. Динамический тупик может быть предотвращен при заполнении ТПН.

4. Вероятность возникновения тупика при алгоритме резервирования направлений тем выше, чем "грубее" разбито рабочее пространство транспортной сети на секции и чем больше число робокаров в системе.

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

Для этого. предлаг >тся выбор оптимального пути производить не на основе ТПН, а использовать для этого алгоритм Дейк-стры (поиск кратчайшего пути в графе между фиксированной вершиной и всеми остальными). В данном случае таблица предпочтительных» направлений несколько изменяет свое функциональное назначение. Она становится таблицей "разрешенных'направлений (ТРН). Перед запуском алгоритма Дейкстры транспортный граф модифицируется:

- из него исключаются дуги "не разрешенные" в ТРН с учетом ц>левого узла. т.е. ТРН выступает в качестве "маски", накладываемой на тра'- портный граф;

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

Нос., модификации алгоритма б ыл о~п рои эь еДё н о~е г ра в и е нио посредством имитационного моделирования с базовым алгоритмом (в дальнейшем базовый алгоритм (резервирования направлений) - 2Б, модифицированный алгоритм - 2Н). Алгоритм

214 при любой количестве робокаров дает выигрыш по производительности по сравнению с алгоритмом 2Б в среднем на на 2,5

...12,32; и снижение среднего пробег робокаров на 5...3,7%.

ОБЩИЕ ВЫВОДЫ

1. Ни один из существующих способов и алгоритмов маршрутизации не обладает абсолютными преимуществами по всем показателям своей работы (оптимальность решеиия, быстродействие, потребляемые вычислительные ресурсы, независимость показателей работы от топологии ТС).

2. Создание инвариантного пакета программ системы управления ТМ в ближайшее время ыаловероятно, однако в пределах ПО удалось выделить инвариантную часть - диспетчер заданий, осуществляющий планирование перевозок, и управляющие процессы, осуществляющие маршрутизацию. Другая часть ПО (интерфейсные блоки), зависимая от особенностей конкретного ТМ, поддается замене.

3. ПО системы управления ТМ, построенное в соответствии с предлагаемой структурой, может быть использовано для широкого класса структурных I: аппаратных решений транспортного модуля ГПС. Инвариантные блоки обеспечивают адаптацию ПО к ТМ В соответствии с требованиями заказчика. Построение ПО можно производить по модульному принципу, т.е. "собирать" из готовых программных модулей.

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

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

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

7. На основе моделирования из трех исследованных алгоритмов (локальной маршру.изаиии, резервирования направлений, цоди-

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

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

Печатные работы по теме диссертации

1. Токарев А.Л. Принципы организации диспетчера автоматической тракспортно-складской систеиы (АТСС)//Научно-производ-ственные и социально-экономические проблемы производства автомобиля "КАМАЗ": Тез. докл. научно-технической конференции. Набережные Челны, 1988 - с.136;

2. Сосоккин В.Л., Токарев А.Л. Принципы построения диспетчера транспортного модуля // Конструкторско-технологическая информатика, автоматизированное создание машин и технологий: Материалы всесоюзной конференции, Москва, 1989 - с.109-114;

3. Токарев А.Л. Принципы управления группой тележек//Перв-довой производственный опыт и начно-технические- достижения, рекомондчоиые для внедрения. БНИИТЭМР, 1989 - вып.II, с.1-2.