Устройство для определения кратчайшего пути автономного транспортного робота

 

Изобретение относится к вычислительной технике и может быть применено в системах управления роботами и манипуляторами . Целью изобретения является повышение быстродействия устройства путем совмещения во времени следования тактов ввода весов дуг и тактов расчета кратчайшего пути графа. Устройство содержит регистры 1, матрицу моделей дуг из счетчиков 2 и триггеров 3, элементы И 4, элементы ИЛИ 5, элемент НЕ 6, генератор тактовых импульсов 7. Причем выходы регистров 1 моделей дуг соединены с соответствуюш,ими входами занесения информации счетчиков 2 и триггеров 3 моделей дуг, а входы регистров 1 моделей дуг являются информационными входами устройства. Введенные регистры моделей дуг выполняют роль буферной памяти и обеспечивают совмещение во времени тактов ввода и обработки информации в устройстве. 1 ил. &

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК

ÄÄSUÄÄ1383387 (m 4 б 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1215116 (21) 4144416/24-24 (22) 10.11.86 (46) 23.03.88. Бюл. № 11 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В. Б. Брагин и О. Н. Костюк (53) 681.333(088.8) (56) Авторское свидетельство СССР

M 1215116, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ АВТОНОМНОГО

ТРАНСПОРТНОГО РОБОТА (57) Изобретение относится к вычислительной технике и может быть применено в системах управления роботами и манипуляторами. Целью изобретения является повышение быстродействия устройства путем совмещения во времени следования тактов ввода весов дуг и тактов расчета кратчайшего пути графа. Устройство содержит регистры 1, матрицу моделей дуг из счетчиков 2 и триггеров 3, элементы И 4, элементы ИЛИ 5, элемент НЕ 6, генератор тактовых импульсов 7. Причем выходы регистров 1 моделей дуг соединены с соответствующими входами занесения информации счетчиков 2 и триггеров 3 моделей дуг, а входы регистров 1 моделей дуг являются информационными входами устройства. Введенные регистры моделей дуг выполняют роль буферной памяти и обеспечивают совмещение во времени тактов ввода и обработки информации в устройстве. 1 ил.

1383387

10

Формула изобретения

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

На чертеже приведена структурная схема устройства.

Устройство содержит группу регистров

1;;, счетчики 2;, и триггеры 3;; моделей дуг матрицы, первую группу элементов И 4;, первую группу элементов ИЛИ 5;, элемент НЕ 6, генератор 7 тактовых импульсов, вход 8 пуска, вторую группу элементов И 9;;, вторую группу элементов ИЛИ 10;, линию 11 задержки, выход 12 признака окончания счета, группу информационных входов 13, вход 14 разрешения ввода информации.

Устройство работает следующим образом.

В исходном состоянии счет в счетчиках 2 моделей дуг заблокирован. Исходная информация о весах и топологии графа заносится в регистры 1 моделей дуг и по сигналу с входа 14, поступающему через элемент 5„и линию 11 задержки к элементам матричной модели, переписывается в счетчики 2 и триггеры 3, после чего устройство готово к счету и приему следующей порции информации о графе маршрутов, которая вводится в регистры 1 моделей дуг одновременно с работой устройства в режиме счета. Счет в устройстве начинается с момента подачи сигнала на вход 8 пуска, после чего импульсы с генератора 7 начинают проходить через элемент И 4i на вычитающие входы счетчиков 2 первой строки матрицы моделей дуг. Далее устройство функционирует согласно следующему алгоритму: при переполнении (обнулении) любого ij-го счетчика 2 на выходе элемента ИЛИ 5; появляется логическая «1», сбрасывающая триггеры 3;;, что обеспечивает блокировку счета на счетчиках 2,-го столбца матрицы моделей дуг, одновременно «1» с выхода элемента ИЛИ 5; разрешает прохождение тактовых импульсов через элемент И 4 к счетчикам i-ой строки матрицы моделей дуг, на счетчики 2 разблокированных строк матрицы поступают тактовые импульсы, обеспечивающие счет счетчиков 2, за исключением принадлежащих заблокированным столбцам.

Так продолжается до переполнения любого счетчика 2 последнего столбца матрицы моделей дуг, при этом на выходе элемента ИЛИ 5„появляется логическая «1», сбрасывающая в «О» триггеры и-го столбца матрицы моделей дуг, а на втором входе элемента И 4 появляется «О», запрещающий поступление импульсов с генератора 7 к счет15

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

Код кратчайшего пути считывается при появлении единичного сигнала на выходе элемента ИЛИ 5„с выходов элементов И 9, при этом на выходе элемента И 9;, присутствует логическая «1» с выхода счетчика 2;;, если соответствующая дуга принадлежит кратчайшему пути, «О» — в противном случае.

Код кратчайшего пути формируется следующим образом. Единичный сигнал с выхода элемента ИЛИ 5„поступает на входы элементов И 9;„, при этом на выходе элемента 9;„И, соответствующего. переполненному счетчику 2;„, появляется логическая «1», на выходах остальных элементов 9;, И присутствует «О»; логическая «1» с выхода элемента 9;; И поступает в соответствующий вход элемента 10;; ИЛИ, на выходе которого также появляется «1», позволяющая идентифицировать очередную дугу, принадлежащую кратчайшему пути, при этом на выходе элемента 9»; И появляется «1» (К;— индекс переполнившегося счетчика 2 столбца

)) и так далее до появления логической «1» на выходе любого элемента И 9и (1 = 2,n), соответствующего счетчику 2п первой строки матрицы моделей дуг, что завершает формирование кода кратчайшего пути и служит признаком окончания расчета кратчайшего пути в графе по информации, занесенной в счетчики 2 и триггеры 3 модели дуг на текущем цикле обработки. Содержащаяся в регистрах 1 информация по топологии и весах графа для следующего цикла расчета по сигналу окончания счета с элемента ИЛИ 5„задержанного линией 11 задержки на время, необходимое для вывода результатов текущего цикла расчета, заносится в счетчики 2 и триггеры 3 моделей дуг.

Устройство готово к следующему циклу работы.

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

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

1383387

Составитель С. Кошелев

Редактор Н. Лазаренко Техред И. Верес Корректор М. Г1ожо

Заказ 915/49 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, )К вЂ” 35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 ввода весов дуг и тактов расчета кратчайшего пути графа, в него введены линия задержки, группа (и — 1) ) (п — 1) регистров, первый выход и-го регистра группы (i= 1, n — 1, j = 2,п) соединен с входом задания коэффициента счетчика ij-й модели дуги Ii =:I, п — (, j nj матрицы (п — 1) )< (и — 1) моделей дуг графа, вход установки в «1» триггера Ij«-й модели дуги соединен с вторым выходом ij-го регистра, входы регистров группы являются группой (п — 1) )((— 1) информационных входов устройства, выход линии задержки соединен с входами разрешения счета счетчиков и входами синхронизации триггеров всех моделей дуг матрицы, вход линии задержки соединен с выходом п-го элемента ИЛИ первой группы и является выходом признака окончания счета устройства, и-й вход п-го элемента ИЛИ первой группы является входом разрешения ввода информации устройства.