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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН цр606 Г 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ших путей в графах, не имеющих двухи более кратчайших путей. Цель изоб,ретения состоит в повышении быстродействия и расширении функциональныхвозможностей за счет идентификациидуг кратчайшего пути. Устройство содержит матрицу(Ь - 1) (Ь) моделейдуг (Ъ - число вершин графа), каждаяиз которых состоит из счетчика итриггера, группу элементов И, первую группу элементов ИЛИ, элемент НЕ,генератор тактовых импульсов, входзапуска устройства, вторую группуэлементов И, вторую группу элементов ИЛИ. Повышение быстродействия ирасширение функциональных воэможностей устройства обеспечиваетсяпутем сокращения числа этапов нахождения кратчайшего пути и идентификации его дуг. 2 ил. ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(1) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции(56) Авторское свидетельство СССР Мф 640314, кл. С 06 С 7/122, 1977.Авторское свидетельство СССР Иф 886006, кл. С 06 С 7/122, 1980, (.54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ АВТОНОМНОГО ТРАНСПОРТНОГО РОБОТА(57) Изобретение относится к области вычислительной техники и может быть использовано цля нахождения кратчайЯО 1215116 АИзобретение относится к вычислительной технике и может быть применено в системах управления роботами иманипуляторами для решения задачнахождения кратчайшего пути междуЖначальной и конечной вершинами графов,о которых заведомо известно, чтоони не имеют двух или более кратчайших путей,Цель изобретения - повышение10быстродействия и расширение функциональных возможностей устройства засчет идентификации дуг кратчайшегопути между начальной и конечной вершинами графа,На фиг. 1 и 2 приведена структурная схема устройства,Устройство содержит матрицу(Н -1)хХ(Н -1) моделей 1 дуг ( - числовершин графа) , каждая из которыхсостоит из счетчика 2 и триггера 3,группу элементов И 4, первую группуэлементов ИЛИ 5, элемент НЕ 6, генератор 7 тактовых импульсов, вход 8запуска устройства, вторую группу,элементов И 9 и вторую группу элементов ИЛИ 10.Первоначально в счетчики 2 зано-сят количество импульсов, соответствующее весам дуг графа, и устанавливают в единичное состояние.триггеры 3 1 , если есть дуга из-й вершины в 4 -ю35Устройство работает следующим образом.После подачи сигнала на вход 8 ямпульсы генераторапроходят через элемент И 41 и вычитающие входы счетчиков 2 первой строки матрицы 40 моделей 1 дуг. Далее устройство функционирует согласно следующему алгоритму: при переполнении (обнулении)Влюбого 1, -го счетчика 2 на выходе элемента ИЛИ 5 появляется логическая 45 "1", сбрасывающая триггеры Зк, (К=1,И) в "О", что обеспечивает блокировку счета на счетчиках 2-го столбца матрицы моделей 1 дуг, одновременно с выхода элемента ИЛИ ф50 разрешает прохождение тактовых импульсов через элемент И 4к счетчи 1кам 2-й строкиматрицы моделей 1 дуг; на счетчики 2 разблокированных строк матрицы поступают тактовые им пульсы, обеспечивающие счет счетчиков 2, за исключением принадлежащих заблокированным столбцам,Так продолЖается до переполнениялюбого счетчика 2 последнего столбца матрицы моделей 1 дуг, при этомна выходе элемента ИЛИ 5 появляетсялогическая "1", сбрасывающая в "О"триггеры Ю -го столбца матрицы моделей 1 дуг, а на втором входе элемента И 4 1 появляется "О", запрещающий поступление импульсов с генератора 7 к счетчикам 2. При этом на,выходах ряда счетчиков 2 будет присутствовать сигналпереполнения,зафиксированный в .процессе работы устройства.Код кратчайшего пути считыванияформируется при появлении единичного сигнала на выходе элемента ИЛИ 5с выходов элементов И 9, при этомна выходе элемента И 9; присутствует логическая "1с выхода счетчика2 ц , если соответствующая дуга при"надлежит кратчайшему пути, и "О"в противном случае. Код кратчайшегопути формируется следующим образом.Единичный сигнал с выхода элементаИЛИ 511 поступает на входы элементов И 9 к (К=1,- 1), при этом навыходе элемента И 9;, , соответствую-щего переполненному счетчику 2;,появляется логическая "1 , на выходах остальных элементов .И 9; присутствует "Ологическая "1" с выхо да элемента И 9" поступает на соответьствующий вход элемента ИЛИ 1 Она выходе которого также появляется "1",позволяющая идентифицировать очередную дугу,принадлежащую кратчайшему пути, приэтом на выходе элемента И 9 К; появляется "1" ( К - индекс переполнившегося счетчика 2 столбцами) и т.д, допоявления логической "1" на выходелюбого элемента И 94 ( 1 =2, ),соответствующего счетчику 2 1 первойстроки матрицы моделей 1 дуг, чтозавершает формирование кода кратчайшего пути и служит признаком оконча-.ния работы устройства,Формула изобретенияУстройство для определения кратчайшего пути автономного транспортного робота, содержащее матрицу (и -1) х(и -1) моделей дуг (Ь - число вершин ,графасостоящих каждая из счетчика и триггера, первую группу элементов ИЛИ, элемент НЕ, первую группу из И -2 элементов И, генератор тактовых импульсов и элемент И, первыйвход которого является входом запуска устройства, а второй вход подключен к выходу генератора тактовых импульсов, выход элемента И соединенс первыми входами элементов И первойгруппы, о т л и ч а ю ш е е с я тем,что, с целью повышения быстродействия и расширения функциональных возможностей за счет идентификациидуг кратчайшего пути, в устройствовведены вторая группа элементов И 1 Опо числу моделей дуг и вторая группа элементов ИЛИ, в каждой моделидуг выход триггера подключен к тактовому входу счетчика, выход элемента НЕ соединен с третьим входом 15элемента И, выход которого подключенк счетным входам счетчиков моделейдуг первой строки матрицы моделейдуг, выходы элементов ИЛИ первойгруппы соединены с нулевыми входами 20триггеров моделей дуг соответствующих столбцов матрицы моделей дуг и вторыми входами соответствующих элементов И первой группы, выходы которых подключены к вычитающим входам счетчиков моделей дуг соответствующи. строк матрицы моделей дуг, начиная со второй, выходы счетчиков каждой модели дуги в столбцах соединены с одноименными входами соответствующего элемента ИЛИ первой группы и первым. входом соответствующего элемента И второй группы, выход 1 э, -го элемента ИЛИ первой группы подкпючен к входу элемента НЕ и к вторым входам соответствующих элементов И второй группы, выходы элементов ИЛИ второй группы соединены с вторыми входами соответствующих элементов И второй групФпы, выход ,3 -го элемента И второй группы (, = 1, П -1, ,1 = 2,ь) является ц -м выходом устройства и подключен к-му входу 1 -го элемента Р 1 ЛИ второй группы.121511 б Составитель А,черенковТехред С.Мигунова Корректор О.Луговая Редактор А.Лежнин каз 9 В оми от ая по дела 113035, Моск