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

 

Изобретение относится к области вычислительной техники и может быть использовано для нахождения кратчайших путей в графах, не имеющих двух и более кратчайших путей. Цель изоб- ; ретения состоит в повышении быстродействия и расширении функциональных возможностей за счет идентификации цуг кратчайшего пути. Устройство содержит матрицу (1 - ) (h-l) моделей дуг (Ь - число вершин графа , каждая из KOTopbfic состоит из счетчика и триггера, группу элементов И, первую группу элементов ИЛИ, элемент НЕ, генератор тактовых импульсов, вход Iзапуска устройства, вторую группу элементов И, вторую группу элементов ИЛИ. Повьшение быстродействия и расширение функциональных возможностей устройства обеспечивается путем сокращения числа этапов нахождения кратчайшего путк и идентификации его дуг. 2 ил. Л

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (д) у 606 F 15/20

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3702667/24-24 (22) 15,02.84 (46) 28.02.86. Бюл. 11- 8 (7l) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.Б.Брагин, О.Н.Костюк, В.Н.Пишванов и Л.В.Косминская (53) 681.333 (088.8) (56) Авторское свидетельство СССР

N- 640314, кл. (, "06 G 7/122, 1977.

Авторское свидетельство СССР

9 886006, кл. С 06 G 7/122, 1980. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ АВТОНОМНОГО ТРАНСПОРТНОГО РОБОТА (57) Изобретение относится к области вычислительной техники и может быть использовано цля нахождения кратчай„„SU„„1215116 A ших путей в графах, не имеющих двух и более кратчайших путей. Цель изоб . ретения состоит в повышении быстродействия и расширении функциональных возможностей за счет идентификации дуг кратчайшего пути. Устройство содержит матрицу(Ф вЂ” 1) (h-1) моделей дуг (И вЂ” число вершин графа), каждая из которых состоит из счетчика и триггера, группу элементов И, первую группу элементов ИЛИ, элемент НЕ, генератор тактовых импульсов, вход запуска устройства, вторую группу элементов И, вторую группу элементов ИЛИ. Повышение быстродействия и расширение функциональных воэможностей устройства обеспечивается путем сокращения числа этапов нахождения кратчайшего пути и идентификации его дуг. 2 ил. а

1215116

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

Цель изобретения — повышение

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

На фиг. 1 и 2 приведена структурная схема устройства.

Устройство содержит матрицу(Н -1)x

Х(Н -1) моделей 1 дуг (n — число вершин графа), каждая из которых состоит из счетчика 2 и триггера 3, группу элементов И 4, первую группу элементов ИЛИ 5, элемент НЕ 6, генератор 7 тактовых импульсов, вход 8 запуска устройства, вторую группу ,элементов И 9 и вторую группу элементов ИЛИ 10.

Первоначально в счетчики 2 заносят количество импульсов, соответствующее весам дуг графа, и устанавливают в единичное состояние.триггеры 3 1g если есть дуга из -й вершины в д ю»

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

После подачи сигнала на вход 8 ямпульсы генератора ? проходят через элемент И 41 и вычитающие входы счетчиков 2 первой строки матрицы 40 моделей 1 дуг. Далее устройство функционирует согласно следующему алгоритму: при переполнении (обнулении)

° любого 1,1 -ro счетчика 2 на выходе элемента ИЛИ 5 появляется логическая 45

"1", сбрасывающая триггеры Зк,1 (К=1,п-1) в "0", что обеспечивает блокировку счета на счетчиках 2 1 -го столбца матрицы моделей 1 дуг, одновременно с выхода элемента ИЛИ g 50 разрешает прохождение тактовых им1 пульсов через элемент И 4 к счетчи1 кам 2 1 -й строки матрицы моделей 1 дуг; на счетчики 2 разблокированных строк матрицы поступают тактовые им- 55 пульсы, обеспечивающие счет счетчиков 2, за исключением принадлежащих заблокированным столбцам, Так продолЖается до переполнения любого счетчика 2 последнего столбца матрицы моделей I дуг, при этом на выходе элемента ИЛИ 5 появляется логическая "1", сбрасывающая в "0" триггеры Ю -ro столбца матрицы моделей 1 дуг, а на втором входе элемента И 4 1 появляется "0", запрещающий поступление импульсов с генератора 7 к счетчикам 2. При этом на, выходах ряда счетчиков 2 будет присутствовать сигналпереполнения,зафиксированный в .процессе работы устройства.

Код кратчайшего пути считывания формируется при появлении единичного сигнала на выходе элемента ИЛИ 5> с выходов элементов И 9, при этом на выходе элемента И 9; присутствует логическая "1 с выхода счетчика

21, если соответствующая дуга при" надлежит кратчайшему пути, и "0" в противном случае. Код кратчайшего пути формируется следующим образом.

Единичный сигнал с выхода элемента

ИЛИ 511 поступает на входы элементов И 9 (К= l, h — 1), при этом на выходе элемента И 9 g соответствую-щего переполненному счетчику 2;„, появляется логическая "1, на выходах остальных элементов .И9; присутствует "0"; логическая ")" с выхода элемента И 9„" поступает на соответ) ствующий вход элемента ИЛИ 10,,на выходе которого также появляется "1",позволяющая идентифицировать очередную дугу, принадлежащую кратчайшему пути, при этом на выходе элемента И9к; появляется "1" (Ki — индекс переполнившегося счетчика 2 столбцаi) и т.д. до появления логической "1" на выходе любого элемента И91 (C =2,h ), соответствующего счетчику 21 первой строки матрицы моделей 1 дуг, что завершает формирование кода кратчайшего пути и служит признаком окончания работы устройства.

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

Устройство для определения кратчайшего пути автономного транспортного робота, содержащее матрицу (h -1)к к(м -l) моделей дуг (b — число вершин ,графа, состоящих каждая из счетчи- . ка и триггера, первую группу элементов ИЛИ, элемент НЕ, первую группу из 1 -2 элементов И, генератор тактовых импульсов и элемент И, первый вход которого является входом запус1215116 ка устройства, а второй вход подключен к выходу генератора тактовых импульсов, выход элемента И соединен с первыми входами элементов И первой группы, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет идентификации дуг кратчайшего пути, в устройство введены вторая группа элементов И 10 по числу моделей дуг и вторая группа элементов ИЛИ, в каждой модели дуг выход триггера подключен к тактовому входу счетчика, выход элемента НЕ соединен с третьим входом 15 элемента И, выход которого подключен к счетным входам счетчиков моделей дуг первой строки матрицы моделей дуг, выходы элементов ИЛИ первой группы соединены с нулевыми входами 20 триггеров моделей дуг соответствую щих столбцов матрицы моделей дуг и вторыми входами соответствующих элементов И первой группы, выходы которых подключены к вычитающим входам счетчиков моделей дуг соответствующи. строк матрицы моделей дуг, начиная со второй, выходы счетчиков каждой модели дуги в столбцах соединены с одноименными входами соответствующего элемента ИЛИ первой группы и первым входом соответствующего элемента И второй группы, выход -го элемента

ИЛИ первой группы подкпючен к входу элемента HE и к вторым входам соответствукщих элементов И второй груп-. пы, выходы элементов ИЛИ второй группы соединены с вторыми входами соответствующих элементов И второй группы, выход iJ — гo элемента И второй группы (i = 1, h — I,,1 = 2,h) является ц -м выходом устройства и подключен к a — му входу i — го элемента

ИЛИ второй группы.

121511б фдг2

Составитель А, Шеренков

Техред С.Мигунова

Корректор О.Луговая

Редактор А.Лежнина

Тираж 673 Подписное

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

113035, Москва, Ж-35, Раушокая наб., д,415

Заказ 908/57

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4