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

(Л

со сх со

00 00

rvj

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

Целью изобретения является повышение быстродейстия за счет совмешения во времени следования тактов ввода весов дуг и тактов расчета кратчайшего пути графа:

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

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

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

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

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

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

Код кратчайшего пути формируется следующим образом. Единичный сигнал с выхо5 да элемента ИЛИ 5п поступает на входы элементов И 9т, при этом на выходе элемента 9т И, соответствующего, переполненному счетчику 2т, появляется логическая «1, на выходах остальных элементов 9т И присутствует логическая «1 с выхода элемен0 та 9,/ И поступает в соответствующий вход элемента 10;/ ИЛИ, на выходе которого также появляется «1, позволяющая идентифицировать очередную дугу, принадлежащую кратчайшему пути, при этом на вы5 ходе элемента И появляется «1 (К/ - индекс переполнившегося счетчика 2 столбца J) и так далее до появления логической «1 на выходе любого элемента И 9i/ (1 2,п), соответствующего счетчику 2i/ первой строки матрицы моделей дуг, что завершает фор0 мирование кода кратчайшего пути и служит признаком окончания расчета кратчайшего пути в графе по информации, занесенной в счетчики 2 и триггеры 3 модели дуг на текущем цикле обработки. Содержащаяся в регистрах 1 информация по топо5 логии и весах графа для следующего цикла расчета по сигналу окончания счета с элемента ИЛИ 5„, задержанного линией 11 задержки на время, необходимое для вывода результатов текущего цикла расчета, заносится в счетчики 2 и триггеры 3 моделей дуг.

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

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

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

Устройство для определения кратчайщего

5 пути автономного транспортного робота по

авт. св. № 1215116, отличающееся тем, что,

с целью повыщения быстродействия за счет

совмещения во времени следования тактов

ввода весов дуг и тактов расчета кратчайшего пути графа, в него введены линия задержки, группа (п-1) X (п-1) регист- ров, первый выход ij-ro регистра группы (, п-1, j 2,п) соединен с входом задания коэффициента счетчика ij-й модели дуги (i 1, п-1, j 2,п) матрицы (п-1)Х(п-1) моделей дуг графа, вход установки в «1 триггера ij«-й модели дуги соединен с вторым выходом ij-ro регистра, входы регистров группы являются группой

(п-1)Х( - 1) информационных входов устройства, выход линии задержки соединен с входами разрешения счета счетчиков и входами синхронизации триггеров всех моделей дуг матрицы, вход линии задержки соединен с выходом п-го элемента ИЛИ первой группы и является выходом признака окончания счета устройства, п-й вход п-го элемента ИЛИ первой группы является входом разрешения ввода информации устройства.

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