Устройство для определения кратчайшего пути автономного транспортного робота Советский патент 1986 года по МПК G06F15/173 

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

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

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

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

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

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

После подачи сигнала на вход 8 ямпульсы генератора 7 проходят через элемент И 4 и вычитающие входы счетчиков 2 первой строки матрицы моделей I дуг. Далее устройство функционирует согласно следующему алгоритму: при переполнении (обнулении) любого Ij -го счетчика 2 на выходе элемента ИЛИ 5 появляется логическая 1, сбрасьгаающая триггеры ,h-1) в О, что обеспечивает блокировку счета на счетчиках 2 j --го столбца матрицы моделей I дуг, одновременно с выхода элемента ИЛИ 5j разрешает прохождение тактовых импульсов через элемент И 4 j к счетчикам 2 J-и строки матрицы моделей 1 дуг; на счетчики 2 разблокированных строк матрицы поступают тактовые им- пульсы, обеспечивающие счет счетчиков 2, за исключением принадлежащих заблокированным столбцам.

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

Код кратчайшего пути считывания формируется при появлении единичного сигнала на выходе элемента ИЛИ 5f, с выходов элементов И 9, при этом на выходе элемента И 9ij присутствует логическая 1 с выхода счетчика 2 IJ , если соответствующая дуга принадлежит кратчайшему пути, и О - в противном случае. Код кратчайшего пути формируется следующим образом. Единичный сигнал с выхода элемента ИЛИ 5ь поступает на входы элементов И 9ц( ( , h -l) , при этом на выходе элемента И 9( ь , соответствую- -щего переполненному счетчику 2jY,, появляется логическая Г , на выходах остальных элементов .И9, присутствует логическая 1 с выхо- . да элемента И поступает на соответствующий вход элемента ИЛИ I О,; ,на выходе которого также появляется 1,позволяющая идентифицировать очередную дугу, принадлежащую кратчайшему пути, при этом на выходе элемента И9ц, появляется 1 ( Ki - индекс переполнившегося счетчика 2 столбца) и т.д. до появления логической 1 на выходе любого элемента (f 2,h ) , .соответствующего счетчику первой строки матрицы моделей 1 дуг, что завершает формирование кода кратчайшего пути и служит признаком оконча-. ния работы устройства.

Формула

и 3

обретения

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

вторыми входами соответствующих элементов И первой группы, выходы которых подключены к вычитающим входам счетчиков моделей дуг соответствующи: строк матрицы моделей дуг, начиная со второй, выходы счетчиков каждой модели дуги в столбцах соединены с одноименными входами соответствующего элемента ИЛИ первой группы и первым входом соответствующего элемента И второй группы, выход и, -го элемента ИЛИ первой группы подключен к входу элемента НЕ и к вторым входам соответствующих элементов И второй груп-- пы, выходы элементов И.ПИ второй группы соединены с вторыми входами соответствующих элементов И второй группы, в1)Гход .J -го элемента И второй группы (i 1 , Ь -1 , j 27) является ij -м выходом устройства-и подключен к J входу -го элемента ИЛИ второй группы.

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

Й/г/